Matpic
mathematics, in pictures
Concept

Infinity

The size of a collection that never runs out, such as the whole numbers or the points of a line. Arguments that work step by step for finite collections can fail for infinite ones, and repairing them usually needs a finiteness condition somewhere else.

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

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 A decisive set halved for ever. voter 37: residues 1, 1, 5, 5, 5, 37; …111: residues 1, 3, 7, 15, 31, 63.

An electorate too large for a dictator

Arrow proved that a voting rule with his four properties must have a dictator, and his proof uses the finiteness of the electorate exactly once. With infinitely many voters the dictator can vanish: the sets of voters who get their way form an ultrafilter, and every free ultrafilter is a rule with all four properties and nobody in charge. The catch is that no such rule can be written down. Its existence is a fragment of the axiom of choice.

logic · Axiom of choice One quantifier blind to two others. The prefix ∀x∃y∀u∃v drawn in a line, where v depends on x, y and u, and in branching form, where y depends only on x and v only on u; six points paired off by a fixed-point-free involution and five points, where no such pairing exists.

Four quantifiers, one of them blind

In 'for every x there is a y, and for every u there is a v', the last choice may depend on everything before it. Leon Henkin asked in 1961 what happens if v may depend on u alone. Using nothing but the equals sign, four such quantifiers then say that a set has an even number of points, or that it is infinite — things no ordinary sentence can say — and the game behind the sentence can end with neither player able to win.

logic · Quantifiers

Named alongside it

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

Axiom of choiceExhaustive searchArrow's theoremBipartite graphChoice functionCompactnessDecisive setDictatorshipEhrenfeucht fraisse gameEquivalence classIndependenceIndependence of irrelevant alternatives

All concepts