Matpic
mathematics, in pictures
Concept

Choice function

A function that picks one element out of each set in a given family of non-empty sets. The axiom of choice asserts that one always exists, even when the family is infinite and no rule describes which element to pick.

Named by 4 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 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 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 Six choices make one. Three tournaments on four points; each arrow points from the chosen end of a pair. Scores: 1 3 1 1; 1 2 2 1; 3 0 1 2. Census of least-score set sizes: {"1":32,"2":24,"3":8,"4":0}.

Six choices make a seventh

Bertrand Russell's millionaire needs the axiom of choice to pick one sock from each of infinitely many pairs. Does having that power for pairs give the same power for sets of four? It does, by a short trick that Tarski found: choosing from the six pairs inside a set of four makes a tournament, and all 64 tournaments single out something definite. For sets of three it fails, and whether a size follows from smaller ones is settled almost entirely by arithmetic: from pairs, 4 is the only other size that can follow.

logic · Axiom of choice

Named alongside it

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

Axiom of choiceIndependenceNon-measurable setAlgebraic numberCardinalityCountabilityDiagonal argumentEquivalence classExhaustive searchGroup actionImpossibilityInfinity

All concepts