Matpic
mathematics, in pictures
Concept

Well-ordering

An order on a set in which every non-empty subset has a least element. The whole numbers carry one and the real numbers carry none that anybody has described, and the assertion that every set has one is equivalent to the axiom of choice.

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

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 Every way of choosing one thing from each of 4 pairs. A table with one row per choice function on a small family of pairs, each row giving what it takes from each pair, with the row a stated rule names picked out.

The choice nobody can write down

Given finitely many pairs, picking one thing from each is a finite list of decisions and needs no justification. Given infinitely many, the list cannot be finished — and whether one exists anyway is an axiom, independent of everything else, whose consequences include a theorem most people refuse to believe.

logic · Axiom of choice Ordinal sums and products, in normal form. A table of ordinal expressions with their Cantor normal forms and whether the two sides of each pair are equal, above two tick lines drawing one such pair.

One step in front of infinitely many

Put one step before an infinite run of them and nothing has changed; put it after and something has. Ordinal addition records that difference, which is why it is not commutative — and why it keeps information that counting throws away.

logic · Ordinals The numbers to 18 in hereditary base 2, and their ordinals. A table of small whole numbers written in hereditary base notation beside the ordinal obtained by replacing the base with omega.

Every ordinal in base omega

Every ordinal below a certain point is a descending sum of powers of ω, in exactly one way. That notation makes comparison mechanical, it is what hereditary base notation becomes when the base is replaced, and it stops at the first ordinal it cannot name.

logic · Ordinals Limit ordinals and the sequences that approach them. Several ordinals with the first terms of their fundamental sequences, and the successors marked as having a predecessor instead.

Reached from below, or not at all

Every limit ordinal anybody meets is the end of an increasing sequence — ω, ω·2, ω^ω, all of them approached one step at a time. The first uncountable ordinal is not, and the reason it is not constrains the size of the continuum.

logic · Ordinals Building a spanning tree by keeping every edge that closes no loop. Four stages of a greedy pass over the fourteen edges of an eight-point graph, ending with a spanning tree of 7 edges.

A spanning tree for every graph

Every connected graph has a spanning tree: a set of its edges that joins every point and closes no loop. For a finite graph the proof is a greedy pass over the edges. For an infinite graph the greedy pass has to keep going past the end of every list, and the statement turns out to be exactly as strong as the axiom of choice — Zorn's lemma supplies the tree, and the existence of spanning trees in every graph gives back the whole axiom.

logic · Axiom of choice

Named alongside it

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

Order typeOrdinalAxiom of choiceCardinalityCountabilityHereditary baseIndependenceLimit ordinalMaximal elementZorns lemmaAssociativityChoice function

All concepts