Question about Cantor's Diagonalization Proof

Question

My discrete class acquainted me with me Cantor's proof that the real numbers between 0 and 1 are uncountable. I understand it in broad strokes - Cantor was able to show that in a list of all real numbers between 0 and 1, if you look at the list diagonally you find real numbers that are not included on the list- but are clearly in between 0 and 1. Thus that particular set is uncountable (and I assume uncountably infinite? Is that a thing?).

My question is this - how is the list constructed? Or is that beside the point, as no list could ever entail every single real number anyway, and looking at any such list diagonally would yield new real numbers 0 < x < 1?

Answer 1

Taking any list of (the decimal representation of) real numbers, you can look at the diagonal (that is, you consider th 1st decimal from the 1st number in the list, the second decimal from the second nimber, etc.), and construct a new decimal number by taking any digit other than what you find on that diagonal. Thus, for example, if the 1st decimal of the first number is a 5, then for the first decimal of the new number pick, say, 7. If the second decimal of the second number is a 3, then for the second decimal of the new number pick, say, 8. This way, the new number (0.78...) will always differ in the n-th decimal from the n-th number on the list, i.e. the new number cannot possibly be in the list! Hence the list is not complete. Since this works for any list, there cannot be a complete listing of all real numbers between 0 and 1.

Answer 2

The list isn't constructed explicitly. What you're doing is starting out by saying "Suppose for contradiction there exists a bijection between $\mathbb{N}$ and $[0, 1]$". If this were the case, then we could write down an ordered list: let $x_1$ be the real number associated with $1$, let $x_2$ be the real number associated with $2$, etc.

From here, one arrives at the contradiction by demonstrating that this "bijection" couldn't have actually associated a natural number to every real number in $[0, 1]$. In particular, if you let $x$ be the real number such that the first digit is the opposite of the first digit of $x_1$, the second digit is the opposite of the second digit of $x_2$, and so forth, it's clear that $x$ is distinct from every real number in the list.

---

The real numbers are written in their binary expansion; by "opposite", I just mean $\Big( \text{Whatever the digit is} \Big) + 1 \pmod{2}$.