Tao Analysis I - 3.4.5

Exercise 3.4.5

Let $f : X \to Y$ be a function from one set $X$ to another set $Y$ . Show that $f(f^{-1}(S))=S$ for every $S \subseteq Y$ if and only if $f$ is surjective. Show that $f^{-1}(f(S))=S$ for every $S \subseteq X$ if and only if $f$ is injective.

Show $f(f^{-1}(S))=S$ if and only if $f$ is surjective.

We need to prove both:

• $f(f^{-1}(S))=S \implies f$ is surjective.
• $f$ is surjective $\implies f(f^{-1}(S))=S$.

Let's start with $f(f^{-1}(S))=S \implies f$ is surjective. 

This is a statement of the form $A \implies B$, which we'll prove by showing the logically equivalent contrapositive $\neg B \implies \neg A$.

So, let's consider that $f$ is not surjective. This means there exists an $s \in S$ for some $S \subseteq Y$, such that $f(x) \neq s$ for all $x \in X$.

The inverse image $f^{-1}(S)$ is, by definition, the set $\{x \in X : f(x) \in S\}$.

If we apply $f$ to the elements of this set, we obtain the set $\{f(x) \in S\}$. However, this set cannot contain $s$ because $f(x) \neq s$ for all $x \in X$.  Therefore the set $\{f(x) \in S\}$ is not always $S$.

Therefore, $f$ not surjective implies $f(f^{-1}(S)) \neq S$.

This is logically equivalent to $f(f^{-1}(S))=S \implies f$ is surjective.

Now let's show $f$ is surjective $\implies f(f^{-1}(S))=S$.

To do this we need to show that under the assumption $f$ is surjective, both of the following are true:

• $f(f^{-1}(S)) \subseteq S$
• $S \subseteq f(f^{-1}(S))$

Let's start with the first $f(f^{-1}(S)) \subseteq S$. 

If $y \in f(f^{-1}(S))$ then $y=f(x)$ for some $x \in f^{-1}(S)$. By definition $f^{-1}(S)$ is the set $\{x \in X: f(x) \in S\}$. 

So if $f(x) \in S$ then $y=f(x) \in S$. That is, $y \in f(f^{-1}(S)) \implies y \in S$. This is equivalent to $f(f^{-1}(S)) \subseteq S$. Note we didn't need $f$ to be surjective for this.

Now let's consider $S \subseteq f(f^{-1}(S))$. 

Since $f$ is surjective, for every $y \in S$ there exists an $x \in f^{-1}(S)$ such that $f(x)=y$. 

Here, $x \in f^{-1}(S)$ gives us $y = f(x) \in f(f^{-1}(S))$. Hence, $y \in S \implies y \in f(f^{-1}(S))$. This is equivalent to $S \subseteq f(f^{-1}(S))$. 

Having shown both $f(f^{-1}(S)) \subseteq S$, and $S \subseteq f(f^{-1}(S))$, we can conclude $f(f^{-1}(S))=S$. This was under the assumption that $f$ is surjective, so we have $f$ is surjective $\implies f(f^{-1}(S))=S$.

Finally, having shown $f(f^{-1}(S))=S \implies f$ is surjective, and $f$ is surjective $\implies f(f^{-1}(S))=S$, we can say $f(f^{-1}(S))=S \iff f$ is surjective. $\square$

Show $f^{-1}(f(S))=S$ if and only if $f$ is injective.

We need to prove both:

• $f^{-1}(f(S))=S \implies f$ is injective.
• $f$ is injective $\implies f^{-1}(f(S))=S$.

Let's start with $f^{-1}(f(S))=S \implies f$ is injective.

This is a statement of the form $A \implies B$, which we'll prove by showing the logically equivalent contrapositive $\neg B \implies \neg A$.

So, let's consider $f$ is not injective. This means there exists an $x_1 \in X$ and $x_2 \in X$, where $x_1 \neq x_2$, such that $f(x_1)=f(x_2)$.

Let's consider the case $S=\{x_1\}$. If $f(x_1) = y \in Y$, then $f(S)=\{y\}$. Since $f(x_1)=f(x_2)$, we also have $y = f(x_2)$.

Now, the inverse image $f^{-1}(f(S))$ is the set $\{ x \in X : f(x) \in f(S) \}$, which here is $\{ x \in X : f(x) \in \{y\} \}$. 

Both $x=x_1$ and $x=x_2$ satisfy the membership condition of this set, and so this set is not $S=\{x_1\}$. 

We have shown that $f$ is not injective implies $f^{-1}(f(S)) \neq S$ for all $S \subseteq X$. This is logically equivalent to $f^{-1}(f(S))=S \implies f$ is injective.

Now let's show $f$ is injective $\implies f^{-1}(f(S))=S$.

To do this we need to show that under the assumption $f$ is injective, both of the following are true:

• $f^{-1}(f(S)) \subseteq S$
• $S \subseteq f^{-1}(f(S))$

Let's start with the first $f^{-1}(f(S)) \subseteq S$.

By definition of inverse images, $f^{-1}(f(S))$ is the set $\{x \in X: f(x) \in f(S)\}$. If $x'$ is a member of this set then $f(x') \in f(S)$.

But $f(S)$ is the set $\{f(x_s): x_s \in S\}$. This means there is an $x_s \in S$ such that $f(x_s) = f(x')$. 

Because $f$ is injective, this implies $x_s=x'$. This $x'$ is also in $S$.

We have shown $x \in f^{-1}(f(S)) \implies x \in S$. That is, $f^{-1}(f(S)) \subseteq S$. 

Now let's consider $S \subseteq f^{-1}(f(S))$.

By definition of inverse images, $f^{-1}(f(S))$ is the set $\{x \in X: f(x) \in f(S)\}$. 

If $x \in S$, then $f(x) \in f(S)$, and so $x$ meets the membership conditions of this set. That is, $x \in S  \implies x \in f^{-1}(f(S))$. This is equivalent to $S \subseteq f^{-1}(f(S))$. Note that we don't need $f$ to be injective for this.

By showing both $f^{-1}(f(S)) \subseteq S$ and $S \subseteq f^{-1}(f(S))$ under the assumption $f$ is injective, we have proven $f$ is injective $\implies f^{-1}(f(S))=S$.  $\square$