diagonal argument

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,

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 $T$ can self-describe $Y$-valued attributes of $T$ (a set $Y^T$) via a function $T \to Y^T$, or via a function $T \times T \to Y$. The name comes from a construction that involves the diagonal map $T \to T \times T$.

- Wikipedia,
*Diagonal argument*

Cantor used a diagonal argument to show that $|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

- F. William Lawvere, Stephen Schanuel,
*Conceptual Mathematics*, Cambridge University Press 1997.

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

- Misha Gromov.
*Ergostuctures, Ergologic and the Universal Learning Problem: Chapters 1, 2.*, p.14-18. 2013.

A nice overview is

- Noson Yanofsky,
*A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points*, 2003 (arXiv:0305282)

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

- David Michael Roberts,
*Substructural fixed-point theorems and the diagonal argument: theme and variations*(2021) (arXiv:2110.00239)

Last revised on October 6, 2021 at 17:04:44. See the history of this page for a list of all contributions to it.