Matpic
mathematics, in pictures
Concept

Termination

The property of a procedure guaranteed to stop, usually because some whole-number quantity strictly decreases at every step. Proving it usually means exhibiting the decreasing quantity, which is the same move as an argument by descent.

Named by 8 essays across 6 fields — each of them below, with the objects they name alongside it.

Euclid's algorithm on a 34 by 13 rectangle. The rectangle is tiled by peeling off the largest square that fits, again and again, until nothing is left.

The oldest algorithm, drawn as a tiling

Euclid's method for finding a greatest common divisor is usually presented as a loop. It is also a way of tiling a rectangle with squares, and the tiling explains why it works.

geometry · Euclidean algorithm φ as a continued fraction. The nested fraction, one quotient per step, descending to the right.

A fraction that never closes

Euclid's algorithm throws away everything except the number of squares it peeled at each step. Those counts are a second name for the number it started from — one that terminates exactly when the ratio is a ratio.

number · Euclidean algorithm The Collatz orbit of 27. Halve an even number, triple an odd one and add one; the sequence plotted on a logarithmic scale.

The question nobody can answer

Halve it if it is even, triple it and add one if it is odd. Every number anyone has tried comes down to one. Nobody can prove they all do, and the reason is not that the problem is hard to state.

dynamics · Collatz The Goodstein sequence from 4, with the ordinal beside each term. A table of the Goodstein sequence with each term's hereditary representation and the ordinal obtained by replacing the base with omega.

A sequence that explodes and still stops

Goodstein's sequence starting at 4 climbs past any number you care to name and reaches zero after about ten to the hundred and twenty million steps. The proof that it stops is a second sequence, running alongside it, that goes down.

logic · Ordinals 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 A landscape nobody is looking at, and every move goes downhill on it. The 8 states of a congestion game with 3 participants and two resources, ordered by Rosenthal's potential, with every improving unilateral move drawn as an arrow. Every arrow points downward.

The landscape nobody is looking at

Letting participants move one at a time to whatever is currently better can cycle forever, and on a network of congestible roads it cannot. The reason is a single number attached to each state that falls by exactly what the mover saves.

applied · Equilibrium Closed after 3 uses of the universal. The Herbrand expansion of a first-order question at 5 stages, with the number of remaining models at each. It reaches nought after 3 instantiations.

The instance that has to be guessed

Every rule of a propositional tableau replaces a formula by shorter ones, which is why it stops. The rule for a universal claim does not replace it — it keeps it and adds an instance — and one word changing turns a decision procedure into a search that may run forever.

logic · Proof systems 6 vertices folded to 4, and a graph that decides. The graph built from 3 generator words, folded until no vertex has two edges of one label leaving it. Reading a word from the base vertex decides membership, and 6 words are tested.

Folding a graph until it decides

A subgroup of a free group usually arrives as a list of words, and almost nothing about it is readable from the list. Draw the words as loops, merge every pair of edges with the same label leaving one point, and what is left is a machine that decides membership by reading.

topology · Covering spaces

Named alongside it

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

Continued fractionsDecision procedureFibonacciGreatest common divisorGraphIncommensurabilityIndependenceIterationOrdinalUndecidabilityBest replyCollatz

All concepts