# Math Help - Proof

1. ## Proof

Working on a proof and I need some help

Let f : A ----> B be an injective (1:1) function and consider C a subset of A. Show that f^(-1)(f(C)) = C or [inverse image of f(C) = C]

e = an element of

What I have so far is...

C = { a e A such that a e C}
f(A) = { b e B such that there exists a e A, for f(a) = b}
f(C) = { b e B such that there exists c e A, for f(c) = b}
f(C) is a subset of B

f^(-1)(f(C)) = { a e A such that f(a) e f(C)}

Am I doing this right so far? And if I am, how do I go from the "f(a) e f(C)" part to "a e C" which would then be equal to C and my proof will be done?

I also have a similar problem to this except f : A ----> B is surjective (onto) rather than injective. How does this change the proof? Very lost...

- Nicole

2. Hi!

$f:A\rightarrow B$ is injective, $C \subseteq A$ and what needs to be shown is $f^{-1}[f[C]]=C$ ?

We want to prove an equality of sets so we need to prove two inclusions.
Let's start with the easy one, $C \subseteq f^{-1}[f[C]]$, where injectivity doesn't play any role.

Let $x \in C$. By definition, $f[C] = \{b \in B: (\exists c \in C) f(c)=b\}$, so we have $f(x) \in f[C]$.
Definition of inverse image gives $f^{-1}[f[C]] = \{z \in A : f(z) \in f[C]\}$. So $x \in f^{-1}[f[C]]$.

Now let's prove the oposite inclusion.
Let $x \in f^{-1}[f[C]]$. By definition of inverse image we get $f(x) \in f[C]$, so, by definition of $f[C]$, there exists some $c \in C$ such that $f(c)=f(x)$.
Now we use that $f$ is injective: $f(c)=f(x)$ implies $c=x$. This is an answer to your question at the end of your attempt, it is just definition of injectivity. So we have $x=c$ and we know that $c\in C$, so $x \in C$ and we are done.

As for the surjective function, what is exactly the question?

3. Oh wow, thanks!

the surjective problem is the exact same problem, except instead of being injective, f is surjective... oh and instead of C, it's D hehe

thanks again! you're the best!

- Nicole

4. If it is like you're saying, surjectivity won't help us .

Consider simple counterexample: $A=\{0,1\}$, $B=\{1\}$, $C=\{0\}\subseteq A$, and define $f:A\rightarrow B$, $f(0)=f(1)=1$.

You see $f$ is surjective, but $f^{-1}[f[C]] = \{0,1\} = A \neq C$.

5. oh wait, I lied... I do that sometimes hehe

here's the problem:
Let f : A --> B be a surjective function and assume that D is a subset of B. Prove that f(f^-1(D)) = D

- Nicole

6. I thought!
Try it first and show how far you can get. Again, one inclusion is easy and the second one uses the surjectivity.

7. So.. I did it the same way you solved the last one...

D = { b e B : b e D}

f^(-1)(D) = {a e A : f(a) = D}
=> f^(-1)(x) e f^(-1)(D)

f(f^(-1)(D)) = { b e B : f(b) e f^(-1)(D)}
=> x e f(f^(-1)(D))

=> D subset of f(f^(-1)(D))

is that right at all?

for the surjective part, I know that A --> B being surjective means for all b e B, there exists a e A s.t. f(a) = b

so D being a subset of B, for all d e D there exists a e A s.t. f(a) = d?

and.... my brain is fried.... I feel like I know it, but I just can't write it...

8. Originally Posted by thaopanda
So.. I did it the same way you solved the last one...

D = { b e B : b e D}

f^(-1)(D) = {a e A : f(a) = D}
=> f^(-1)(x) e f^(-1)(D)

f(f^(-1)(D)) = { b e B : f(b) e f^(-1)(D)}
=> x e f(f^(-1)(D))

=> D subset of f(f^(-1)(D))
You got it wrong way, this one is the part where surjectivity is needed!
Also, reading your notation is like learning a new language, please start using LaTeX - if you left-click on math expressions on one of my posts, you can see how easy the code is, and for other symbols check http://www.mathhelpforum.com/math-help/latex-help/

So let's look at that inclusion $D \subseteq f[f^{-1}[D]]$.
Let $x \in D$. Since $f$ is surjective, there exists some $y\in A$ such that $f(y)=x$, and this means that $y\in f^{-1}[D]$. And obviously $x=f(y) \in f[f^{-1}[D]]$. So $D \subseteq f[f^{-1}[D]]$.

Now you try the other, easier inclusion (using some latex ).

9. I'm probably gonna get this wrong again...

so i started with
f(y) $\in f[f^{-1}[D]]$
where f(y) = b and $b \in B$
$
b \in f[f^{-1}[D]]
$

$
f^{-1}(b) \in f^{-1}[D]
$

$
b \in D
$

I think I'm a hopeless case... I'll figure this out eventually...

10. Nice work with LaTeX!
Moreover, if I'm reading your proof in certain order (not down from top as usual) i think it is correct

Let's look at it. We want to prove that $f[f^{-1}[D]] \subseteq D$ so we start by picking arbitrary element say $x$ from $f[f^{-1}[D]]$ and we try to prove that this element must belong to $D$ too. This is the third line of your proof, with which you should begin. So first line:

$x \in f[f^{-1}[D]]$

Definition of "image of $f$", $f[f^{-1}[D]] = \{y: y \in B \; \& \; (\exists z \in f^{-1}[D]) \, f(z)=y\}$, tells us that there must be some $z \in f^{-1}[D]$ such that $f(z)=x$ (because $x \in f[f^{-1}[D]]$).

But because $z \in f^{-1}[D]$, definition of inverse image, $f^{-1}[D]=\{t \in A: f(t)\in D\}$, tells us that $f(z)\in D$.

But $f(z)=x$, which means that $x \in D$.

We conclude that $f[f^{-1}[D]] \subseteq D$.

11. woooo!
thanks soooo much! now if only you could take my test for me tomorrow