Why doesn't diagonalization require taking a limit?

Question

When we quantify infinite sums, we do so by taking the limit as $i$ goes to infinity. For example, we look at $\lim_{n\rightarrow \infty}\sum_{n\in \mathbb{N}}n$, and then we say that this diverges and does not have a sum.

When we do diagonalization, we iterate over an infinite list while indexing each list item by a natural number, and then talk about the result. Why can we do this instead of having to invoke limits?

In the same way, would it be fine to assign a value to $\sum_{n\in \mathbb{N}}n$ with the value being an infinite sequence?

Answer 1

Some diagonalization arguments might require limits to be able to nail down all the details (e.g. if they involve an infinite sum, or an infinite decimal expansion, which is formally just an infinite convergent sum of a certain kind), but they do not require limits in general.

The most popular diagonalization argument proves that $|\mathbb{N}| \neq |\mathbb{R}|$. Depending on how you've seen this, resolving some of the details might end up requiring limits because of the nature of $\mathbb{R}$. So let's look at a decidely discrete example of diagonalization instead:

Theorem $|\mathbb{N}| \neq |\{0, 1\}^\mathbb{N}|$

We take $\{0, 1\}^\mathbb{N}$ to be the set of all infinite sequences of ones and zeros (you can also think of it as the function space $\mathbb{N} \to \{0,1\}$). So for example, we could have the sequences $a = (0, 1, 0, 1, 0, 1, 0, 1, \cdots)$ such that $a_{2i} = 0$ and $a_{2i+1} = 1$.

Since this is a diagonalization argument, we proceed via contradiction. We first assume that it's possible to enumerate all elements of $\{0, 1\}^\mathbb N$ via some function $f$, so that for all $i \geq 0$, $f(i)$ is an infinite sequence of 0s and 1s.

We will construct an explicit infinite sequence which doesn't show up in the image of $f$, which proves that no such $f$ can enumerate all infinite sequences of 0s and 1s, which means that $|\mathbb N| \neq |\{0,1\}^\mathbb N|$ as desired:

$$ a_i \triangleq 1 - f(i)_i $$

And now we can immediately see by construction that for each $i \geq 0$, $a \neq f(i)$, since if $a = f(i)$ then for all $k$, $a_k = f(i)_k$, but in particular for $k = i$ we have $a_i = 1 - f(i)_i \neq f(i)_i$. $\blacksquare$

---

This construction clearly doesn't involve any limits - all of the objects are discrete. The equivalent complete proof specifically for $\mathbb R$ might involve a limit or an (easy and automatic) proof of convergence for the construction of the real number $a$, but there's nothing particularly insightful about that step.