I am working on the exercise from Terence Tao's Analysis I and I wanted to verify the following proof. I have proven one side of the biimplication and am now stuck on the second part (a hint would be sufficient). Since I am self-studying mathematics I would also be happy to hear your comment on the overall structure and style of the proof.

Exercise 3.4.5 Let $X,Y$ be sets, let $f:X\to Y$. Show that $\forall S\subseteq X: f^{-1} \left(f(S)\right) = S$ if and only if $f$ is injective.

\begin{proof} We first show that $f$ is injective implies $f^{-1} \left(f(S)\right) = S$.

We have already proven the cancellation law for bijective functions: $$ \forall x: g^{-1} \left(g(x)\right) = x \text{ and } g \left(g^{-1}(x)\right) = x$$

We use this fact to prove this proposition. We restrict $f:X \to Y$ to the mapping $f_S$ with the domain $S$ and range $f(S)$ $$f_S: S \to f(S), \quad f_S(x) := f(x)$$ Then $f_S$ is a function and in particular $f_S$ is bijection (Proof: Argue by contradiction. Suppose $f_S$ is not a bijection. Then by negating bijection property $\left(\forall y \in f(S) \quad \exists_{1} x \in S: f_S(x)=y \right)$ we obtain one of the following mutually exclusive cases by trichotomy of order on natural numbers:

  1. $\exists y \in f(S) \quad \exists_{0} x \in S: f_S(x)=y$, a contradiction to the definition of the forward image $f(S):=\{f(x): x\in S\}$
  2. $\exists y \in f(S) \quad \exists_{>1} x \in S: f_S(x)=y$, a contradiction to the injectivity assumption of $f$, since $\exists x,x' \in S: x\neq x'$ and $f_S(x)=f_S(x')$ implies $\exists x,x' \in X: x\neq x'$ and $f(x)=f(x')$.

as desired.) Since $f_S: S \to f(S)$ is bijection, we must have $$f_S^{-1} \left(f_S(S)\right) = S$$ since by Exercise 3.6.3 we have $\forall x \in S: f_S^{-1} \left(f_S(x)\right) = x$ hence $\{ f_S^{-1} \left(f_S(x)\right): x \in S\} = \{x \in S: x \in S\} = S$. It is then left to show that $$f_S^{-1} \left(f_S(S)\right) = f^{-1} \left(f(S)\right)$$ The fact that $f_S(S) = f(S)$ is true since $\forall x \in S: f_S(x) = f(x)$ and injectivity of $f$ together imply $\{f(x) \in Y: x \in S\} = \{f_S(x) \in f(S): x \in S\}$. $$f_S^{-1} \left(f(S)\right) = S$$ The fact that $f_S^{-1} \left(f(S)\right) = f^{-1} \left(f(S)\right)$ is true since $\forall y \in f(S): f_S^{-1}(y) = f^{-1}(y)$ and injectivity of $f$ imply $\{x \in X: f(x) \in f(S)\} = \{x \in S: f_S(x) \in f(S)\}$ $$f^{-1} \left(f(S)\right) = S$$ as desired.

Now we show that $f^{-1} \left(f(S)\right) = S$ implies that $f$ is injective.

proof \end{proof}


Assume f is injective.
Quickly show A subset $f^{-1}f(A).$ Now assume x in $f^{-1}f(A).$
Thus f(x) in f(A); exists a in A with f(x) = f(a).
Conclude x = a in A. Thus the reverse inclusion.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.