Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Proving Subsets

Date: 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
Associated Topics:
High School Functions

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/