Back to Ishan Levy’s website

Diagonal Argument

2 Interpretations

If we work in the category of sets, this becomes the familiar Cantor’s Theorem. However we can also interpret this proof to give Godel’s Incompleteness Theorem and the solution to the Halting Problem.

For the Halting Problem, \(X\) is a countable set of inputs, and a program is a map \(X \to \Omega \) as it takes an input and either halts or doesn’t. We label our countable number of programs so that \(X \cong \Omega ^X\) Now if there were a solution to the halting problem, the evaluation map \(X \times X \to \Omega \) is a program. But then our proof yields another program that halts iff it doesn’t halt.

For Gödel’s incompleteness theorem, \(X\) is the natural numbers \(\NN \), and a map \(\NN \to \Omega \) is a statement that depends on a natural number parameter (the value in \(\Omega \) is whether that statement is true or false). Then we have assumed that our formal system is strong enough such that we can have a Gödel numbering: i.e our statements can be indexed over the natural numbers in such a way that the formal system can answer the family of statements "Is this statement true on this natural number?" Then the diagonal construction leads to the statement "is this statement false", which is neither true nor false.