Diagonalization arguments

Definition

A diagonalization argument is a construction, introduced by Cantor, that defines an object outside the image of a proposed parametrisation, thereby showing that the parametrisation is not surjective.

General Form

1. Let $f:X\to (X\to Y)$ and suppose, for a contradiction, that $f$ is surjective.

2. Choose a function $s:Y\to Y$ with no fixed points, meaning that $s(y)\ne y$ for every $y:Y$. Define $g:X\to Y$ by $gx=s(fxx)$.

3. For every $x:X$, $gx=s(fxx)\ne fxx$. Therefore $g\ne fx$, since the two functions differ at the argument $x$.

4. Hence $g$ is not in the image of $f$, contradicting the assumption that $f$ is surjective.

Equivalently, if surjectivity gave some $a:X$ such that $fa=g$, then evaluating both sides at $a$ would give $faa=ga=s(faa)$, so $faa$ would be a fixed point of $s$, contradicting the assumption that $s$ has no fixed points.

Related Concepts

• Cantor’s theorem is obtained by taking $Y$ to be the type of truth values and $s$ to be negation.
• Lawvere’s fixed-point theorem