Six sentences from two quantifiers

Every row, or one column put two sentences side by side — for every $x$ there is a $y$, and there is a $y$ for every $x$ — and drew a relation as a grid so that one became a question about rows and the other a question about columns. That was one pair. With one relation $R(x, y)$ and two quantifiers there are more sentences than that, and a complete account of how they relate is small enough to draw.

Put a quantifier in front of $x$ and one in front of $y$, in either order. That gives eight arrangements. Two quantifiers of the same kind can be swapped freely — for every $x$ and every $y$ says the same as for every $y$ and every $x$ — so the eight collapse to six different sentences. Which of them imply which?

Reading the six on a grid #

Draw the relation as a grid with $x$ down the side and $y$ across the top, marking the cells where $R(x, y)$ holds. Each sentence is then a question about the marks.

For every $x$ and every $y$ asks whether every cell is marked, and there is an $x$ and a $y$ whether any cell is. Those are the two extremes, and on three points exactly one relation satisfies the first and all but one satisfy the second — 1 and 511 of 512.

The four mixed sentences are about rows and columns. There is an $x$ such that for every $y$ asks for a full row. There is a $y$ such that for every $x$ asks for a full column. For every $x$ there is a $y$ asks for a mark in every row, and for every $y$ there is an $x$ for a mark in every column. The earlier essay compared a mark in every row with a full column; here all four appear, and the diagram shows how they sit.

The arrows follow from the pictures. A full row puts a mark in every column, since the row crosses every column; so some row is full implies every column has a mark. For the same reason some column is full implies every row has a mark. Everything implies some cell is marked, and every cell is marked implies everything. That is the whole diagram: six arrows, and the middle pairs cross over — a full row is linked downward to columns, a full column to rows.

Why exactly these arrows and no others #

A diagram of implications makes two kinds of claim. Each arrow says an implication always holds, and each missing arrow says it can fail. The figure checks the first kind by running through all 512 relations on three points and confirming that no relation satisfies an upper sentence while failing a lower one joined to it. The second kind needs a witness for every missing arrow.

The first witness is the kind from the earlier essay: a relation with a mark in every row and no full column — three marks, two in one column and one in another. The second shows that a mark in every row does not force a mark in every column: all three rows point to the same column, and the other two columns are empty. The third shows that a full row does not force a mark in every row: one full row and two empty ones. The fourth is the same relation read the other way — its full row gives every column a mark, and still leaves two rows with none — which is the second witness turned on its side.

With both kinds of claim checked, the diagram is complete for relations on three points: a sentence implies another exactly when an arrow joins them. The argument for the arrows works on any domain, and the witnesses scale up by adding blank rows and columns, so the same diagram holds for relations of every size. The check on three points was a search; the conclusion for every size is the two short arguments together.

Negation turns the diagram upside down #

Denying a sentence flips each quantifier as the negation passes inward — the rule the earlier essay drew as denying that every row is marked is claiming an empty row. There is a way to see all six negations at once, through the complement: the relation with every mark erased and every blank marked.

Negating a sentence about $R$ is the same as claiming the dual sentence — every quantifier flipped — about the complement of $R$. Not every row of $R$ has a mark means some row of $R$ is empty, which means some row of the complement is full. So the six sentences pair up under duality: every cell with some cell, a full row with a mark in every row, a full column with a mark in every column. Duality turns the diagram upside down, sending the top to the bottom and each side of the middle to the other side of the crossing.

The counts record it. On three points, 343 relations have a mark in every row, and 169 have a full row; the two add to 512, because a relation fails to have a mark in every row exactly when its complement has a full row. The same holds for every dual pair — 1 and 511, 169 and 343 twice — and the figure checks it on all 512 relations.

This is the square of opposition, extended. Medieval logic arranged all, some, none and not all in a square whose diagonals are contradictories, and twenty-four out of two hundred and fifty-six found how much of Aristotle’s syllogistic rests on it. With two quantifiers instead of one the square becomes the six-sentence diagram, and the contradictories are the dual pairs.

Counting on larger domains #

The counts are not specific to three points; each has a formula.

A relation on $n$ points is a grid of $n^2$ cells, so there are $2^{n^2}$ of them. A mark in every row means each row is anything except blank, and each row has $2^n - 1$ non-blank patterns, so $(2^n - 1)^n$ relations qualify. A full row is the complement of that count by duality: $2^{n^2} - (2^n - 1)^n$. At five points there are 33,554,432 relations, of which 28,629,151 have a mark in every row and 4,925,281 have a full row.

The two middle sentences, with the same two words in the two orders, are satisfied by very different numbers of relations, and the gap grows. That is where the next figure goes.

Swap two quantifiers and a sure thing becomes a lost cause #

Choose a relation at random, each cell marked with chance one half independently. The chance of a mark in every row is the count divided by the total, and it has a simple form: each row is non-blank with chance $1 - 2^{-n}$, independently, so all $n$ rows are with chance $(1 - 2^{-n})^n$.

As $n$ grows, $(1 - 2^{-n})^n$ tends to one — the chance that some row is blank is at most $n$ times $2^{-n}$, which vanishes. So a random relation almost certainly has a mark in every row, and by duality almost certainly has no full row. Swapping the order of the two quantifiers turns a statement that is almost always true into one that is almost always false. On three points the counts, 343 against 169, look like a modest difference; on sixteen they are 99.98 per cent against 0.02 per cent.

The same thing happens for every first-order sentence about random structures, as nearly always or nearly never found: each sentence’s probability goes to zero or one. The two middle sentences here are the simplest pair on opposite sides of that divide, and they differ only in the order of two words.

The six in ordinary mathematics #

The diagram is abstract, and the sentences it arranges turn up everywhere once they are looked for. A key for every lock, $\forall$ lock $\exists$ key, is a mark in every row; a master key, $\exists$ key $\forall$ lock, is a full column; and the arrow from the second to the first is the observation that a master key is a key for every lock. The relation $y$ is a multiple of $x$, on the whole numbers, has a mark in every row — every number has a multiple — and a full row as well, the row of the number one, which divides everything. The same relation has no full column, since no number is a multiple of every number, and on the numbers from one upwards it has a mark in every column too. Four of the six sentences hold for it and two fail, and the diagram predicted which combinations were possible.

Some of the most important arguments in mathematics have exactly the middle shape. The row that is not on the list — Cantor’s diagonal argument — proves for every list there is a sequence missing from it, a mark in every row of a relation whose rows are lists, and its force is that no single sequence is missing from every list: the full column fails, and the argument depends on choosing the missing sequence after seeing the list. The inverse move, from every row has a mark to there is a function picking a mark in each row, is where the choice nobody can write down enters when the rows are infinitely many.

Where analysis keeps the diagram #

The definitions of analysis are chains of three and four quantifiers, and their difficulty is the crossing in the middle of this diagram, repeated. A sequence of functions converges pointwise when for every point $x$ and every tolerance $\varepsilon$ there is a stage $N$ after which the functions stay within $\varepsilon$ at $x$. It converges uniformly when for every $\varepsilon$ there is an $N$ that works for every $x$ at once. The two definitions differ only in whether there is an $N$ comes before or after for every $x$ — a mark in every row against a full column, with rows indexed by points.

A limit that forgets to be continuous is the witness for the missing arrow. The powers $x, x^2, x^3, \ldots$ on the interval from $0$ to $1$ converge at every point — each row has a mark — but no single stage works for every point near $1$ at once, so the full column fails, and continuity is lost in the limit because of it. The implication that does hold, from uniform to pointwise, is the arrow from the full column to every row having a mark.

That is why students of analysis are told to watch where the $N$ sits. The advice is the six-sentence diagram, applied one level up: moving an existential quantifier leftwards past a universal one strengthens a statement, sometimes decisively, and every definition in the subject that carries the word uniform is a statement in which that move has been made.

Order is information #

The reason the order matters so much is the one the earlier essay gave through games, and that a game that decides what can be said pushed to sentences of any length. In for every $x$ there is a $y$, the choice of $y$ is made after $x$ is known, so it can depend on $x$; in there is a $y$ for every $x$, $y$ is chosen first and must work for everything. A later quantifier has more information than an earlier one, and a sentence whose existential quantifier comes later asks for less.

The diagram is that principle made complete. Moving an existential quantifier later — from there is an $x$ for every $y$ to for every $y$ there is an $x$ — weakens a sentence, which is why every arrow in the middle goes from a sentence with $\exists$ first to one with $\forall$ first. And the crossing is the observation that the two variables play different roles: moving the existential quantifier later over $y$ turns a full row into a mark in every column, not every row, because the variable being chosen is still $x$.

This is also why the diagram cannot be extended by arrows between the two sides. Some row is full and some column is full are unrelated, as are every row has a mark and every column has a mark: the relation is not assumed symmetric, and rows and columns are different questions. For a symmetric relation — a friendship, a distance under a threshold — the two sides collapse into one and the six sentences become four.

What the grids cannot show #

Infinite domains. Every grid here is finite, and on a finite grid each of the six sentences is decided by looking. On an infinite domain the same six sentences are still ordered by the same diagram — the arguments for the arrows never used finiteness — but deciding which of them hold for a particular relation can be impossible. The implications survive; the looking does not.

More than two quantifiers. Three quantifiers over three variables give many more sentences, and the diagram of their implications is no longer a small drawing; with alternations of $\forall$ and $\exists$ it becomes the start of a hierarchy in which each extra alternation can express properties the previous level cannot. The six-sentence diagram is the first level of that hierarchy and nothing in it shows the levels above.

Relations that are not random. The fractions figure is about relations chosen by coin tosses. Relations that arise in mathematics — divisibility, order, adjacency in a particular graph — are highly structured, and for them either middle sentence may hold or fail regardless of size. The probability is a fact about typical relations and says nothing about any one.

Still open: whether more alternation says more #

Quantifiers over individual points, as here, are first-order. The first-order version of that climb is the arithmetical hierarchy that the instance that has to be guessed named as the measure of how undecidable a question is. Allowing quantifiers over relations themselves — there is a relation $S$ such that … — gives second-order logic, and Ronald Fagin showed in 1974 that on finite structures the properties expressible by a single there is a relation in front are exactly the problems in NP: the ones whose solutions can be checked quickly. Adding alternations of second-order for every and there is gives the levels of the polynomial hierarchy, one level per alternation, exactly as the first-order diagram gains power with each alternation of $\forall$ and $\exists$.

Whether those levels are all different is not known. If NP equals its complement — if every property with a quickly checkable proof also has a quickly checkable disproof — the hierarchy collapses to its first level, and extra alternations of second-order quantifiers add nothing. Whether that happens is a question at the heart of the P versus NP problem, and it is, in this language, a question about whether swapping for every and there is at the level of relations changes what can be said — the question this essay settled completely for two quantifiers over three points.

Six sentences, six arrows #

One relation and two quantifiers make six sentences. Every cell marked is at the top and some cell marked at the bottom; between them a full row and a full column, then a mark in every column and a mark in every row, with the arrows crossing because a full row reaches every column. Every arrow holds for every relation, and every missing arrow has a three-point relation that breaks it.

Negation is the complement read upside down, which is why the counts pair off as 343 and 169. And as the domain grows the two middle sentences, the same words in different orders, part company completely: one true of almost every relation, the other of almost none.