Written as a MATS extension fellow, mentored by Richard Ngo.
Diagonalisation is a bundle of techniques used to generate paradoxes of self-reference in math. These techniques show up under different names across set theory, logic, and computer science. This post takes a stab at abstracting all the diagonalisation arguments into an informal common denominator.[1][2]
The argument
Consider a language L, which we discuss using a meta-language ML. You can think of ML as an exhaustive collection of pointers that refer to sentences of the language L. Diagonalisation negates the question:
can we have L refer to ML exhaustively, the way that ML refers to L? i.e can we have L work as a meta-language for its own meta-language?
Assume that you could have L refer to ML in this way. Pick a sentence of ML that refers to exactly the sentences in L that aren't referred to by any element of ML that they refer to.
Since L can also refer to ML, pick a sentence of L that refers to . Does refer to ?
If refers to , then since refers to and considering the definition of we must have that doesn't refer to .
Suppose doesn't refer to , then since refers to and considering the definition of we must have that does refer to .
Intuition
Your language breaks on statements that require it to simultaneously serve the role of the base language and the role of the meta-language of its meta-language.
Diagonalisation does have a category-theoretic formalisation (of course). I don't understand it well enough to draw a connection to the vibe explanation I provide here.
Projecting this vibe-explanation onto particular examples of diagonalisation involves formalising the terms "language," "exhaustive collection of pointers," and "refer." This is left as an exercise to the reader™.
L only fails if ML needs to be able to make arbitrary statements about properties of L (e.g., as discussed by Tarski), otherwise Gödel numbering suffices.
Written as a MATS extension fellow, mentored by Richard Ngo.
Diagonalisation is a bundle of techniques used to generate paradoxes of self-reference in math. These techniques show up under different names across set theory, logic, and computer science. This post takes a stab at abstracting all the diagonalisation arguments into an informal common denominator.[1][2]
The argument
Consider a language L, which we discuss using a meta-language ML. You can think of ML as an exhaustive collection of pointers that refer to sentences of the language L. Diagonalisation negates the question:
Assume that you could have L refer to ML in this way. Pick a sentence
Since L can also refer to ML, pick a sentence
Intuition
Your language breaks on statements that require it to simultaneously serve the role of the base language and the role of the meta-language of its meta-language.
Diagonalisation does have a category-theoretic formalisation (of course). I don't understand it well enough to draw a connection to the vibe explanation I provide here.
Projecting this vibe-explanation onto particular examples of diagonalisation involves formalising the terms "language," "exhaustive collection of pointers," and "refer." This is left as an exercise to the reader™.