nLab diagonal argument

Contents

Contents

Idea

Diagonal arguments are typically arguments that place limitations on the extent that a set TT can “talk about” attributes of elements of TT. 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,

but also the traditional construction of a

due to Haskell Curry.

As explained by Yanofsky (after Lawvere), each of these diagonal arguments can be viewed as instances of the

which places limitations on how a set TT can self-describe YY-valued attributes of TT (a set Y TY^T) via a function TY TT \to Y^T, or via a function T×TYT \times T \to Y. The name comes from a construction that involves the diagonal map TT×TT \to T \times T.

References

Cantor used a diagonal argument to show that |X||2 X||X|\ncong|2^X| for the first time here:

  • Georg Cantor, Über eine elementare Frage der Mannigfaltigskeitslehre , Jahresbericht DMV 1 (1891) pp.75-78. (gdz)

But he was anticipated by

  • Paul Du Bois-Reymond, Über asymptotische Werthe, infinitäre Approximationen und infinitäre Auflösung von Gleichungen , Math. Ann. 8 (1874) pp.363-414. (gdz)

Lawvere’s seminal ideas occurred in

  • F. William Lawvere, Diagonal arguments and cartesian closed categories, pp.134-145 in Category Theory, Homology Theory and their Applications II (Battelle Institute Conference, Seattle, Wash., 1968, Vol. Two), Springer LNM 92 Berlin 1969. (Reprinted with an author’s comment as TAC reprint 15 (2006): link)

For a leisurely account see the discussion in

A discussion of logic and rigor using Lawvere’s ideas about the diagonal argument and Godel theorem

A nice overview is

The necessary assumptions for Lawvere’s account are reduced in various ways in

Last revised on August 10, 2023 at 11:56:16. See the history of this page for a list of all contributions to it.