Why is the set of all functions mapping $\{0,1\}\to\Bbb N$ countable, but the set of all functions mapping $\Bbb N\to\{0,1\}$ uncountable? Is there an intuitive way to think about this question? I understand that for the set of all functions mapping $\{0,1\}\to\mathbb{N}$, you can think of each function as a tuple of $(0, 1),(1,1),(0,2),\ldots$. However, doesn't think same logic apply to the set of all functions mapping $\mathbb{N}\to\{0,1\}$, where you can think of each function as a tuple (some natural number, $0$ or $1$)? 
 A: This is a cool problem and it basically comes down to the countability of the rationals and uncountability of the reals which are both so called "standard" results. 
For the former set of functions: 
$$|\{0,1\}\rightarrow \mathbb{N}| = |\mathbb{N}^2| = |\mathbb{N}|$$
The "intuitive" (I dislike that word) way to see this is to think of maps as tuples in $\mathbb{N}^2$ with each coordinate specifying where either $0$ or $1$ are mapped to. For example $(3,4)$ is the map that takes $0\mapsto 3$ and $1\mapsto 4$. The reason this has the same cardinality as $\mathbb{N}$ is because we can define a one to one map between the two sets (to find this map look up a proof for the countability of the rational numbers). 
Now for the latter set of functions (which are far far cooler to think about)
 $$| \mathbb{N}\rightarrow\{0,1\}| = |2^\mathbb{N}| = |\mathbb{R}|$$
The reason being  is that for each $n$ in $\mathbb{N}$ we either map to $0$ or $1$, which means we can represent each of our functions as a binary address (binary number) 
$$a=0.a_1a_2a_3...$$ 
Where the $n^{th}$ digit  $a_n\in\{0,1\}$ of the binary number $a\in[0,1]$ tells us where $n$ is mapped to. 
For example the binary number $0.\dot{0}$ is the map that takes everything in $\mathbb{N}$ to $0$ and the binary number $0.\dot{0}\dot{1}$ takes even numbers to $0$ and odd numbers to $1$ (if we take $0\in\mathbb{N}$, otherwise it's the other way round). Now every binary address defines a valid function from the natural numbers to $\{0,1\}$ and hence the carinality of the set of such maps is the cardinality of the real numbers between $0$ and $1$ which is uncountable and equal to $|\mathbb{R}|$. (If you haven't already go check out a proof for the uncountability of the real numbers between $0$ and $1$, it's neat!)
A: In general, graph $\Gamma_f\subseteq X\times Y$ of a map $f:X\to Y$ is in one-to-one correspondence with $X$ (send $(x,f(x))\in\Gamma_f$ to $x\in X$; since $f(x)$ exists and is uniquely determined for any $x$, this map is bijective).
Now it is indeed true that graphs both of maps $\{0,1\}\to\mathbb N$ and $\mathbb N\to\{0,1\}$ are subsets in $\{0,1\}\times\mathbb N$. But in the first case they are two-element subsets, while in the second they are infinite. So, even regardless of further restrictions making them graphs (and not any subsets) it is clear that there are "much more" infinite subsets than two-element subsets.
Hope this is intuitive enough...
