Matpic
mathematics, in pictures
Concept

Axiom of choice

The assumption that one member can be picked from every set in a family at once, with no rule given for the picking. It is independent of the other axioms of set theory, and a surprising number of ordinary theorems — that a countable union of countable sets is countable, among them — quietly need it.

Named by 11 essays across 4 fields — 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 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 The classes, a selection from them, and the translates that cannot have a length. Points of several classes of the unit interval under translation by rationals, drawn one class per row, above rows showing rational translates of a selection that never overlap.

A set that has no size at all

Slide the unit interval along itself by every rational and the points fall into classes. Choose one point from each and the resulting set has no length — not zero, not positive, none: countably many disjoint copies of it would have total length nought or infinity, and the union needs something in between.

analysis · Measure The share of a ball that is its own edge. A plot of the proportion of each ball formed by its outermost shell against the radius, one line per group — falling towards nothing for the lattice groups and holding steady for the free group.

The edge that is as big as the ball

In a lattice the boundary of a large ball is a negligible fraction of it. In a tree it is two thirds of it at every size — and that single ratio, not the group's size, is what decides whether a set can be cut into pieces and reassembled into two copies of itself.

algebra · Cayley graph An additive function that is nowhere a line. A square window with 1157 points of the graph of an additive function that sends √2 to 0, scattered across the window and meeting every part of it, beside a dashed diagonal marking the straight line y = x.

A function that adds and is nowhere a line

Every continuous function with f(x + y) = f(x) + f(y) is a straight line through the origin. Drop continuity and, given the axiom of choice, there are others — functions that add perfectly and whose graphs are scattered densely over the whole plane. A finite piece of the construction can be drawn exactly; the whole of it needs a basis of the real numbers that no one can write down.

logic · Axiom of choice Infinitely many guessers, finitely many wrong. Three rows over the first 40 places: the hats worn, the chosen representative of their class, and a row of marks showing each guess right or wrong. The 5 wrong guesses all fall within the first 14 places, up to a marked place; every later guess is right.

Infinitely many guessers, finitely many wrong

An infinite line of people each wears a black or white hat, sees every hat in front and none of their own, and must guess their own colour. With a finite line, each guesser is right half the time whatever they agree in advance. With an infinite line and the axiom of choice, they can agree a strategy under which all but finitely many are right — and nobody can carry it out.

logic · Axiom of choice An infinite graph that passes every finite test. Two columns of vertices continuing downward without end. The top left vertex joins every vertex on the right; each other left vertex joins only the one beside it.

Enough partners in every finite group

Hall's theorem says a matching exists unless some group has too few partners between them. On an infinite graph that is false: one vertex that can be paired with anybody, and every other with exactly one, passes the test on every finite group and has no matching at all. The failure needs a vertex with infinitely many choices. Forbid that, and the theorem comes back, by an argument about trees rather than about matchings.

discrete · Halls theorem The Moser spindle: 7 points, every edge one unit, and no three-colouring. the Moser spindle drawn to scale with 7 vertices and 11 unit-length edges, coloured with four colours; none of its 2187 three-colourings is proper.

How many colours the plane needs

Colour every point of the plane so that no two points exactly one unit apart share a colour. Seven colours are enough, by a tiling with hexagons, and four are necessary, by a graph of seven points. For sixty-eight years nothing better was known on either side; then in 2018 a graph of 1,581 points showed four is not enough — and the answer is still somewhere from five to seven.

discrete · Graph colouring Three sizes of infinity, and the collections that have each. ℵ₀: the fractions, the algebraic numbers, every finite text, every definition of a number; 2^ℵ₀: the real numbers, the continuous functions, the open sets, the closed sets, the Borel sets; 2^(2^ℵ₀): all functions, all sets of reals, the non-Borel sets, the measurable sets.

What counting can prove exists

There are only as many continuous functions as points of a line, only as many Borel sets, only countably many definitions — and more sets of reals than any of those. So counting proves that discontinuous functions, non-Borel sets and undefinable numbers exist without exhibiting one. It cannot prove that a set with no length exists, because the sets that have a length are exactly as numerous as all sets, and that difference turns out to be the difference between what the axioms force and what they merely allow.

logic · Cardinality A diagonal walk through countably many listed sets. A grid of six rows and seven columns, each cell numbered by Cantor's diagonal order, with the path of the first twenty-one cells drawn.

The choice inside a countable union

A countable union of countable sets is countable: list each set, then walk the grid of all their members along its diagonals. The proof is two lines and every student meets it early. It also makes infinitely many arbitrary choices at once — one listing for each set — and without the axiom of choice the theorem can fail: there are consistent worlds in which the real numbers are a countable union of countable sets, and worlds in which countably many pairs of socks cannot be counted.

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.

Non-measurable setCountabilityIndependenceCardinalityChoice functionWell-orderingZorns lemmaCompactnessDense setExhaustive searchInfinityMaximal element

All concepts