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.

  • $\begingroup$ $\{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\}$. $\endgroup$ – André Nicolas Jun 1 '15 at 0:52
  • $\begingroup$ Yes, when I said "each function" I meant "each function of S." I'll edit it now. $\endgroup$ – Moz Jun 1 '15 at 0:53
  • 1
    $\begingroup$ The notation $B^A$ is used to denote the set of all functions $f: A \to B$, typically. $\endgroup$ – David Wheeler Jun 1 '15 at 0:54
  • $\begingroup$ I apologize for my other errors, it's very late and I'm determined to make sure I have this right before sleep. $\endgroup$ – Moz Jun 1 '15 at 0:55
  • $\begingroup$ 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}$ $\endgroup$ – 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\}$.

| cite | improve this answer | |
  • $\begingroup$ Yes, thank you. $\endgroup$ – 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

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Moz Jun 1 '15 at 1:10
  • $\begingroup$ how is that possible ?? some numbers have more than one binary expansion, does he mean, $0011$ is the same as $11$ ?? $\endgroup$ – alkabary Jun 1 '15 at 1:12
  • $\begingroup$ 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. $\endgroup$ – Moz Jun 1 '15 at 1:14
  • $\begingroup$ 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 $\endgroup$ – alkabary Jun 1 '15 at 1:17
  • $\begingroup$ 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} + ... $ $\endgroup$ – 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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.