I've been trying to find everything I can to understand Cantors Diagonalization to prove that real numbers are infinitely uncountable and I simply cannot understand why it makes sense.
My first question is why we take the numbers in the diagonal and construct a new real number, why not take any random row and construct a new real number?
And how does constructing that new number incremented by some random amount prove its not in our list?
On
The point is to construct a new real number that we know is not on the list. If you take one of the reals on the list and change every digit, you might wind up with a real that is somewhere else on the list. To avoid that, we want to make sure there is (at least one) digit in our new real that disagrees with every real on the list. The diagonal is a nice pattern that assures that. When we do the diagonal, we know our new real disagrees with the first number on the list in the first place, the second number in the list in the second place, and so on. The pattern makes sure it disagrees with every number on the list in at least one place, so we know it is not on the list already.
On
We take the diagonal because it's a choice that's extremely easy to describe and has the properties that make the diagonal argument easy and successful:
Why is the sequence of digits so constructed not in the list? For every integer $n$, the number we construct can't be on the list because its $n$-th digit is different from the from the $n$-th digit of the $n$-th entry in the list.
More formulaically...
Our list of real numbers is thus a two-dimensional grid of digits. Let $f(n)$ denote the $n$-th row of the grid, and $f(n,m)$ denote the $m$-th digit of $f(n)$.
Let $g$ be the new number we define, and let $g(n)$ be its $n$-th digit.
We define $g(n) = 9 - f(n,n)$.
Theorem: for every integer $n$, $g \neq f(n)$.
Proof: Suppose that $g = f(n)$. Then $g(n) = f(n,n)$. But that would imply $9 - f(n,n) = f(n,n)$ which is impossible. Thus our supposition is false: $g \neq f(n)$.
Remark: Technically, the argument I give above only constructs a numeral that isn't on a given list. Talking about numbers introduces an annoying detail because of things like $0.999\ldots = 1.000\ldots$. This doesn't introduce any real problems; it's just annoying to deal with.
On
The choice of the diagonal is fairly natural... it is advantageous in that we need the constructed number to differ from all the numbers in the list in at least one (decimal ) place... if we went straight down (or straight across ) we'd be wasting our time; but by going along the diagonal (the next simplest thing to do) we accomplish the task at hand (changing at least one entry) in a most economical fashion. ..
You could do it in a different order, but it would take some extra effort to keep track of what you're doing. .. in a sense. .. when going along the diagonal does the trick without having to do any extra thinking about where you're going next. .. with no wasted steps...
As they say, "don't fix it if it ain't broken"
The goal is to construct a number that isn't on the list (and thereby derive a contradiction). If we just pick some random row on our list, then that number is definitely on our list, because... well, it was plucked straight from our list.
The elegance of the diagonal argument is that the thing we create is definitely different from every single row on our list. Here's how we check:
And so on. Thus, our number isn't on our list, even though our list was allegedly complete.