Prove Cardinality of Power set of $\mathbb{N}$, i.e $P(\mathbb{N})$ and set of infinite sequences of $0$s & $1$s is equal.

Question

I tried doing this by defining a function $f$ which takes an element (a subset of $\mathbb{N}$) and maps it to an infinite sequence of $0$s & $1$s. A subset, i.e the element of $P(\mathbb{N})$ will contain discrete numbers from $\mathbb{N}$ (arranged in increasing order, since the order of numbers in a subset does not change the element), The same positions as those numbers will get $1$ (become activated) and others would be $0$ (switched off). E.g: $(2,4,6,8,10,\ldots)$ will map to $(0101010101010\ldots)$, $(1,3,5,7,9)$ will map to $(10101010101\ldots)$ , $\mathbb{N}$ itself will map to $(11111111111111111\ldots)$ and null set will map to $(00000000\ldots)$. Is the approach correct? Someone asked me what if I give you an infinite sequence of natural numbers $(a,b,c,d,\ldots)$ i.e an element of $P(\mathbb{N})$, what will be its image? What should be an ideal answer.In other words how to rigorously show that $f$ is well-defined (one-one and onto)?

Answer 1

Your approach is essentially correct, but it is not very precise because you are identifying subsets of $\mathbb{N}$ with their increasing enumerations. Although one could say that these two things are "essentially the same," one could also say that subsets of $\mathbb{N}$ are "essentially the same" as infinite sequences of zeroes and ones, but the challenge remains to make these relationships mathematically precise.

First we need a precise notion of "infinite sequence of zeroes and ones." The set of such sequences can be written as $\{0,1\}^\mathbb{N}$ and we can think of its elements as functions from $\mathbb{N}$ to the set of digits $\{0,1\}$. The $n$-th element of the sequence is just its value at the argument $n$.

Given a subset $A \subset \mathbb{N}$, we can define a corresponding element $f(A)$ of $\{0,1\}^\mathbb{N}$. Because $f(A)$ is supposed to be a function on $\mathbb{N}$, the way to define it is to specify its value $f(A)(n)$ at each number $n \in \mathbb{N}$. We can do this by writing $$ f(A)(n) = \begin{cases} 0 & \text{if } n \notin A\\ 1 & \text{if } n \in A. \end{cases} $$

This is just a precise way of expressing what you said, namely that we put a $1$ in the positions corresponding to numbers that are in $A$ and a $0$ in the positions corresponding to numbers that are not in $A$. Now that we have defined the function $f$, you may be able to show that it is a bijection from $\mathcal{P}(\mathbb{N})$ to $\{0,1\}^\mathbb{N}$ (if you get stuck on this, please feel free to leave a comment.)