Matpic
mathematics, in pictures
Concept

Self-reference

A statement or object that describes itself, usually by way of a numbering that lets it be named inside its own system. It is what makes a sentence able to talk about its own provability, and it is the engine of the incompleteness and halting arguments alike.

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

The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

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 Does this set contain that one — and the row that is missing. A membership table with the diagonal marked, and beneath it the complement of the diagonal, which is not among the rows.

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 The diagonal, and the row built to be off the list. A table of rows of ones and zeros with the diagonal marked, and beneath it the row obtained by flipping every diagonal entry.

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 The frames on which provability makes sense, and the two that are refused. Six small frames marked by whether Löb's axiom is valid on them: transitive frames with no cycles accept it, and any frame in which a world can reach itself does not.

Necessity that means provable

Read the box as "the theory proves" and one modal logic stops being a proposal about what necessity might mean. It becomes a complete description of what a formal system can prove about its own proofs — and its frames run forward, compose, and stop.

logic · Modal logic

Named alongside it

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

Diagonal argumentConsistencyFixed pointFormal systemIncompletenessProvabilityArithmetisationBijectionCardinalityComprehensionCountabilityFrame

All concepts