Generator

j is one more than i, counting round — as a grid, with both quantifier readings

A generator in the logic library, called 54 times across 13 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.

relation-grid 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

j is one more than i, counting round — as a grid, with both quantifier readings. A grid of marks for a relation, with the row and column facts the two quantifier orders ask about.

Does this set contain that one — and the row that is missing

The diagonal, and the row built to be off the list

"There is an x" is a shadow: x² + ax + 1 = 0 has a solution exactly when |a| ≥ 2

Two quantified sentences about a quadratic, and the parabola between them

Eliminating one quantifier from ax² + bx + c = 0 needs three cases

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.

column 2 ×59
column 2 is empty exactly when 2 is prime ×59
slice a = 1: a solution exists exactly when the eliminated formula says so ×2
the formula for ∀x ∃y at n = 2 ×2
the shadow repeats every 5 ×2
∀x ∀y R(x, y) holds for R exactly when its dual fails for the complement ×1
∀x ∀y R(x, y) implies ∃x ∀y R(x, y) with nothing between ×1
∀x ∀y R(x, y) implies ∃y ∀x R(x, y) with nothing between ×1
∀x ∃y R(x, y) holds for R exactly when its dual fails for the complement ×1
∀x ∃y R(x, y) implies ∃x ∃y R(x, y) with nothing between ×1
∀y ∃x R(x, y) holds for R exactly when its dual fails for the complement ×1
∀y ∃x R(x, y) implies ∃x ∃y R(x, y) with nothing between ×1
∃x ∀y R(x, y) holds for R exactly when its dual fails for the complement ×1
∃x ∀y R(x, y) implies ∀y ∃x R(x, y) with nothing between ×1
∃x ∃y R(x, y) holds for R exactly when its dual fails for the complement ×1
∃y ∀x R(x, y) holds for R exactly when its dual fails for the complement ×1
∃y ∀x R(x, y) implies ∀x ∃y R(x, y) with nothing between ×1
7³ = 343 relations have a mark in every row ×1
a column holds a mark exactly when its values of a satisfy |a| ≥ 2 ×1
a full column forces every row to carry a mark, so one reading implies the other ×1
a machine that keeps writing and never halts exists ×1
a machine that runs six steps and leaves four ones exists ×1
a program computing how many times f occurs in it gets it right about itself ×1
a program computing its own length gets it right about itself ×1
a program computing its own text reversed, first 24 characters gets it right about itself ×1
a program computing whether its length is even gets it right about itself ×1
a row copied from the table is found in the table ×1
almost every cell is checked against the formula ×1
and 512 − 343 = 169 have a full row ×1
and for ∃x ∀y ×1
and none leaves more than four ones ×1
at 16 points almost every relation has a mark in every row ×1
carrying out the instruction prints the instruction itself ×1
each generation prints exactly the next one ×1
every halting machine is counted once ×1
every total past the largest gap can be made ×1
every x makes it positive exactly when a² − 4b < 0 ×1
M′ computes the successor exactly when M halts ×1
most halting machines never read all four entries of their table ×1
no drawn row agrees with the built row everywhere it has been checked ×1
no halting two-state machine runs more than six steps ×1
no language defines truth for its own sentences ×1
no row of the table is the Russell row ×1
one half begins 0.5000 ×1
pi minus three begins 0.14159 ×1
six machines are chosen, halting and not ×1
slice a = -1: a solution exists exactly when the eliminated formula says so ×1
some relation satisfies ∀x ∃y R(x, y) but not ∀y ∃x R(x, y) ×1
some relation satisfies ∀x ∃y R(x, y) but not ∃y ∀x R(x, y) ×1
some relation satisfies ∀y ∃x R(x, y) but not ∀x ∃y R(x, y) ×1
some relation satisfies ∃x ∀y R(x, y) but not ∀x ∃y R(x, y) ×1
some x makes it zero exactly when a² − 4b ≥ 0 ×1
the built row differs from row n in place n ×1
the chart counts table entries read or ones left ×1
the coins share no common factor, so every large enough total is reachable ×1
the count of phrases grows no faster than the alphabet's powers ×1
the diagram has six arrows ×1
the drawn range contains the largest total that cannot be made ×1
the drawn window is at least as wide as it is tall ×1
the gaps between squares keep growing ×1
the labelling is one this figure knows ×1
the largest number is a whole number between 20 and 80 ×1
the new number's i-th digit differs from phrase i's ×1
the number of columns is a whole number between 2 and 14 ×1
the number of drawn columns is a whole number between 3 and 16 ×1
the number of drawn rows is a whole number between 3 and 12 ×1
the number of levels is a whole number between 3 and 9 ×1
the number of rows is a whole number between 2 and 14 ×1
the number of sets in the table is a whole number between 3 and 10 ×1
the phrase itself has fewer than ninety characters ×1
the program's output is its own text, character for character ×1
the relation is one this figure knows how to draw ×1
the row of 'does not describe itself' differs from each adjective's row on the diagonal ×1
the Russell row disagrees with row k at column k ×1
the search agrees with 256b³ ≤ 27a⁴ ×1
the set defined by ∃y (x = y + y) is eventually periodic ×1
the set defined by ∃y (y + y + y ≤ x ≤ y + y + y + 1) is eventually periodic ×1
the set defined by ∃y ∃z (x = 3y + 5z) is eventually periodic ×1
the set defined by ∃y ∃z ∃w (x = 6y + 9z + 20w) is eventually periodic ×1
the shadow is exactly the x whose remainder a·x mod b lies within c of a multiple of b ×1
the share with every row marked eventually only rises ×1
the slope's rise is a whole number between 1 and 9 ×1
the slope's run is a whole number between 2 and 9 ×1
the squares are not eventually periodic with any small period on the range checked ×1
two coins: the largest total that cannot be made is ab − a − b ×1
two to four coin values ×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 game that decides what can be said

Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.

Logic

A list that cannot contain itself

The set of all sets that do not contain themselves is not a set. The argument is the diagonal again, applied to a table whose rows and columns are the same objects, and it destroyed the foundations of mathematics in a postcard.

Logic

A quantifier is a shadow

'There is an x such that …' asks whether a column of a grid contains a mark — which is the same as asking whether a shape casts a shadow on the axis below it. Over the real numbers every such shadow can be described without the quantifier, by polynomial inequalities: 'x² + ax + 1 = 0 has a solution' is just a² ≥ 4. Over the whole numbers the same kind of shadow can carve out the primes, and any set a computer can list.

Logic

An infinite tree has an infinite path

A tree that goes on forever, in which every node has only finitely many children, must contain a single branch that goes on forever. The proof is a rule for walking, and the rule is the whole of why finite information can decide an infinite question.

Logic

Arithmetic with addition alone

Over the real numbers, a quantifier's shadow is described by inequalities. Over the whole numbers with addition and multiplication, a shadow can be any set a computer can list. In between lies arithmetic with addition and no multiplication, and there the shadows are always the same kind of thing: a finite exception, then a pattern that repeats. The whole numbers made from coins worth 6, 9 and 20 are every number from 44 on; the squares, which need multiplication, never repeat at all.

Logic

Every row, or one column

For every person there is someone who loves them, and there is someone who loves everyone, are the same six words in a different order. Draw the relation as a grid and they become two obviously different questions — one about rows, one about columns.

Logic

No algorithm can read what a program does

Whether a program halts cannot be decided by any algorithm. Henry Rice showed in 1953 that the halting problem is not special: no algorithm can decide any property of what a program does — whether it ever prints a 7, whether it computes the successor function, whether it is a virus — except the two properties that hold of every program or of none. Every one of the 20,736 smallest Turing machines can be checked by hand; the theorem says why that stops.

Logic

Six sentences from two quantifiers

One relation, two variables, 'for every' and 'there is': there are eight ways to arrange them and six different sentences come out. Which of them imply which is a small, complete diagram, found by checking all 512 relations on three points — and the diagram crosses over in the middle, which is where every confusion about the order of quantifiers lives.

Logic

The arithmetic that loses subtraction

Adding one to an infinite collection changes nothing, and neither does doubling it, or squaring it. What that costs is the two operations that were doing the work — an equation between infinite sizes cannot be cancelled, and how many are left stops being a question.

Logic

The program that prints itself

The diagonal argument has always been used to destroy — to show that a list misses something, that a sentence cannot be proved. Run the same move the other way and it builds. Kleene's recursion theorem says every program can be given its own text to work with, and the proof is a program that prints itself, thirty-two characters long, which can be run and checked.

Logic

The row that is not on the list

Write down a list of infinite sequences, any list at all, and there is a rule that builds a sequence missing from it. The rule reads one entry from each row, and it is the single most reused argument in this field.

Logic

The sentence that says it has no proof

Number every sentence and every proof, and a formal system can talk about itself. Then the diagonal is available one more time, and what it builds is a sentence that is true exactly when it is unprovable.

Logic

The word that cannot describe itself

Some adjectives describe themselves — 'short' is short — and some do not — 'lengthy' is not lengthy. Call the second kind heterological, and ask whether 'heterological' is heterological. It is exactly when it is not. The diagonal that beat every list of numbers, every set of sets and every provability predicate has been turned on words that describe words, and it proves that no language can contain a word for its own notion of describing, naming or truth.

The whole library · What the figures prove