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?

  • $\begingroup$ The question is about defining the sequence on the diagonal. If we say the sum of the natural numbers doesn't exist, why can we say the number on the diagonal exists? I would guess it's because we've arbitrarily narrowed the definition of a summation so that we always produce a number? Would the summation of the natural numbers translated to applications of ZFC axioms be well defined? 111... $\endgroup$
    – MVTC
    Aug 23 '20 at 4:10

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.


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.