Proof of $\mathcal{F}\approx\mathcal{P}(\mathbb{N})$ using elementary notations and Cantor Bernstein Theorem?

Question

Suppose $\mathcal{F}$ is the set of all functions from $\mathbb{N}$ to $\{0,1\}$. My math textbook wants me to use Cantor-Bernstein Theorem.

Question: Using Cantor-Bernstein Theroem, prove $\mathcal{F}=\mathcal{P}(\mathbb{N})$.

Proof:

The definition of $\mathcal{F}$ represent all subsets of $\mathbb{N}\times\{0,1\}$. Hence $\mathcal{F}=\mathcal{P}(\mathbb{N}\times\{0,1\})$.

Suppose we create a function $f:\mathbb{N}\to\mathbb{N}\times\{0,1\}$. If $f(x)=(x,1)$, then it is automatically one-to-one. Hence, $|\mathbb{N}|\le|\mathbb{N}\times\{0,1\}|$. Therefore, $|\mathcal{P}{(\mathbb{N})}|\le|\mathcal{P}(\mathbb{N}\times\{0,1\})|$. Hence, $|\mathcal{P}(\mathbb{N})| \le|\mathcal{F}|$.

Now suppose we create $g:\mathbb{N}\times\{0,1\}\to\mathbb{N}$. If $g=xy$, then if $x_1y_1=x_2y_2$ then $x_1=x_2$ and $y_1=y_2$. Hence $g$ is one-to-one. Hence $|\mathbb{N}\times\{0,1\}|\le|\mathbb{N}|$. Therefore, $|\mathcal{F}|\le|\mathcal{P}(\mathbb{N})|$.

Hence using Cantor-Bernstein Theorem, $|\mathcal{F}|=|\mathcal{P}(\mathbb{N})|$. Therefore $\mathcal{F}\approx\mathcal{P}(\mathbb{N})$

Is my proof correct? If not, how can we improve it? (If you don't understand my proof, make your own answer.)

Answer 1

Proof:

The definition of $\mathcal{F}$ is one of the subsets of $\mathbb{N}\times\{0,1\}$. Hence $\mathcal{F}\subseteq\mathcal{P}(\mathbb{N}\times\{0,1\})$.

Suppose we create $g:\mathbb{N}\times\{0,1\}\to\mathbb{N}$. If $g(x,y)=2^x(2y+1)$; then, if $2^{(x_1)}{(2y_1+1)}=2^{(x_2)}{(2y_2+1)}$, then $2^{x_1}=2^{x_2}$ and $2y_1+1=2y_2+1$. Therefore $x_1=x_2$ and $2y_1=2y_2$; and therefore $y_1=y_2$. This means $g$ is one-to-one. Therefore, $|\mathbb{N}\times\{0,1\}|\le|\mathbb{N}|$. This means $|\mathcal{P}(\mathbb{N}\times\{0,1\})|\le|\mathcal{P}(\mathbb{N})|$, moreover; since $\mathcal{F}\subseteq\mathcal{P}(\mathbb{N}\times\{0,1\})$, $|F|\le|\mathcal{P}(\mathbb{N}\times\{0,1\})|\le|\mathcal{P}(\mathbb{N})|$ giving $|\mathcal{F}|\le|\mathcal{P}(\mathbb{N})|$.

Now consider $f:\mathcal{P}(\mathbb{N})\to\mathcal{F}$, we can construct $f(A)=\chi_A$ where $A\in\mathcal{P}(\mathbb{N})$ and $\chi_{A}:\mathbb{N}\to\mathbb{N}$ is the characterisitic function. If $f(A)=f(B)$ then $\chi_{A}=\chi_{B}$. Therefore, $A=B$. Since $f$ is injective, $|\mathcal{P}(\mathbb{N})|\le|\mathcal{F}|$.

Using Cantor-Bernstein Theorem, $|\mathcal{F}|=|\mathcal{P}(\mathbb{N})|$. Therefore $\mathcal{F}\approx\mathcal{P}(\mathbb{N})$

Is my proof correct? If not, how can we improve it?

Answer 2

Cantor-Bernstein-Schröder is overkill. If $X$ is any set, and $\mathcal{F}$ denotes the set of all functions $X \to \{0,1\}$, then the map $$\wp(X) \ni A \mapsto \chi_A \in \mathcal{F}$$ is a bijection, where $\chi_A$ is the characteristic function of $A$, defined by $\chi_A(x)=1$ if $x \in A$ and $\chi_A(x)=0$ if $x \not\in A$.

• Surjectivity: if $f \in \mathcal{F}$, then $f = \chi_{f^{-1}[\{1\}]}$.
• Injectivity: if $A,B \in \wp(X)$ and $A \neq B$, there is $x \in (A\setminus B)\cup (B\setminus A)$, so $\chi_A(x)\neq \chi_B(x)$ says that $\chi_A \neq \chi_B$ (as functions).