In 1969, William Lawvere proved that Cantor's theorem, Russell's paradox,
Gödel's incompleteness, and Turing's halting problem are all instances
of the same categorical theorem. The machine below shows how.
The structure: a matrix f, a diagonal δ, a change map α,
and a single question — can the changed diagonal be a column?
Cantor
Russell
Gödel
Turing
the matrix f : X × X → Y
f : X × X → Y
structure
· · ·
Self-reference is the diagonal map δ: x ↦ (x, x). It is the simplest
possible structure — a thing paired with itself. Yet combined with a system
expressive enough to represent its own operations, it forces either fixed points
into existence (Gödel) or proves that no such representation can be complete
(Cantor, Turing). Every limit of knowledge and every self-referential truth
is the same theorem wearing different clothes.