Proving SubsetsDate: 07/01/2003 at 23:53:45 From: Martin Subject: Linear Algebra Given the function f:X-->Y and subsets A of X and B of Y, prove the following statements: i. A is a subset of f^{-1}(f(A)) ii. f(f^{-1}(B)) is a subset of B Date: 07/02/2003 at 04:10:16 From: Doctor Jacques Subject: Re: Linear Algebra Hi Martin, If A is a subset of X, f(A) is the set of images of elements of A, i.e. the set: f(A) = {f(x) | x in A} [1] If B is a subset of Y, f^(-1)(B) is the set of elements of X whose images belong to B, i.e. the set: f^(-1)(B) = {x | f(x) in B} [2] In question (i), we want to show that A is a subset of f^(-1)(f(A)). This means that, for all x in A, x must belong to f^(-1)(f(A)). Let us write C for f(A): by definition, an element y belongs to C iff it is equal to f(a) for some a in A. Pick any element x of A. We must show that x is in f^(-1)(f(A)). f(x) = y is in C. This shows that x satisfies definition [2], i.e. x is in: f^(-1)(C) = f^(-1)(f(A)) and this is what we wanted to prove. (The argument itself is quite simple, the hard part is understanding what the notation means.) Note that we do not always have equality: f^(-1)(f(A)) may be larger than A, because other elements of A can have the same images. For example, let: X = {1,2,3} Y = {a,b} A = {1} f(1) = f(2) = a, f(3) = b +----+ +---+ A| 1 |--------->| a |C |----| ^ | | | 2 |----+ |---| | | | | | 3 |--------> | b | +----+ +---+ X Y In this case, f(A) = C = {a}, but f^(-1)(C) is the set of elements whose image is a, i.e. {1,2}, which is strictly greater than A. If f is one to one (injective) - this is not the case here - we will have A = f^(-1)(f(A)). For question (ii), we want to show that f(f^(-1)(B)) is a subset of B. This means that, for all y in f(f^(-1)(B)), y is an element of B. Let us write D for f^(-1)(B). D is the set of elements whose image is in B. Pick any element y in f(f^(-1)(B)) = f(D). This means that we have y = f(d) for some d in D. We want to show that y is in B. As d is in f^(-1)(B), definition [2] shows that f(d) is in B; as f(d) = y, we have shown that y is in B, as we wanted. In this case also, we will not always have equality - f(f^(-1)(B)) may be a proper subset of B (i.e. smaller than B), because B is an arbitrary subset and can contain elements which are not images of any element of X. For those elements, there will be no corresponding element in D to be used in the proof. For example, if: X = {1,2,3} Y = {a,b,c} B = {a,b} f(1) = f(2) = a, f(3) = c +----+ +---+ | 1 |--------->| a |B D| | ^ | | | 2 |----+ | b | |----| |---| | 3 |--------> | c | +----+ +---+ X Y f^(-1)(B) is the set of elements whose image is a or b, i.e. f^(-1)(B) = D = {1,2} and f(f^(-1)(B)) = f(D) is the set of images of elements of D, i.e. f(D) = {f(1), f(2)} = {a} which is not equal to B. If f is onto (surjective) - this is not the case here - we will have f(f^(-1)(B)) = B. Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ Date: 07/02/2003 at 09:05:30 From: Martin Subject: Thank you (Linear Algebra) Thank you very much for taking the time to answer my question. You provided far better documentation than any of the lecture notes given out at my university. As you said, the problem seemed easy enough - the most difficult part is deciphering the notation and understanding the underlying theory. Your answer has provided me with a new motivation and vigour to get into my mathematics course with real enthusiasm now that I know there are people out there like you who can help when I get stuck. Thanks heaps! Marty |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/