# Show that $\alpha$ is a bijection.

Let $X$ be a set and consider the function, $\alpha : \mathcal P \left({X}\right) \rightarrow \mathcal P \left({X}\right)$ such that for all $S \in \mathcal P \left({X}\right), \alpha (S) = X \backslash S$. Show that $\alpha$ is a bijection. What is $( \alpha \circ \alpha) (S)$ for any $S \in \mathcal P \left({X}\right)?$

My attempt:

We need to prove that $\alpha$ is not a bijection.

Suppose that $\alpha$ is a surjection. Definition 5.4.1 states that a function $f: X \rightarrow Y$ with the property $(\forall Y \in Y)( \exists \in X ) [f(x) = y ]$ is a surjection of $X$ onto $Y$.

$$\forall T\in \mathcal P(X)\ \exists S\in \mathcal P(x)\quad X\setminus T = S$$

There is a subset in $X$ that is complement for $T$. We know that $S$ is in $P(X)$ because $S$ must be a subset of $X$. By complementing both sides, we have:

$$\forall T \in\mathcal P(X)\ \exists S\in\mathcal P(S) \quad (X\setminus T)^C=S^C$$

Then, we intersect both of them with $X$.

$$\forall T\in\mathcal P(X)\ \exists S\in\mathcal P(S) \quad X\cap (X\setminus T)^C=X\cap S^C$$

For, $$X\cap(X\setminus T)^C = X\cap(X\cap T^C)^C = X\cap(X^C\cup T)= (X\cap X^C)\cup (X\cap T)= T$$

By Proposition 3.3.5(i),

$$X\cap S^C = X \setminus S$$

We have proven that $\alpha$ is a surjection.

Suppose $\alpha$ is not an injection. Definition 5.4.5 states that a function $f: X \rightarrow Y$ with the property $\forall x_1, x_2 \in X)[ x_1 \neq x_2] \rightarrow f(x_1) \neq f(x_2)$ is an injection of $X$ into $Y$. We are going to prove the contrapositive of the injection definition by using $\forall x_1, x_2 \in X)[ x_1 = x_2] \rightarrow f(x_1) = f(x_2)$.

$$X \setminus S_1 = X\setminus S_2 \rightarrow s_1=s_2$$

By complementing both sides, we have:

$$(X \setminus S_1)^C = (X\setminus S_2)^C$$

Then, we intersect both of them with $X$.

$$X \cap (X \setminus S_1)^C = X \cap (X\setminus S_2)^C \qquad \text{by Proposition 3.3.5i}$$

$$X \cap (X \cap S_1^{c})^c=X \cap (X \cap S_2^{c})^c \qquad \text{by negation law}$$

$$X \cap (X^c \cup S_1) = X \cap (X^c \cup S_2) \qquad \text{by distributive law}$$

$$(X \cap X^c) \cup (X \cap S_1) = (X \cap X^c) \cup (X \cap S_2) \qquad \text{by identity law}$$

$$\emptyset \cup X \cap S_1 = \emptyset \cup X \cap S_2 \qquad \text{by identity law}$$

$$X \cap S_1 = X \cap S_2$$

$$S_1 \subseteq X = S_2 \subseteq X$$

$$S_1=S_2$$

Since $S_1 \subseteq X$ and $S_2 \subseteq X$ there are elements in $S_1$ and $S_2$ that are the same in $X$, so the intersection won't take away any elements from $S_1$ and $S_2$.

We need to show that for any $X \backslash S$, there is only one corresponding $S$. Since $\alpha(S) = X \backslash S$, the term $(\alpha \circ \alpha)$ is its own inverse.

$$( \alpha \circ \alpha) = X \backslash (X \backslash S)$$

$$=X \backslash X \qquad \text{by complement definition}$$

$$=S$$

Apparently, I screwed up big time because $\alpha$ is indeed a bijection which means that it's onto (surjection) and a one-to-one (injection). I need to start with an alternative proof by proving that $\alpha \circ \alpha =I_d$.

Proposition 5.4.4 states that the composition of two surjections is a surjections. Also, proposition 5.4.9 states that the composition of two injections is a injection.

My question is should I use Theorem 5.5.2 which is if the functions $f: X \rightarrow Y$ and $g : Y \rightarrow X$ satisfy $g \circ f =I_x$, then $f$ is an injection and $g$ is a surjection? Only in this case that would be that the left $\alpha$ is $f$ and the right $\alpha$ is $g$.

By a very succinct way: we have $$\alpha\circ\alpha=\operatorname{id}_{\mathcal P(X)}$$ hence $\alpha$ is a bijection and $$\alpha^{-1}=\alpha$$

• Wait question... what definitions did you use to prove that $\alpha \circ \alpha$ is an identity power set ? and where did the alpha inverse come from? – usukidoll Feb 22 '14 at 22:32
• To prove that $\alpha\circ\alpha$ is the identity power set you should understand the meaning of $\alpha(S)=X\setminus S$ and for the second question, what's the meaning of $$f\circ g=g\circ f=\operatorname{id}\; ?$$ – user63181 Feb 22 '14 at 22:36
• oh... that second part came from one of the theorems that I recently posted... – usukidoll Feb 22 '14 at 22:38

Let's try to make it shorter.

You need to show two things:

1) $\alpha$ is one-to-one and

2) $\alpha$ is onto.

Proof of 1). Let $\alpha(S)=\alpha(T)$. Then $X\smallsetminus S=X\smallsetminus T$, and thus $$S=X\smallsetminus (X\smallsetminus S)=X\smallsetminus (X\smallsetminus T)=T.$$ Thus $\alpha$ is one-to-one.

Proof of 2). If $S\in\mathscr P(X)$, then $T=X\smallsetminus S\in\mathscr P(X)$, as well, and $$\alpha(T)=X\smallsetminus (X\smallsetminus S)=S.$$ Thus $\alpha$ is onto.

Remember that $f$ is a bijection if and only if $f$ is invertible. Sometimes - and this is probably the case - it is easier to find the inverse of a function rather than directly proving that it is a bijection.

It should be intuitively clear to you that $\alpha$ is the inverse of itself. If not, try and see what $\alpha$ does to small sets (e.g. take $X = \{1,2,3,4,5\}$ and $S = \{2,3,5\}$ - what's $\alpha(S)$? $\alpha(\alpha(S))$?).

For a formal proof of $\alpha \circ \alpha = id$, we need to show that $X \setminus (X \setminus S) = S$. Can you do that?

• won't that mean using the complement definition? If I do it twice, I'll have an empty set...unless there's a property that shows that X is a subset of S. – usukidoll Feb 22 '14 at 23:06
• @usukidoll No, consider the example I used: we have $X \setminus S = \{1,4\}$, therefore $X \setminus (X \setminus S) = X \setminus \{1,4\} = \{2,3,5\} = S$ – dani_s Feb 22 '14 at 23:09