Generator

A closed interval and an open one, matched point for point

A generator in the logic library, called 45 times across 9 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

chains is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

A closed interval and an open one, matched point for point. Two number lines, one closed and one open, with arrows showing the countable sequence of points that has to move.

An additive function that is nowhere a line

The points additivity pins down

A plane of pairs on a single line

Building a spanning tree by keeping every edge that closes no loop

All the forests of a small graph, and the spanning trees on top

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

person 1 is right on exactly half the assignments ×5
the number of people is a whole number between 3 and 12 ×2
a choice from each of the pairs is one of two to the power of their number ×1
a set containing a decisive set is decisive ×1
after its last difference each sequence agrees with the representative for good ×1
all scores equal is impossible at even sizes ×1
and everyone after it is right ×1
between two and five pairs, each of two named things ×1
beyond voter 5 the ballots agree ×1
different pairs of whole numbers name different numbers a + b√2 ×1
different spanning trees from the three listings ×1
each element belongs to exactly one chain ×1
each rational point sits on the line through (1, f(1)) ×1
each stage of the chain is a forest ×1
edges kept, which a spanning tree of eight points has ×1
edges of each spanning tree ×1
every moved point lands strictly inside the open interval ×1
every point the map has to reach is reached ×1
every transitive two-voter rule is of one of the four kinds ×1
exactly one of each set and its complement is decisive ×1
f(x + y) = f(x) + f(y) on a + b√2 ×1
in the cyclic profile each pair is won by two classes in three ×1
joint choices for the first five rows ×1
no two moved points land on the same place ×1
no whole number lies in every class of the chain …111 ×1
of them always transitive ×1
on every one of the 2^8 assignments, everyone after the first is right ×1
rules for two voters that decide each pair from that pair alone ×1
spanning trees of a square with one diagonal ×1
the assembled map sends no two elements to the same place ×1
the chain of …111 keeps only 4,095 below 4,096 and loses it at the next halving ×1
the chain of voter 37 closes on voter 37 alone ×1
the common part of two decisive sets is decisive ×1
the dictator is voter 1, 2 or 3 ×1
the empty set is not decisive, and the dictator alone is ×1
the function is not the line y = x ×1
the kinds number 6, 84, 2 and 2 ×1
the largest denominator is a whole number between 2 and 24 ×1
the last wrong guess is at the last place the hats differ from the representative ×1
the left-to-right map sends different elements to different places ×1
the left-to-right shift is a whole number between 1 and 4 ×1
the maximal forests are exactly the spanning trees ×1
the members of a pair are named apart exactly when an order is claimed ×1
the number of elements drawn from each side is a whole number between 5 and 14 ×1
the number of sequence terms drawn is a whole number between 4 and 12 ×1
the option is one this view reads ×1
the pairs either carry an order or they do not ×1
the plotted graph meets every cell of a six-by-six grid over the window ×1
the range of whole coefficients is a whole number between 2 and 6 ×1
the right-to-left map sends different elements to different places ×1
the right-to-left shift is a whole number between 1 and 4 ×1
the rule fits two to the power of the pairs it cannot tell apart ×1
the rule names exactly one of the rows exactly when the pairs carry an order ×1
the rule of the chosen voter is among the survivors ×1
the two maps are different, or there are no chains to see ×1
the union of the chain is a forest ×1
the value given to √2 is a number of modest size ×1
the view is one the family draws ×1
the window shows at least three chains ×1
two regular tournaments on three points and 24 on five ×1
unanimous rules for three voters that decide each pair from that pair alone ×1
under the parity strategy all are right together or all wrong together ×1
voter 37 is odd, prime and a multiple of 37 ×1
with √2 sent to √2 the function is the line y = x ×1
with three voters the unanimous transitive rules are the three dictators ×1
with two voters the unanimous transitive rules are the two dictators ×1

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Logic

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

A line with as many points as a square

Interleave the decimal places of two numbers and one number comes out; take every other place back and the two return. The square has no more points than the segment, and dimension turns out to be invisible to counting.

Logic

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

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

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

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

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

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

Two injections make a bijection

If each of two collections fits inside the other without collisions, they are the same size. That sounds obvious and is not, because neither injection needs to be onto — and the proof is a rule for deciding which of the two to follow, one chain at a time.

The whole library · What the figures prove