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 nice overview is

- Noson Yanofsky,
*A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points*, arXiv preprint http://arxiv.org/abs/math/0305282, May 2003.

Revised on July 1, 2017 21:21:44
by Todd Trimble
(24.146.226.222)