1

Suppose the set is countable, and can be arranged in a sequence. Then we construct a number whose nth digit is different than the nth digit of the nth number in the sequence, which means that it is not in the sequence.

John
  • 65
  • 7
    Such a "number" is an infinite string of characters and is not a number. – David Kraemer Mar 20 '20 at 03:39
  • @DavidKraemer Then what makes the difference between a number and a string? – John Mar 20 '20 at 03:49
  • 2
    There is a bijection between $\mathbb{N}$ and the set of all finite strings of characters in the alphabet ${0,\dots, 9}$. The "number" you constructed is not in this set, so you haven't shown that $\mathbb{N}$ is uncountable. – David Kraemer Mar 20 '20 at 04:00
  • 2
    I'll give you such a sequence: $(1, 2, 3, 4,\cdots)$. Now we construct the number $2$. Its $n$th digit is different from the $n$th number in the sequence, where $n=1$. What has been proved here? – Ben W Mar 20 '20 at 04:09
  • 2
    In other words, you are not guaranteed that each $n$th number in your list has as many as $n$ digits, hence your proof fails. If you want to give each natural number an infinite preamble of zeros, and count digits from right-to-left, you will need to create a “number” that contains an infinite number of nonzero digits (which is what the first comment says) because you will need to change an infinite number of zeros to nonzeros. – Michael Mar 20 '20 at 04:40

1 Answers1

1

I guess your proof has been at least partially inspired by Cantor's diagonal argument, so I think I can see where your confusion stems from. In case you need a refresher, say we want to prove that the set of real numbers in $(0, 1)$ is uncountable. Suppose it isn't, then we can enumerate the set $\left\{s_0, s_1, s_2, ... \right\}$

Each $r \in (0, 1)$ can be represented in base 10 as $(0.a_0a_1a_2a_3...)_{10}$ where $a_i \in \left\{1,2,...,9\right\}$. We know that $r$ can be uniquely represented in base 2 as $(0.b_0b_1b_2b_3...)_2, \forall {b} \in \left\{0, 1\right\}$

From then on the proof is similar to what you proposed: We consider $s$ to be a number when the ith digit of it's binary representation is different to the ith digit of the binary representation of $s_i$. Since $s \in (0, 1)$ and $\nexists i, \ s_i = s \ $we can then conclude that $(0, 1)$ is uncountable.

Why doesn't the same argument work for $\mathbb N$? For one, we have no idea how we can even represent the members of $\mathbb N$. For example $(2)_{10} = (10)_2 = (.10000...)2^2$. But $(4)_{10} = (100)_2 = (0.100000...)2^3$, so you see that we can't uniquely define a number in the same way we did before.

I think at this point you can see why your argument fails: the nth digit isn't guaranteed to exist because you don't have a clear idea what the "nth digit" really is.

Eleftheria Chatziargyriou
  • 787
  • I think the problem with the argument is that the hypothetical “number” is not a number, since it has indefinitely many digits. We can define nth digit as the first non zero digit in base 10 counting from right to left. – John Mar 20 '20 at 08:02
  • Again, how can you guarantee that the nth digit exists? You have to set additional restrictions (e.g $s_i$ has at least $i$ digits in its decimal representation) but then there won't exist a bijective mapping between $S$ and $N$ – Eleftheria Chatziargyriou Mar 20 '20 at 08:09