Description du poste
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 argumentConsider 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
mjx-math {
display: inline-block;
text-align: left;
line-height: 0;
text-indent: 0;
font-style: normal;
font-weight: normal;
font-size: 100%;
font-size-adjust: none;
letter-spacing: normal;
border-collapse: collapse;
word-wrap: normal;
word-spacing: normal;
white-space: nowrap;
direction: ltr;
padding: 1px 0;
}
mjx-container[jax="CHTML"][display="true"] {
display: block;
text-align: center;
margin: 1em 0;
}
mjx-container[jax="CHTML"][display="true"][width="full"] {
display: flex;
}
mjx-container[jax="CHTML"][display="true"] mjx-math {
padding: 0;
}
mjx-container[jax="CHTML"][justify="left"] {
text-align: left;
}
mjx-container[jax="CHTML"][justify="right"] {
text-align: right;
}
mjx-mi {
display: inline-block;
text-align: left;
}
mjx-c {
display: inline-block;
}
mjx-utext {
display: inline-block;
padding: .75em 0 .2em 0;
}
mjx-mo {
display: inline-block;
text-align: left;
}
mjx-stretchy-h {
display: inline-table;
width: 100%;
}
mjx-stretchy-h > * {
display: table-cell;
width: 0;
}
mjx-stretchy-h > * > mjx-c {
display: inline-block;
transform: scalex(1.0000001);
}
mjx-stretchy-h > * > mjx-c::before {
di