Concept

Maximal element

An element of a partially ordered set with nothing strictly above it, though other elements may be incomparable to it. Zorn's lemma guarantees one whenever every chain has an upper bound, which is how spanning trees, bases and maximal ideals are shown to exist without being built.

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

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

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.

Axiom of choice Well-ordering Zorns lemma Choice function Greedy algorithm Independence Non-measurable set Partial order Spanning tree Transfinite recursion

All concepts