Let $Maps(\mathbb N,\{0,1\})$ denote the set of all maps from $\mathbb N$ to $\{0,1\}$. Prove that there does not exist any bijective map from $\mathbb N$ to $Maps(\mathbb N,\{0,1\})$.
The first thing that I thought of was to use proof by contradiction, but the problem is how do I deal with "$Maps(\mathbb N,\{0,1\})$"? I feel that I need to show that the cardinality of these 2 sets are different.
Any help or hints is seriously appreciated!
On
Assume that there is bijection $\varphi\colon\mathbb N\to \operatorname{Maps}(\mathbb N,\{0,1\})$. Define $f\colon\mathbb N\to\{0,1\}$ with formula
$$f(n)=\begin{cases} 0,&\varphi(n)(n) = 1\\ 1,&\varphi(n)(n) = 0\\\end{cases}.$$
Note that the idea behind $f$ is that $f(n) \neq \varphi(n)(n)$, for all $n$.
Since $\varphi$ is surjective, there exists some $n\in\mathbb N$ such that $\varphi(n) = f$. But, then we have $$\varphi(n)(n)=f(n) \neq \varphi(n)(n)$$ which is contradiction. Hence, there is no bijection of $\mathbb N$ and $\operatorname{Maps}(\mathbb N,\{0,1\})$.
The argument above is called Cantor diagonal argument, and here is why. Functions from $\mathbb N$ to $\{0,1\}$ are sequences of $0$'s and $1$'s. So, a function $\varphi\colon\mathbb N\to \operatorname{Maps}(\mathbb N,\{0,1\})$ maps every natural number to a sequence of $0$'s and $1$'s. For example, $\varphi$ might look like
\begin{array}{ccccccc} 0,& 1,& 1,&0,&0,&1,&\ldots\\ 0,& 1,& 0,&0,&0,&1,&\ldots\\ 1,& 0,& 1,&1,&0,&0,&\ldots\\ 0,& 1,& 0,&0,&1,&1,&\ldots\\ 1,& 1,& 0,&1,&0,&1,&\ldots\\ 0,& 0,& 1,&0,&0,&0,&\ldots\\ \vdots& \vdots& \vdots&\vdots&\vdots&\vdots& \end{array}
The idea is that if $\varphi$ is bijection, then all possible sequences are written in some row of the above table. Then, define $f$ as we did above. What is happening is that we are taking diagonal of the above table and change every $0$ to $1$ and every $1$ to $0$.
\begin{array}{cc} {\begin{array}{ccccccc} \color{blue}0,& 1,& 1,&0,&0,&1,&\ldots\\ 0,& \color{blue}1,& 0,&0,&0,&1,&\ldots\\ 1,& 0,& \color{blue}1,&1,&0,&0,&\ldots\\ 0,& 1,& 0,&\color{blue}0,&1,&1,&\ldots\\ 1,& 1,& 0,&1,&\color{blue}0,&1,&\ldots\\ 0,& 0,& 1,&0,&0,&\color{blue}0,&\ldots\\ \vdots& \vdots& \vdots&\vdots&\vdots&\vdots& \end{array}} & {\begin{array}{c|c} \text{diagonal} & 0,\ 1,\ 1,\ 0,\ 0,\ 0,\ \ldots\\\hline f & 1,\ 0,\ 0,\ 1,\ 1,\ 1,\ \ldots \end{array}} \end{array}
Now, as we said, if $\varphi$ were bijection, then $f$ must be in the table. But, it can't be in the first row, because the first row is different from $f$ in the first place. It can't be in the second row since the second row is different from $f$ in the second place, etc. (This is what we wrote above as $f(n)\neq\varphi(n)(n)$, for all $n$.) Finally, we conclude that $f$ is not in the table, and hence we found a sequence that is not in the image of $\varphi$, so $\varphi$ can't be bijective.
The easiest way would be to show that there does exist a bijection between $Maps(\mathbb N, \{0,1\})$ and $\mathcal P(\mathbb N)$.
You can do this by looking at elements of $Maps(\mathbb N, \{0,1\})$ as indicator functions.
Alternatively, you could write a variant of Cantor's diagonal argument yourself.
Assume that there is a bijection. Then $Maps(\mathbb N,\{0,1\})=\{m_1,m_2,\dots\}$ where $m_i$ is a mapping from $\mathbb N$ to $\{0,1\}$.
Since $m_1$ is a mapping to $\{0,1\}$, we can represent it as, for example,
$$m_1 \equiv [0,0,1,0,0,0,1,0,1\dots]$$
(this would mean $m_1(1)=0, m_1(2)=0, m_1(3)=1\dots$).
Now write down
$$m_1=[_1m_1, _2m_1,_3m_1\dots]\\ m_2=[_1m_2, _2m_2,_3m_2\dots]\\ m_3=[_1m_3, _2m_3,_3m_3\dots]\\\vdots$$
and you can (using a Cantor-like argument) construct a mapping $m$ that is not equal to any of the above mappings.