# Discrete Mathematics Function Proof

The question is as follows :

Let $f:A\rightarrow B$ be a surjective function and let $C$ be a subset of $B$. Prove $f(f^{-1}(C)) = C$.

I understand what the question is asking. It's basically saying that for some element in $C$, the inverse function points to an element in the domain, $A$, and then for the element in $A$, the function points back to the element in $C$.

Here's my attempt at the proof :

Let $c$ be contained in $C$, which is also contained in $B$ because $C$ is a subset of $B$. Let $b$ be contained in $B$, and let $a$ be contained in $A$. $f:A\rightarrow B$ gives $f(a) = b$. Assume that the $b$ in $f(a) = b$ is in the set $C$, which is possible because $C$ is a subset of $B$. Then, $c = b$, so we have $f(a) = c$. Then, for $f^{-1}(C)$, we would have $f^{-1}(b) = a$, and therefore $f^{-1}(c) = a$. Then for $f(a)$, we have $c$, which is again in the set $C$. Hence, $f(f^{-1}(C)) = C$.

If this is incorrect, I'd appreciate feedback and a starting point on where to go with this proof!

Also, I apologize for the poor formatting, I'm not familiar with how to format these types of problems with HTML commands and such.

-
$f^{-1}(b)$ does not make sense, because $f$ not necessary bijective. – Hamou Jul 22 '14 at 23:29
@Hamou $f^{-1}(b)$ is the set of all elements that map to $b$. – Joe Johnson 126 Jul 22 '14 at 23:32
$f^{-1}(b)$ is an element, but the set is $f^{-1}(\{b\})$ – Hamou Jul 22 '14 at 23:35
@Hamou Convention is to not use the brackets in this situation. – Joe Johnson 126 Jul 22 '14 at 23:36
what is the sense for $f^{-1}(b)=a$, as sets or elements. – Hamou Jul 22 '14 at 23:38

You have a good start, but there are some issues here.

First, make sure you are clear on all definitions. Note $C$ and $f(f^{-1}(C))$ are sets, so to prove that they are equal you must show that they contain all the same elements. A typical way to do this is by showing $C \subset f(f^{-1}(C))$ and $f(f^{-1}(C)) \subset C$. In your proof, it looks like you only check that $C \subset f(f^{-1}(C))$.

Second, note that $f^{-1}$ is not defined as a function. Rather, $f^{-1}(C)$ for $C$ a subset of $B$ is defined to be the set of all $x \in A$ such that $f(x) \in C$. In particular, it does not make sense to write $f^{-1}(b)=a$ for a single element $b$. You can consider the inverse image of the subset $\{b\}$, which is typically written as $f^{-1}(b)$. However, in this case you would write $a \in f^{-1}(b)$, not that the two are equal -- there may be other elements in the set $f^{-1}(b)$.

Third, make sure that you use the fact that $f$ is surjective in your proof! When you write "f:A->B gives f(a) = b," how do you know that, for any $b\in B$, you can find an $a$ making this statement true? (In general, if you are given a hypothesis that you do not explicitly use in your solution, you should double check your proof very carefully to be sure you have not made a mistake and/or omitted an explanation. )

-
I would also add that saying "Let $a\in A$ and $b\in B$. Then $f(a)=b$" is misleading. It is not true that for any $a\in A$ and $b\in B$ one has $f(a)=b$. Be more clear by saying, "Let $a\in A$. Then let $b=f(a)$." – Joe Johnson 126 Jul 22 '14 at 23:44
I'll attempt C is a subset of f(f^1(C) first: f^-1(C) is the set of all a in A such that f(a) is in C. Also, because f is surjective, we have f(a) = b, and because C is a subset of B, we have f(a) = c. If f(a) = c, then a is in the set f^-1(C) which implies f(a) is in f(f^-1(C)). Then, because f(a) = c, we have c is in f(f^-1(C)). Hence, C is a subset of f(f^-1(C)). Is this correct? I looked at a the below comments a bit, but I tried to go further in detail to explain some of the implied steps in order to show that I understand it now. Also, now I see the necessity of surjectivity! – jonba Jul 23 '14 at 1:20
When you say "Also, because f is surjective, we have f(a) = b, and because C is a subset of B, we have f(a) = c," it's a little ambiguous. What are $b$ and $c$? You have to be careful to specify where each element lives, so to speak. Let me try to modify this particular sentence of yours, to illustrate what I mean: "Also, because $f$ is surjective, given any $b \in B$ there exists an $a \in A$ so that $f(b)=a$. Because $C \subset B$, given $c\in C$ we have $f(a)=c$ for some $a \in A$." Beyond this, your proof looks good. You have the right idea, just be careful to phrase things precisely! – vociferous_rutabaga Jul 23 '14 at 1:53
I see, thank you very much! I'll work on the phrasing - proofwriting is tough! – jonba Jul 23 '14 at 2:02
Yes, it's definitely something to get used to. Keep working at it, and it will get a lot easier. (And make sure you do the other containment as well -- i.e. show that $f(f^{-1}(C)) \subset C$). – vociferous_rutabaga Jul 23 '14 at 2:05

$f^{-1}(C) =\{ a \in A | f(a)\in C \}$. So let $z\in f^{-1}(C)$. Then $f(z) \in C$ by definition. Therefore $f(f^{-1}(C)) \subset C$.

Let $c\in C$. Then $c \in B$, so by surjectivity there exists $a\in A$ such that $f(a)=c$. In other words, $a\in f^{-1}(C)$, and so $f(a) \in f(f^{-1}(C))$. Thus, $c\in f(f^{-1}(C))$. Therefore $C\subset f(f^{-1}(C))$. Together this gives $C= f(f^{-1}(C))$

-

At some point, you need to use the fact that $f$ is surjective. Each time you introduce a new variable, you should first think about why such a variable should even exist.

Let's start by showing that $f(f^{-1}(C)) \supseteq C$. To this end, choose any $c \in C$. Now since $C \subseteq B$, we know that $c \in B$. Hence, since $f$ is surjective, we know that there exists some $a \in A$ such that $f(a) = c$. But then since $f^{-1}(C) = \{x \in A \mid f(x) \in C\}$, we know that $a \in f^{-1}(C)$. But then since $f(D) = \{f(d) \mid d \in D\}$, we conclude that $c = f(a) \in f(f^{-1}(C))$, as desired.

Hopefully you can do the other direction yourself.

-