Quantifiers — the series

1. 

   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.

   part 1 · logic
2. 

   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.

   part 2 · logic
3. 

   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.

   part 3 · logic
4. 

   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.

   part 4 · logic
5. 

   A machine that carries one bit

   Write three numbers in base two, one above another, and read the columns from the right. Whether the bottom number is the sum of the top two can be checked with one bit of memory — the carry. That two-state machine is the whole of addition, and machines can be combined, negated and made to guess a missing number. So every sentence about whole numbers built from addition can be decided by building a machine for it, and the same machines can also handle 'x is a power of two', which addition alone cannot say.

   part 5 · logic
6. 

   There is a relation such that

   A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.

   part 6 · logic
7. 

   The sizes at which a sentence can come true

   Write a sentence about a relation and ask for which numbers of points some relation makes it true. "Every two points have exactly one common neighbour" comes true at every odd size and no even one, and every graph that satisfies it is a windmill of triangles. "Every two players are both beaten by some third" fails for every tournament of two to six players and holds from seven on. A search can settle one size at a time; only a proof settles all of them, and the two sentences need different kinds.

   part 7 · logic
8. 

   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.

   part 8 · logic

All series