##G## is Injective ##\iff ## ## f ## is onto ## Y ## (Lambda Notation)

[CGandC]

Homework Statement

We define the function $G = \lambda A \in P(Y). f^{-1}[A]$ ,
Prove that for every $X , Y$ and $f \in X \rightarrow Y$ :
$G$ is Injective $\iff$ $f$ is onto $Y$.

Relevant Equations

-Familiarity with Lambda notation ( from lambda calculus )
- $P(Y)$ is power-set of $Y$

My attempt:
$( \rightarrow )$ Suppose G is injective. Let $y \in Y$ be arbitrary, denote A = $\{ y \}$ so that $G(A) = G(\{ y \}) = f^{-1}[\{ y \}] = \{ x \in X | f(x) \in \{ y \} \} =\{ x \in X | f(x)= y \}$.
[ However, now I am stuck because I don't know if $G(A)= \emptyset$ and trying to assume it and find a contradiction also had me getting stuck. If I knew that $G(A) \neq \emptyset$ I'm practically finished proving this side. Any ideas? ].

$( \leftarrow )$ Suppose $f$ is onto $Y$. Let $A_1 , A_2 \in P(Y)$ be arbitrary. Suppose $G(A_1) = G(A_2)$ , meaning $\{ x \in X | f(x) \in A_1 \} = \{ x \in X | f(x) \in A_2 \}$
[ I'm kinda lost, how do I use the assumption that f is onto in order to continue? ]

Thanks in Advance!

 

[Office_Shredder]

For the injective direction, what is $G(\emptyset)$? What does that say about $G(\{y\})$?

For the other direction, if $f^{-1}(A_1)=f^{-1}(A_2)$, let $a\in A_1$ be an element such that $a\notin A_2$. What can you say about it?

 

[CGandC]

Ok I think I understand better now after your guidance:
If $Y = \emptyset$ then it is vacuously true that G is injective $\iff$ f is onto Y ( If we assume G is injective then it is vacuously true that f is onto Y , and if we assume f is onto Y then it is vacuously true that G is injective ) .

For the injective direction, what is $G(\emptyset)$? What does that say about $G(\{y\})$?

Now Suppose $Y \neq \emptyset$.
Since $f$ is a function $G( \emptyset ) = f^{-1}[ \emptyset ] = \emptyset$. If we assume ( in order to get contradiction ) $G( \{ y \} ) = \emptyset$ then this implies $\{ y \} = \emptyset$ . Cleary a contradiction since we have $Y \neq \emptyset$. Hence $G(\{ y \}) \neq \emptyset$.

For the other direction, if $f^{-1}(A_1)=f^{-1}(A_2)$, let $a\in A_1$ be an element such that $a\notin A_2$. What can you say about it?

Assuming $a \in A_1$ and $a \notin A_2$ then since $f$ is onto $Y$ there exists $x \in X$ s.t. $f(x) = a \in A_1$ . Meaning $x \in f^{-1}[A_1]$ and specifically $f(x) = a \in A_2$ ( since we assumed $f^{-1}(A_1)=f^{-1}(A_2)$ then $x \in f^{-1}[A_1]$ also means $x \in f^{-1}[A_2]$ and this means $f(x) = a \in A_2$ ). So we got a contradiction.
We very similarly contradict the assumption $a \notin A_1$ and $a \in A_2$.
Hence we're left with $a \in A_1$ and $a \in A_2$. And since $a$ was arbitrary, $A_1 = A_2$ . Hence we just showed $G$ is an injection.

 

[Office_Shredder]

Looks good!