# Need help with very simple set theoretic proofs

I am self studying Munkres' Topology book, and I'm having a hard time writing down proofs that relate to set theory. I can see why certain arguments are true, but constructing a formal proof seems to be difficult. Here's a very simple example of a problem in the book.

Let $f:A \rightarrow B$

(a) Prove that $A_0 \subset f^{-1}(f(A_0))$, show that $A_0 = f^{-1}(f(A_0))$ if $f$ is injective.

(b) Prove that $f(f^{-1}(B_0)) \subset B_0$, show that $B_0 = f(f^{-1}(B_0))$ if $f$ is surjective.

Conceptually, the ideas are simple. In (a), let $S$ be the image set of $A_0$ under $f$ (sorry if I use non-conventional notation, I'm still somewhat new to this). This means that $S= \{ b \mid f(a)=b \text{ for at least one } a \}$. This we take the inverse we may end up with some of the $a \in A^C_0$, where $A^C_0$ is the complement of $A_0$ in $A$. This happens because of the at least one in the definition of S. If we said exactly on instead, i.e. $f$ is injective, we can see that $f^{-1}(f(A_0))$ would give us $A_0$ back.

In (b) -- I'll scan through this one quickly -- let $P$ be the pre-image of $B_0$ under $f^{-1}$. Then $f^{-1}(B_0)$ gives us all points $a$ s.t. $f(a)=b \in B_0$ However we cannot guarantee that every $b \in B_0$ is the image of some a. Therefore $f(f^{-1}(B_0))$ only gives a subset of the original $B_0$. If we can guarantee that every $b \in B_0$ has a matching $a \in A$, that is $f$ is surjective, we get the entire $B_0$ back.

Now that I've shown that I understand how to prove both (a) and (b), can someone help me put these proofs in elegant mathematical form?

-
There's nothing (significantly) wrong with your proofs. (My main quibble is with your formula $\forall a \, f(a) = b \in B_0$, which doesn't make much sense to me.) What do you think an elegant proof is, and why do you think your proof lacks elegance? Certainly other proofs are possible, but elegance is an aesthetic judgement. – Zhen Lin Aug 5 '11 at 13:41
Yes, you're right. I didn't proofread correctly. Fixed it. – Phonon Aug 5 '11 at 13:51

Here is a more precise way of phrasing your proof.

Let $f : A \to B$ be a function, $A_0 \subseteq A$, $B_0 \subseteq B$. Let $f_! : \mathscr{P}(A) \to \mathscr{P}(B)$ be the function mapping subsets of $A$ to their images under $f$; that is, $f_! (A_0) = \{ b \in B : \exists a_0 \in A_0. \, f(a_0) = b \}$. Let $f^* : \mathscr{P}(B) \to \mathscr{P}(A)$ be the preimage map, that is, $f^*(B_0) = \{ a \in A : \exists b_0 \in B_0 . \, f(a) = b_0 \}$.

1. Following the definitions above, $f^* ( f_! (A_0)) = \{ a \in A : \exists a_0 \in A_0 . \, f(a) = f(a_0) \}$. It is immediate that $A_0 \subseteq f^*(f_!(A_0))$. If $f$ is moreover injective, then $f(a) = f(a_0)$ if and only if $a = a_0$, so in that case $A_0 = f^*(f_!(A_0))$.

2. Similarly, $f_!(f^*(B_0)) = \{ b \in B : \exists a \in A . \, \exists b_0 \in B_0 . \, f(a) = b = b_0 \}$. It is immediate that $f_!(f^*(B_0)) \subseteq B_0$. If $f$ is moreover surjective, then for all $b$ in $B$, there exists an $a$ in $A$ such that $f(a) = b$, so it follows that $f_!(f^*(B_0)) = B_0$ in this case.

But here is what I think an elegant proof looks like. Observe that $f_!$ and $f^*$ are inclusion-preserving maps and moreover have the following adjunction property:

$$f_!(A_0) \subseteq B_0 \text{ if and only if } A_0 \subseteq f^*(B_0)$$

This is obvious from the definition. We say $f_!$ is the left adjoint of $f^*$, and of course, $f^*$ is the right adjoint of $f_!$. We obtain the following results:

1. $A_0 \subseteq f^*(f_!(A_0))$. [Set $B_0 = f_!(A_0)$ and use the adjunction property.]
2. $f_!(f^*(B_0)) \subseteq B_0$. [Set $A_0 = f^*(B_0)$ and use the adjunction property.]
3. Now consider $f_!(f^*(f_!(A_0)))$. By (1), we have $f_!(A_0) \subseteq f_!(f^*(f_!(A_0)))$, and by (2) we have $f_!(f^*(f_!(A_0))) \subseteq f_!(A_0)$. So $f_!(A_0) = f_!(f^*(f_!(A_0)))$. But it is clear that $f_!$ is injective if $f$ is injective, so we can cancel $f_!$ from both sides of the equation to get $A_0 = f^*(f_!(A_0))$ in that case.
4. Similarly, $f^*(f_!(f^*(B_0))) = f^*(B_0)$. Observe that $f^*$ is injective if $f$ is surjective. [Confusing, but true!] So in that case we can cancel $f^*$ and get $f_!(f^*(B_0)) = B_0$.

The reason I think this is an elegant proof is because it highlights the symmetry underlying the two questions. Of course, you are free to disagree.

Exercise. Show that $f^* : \mathscr{P}(B) \to \mathscr{P}(A)$ itself has a right adjoint $f_* : \mathscr{P}(A) \to \mathscr{P}(B)$. [It is called the dual image map.] Using the only the adjunction properties between $f_!$, $f^*$, and $f_*$, prove the following:

1. $f_!$ and $f^*$ preserve all unions and the empty set. [Use the fact that they are left adjoints.]
2. $f^*$ and $f_*$ preserve all intersections and the full set. [Use the fact that they are right adjoints.]
-

You are right, you do know the geometry of what's going on, and have given a clear account. But a few times at least, it is worthwhile to do the details, step by grinding step. The presentation below is definitely not elegant, nor is it meant to be. I will do (a) only.

(a) (i) We show that $A_0 \subset f^{-1}(f(A_0))$.

Let $a\in A_0$. We need to show that $a\in f^{-1}(f(A_0))$.

Note that $f(a) \in f(A_0)$. It follows that $a\in f^{-1}(f(A_0))$.

(ii) Let $f$ be injective. We show that $A_0 = f^{-1}(f(A_0))$.

In part (i), we have shown that $A_0 \subset f^{-1}(f(A_0))$. We will now show that if $f$ is injective, then $f^{-1}(f(A_0)) \subset A_0$.

So let $a \in f^{-1}(f(A_0))$. Then $f(a)=b$ for some $b \in f(A_0)$. It follows that $b=f(a')$ for some $a'\in A_0$.

Since $f$ is injective, and $f(a)=f(a')$, we conclude that $a'=a$, and hence $a\in A_0$.

-