# Injections with power sets

Let $X$ and $Y$ be two non-empty sets and $f: X \to Y$ is a function then we can define $f^{\rightarrow}: \mathcal P(X) \to \mathcal P(Y)$ and $f^{\leftarrow}: \mathcal P(Y) \to \mathcal P(X)$ where $\mathcal P$ is notation for supersets:

\begin{align*} f^{\rightarrow}(A) & = \{ f(x) \in Y : x \in A\} & A\in \mathcal P(X) \\[1ex] f^{\leftarrow}(B) & = \{ x \in X : f(x) \in B\} & B\in \mathcal P(Y) \end{align*}

Show that if $f$ is an injection $f^{\leftarrow}(f^{\rightarrow}(A)) =A\;\;\forall A \subset X$ and that if $f$ is not an injection there exists a set $A \subset X$ so that $f^{\leftarrow}(f^{\rightarrow}(A)) \neq A$.

So for the first we have to show that $A \subset f^{\leftarrow}(f^{\rightarrow}(A))$ and $f^{\leftarrow}(f^{\rightarrow}(A))\subset A$.

$$A \subset f^{\leftarrow}(\{ f(x) \in Y : x \in A\})$$

$A$ is in superset of $X$ and because the function is injective the elements from the domain are mapped to at most one element of the co domain.

$$A \subset \{ x \in X : f(x) \in A\}$$

And now we map the range back to a set of elements that is a subset of $A$. Then the next case should be done with same logic? I don't quite follow how the proof should be done for the non-injective case? Any help & hints are welcome.

• An element of the domain is always mapped to exactly one element of the codomain, regardless of injectivity. Commented Sep 18, 2015 at 11:54
• Oh yeah good call! I edited my post
– ELEC
Commented Sep 18, 2015 at 12:00

Suppose $f$ is not injective. Let $x \neq y$ be elements of $X$ with $f(x) = f(y)$.

Take $A = \{x\}$.

Then $f^{\rightarrow}(A) = \{f(x)\}$

And $f^{\leftarrow}(f^{\rightarrow}(A)) \supset \{x,y\} \supsetneq A$

So $f^{\leftarrow}(f^{\rightarrow}(A)) \neq A$

A function is injective (aka one-to-one) if it preserves distinctness. It never maps distinct elements in the domain to the same element in the co-domain.

Then $f^\leftarrow\circ f^\to$ maps A one-to-one to an image in Y and then maps that image back to A.

A function is not injective if distinctness is not preserved; that there exists distinct elements in the domain that do map to the same element in the co-domain. It's many-to-one.

Then there is some A where the image does not map back to A . Specifically: $$\Big[\exists x_1\in A, \exists x_2\in X{\setminus}A: f(x_1)=f(x_2)\Big] \to \Big[\exists x\in X{\setminus}A: x\in f^\leftarrow( f^\to (A))\Big]$$