Proof Validation: Let $f: A \to B$. Then $f^{-1}f$ is the identity on $\mathcal{P}(A)$ if 1-1, and $ff^{-1}$ the identity on $\mathcal{P}(B)$ if onto.

Question

I am attempting some self-learning of proof based texts, and I'm a little confused on what's "allowed". Specifically, I am trying to prove the below claim, and I am unsure about a few steps in my proof.

My questions:

1. Can I just deal with the mapping on sets directly, or do I need to show inclusion by focusing on actual elements in $s \in S \subset \mathcal{P}(A)$? If so, why?
2. I find it very hard to "find" what I need to show for some of these proofs because they just seem...obvious. I don't mean to sound whiny, but sometimes it just seems like I'm manipulating symbols without really providing any meaningful insight to the problem. Is this just a matter of "cutting your teeth" on more contained problems? Does anyone have any advice for self-correcting these more basic proofs?

Let $f\colon A \to B$. Then $f^{-1}f$ is the identity on $\mathcal{P}(A)$ if $f$ is 1-1, and $ff^{-1}$ is the identity on $\mathcal{P}(B)$ if $f$ is onto.

Proof: Let $T \subset B$ and $f\colon A \to B$ a surjective mapping. By definition, $T \in \mathcal{P}(B)$, and $\forall T \in \mathcal{P}(B), \exists S \in \mathcal{P}(A)$ such that $f(S) = T$. Notice that we also have the induced mapping $f^{-1}\colon B \to A$ such that $\forall T \in \mathcal{P}(B)$, $f^{-1}(T) = S$ for some unique $S \in \mathcal{P}(A)$. So, $T = f(S) = f(f^{-1}(T)) = ff^{-1}(T)$.

$\therefore ff^{-1} = id_{\mathcal{P}(B)}$

Now, let $f$ be injective and consider $S \subset A$. Again, we see $S \in \mathcal{P}(A)$, and $S_1 \neq S_2 \implies f(S_1) \neq f(S_2)$. Notice we still have the induced mapping $f^{-1}$ such that $\forall T \in \mathcal{P}(B), \exists!S \in \mathcal{P}(A)$ and $f^{-1}(T) = S$. In this way, let $S_1 = f^{-1}(T_1)$ and $S_2 = f^{-1}(T_2)$. Suppose $S_1 \neq S_2$. Then $f(S_1) \neq f(S_2) \implies f^{-1}(f(S_1)) \neq f^{-1}(f(S_2))$. Thus, conversely, $f^{-1}(f(S_2)) = f^{-1}(f(S_2)) \implies S_1 = S_2$.

$\therefore f^{-1}f = id_{\mathcal{P}(A)}$

$\blacksquare$

Answer 1

The problem is abusing notation rather badly by using $f$ to represent two different functions. We are told that $f:A\to B$, so the domain of $f$ is $A$. We are then asked to show that if $f$ is injective, then $f^{-1}f$ is the identity on $\wp(A)$. This is nonsense: the domain of the composite function $f^{-1}f$ is necessarily the same as the domain of $f$, which is $A$, not $\wp(A)$. What is true is that $f$ induces a function

$$F:\wp(A)\to\wp(B):S\mapsto f[S]\overset{\text{def}}=\{f(a):a\in S\}\,.$$

(Note the square brackets in $f[S]$: this is a standard notation used to show that the argument $S$ is a subset of the domain of $f$, not an element of it, and that $f[S]$ is the set of images under $f$ of the elements of $S$.)

The function $F$ is very closely related to $f$, but $f$ and $F$ are not the same function. The function $f$ also induces a function

$$G:\wp(B)\to\wp(A):T\mapsto f^{-1}[T]\overset{\text{def}}=\{a\in A:f(a)\in T\}\,,$$

and the result that you’re asked to prove is really that $GF=\operatorname{id}_{\wp(A)}$ if $f$ is injective, and $FG=\operatorname{id}_{\wp(B)}$ if $f$ is surjective. Thus, it really is a question about mappings of sets.

In the first part of your proof you say that for each $T\in\wp(B)$ there is an $S\in\wp(A)$ such that $f[S]=T$. This is true and is the crux of the argument, but you haven’t actually justified it. That a justification is required would be more readily apparent if the statement of the problem had carefully distinguished $f$ and $F$, because what you actually need to show here is that for each $T\in\wp(B)$ there is an $S\in\wp(A)$ such that $F(S)=T$; that is, you need to show that $F$ is surjective if $f$ is. This is of course very easy, but it’s an essential part of the argument, since $f$ and $F$ are not the same function. Here is one possible argument:

Let $T\in\wp(B)$; $f$ is surjective, so for each $b\in T$ there is an $a_b\in A$ such that $f(a_b)=b$. Let $S=\{a_b:b\in T\}$; then $$F(S)=f[S]=\{f(a_b):b\in B\}=\{b:b\in B\}=B\,,$$ as desired.

Now we can argue as follows. Let $T\in\wp(B)$; we’ll be done if we can show that $(FG)(T)=T$. Let $S=G(T)=\{a\in A:f(a)\in T\}$; we want to show that $F(S)=T$. Clearly

$$\begin{align*} F(S)&=F(\{a\in A:f(a)\in T\})\\ &=f[\{a\in A:f(a)\in T\}]\\ &=\{f(a):f(a)\in T\}\\ &\subseteq T\,. \end{align*}$$

On the other hand, we know (since $F$ is surjective) that there is a $U\in\wp(A)$ such that $F(U)=T$. Clearly $f(a)\in T$ for each $a\in U$, so $U\subseteq S$, and therefore

$$\begin{align*} T&=F(U)\\ &=\{f(a):a\in U\}\\ &\subseteq\{f(a):a\in S\}\\ &=F(S)\,, \end{align*}$$

and it follows that $F(S)=T$.

The beginning of the second half of your argument is easily modified to show that $F$ is injective if $f$ is. Now you want to show that if $S\in\wp(A)$, then $(GF)(S)=S$. We can use the injectivity of $F$.

$$\begin{align*} (GF)(S)&=G(\{f(s):s\in S\})\\ &=\big\{a\in A:f(a)\in\{f(s):s\in S\}\big\}\,, \end{align*}$$

so

$$\begin{align*} F\big((GF(S)\big)&=F\left(\big\{a\in A:f(a)\in\{f(s):s\in S\}\big\}\right)\\ &=\big\{f(a):f(a)\in\{f(s):s\in S\}\big\}\\ &=\{f(s):s\in S\}\\ &=F(S)\,, \end{align*}$$

and since $F$ is injective, we conclude that $(GF)(S)=S$.

In this case I really think that what you needed to show is to a significant extent hidden by the very sloppy statement of the problem in the first place. Combine that with the fact that the result is intuitively pretty clear anyway, and it’s not surprising that it wasn’t clear just what actually has to be proved here. I’ve tried to make that clearer both by being much more careful with my notation and by including a great deal of detail in order to show what is really going on behind the intuitive understanding.