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

elementary-set-theoryfunctionsreal-analysissolution-verification

First I am aware of similar posts such as this one, however my question falls under the solution-verification tag and I used a totally different method.

Complete question:

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

My answer:

A function can be surjective, injective, or bijective. The function being bijective doesn't contradict our statement since it has to surjective as well for it to be bijective. Hence, I am going to take a look at the case where $f$ is injective.

Assuming $f$ is injective then it's not necessarily true that for all $s \in S$ there exists an $s' \in X$ such that $f(s')=s$, thus sometimes $f^{-1}(s)=\emptyset$ so $f(f^{-1}(s))=\emptyset \neq s$

Contradiction, end of proof.

Other approaches I thought of:

$1$-Similar as the previous one but after assuming the function is injective I give a concrete counter example (such that $f(S)=S^2$, so $f^{-1}(S)=\sqrt{S}$ while taking $S=\{1,2,3\}$ with the domain and range being the set of natural numbers. In this case $f^{-1}(S)=\emptyset$

$2$-Similar to the ones in other posts here, $f(f^{-1}(S))$ means that for all $S$ there exists $s' \in X$ such that $f^{-1}(S)=s'$ and $f(s')=S$ however the statement "for all $S$ there exists $s' \in X$ such that $f^{-1}(S)=s'$" means the function is surjective. (I am not quite sure about this one, felt like I was citing definitions)

Best Answer

You seem to have some misconceptions about certain mathematical objects/properties:

  • If a function is not surjective, it does not need to be injective ($f: \mathbb{R} \to \mathbb{R}:x \mapsto x^2$ is neither surjective, nor injective).
  • if $S$ is a set, then so is $f(S)$ and $f(S)$ is not necesasrily a singleton (which you assume in your last proof: $f(S) = s$ for some $s\in X$.

In order to give a correct proof, you need to prove two implications:

  • If $S = f(f^{-1}(S))$ for all $S \subset Y$, then $f$ is surjective
  • If $f$ is surjective, then $S = f(f^{-1}(S))$ for all $S \subset Y$. This second part requires you to prove two inclusions: $S \subset f(f^{-1}(S))$ and vice versa. To do this, let $s \in S$ be arbitrary and show that it is an element of $f(f^{-1}(S))$.
Related Question