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$)?

• First of all, the first should be all ordered pairs of natural numbers (which — for me — do not include $0$). So it's the set of all integer points in the first quadrant of $\Bbb R^2$. The second is all infinite sequences of $0$'s and $1$'s. The first you should be able to see how to count. For the second, you need Cantor's proof by contradiction or something similar. – Ted Shifrin May 4 '17 at 5:03
• @TedShifrin is it not possible to count the second one as (1,0),(1,1),(2,0),(2,1).....? I know I'm mistaken here (since the second one is uncountable) but I just don't conceptually understand why. – javanewbie May 4 '17 at 5:07
• No, a map from $\Bbb N$ to a set assigns elements of that set to each of $1$, $2$, $3$, and so on ... so you get an entire infinite tuple or infinite sequence. – Ted Shifrin May 4 '17 at 5:15
• @javanewbie each "element" of the second one if you wish would be written in the form $\{(1,f(1)),(2,f(2)),(3,f(3)),(4,f(4)),\dots\}$ So you if you really wanted to try to write them all out you would have the list begin as $\{\{(1,f_1(1)),(2,f_1(2)),(3,f_1(3)),\dots\},\{(1,f_2(1)),(2,f_2(2)),(3,f_2(3)),\dots\},\{(1,f_3(1)),\dots\},\dots\}$. You can show however using cantor's diagonal argument that this listing misses a function from the list, implying that the list could never be complete – JMoravitz May 4 '17 at 5:15
• javanewbie: what you've written (based on the way you're counting) is exactly the set of functions from $\{0,1\}\mapsto\mathbb{N}$, not the set of functions the other direction: $(2, 1)$, for instance, corresponds to the function $\{0,1\}\mapsto\mathbb{N}$ that sends $0\mapsto 2$ and $1\mapsto 1$. – Steven Stadnicki May 4 '17 at 5:52

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!)

• I took a look at the countability of rational numbers and saw the visual proof where you construct a table with naturals for rows and columns and thus, are presented with an ordering of the rationals. I just tried making this same table for N -> (0,1) and had no problem tracing a path. – javanewbie May 4 '17 at 5:38
• Awesome! does the second part of my answer make sense to you as well? :) – Angus Leck May 4 '17 at 5:40
• Yes! Thanks for your answer. However, the problem is that the Rationals are countable but N->(0,1) should not be, yet I (definitely with a mistake when making the table that I'm unaware of), seemingly showed that the same manner of proof works just as well for N->(0,1) as it does for the Rationals. – javanewbie May 4 '17 at 5:44
• Almost certainly your list of maps is missing some, in fact if you wrote them down for me as binary numbers as in my answer I can construct a missing map. Look up the proof of the uncountability of the reals between 0 and 1 it's identical. – Angus Leck May 4 '17 at 5:50
• There have been many erroneous attempts submitted on this site to countably enumerate all of $\{0,1\}^N.$ The usual error is to enumerate only those $r\in [0,1)$ whose binary representation has only finitely many $1$'s, which are all rational numbers. – DanielWainfleet May 5 '17 at 0:51

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