Matpic
mathematics, in pictures
Concept

Undecidable sentence

A statement that a given list of axioms neither proves nor refutes. Its existence is a theorem about the axioms rather than a report of unfinished work, and it is established by exhibiting two structures obeying the axioms that disagree about the statement.

Named by 3 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 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 tower of sizes, and the gap in it. A ladder of infinite sizes, each the number of sub-collections of the one below, with the space between the first two marked as the one no proof decides.

The size that cannot be pinned down

There is no largest infinity, because no collection has as many members as it has sub-collections. What is not settled is whether anything sits between the first two — and that is not an open problem but a proved absence of an answer.

logic · Cardinality The fast-growing hierarchy at its first few ordinals. A table of the fast-growing hierarchy: one row per ordinal index, one column per argument, with the cells too large to evaluate marked as such.

An ordinal as a growth rate

Index a family of functions by the ordinals, each one iterating the last, and the index becomes a measure of how fast a function grows. The point where the index leaves what arithmetic can prove is exactly where the Goodstein sequence became unprovable.

logic · Ordinals

Named alongside it

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

ConsistencyIndependenceAlephArithmetisationAxiomatic set theoryCardinalityContinuum hypothesisDiagonal argumentDiagonalisationEpsilon noughtFast growing hierarchyFixed point

All concepts