# Show $\mathbb{N}^{\{0,1\}}$ is uncountable with a hint

Let $\mathbb{N}^{\{0,1\}} :=\{f: \mathbb{N} \to \{0,1\}\}$ is uncountable

I have never heard of the table approach, and all the proofs say uncountability of $\mathcal {P}(\mathbb{N})$ I have seen so far do not use the table approach. There was a hint how to do this without listing stuff in a table: Is the set of all functions from $\mathbb{N}$ to $\{0,1\}$ countable or uncountable?

Suppose that $f_1,…$ is a countable sequence of functions in $\{0,1\}^\mathbb{N}$, we define the function $F(n)=1−f_n(n)$. Check that $F:\mathbb{N}\to\{0,1\}$, and now show that it differs from $f_1,f_2,…$. If $\{0,1\}^\mathbb{N}$ was countable we could have enumerated it like that, but then $F$ would be somewhere in the list. This is impossible and therefore $\{0,1\}^\mathbb{N}$ is uncountable.

Couple of questions:

1. Does $\{0,1\}^\mathbb{N} = \{f: \mathbb{N} \to \{0,1\}\}$, I maybe using conflicting notations

If that is the case, then the function $F$ makes sense

1. What does it mean by "now show that it differs from $f_1,f_2,…$"?

Does it mean suppose $f_k(n) = F(n)$, then $F(n) = 1 - f_k(n) = 1 - F(n)$, so $F(n) = \dfrac{1}{2}$ so this is impossible.

• By definition, $A^B$ is the set of functions from $B$ to $A$, for all sets $A$ and $B$. – Git Gud Jun 7 '16 at 21:37
• @GitGud Oh that's a terrible convention, your pre-image should come before your image. Looking at $A^B$ makes me think of $f: A \to B$ – Shamisen Expert Jun 7 '16 at 21:39
• @TheSilenceoftheCows I disagree, since for finite sets, you have $|A^B| = |A|^{|B|}$. It feels more akward to have $|A^B| = |B|^{|A|}$ – JMoravitz Jun 7 '16 at 21:39
• @TheSilenceoftheCows "Before" is a relative term. You're reading from left to right. Anyway, the motivation behind the notation is this. Consider the number $2^3$. Now take a set with two members, say $\{0,1\}$ and another one with three elements, say $\{0,1,2\}$. You can prove that the set of functions from the latter to the form has exactly $8$ elements (which equals $2^3$). This is true for any choice of finite sets, hence the generalization of the notation. – Git Gud Jun 7 '16 at 21:42
• @TheSilenceoftheCows You couldn't be more mistaken about the definition of $A^B.$ It's perfectly natural. – zhw. Jun 7 '16 at 21:48