Let $a_0$ $\in$ $\mathit A$. Show that that the function $f:\mathcal P(\mathit A) \to \mathcal P(\mathit A)$ is bijective

Question

I have the following exercise in my discrete mathematics course.

Let $a_0$ $\in$ $\mathit A$. Show that that the function $f : \mathcal{P}(A) \to \mathcal{P}(A)$ defined by

$f(X) = \begin{cases} X \cup \{a_0\} & a_0 \notin X \\ X \setminus \{a_0\} & a_0 \in X \end{cases}$

is bijective.

I know that a function f is bijective if:

1. f is injective, i.e. $f(x) = f(y) \to x = y$
2. f is surjective, i.e. for all $y \in$ codomain there is an element $x \in$ domain, such that $f(x) = y $.

I also know that per definition of $f$, $\mathit X$ is a set of elements. But I'm stuck to show the injective and surjective propertie.

Answer 1

1. To prove that $f$ is injective: Let $X,Y\in\mathcal{P}(A)$. Suppose that $f(X)=f(Y)$. Consider two cases. Case I: $a_{0}\notin X$. In this case $f(Y)=f(X)=X\cup\{a_{0}\}\Rightarrow a_{0}\in f(Y)$. If $a_{0}\in Y$, then $f(Y)=Y\setminus\{a_{0}\}\Rightarrow a_{0}\notin f(Y)$, a contradiction. Therefore, $a_{0}\notin Y$. Now, $f(X)=f(Y)\Rightarrow X\cup\{a_{0}\}=Y\cup\{a_{0}\}$, from which we can infer that $X=Y$. (Formally, let $x\in X$, then $x\in X\cup\{a_{0}\}\Rightarrow x\in Y\cup\{a_{0}\}$. Since $x\in X$, $x\neq a_{0}$. Therefore, $x\in Y$. This shows that $X\subseteq Y$. Similarly, $Y\subseteq X$.) Case II: $a_{0}\in X$. In this case, $f(Y)=f(X)=X\setminus\{a_{0}\}$. If $a_{0}\notin Y$, then $f(Y)=Y\cup\{a_{0}\}$. Hence, $Y\cup\{a_{0}\}=X\setminus\{a_{0}\}$ which is a contradiction because LHS contains $a_{0}$ but RHS does not contain $a_{0}$. Therefore $a_{0}\in Y$. Finally, $f(X)=f(Y)\Rightarrow X\setminus\{a_{0}\}=Y\cup\{a_{0}\}$ from which we can prove that $X=Y$. (Formally, let $x\in X$. If $x=a_{0}$, then $x\in Y$. If $x\neq a_{0}$, then $x\in X\setminus\{a_{0}\}=Y\setminus\{a_{0}\}\Rightarrow x\in Y$. Hence, $X\subseteq Y$. Similarly, we can prove that $Y\subseteq X$.)

2. To prove that $f$ is surjective: Let $Y\in\mathcal{P}(A)$. Consider two cases. Case I: $a_{0}\in Y$. Define $X=Y\setminus\{a_{0}\}$, then $a_{0}\notin X$. Therefore, $f(X)=X\cup\{a_{0}\}=(Y\setminus\{a_{0}\})\cup\{a_{0}\}=Y$. Case II: $a_{0}\notin Y$. Define $X=Y\cup\{a_{0}\}$, then $a_{0}\in X$. Therefore, $f(X)=X\setminus\{a_{0}\}=(Y\cup\{a_{0}\})\setminus\{a_{0}\}=Y$.