Matpic
mathematics, in pictures
Concept

Diagonal argument

The construction that reads one entry from each row of a table and changes it, producing something that cannot be any row.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

Also named here as self reference — the same set of essays touches all of them, so they are one junction rather than several.

x10110101000x21101010000x30011111000x41010100000x50001001000x60111110000x71110011001x8010100000110011001neweach row is a number between 0 and 1, written in binary; the marked squares are thediagonalthe row underneath is the number that differs from the nth in its nth binary digit — so thelist is missing a number, and it was an arbitrary list

The row that is not on the list

Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.

logic · diagonalisation S1S2S3S4S5S6S7S1S2S3S4S5S6S7Rthe sets that do not contain themselvesrow i, column j is marked when set i contains set j — the diagonal asks whether a set contains itselfthe row beneath is the complement of the diagonal, and it is not one of the rows above it

A list that cannot contain itself

The set of all sets that do not contain themselves is not a set. The argument is the diagonal again, applied to a table whose rows and columns are the same objects, and it destroyed the foundations of mathematics in a postcard.

logic · diagonalisation φ10110101000φ21101010000φ30011111000φ41010100000φ50001001000φ60111110000φ71110011001φ8010100000110011001neweach row is a sentence, and whether it says yes to each numbered question; the markedsquares are the diagonalthe row underneath is the sentence that answers each question the opposite way to theone asked about it — so the answers cannot all be given by a sentence on the list

The sentence that says it has no proof

Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.

logic · diagonalisation

Named alongside it

The objects these essays reach for when they reach for this one.

Self referenceConsistencyArithmetisationBijectionCardinalityComprehensionCountabilityFixed pointFormal systemIncompletenessMembershipPower set

All concepts