The diagonal argument is a general proof strategy that is used in many proofs in mathematics. I want to consider the following two examples:
- There is no enumeration of the real numbers. Because if there were such an enumeration of all real numbers, one could define a real number $x$ not contained in the list by considering, for each $n$, the $n$th decimal place of the $n$th real number, say $a_n^n$, and set $x=0.b_1b_2\dots$, where $b_n$ is chosen in such a way that $b_n\not=a_n^n$ for each $n$. Of course, whenever I use the variable $n$, $n$ should range over all natural numbers.
- There is a computable function that is not primitive recursive. Since the set of all primitive recursive functions is countable, one can enumerate all the primitive recursive functions: $f_1, f_2, \dots$ Now $n\mapsto f_n(n)+1$ is not primitive recursive.
In these two arguments one uses the diagonal method to construct an element not contained in a list. In both proofs, this list is countable, thus the families $(a_n^n)_n$, $(b_n)_n$, and $(f_n)_n$ are indexed by the set $\mathbb N$.
Question: Are there similar usages of diagonal arguments, where the index set is uncountable?
Note: I know Cantor's theorem, which is true for all sets (no matter what cardinality). So this would be an abstract answer to my question. But I would be interested if there are other examples, maybe some more concrete ones.
Yes. Let $\kappa$ be a regular cardinal, for example $\omega_1$. We say that $C\subseteq\kappa$ is unbounded if $\sup C=\kappa$, and we say that it is closed if $\sup(C\cap\beta)=\beta\to\beta\in C$. If $C$ is closed and unbounded we call it a club. In some sense the notion of a club is a good approximation of "almost everywhere" as far as the order topology is concerned.
Now you might ask, how many clubs are there? Well, there are certainly $\kappa$ of them, since $\kappa\setminus\alpha$ is a club. And it is not hard to check that the intersection of any two clubs is a club, and in fact if $\gamma<\kappa$ and $\{C_\alpha\mid\alpha<\gamma\}$ is a collection of clubs, then $\bigcap C_\alpha$ is a club.
So we have at least $\kappa^{<\kappa}$ clubs. But is that everything? Well, clearly the intersection of $\kappa$ different clubs can be empty, just look at $\bigcap_{\alpha<\kappa}\kappa\setminus\alpha$.
But we can define the diagonal intersection of $\{C_\alpha\mid\alpha<\kappa\}$ which is denoted by $\triangle_{\alpha<\kappa}C_\alpha$ and defined by $$\beta\in\triangle_{\alpha<\kappa}C_\alpha\iff\beta\in\bigcap_{\alpha<\beta}C_\alpha.$$
This is a form of diagonalization, and it turns out that the diagonal intersection of clubs is a club. Therefore there are $\kappa^\kappa$ different clubs.