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.

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
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search