# Show the set of all functions from $\mathbb{N}$ to $\{0, 1\}$ is uncountable using a contradiction.

This is what I have written:

By contradiction, assume it is countable. Write $S=\{\text{all functions } \mathbb{N} \rightarrow \{0,1\} \}$. Then, we can find a bijection $\mathcal{H}: S \rightarrow \mathbb{N}$. Now, I would like to check how to incorporate Cantor's method to find the contradiction. Would it be right to think of each function as a binary representation (because they map to either $0$ or $1$)? So, I will write

$f(1) \mapsto a_{11}a_{12}a_{13}...$

$f(2) \mapsto a_{21}a_{22}a_{23}...$

$f(3) \mapsto a_{31}a_{32}a_{33}...$

where $a_{ij} \in \{0,1\}$.

and so on. So for example, $f(1)$ has input any natural number, so it will spit out either a $0$ or a $1$, and I have written all possibilities in a list.

Then, I define a function in $S$ that is $0$ if a string value is $1$ and $1$ if the string value is $0$.

I have one more question: what is the meant by the notation $\{0,1\}^{\mathbb{N}}$?

Thank you.

• $\{0,1\}$ is the set whose only objects are $0$ and $1$. Then $\{0,1\}^{\mathbb{N}}$ is the set of all functions from the natural numbers to $\{0,1\}$. – André Nicolas Jun 1 '15 at 0:52
• Yes, when I said "each function" I meant "each function of S." I'll edit it now. – Moz Jun 1 '15 at 0:53
• The notation $B^A$ is used to denote the set of all functions $f: A \to B$, typically. – David Wheeler Jun 1 '15 at 0:54
• I apologize for my other errors, it's very late and I'm determined to make sure I have this right before sleep. – Moz Jun 1 '15 at 0:55
• if you take $a=a_{j1}a_{j2}a_{j3}...$ where $a_{jk}\neq a_{kk}$, you have a $a$ which is not equal to some $f(n)$ for all $n$ because it differs from $f(n)$ in the term $a_{jn}$ – Luis Felipe Jun 1 '15 at 0:57

You can get contradiction by defining another $f(x)$ that can never be in list as follow:

$f(x)=b_{11}b_{22}\cdots, \hspace{2 mm} b_{ii}\neq a_{ii}$

Note that $f(x)$ can not be in the list anyway because if there is a $j$ such that $f(j)=f(x)$, then $b_{jj}=a_{jj}$, a contradiction. So no $1-1$ mapping is possible.

$\{0,1\}^{\mathbb{N}}$ is the set of all functions that map $\mathbb{N}$ to $\{0,1\}$.

• Yes, thank you. – Moz Jun 1 '15 at 23:04

Your idea is correct, Using the binary representation actually makes the explanation way easier. You can always get a binary number that is not in the list and obtain a contradiction using cantor's diagonal method

• Ok, but another user said "we do have to worry about the fact that some numbers have more than one binary expansion" and I am not sure if my enumeration addresses this. – Moz Jun 1 '15 at 1:10
• how is that possible ?? some numbers have more than one binary expansion, does he mean, $0011$ is the same as $11$ ?? – alkabary Jun 1 '15 at 1:12
• I think the user meant that $f(1)=0011...$ is a possibility and so is $f(1)=11000$. Maybe I am misreading the user's comment. – Moz Jun 1 '15 at 1:14
• If it is the case like I said , if he is worried that $0011$ is the same as $11$ then you just assume that the binary is reduced meaning that you don't accept an entry with a leading $0$ unless the $0$ number itself. Assume the representation is reduced – alkabary Jun 1 '15 at 1:17
• No, what they mean is that in binary $.0111111111...$ (continue 1's forever) is equal to $.1000000...$ (this is the same issue as $.9999... = 1$. This is because $\frac{1}{2} = \sum_{n=2}^\infty \frac{1}{2^n} = \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + ...$ – JHance Jun 1 '15 at 2:04

This is a classic application of Cantor's argument, first instead of thinking about functions lets just think about sequences of 0's and 1's. That is if $f: \mathbb{N} \to \{0,1\}$ and $f(1)=0, f(2)=1,f(3)=1, \ldots$ I will just write the sequence $011\ldots$. Suppose that the set is countable and list the elements $$a_{1}=a_{11}a_{12}a_{13} \ldots\\ a_{2}=a_{21}a_{22}a_{23} \ldots\\ a_{3}=a_{31}a_{32}a_{33} \ldots\\ \vdots$$ Now we construct an element $b$ that we have not listed by taking $$b_{n}=1 \text{ if }a_{nn}=0 \text{ or }b_{n}=1 \text{ if }a_{nn}=0$$ $b_{n}$ is not in the list because it differs from $a_{n}$ in the $n$th position for all $n$.