Examples of diagonal argument in Mathematics?

Question

I have seen several examples of diagonal arguments. One of them is, of course, Cantor's proof that $\mathbb R$ is not countable. A diagonal argument can also be used to show that every bounded sequence in $\ell^\infty$ has a pointwise convergent subsequence.

Here is a third example, where we are going to prove the following theorem:

Let $X$ be a metric space. $A\subseteq X$. If $\forall \epsilon>0$, $\exists x_1,x_2,\ldots, x_n\in A, A=\bigcup_{k=1}^n B(x_k,\epsilon)$ (i.e. totally bounded), then all sequences in $A$ has a Cauchy subsequence.

Proof. Let $(x_n)\subseteq A$ be a sequence. Let $F_k$ be a finite $(1/k)$-net of $A$. Define the sequences of positive integers $n_{r,s}$ as follows:

1. $(x_{n_{1,s}})_{s=1}^\infty$ is the part of $(x_n)$ that lies in $B(p_1,1)$, where $p_1\in F_1$. Such $p_1$ exists because $(x_n)$ is infinite but $F_1$ is finite.
2. $(x_{n_{r+1,s}})_{s=1}^\infty$ is the part of $(x_{n_{r,s}})_{s=1}^\infty$ that lies in $B(p_{r+1},1/(r+1))$.

Now, let $n_k=n_{k,k}$. Then $(x_{n_k})$ is a Cauchy subsequence.

Are there any other interesting examples of "diagonal" proof in mathematics? From the three examples above, it appears that diagonal arguments help us repeat a process infinitely many times. (For example, the construction of $n_{r,s}$ cannot be repeated to obtain something like $n_{\infty, s}$, since the interesction of a descending chain of infinite subsets of $\mathbb N$ might be finite -- but a diagonal argument help us get what we want.) What is the essence of "diagonal"?

Answer 1

One of my favorite diagonal arguments that appears is is as follows: if $\mathcal{L}(X,Y)$ is the set of all bounded linear operators from a normed vector space $X$ to a Banach space $Y$, then the set $\mathcal{K}(X,Y)$, the set of all compact operators, is a closed subspace.

Handwaving the proof, we begin with a sequence of compact operators $K_n$ that we assume converges to some operator $T$, and a bounded sequence $x_n$ in $X$. Since $K_1$ is compact, we find a subsequence for $x_n$, calling it $x^{(1)}_n$, such that $K_1x^{(1)}_n$ converges. For $K_2$, there must be a subsequence of $x^{(1)}_n$, calling it $x^{(2)}_n$, such that $K_2x^{(2)}_n$ converges. We can continue the process such that $x^{(k)}_n$ is a subsequence of $x^{(k-1)}_n$ and the sequence $K_jx^{(k)}_n$ converges for all $1\leq j\leq k$.

The diagonal part comes into play when we consider the sequence $x^{(n)}_n$. The new sequence $Tx^{(n)}_n$ can be shown to be Cauchy in $Y$, so it must converge, meaning that $T$ is indeed a compact operator.

Answer 2

Jair Taylor mentioned the halting problem in the comments. Here is another example from recursion theory.

Loosely speaking, a (total) recursive function is a function $\mathbb N\to \mathbb N$ that can be computed in principle by a computer program and a primitive recursive function is one that can be done without any unbounded searches (i.e. in a C program with for loops but no while loops).

Theorem There is a recursive function that is not primitive recursive.

Proof Sketch. We can write an algorithm that recognizes when a given computer program is a primitive recursive function, so we can write a computer program that enumerates the primitive recursive functions $f_1,f_2,\ldots$ by enumerating all of the possible strings of text and outputting the ones deemed to be code for a primitive recursive function. Now define the algorithm as follows. On input $n,$ the algorithm enumerates up to function $f_n,$ computes $f_n(n)$ and then outputs $f_n(n)+1.$ This is a recursive function that differs from every primitive recursive function.

Why won't this same process allow us to make a recursive function that isn't recursive and cause a contradiction? Because we can't write an algorithm that will detect if a given computer program is recursive. When there are only for loops, we know the program will terminate, so any syntactically correct code will compute a value for any input. However if there are while loops, it could run forever on some inputs, so we can't say that a given piece of code is a total function. In fact, this amounts to a proof that the halting problem is not computable.

(It's obligatory to mention that there also explicit, not-too-artificial examples of recursive functions that aren't primitive recursive.)

Answer 3

A collection $\mathcal C$ of infinite subsets of $\mathbb N$ is called almost-disjoint if for any distinct $x,y\in \mathcal C,$ $x\cap y$ is finite. An almost disjoint set is called maximal if it is not strictly contained in any other (in other words if any set outside it has infinite intersection with one of its sets).

Theorem There is no countable maximal almost-disjoint set.

Proof. Let $\mathcal C=\{C_i:i\in \mathbb N\}.$ Choose $a_0\in C_0,$ then choose $a_1\in C_1\setminus C_0,$ and in general, recursively choose $a_n\in C_n\setminus \bigcup_{m<n}C_m.$ This is always possible since $C_n\setminus \bigcup_{m<n}C_m=C_n\setminus \bigcup_{m<n}(C_m\cap C_n)$ and each $C_m\cap C_n$ is finite since $\mathcal C$ is almost-disjoint. Then $A=\{a_i:i\in\mathbb N\}$ has $C_n\cap A$ finite for all $n$, since $a_k\notin C_n$ for all $k>n.$

---

Here is an alteration that will hopefully show why people sometimes refer to the above as a diagonal argument. Instead of subsets (functions $\mathbb N\to 2$) do functions $\mathbb N\to \mathbb N.$ Then say a collection of functions is almost disjoint if for any distinct $f,g$ in the collection, $\{n: f(n)=g(n)\}$ is finite. Now, enumerate any countable collection $f_1,f_2,\ldots$ Define $$g(n) = \max\{f_i(n)+1: i<n\}.$$ Then for any $i,$ $g(n)>f_i(n)$ for all $n>i,$ so $g$ and $f_i$ are almost disjoint.

Answer 4

Some simple examples.

1. If $\{f_n:n\in \Bbb N\}$ is a set of functions from $\Bbb N \to \Bbb R$ then there exists $g:\Bbb N\to \Bbb R$ such that $\{m: g(m)\le f_n(m)\}$ is finite for every $n\in \Bbb N.$ Proof: Let $g(n)=1+\max \{f_j(n):j\le n\}.$ Then $\forall m\ge n\,(\,g(m)> f_n(m)\,).$

2. The box-product topology on $S=\Bbb R^{\Bbb N}$ is not first-countable. Proof: Let $x=(x_n)_{n\in \Bbb N}\in S$ and let $\{U_m:m\in \Bbb N\}$ be a countably family of nbhds of $x.$ For each $m$ take $f_m:\Bbb N \to \Bbb R^+$ such that $U_m\supset \prod_{n\in \Bbb N}(x_n-f_m(n),x+f_m(n)).\quad$ Let $g(m)=f_m(m)/3$ for $m\in \Bbb N.$

   Then $V=\prod_{m\in \Bbb N}(x_m-g(m),x+g(m))$ is a nbhd of $x$ but $U_n\not \subset V$ for any $n,$ because $(x_m+2f_n(m)/3)_{m\in \Bbb N}\in U_n\setminus V.$

3. If $F=\{F_n:n\in \Bbb Z\}$ is a countable family of open subsets of $\Bbb R$ with $F_n\supset \Bbb Z$ for all $n$ then $\Bbb R$ has an open subset $A$ such that $A\supset \Bbb Z$ but $F_n\not \subset A$ for all $n$. Proof: For $n\in \Bbb Z$ let $0<x_n\le 1/2$ such that $(n-x_n,n+x_n)\subset F_n.\quad$ Let $A=\cup_{n\in \Bbb Z}(n-x_n/2,n+x_n/2)$.

   Then for $n\in \Bbb Z$ we have $A\cap (n-1/2,n+1/2)=(n-x_n/2,n+x_n/2)$ but $F_n\cap (n-1/2,n+1/2)\supset (n-x_n,n+x_n)$ so $F_n\not \subset A.$

Example 3. is covered in R. Engelking's General Topology for an example of a quotient map $q:X \to X_{/E}$ with closed $E$-equivalence classes, where $X$ is first-countable but $X_{/E}$ is not. I.e. $X=\Bbb R$ and $xEy\iff (x=y\lor \{x,y\} \subset \Bbb Z).$

Answer 5

Let me give something I consider a near-miss non-example: priority arguments (see e.g. here).

To my mind a fundamental feature of diagonalization is that we explicitly meet each requirement. For example, in the classical argument, we have a sequence $\mathcal{S}=(S_i)_{i\in\mathbb{N}}$ of sets of naturals and we need to build an $A\subseteq\mathbb{N}$ such that $A\not\in\mathcal{S}$. The standard way is to set $$A=\{i: i\not\in S_i\},$$ but we could also just as well use $$A=\{2i+17: 2i+17\not\in S_i\},$$ or so forth. The key feature though is that we have a list $(R_i)_{i\in\omega}$ of requirement, namely $$R_i: \quad A\not=S_i,$$ and we know exactly how each requirement is satisfied.

Of course, plenty of arguments we confidently refer to as "diagonalization" aren't written to be this explicit. But most of them can be easily modified to provide such extra information, and certainly there are none that I'm aware that actively rely on the lack of such information. This, however, is exactly what a priority argument does: the "true path" associated to a priority argument, which records how the various requirements are satisfied, is in general vastly more complicated (in a precise sense) than the actual object(s) we're building.

• Interestingly the complexity of the true path often yields unasked-for additional properties of the set(s) being built - e.g. the Friedberg-Muchnik theorem merely asks for Turing-incomparable c.e. sets, but the finite-injury argument makes them low and join to ${\bf 0'}$ - which are interesting properties which a priori seem difficult to ensure. There are a number of questions around this issue I think are natural but haven't been explored; I mention this only to drive home (hopefully!) the point that the complexity of the manner in which we satisfy requirements is something of interest.

Of course, not everyone (indeed, maybe almost nobody) will share my assessment. But I do think it reveals an interesting feature of diagonalization.

Answer 6

Diagonal arguments are typically arguments that place limitations on the extent that a set T can “talk about” attributes of elements of T. They are related to the paradoxes of old (e.g., the liar paradox, Russell's paradox) that typically involve some degree of self-reference.

Traditional “diagonal arguments” enter the proofs of, for example,

Cantor's theorem

Gödel‘s incompleteness theorem

halting theorem

https://ncatlab.org/nlab/show/diagonal+argument

The similarity between the famous arguments of Cantor, Russell, Gödel and Tarski is well-known, and suggests that these arguments should all be special cases of a single theorem about a suitable kind of abstract structure. We offer here a fixed-point theorem in cartesian closed categories which seems to play this role. [...]

Lawvere, F. W. (1969). Diagonal arguments and cartesian closed categories. In Category theory, homology theory and their applications II (pp. 134-145). Springer, Berlin, Heidelberg.

Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

[...]

On a philosophical level, this generalized Cantor’s theorem says that as long as the truth-values or properties of $ T $ are non-trivial, there is no way that a set $ T $ of things can “talk about” or “describe” their own truthfulness or their own properties. In other words, there must be a limitation in the way that $ T $ deals with its own properties. The Liar Paradox is the three thousand year-old primary example that shows that natural languages should not talk about their own truthfulness. Russell’s paradox shows that naive set theory is inherently flawed because sets can talk about their own properties (membership). Gödel’s incompleteness results shows that arithmetic can not talk completely about its own provability. Turing’s Halting problem shows that computers can not completely deal with the property of whether a computer will halt or go into an infinite loop. All these different examples are really saying the same thing: there will be trouble when things deal with their own properties. It is with this in mind that we try to make a single formalism that describes all these diverse – yet similar – ideas.

Yanofsky, N. S. (2003). A universal approach to self-referential paradoxes, incompleteness and fixed points. Bulletin of Symbolic Logic, 9(3), 362-386.