2
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – usukidoll Feb 22 '14 at 22:32
  • $\begingroup$ 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}\; ?$$ $\endgroup$ – user63181 Feb 22 '14 at 22:36
  • $\begingroup$ oh... that second part came from one of the theorems that I recently posted... $\endgroup$ – usukidoll Feb 22 '14 at 22:38
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – usukidoll Feb 22 '14 at 23:06
  • $\begingroup$ @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$ $\endgroup$ – dani_s Feb 22 '14 at 23:09

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.