Every row, or one column

Two sentences, the same six words, one difference in order.

For every $i$ there is a $j$ with $R(i, j)$.

There is a $j$ such that for every $i$, $R(i, j)$.

The first is weaker than the second and it is not always obvious which one a piece of English is saying. Drawn as a picture the difference stops being subtle.

Every row has a mark. No column is full. So the first sentence is true here and the second is false, and the whole of the difference between them is visible in one glance: the marks are there, but they are in different places for different rows.

Why the order changes the meaning #

Read the two sentences again against the grid.

The first says: whatever row is picked out, that row has a mark somewhere. The $j$ is allowed to depend on the $i$ — a different column for each row is fine.

The second says: there is a column that can be named first, and it then works for every row. The $j$ has to be chosen before the $i$ is known, so one column has to cover all of them.

That is the entire content of quantifier order, and it is a statement about dependence. ∀i ∃j allows the witness to depend on the thing it witnesses for; ∃j ∀i demands a witness that works uniformly. The second implies the first — a full column certainly puts a mark in every row — and the first does not imply the second, which the figure above is a counterexample to.

The implication one way and not the other is asserted rather than assumed in every figure here: if a column is full then every row is marked, and the generator checks that consequence on the grid it drew.

A relation where both hold #

Here the marks are all in one column. Every row has a mark — trivially, because they are all in the same place — and there is one $j$ that works for every $i$.

Comparing the two figures is the point of having two. The first grid’s marks and the second grid’s marks are the same number of marks, six each. What differs is their arrangement, and the two sentences are exactly two different questions about arrangement.

Where this is not a curiosity #

The distinction earns its place because a great deal of mathematics is precisely the difference between the two orders, and in several famous cases the whole subject is the gap.

Continuity and uniform continuity. A function is continuous when for every point $x$ and every tolerance $ε$ there is a $δ$ that works at $x$. It is uniformly continuous when for every $ε$ there is a $δ$ that works at every $x$ at once. The definitions differ only in where the “$\forall x$” is placed, and $x \mapsto 1/x$ on the open interval $(0, 1)$ is the standard example of the first without the second: near zero the function is steeper and steeper, so the $δ$ that works at $x$ shrinks with $x$ and no single $δ$ serves everywhere.

Convergence and uniform convergence. A sequence of functions converges pointwise when for each $x$ the numbers converge; uniformly when one rate serves for every $x$. The difference decides whether limits and integrals can be exchanged, and the nineteenth century spent decades finding out that they cannot in general — Cauchy published a false theorem asserting that a convergent series of continuous functions has a continuous sum, and the repair was to notice which quantifier came first.

Approximation, in this collection. How close a fraction can get is a statement of the first kind: for every real number and every bound there is a fraction inside it. The strong statements in that subject are of the second kind, where a single constant is claimed to work for every number at once, and the difference between them is where the interesting theorems live.

In each case somebody once wrote a sentence in English, meant one order, and was read as the other. The picture is a small guard against that.

Two more relations, and what they show #

Divisibility is worth a second look because it is asymmetric, and the asymmetry is exactly what the two readings pick apart. Every number divides something (its own multiples), so the weak statement holds by the diagonal alone. Nothing in range is divisible by everything, so the strong one fails — and it fails for a reason that would stop failing if the grid were extended: $840$ is divisible by all of $1$ through $8$, so on a wide enough grid a full column appears.

That is a small warning about reading a window. The grid shows a relation restricted to eight by eight, and “no column is full” is a true statement about what is drawn and a false one about the relation it is a window on. Every figure in this essay states what it measured, and what it measured is the drawing.

Coprimality is a good relation to end the survey on because the marks have no tidy shape at all, and neither “every row is marked” nor “some column is full” is a property anyone could see by staring at the definition. Both are read off the grid, and the second is true for a reason — the number one — that is invisible in the drawing until it is looked for.

Four relations, four different arrangements, and the same two questions asked of each. That is what a picture buys here: not an answer, but a form in which the question is always the same question.

The witness as a function #

There is a way of reading ∀i ∃j that makes the dependence explicit, and it is worth having because it turns the weaker statement into an object rather than a claim.

Look again at the marked squares in the first figure. Each row has at least one, and the generator picks out the first — the dot in each row is the chosen witness for that row. Take those choices together and they are a function: a rule sending each $i$ to a $j$ that works for it.

So ∀i ∃j R(i,j) is equivalent to there exists a function $f$ with $R(i, f(i))$ for every $i$, and ∃j ∀i R(i,j) is the special case where that function is constant. Written that way the whole distinction is: is the witnessing function constant or not?

That reformulation is called Skolemisation and it is a genuine technique rather than a rephrasing — it is how a formula with nested quantifiers is put into the shape an automated prover can work on, by replacing each existential with a function of the universals outside it.

It also has a sting that this collection should not skip. For a finite grid, the function is built by scanning each row and taking the first mark, which is a procedure. For infinitely many rows there is no scanning, and asserting that the choices can be made all at once is the axiom of choice. Most working mathematics uses it without comment; it is independent of the other axioms, which is a fact of exactly the kind two models can establish; and its role here is quiet and structural — turning for each row there is one into there is a function is precisely where it is needed.

Negation, which reverses everything #

The other half of quantifier discipline is what happens under negation, and the grid makes it a single observation.

To deny every row has a mark is to claim some row has no mark at all. To deny some column is full is to claim every column has a gap. In symbols:

$$¬∀i ∃j \, R(i,j) \quad\text{is}\quad ∃i ∀j \, ¬R(i,j)$$

Negation moves inwards and flips each quantifier as it passes. That is a rule people memorise and get wrong, and the reason it is easy to get wrong is that in English the negation lands in a different place: “not everyone has a friend” and “someone has no friends” are the same claim and do not sound like it.

On the grid it is not a rule at all. Denying that every row is marked is saying there is an empty row, and whether there is an empty row is visible. The formal rule is a description of what looking at the picture does.

There is a consequence worth extracting. A universal claim is refuted by one counterexample — one empty row — and an existential claim is refuted only by checking everything. That asymmetry is why counterexamples are the cheap currency of mathematics and existence proofs are the expensive one, and it is entirely a fact about which quantifier is on the outside.

Where the finite picture stops #

The grids here are finite, and the honesty of the essay depends on saying what that costs.

For a finite relation both questions are decidable by looking: scan the rows, scan the columns, done. That is why the figures can assert their answers. For an infinite relation neither is decidable in general, and the two orders come apart in a way the picture cannot show.

The clearest instance is a grid with infinitely many rows and columns where every row has a mark, every column has a gap, and the marks march away down the diagonal. Every finite window of it looks like the first figure on this page. There is no finite window that distinguishes it from a relation where some column does eventually fill up, because “eventually” is not in any window.

So the finite drawing teaches the distinction and cannot decide the infinite case. That is the standing limitation of every picture in this field, and the response to it is the same each time: draw a finite piece, check the mechanism on it, and be explicit that the mechanism is what generalises rather than the picture. Here the mechanism is the witness is allowed to depend on what it witnesses for, and that sentence survives at any size.

The move that made this expressible at all #

There is a historical point that belongs here rather than anywhere else in this field.

The syllogism cannot say any of this. Its four sentence forms talk about classes — all $S$ are $P$ — and there is no way to write a relation between two things, let alone to nest two quantifiers over it. Every student has a supervisor is not expressible, because the class of supervisors and the class of students are related in a way the language has no words for.

Frege’s Begriffsschrift of 1879 is where that changed, and the change is precisely the ability to write $∀x ∃y \, R(x, y)$ with the scopes marked. It is a notational invention rather than a discovery about the world, and it is one of the largest in the subject: two thousand years of a system that could not express the difference this essay is about, followed by a notation in which the difference is the position of two symbols.

What it cost is decidability. The syllogism’s 256 forms can be settled by exhaustion because the space of situations is finite; the moment relations and nested quantifiers are available, the space of situations is not, and no exhaustion is possible. That trade — expressive power for decidability — is the one the whole field is organised around, and it is worth noticing that it was made almost immediately and has never been taken back.

The definition this is usually met in #

It is worth writing one real definition out with the quantifiers labelled, because the epsilon-delta definition of a limit is where most readers first meet three nested quantifiers and where most of the confusion about them originates.

The function $f$ is continuous at $a$ means: for every $ε > 0$ there is a $δ > 0$ such that for every $x$ within $δ$ of $a$, $f(x)$ is within $ε$ of $f(a)$.

Three quantifiers, in the order $∀ε \, ∃δ \, ∀x$. Read as a grid whose rows are tolerances and whose columns are distances: every row must carry a mark, and the mark for a given $ε$ is any $δ$ that works.

Now move the $∀a$ that has been left implicit. Put it outside everything — for every $a$, for every $ε$, there is a $δ$ — and the $δ$ may depend on both $a$ and $ε$: that is ordinary continuity. Put it after the $∃δ$ — for every $ε$ there is a $δ$ such that for every $a$ and every $x$ — and one $δ$ must serve every point at once: that is uniform continuity.

The two definitions differ by moving one quantifier past one other, and the difference is the whole of a chapter in analysis. $1/x$ on $(0,1)$ satisfies the first and not the second; on $[1, 2]$ it satisfies both; and the theorem that a continuous function on a closed bounded interval is automatically uniformly continuous is precisely a theorem that says in this situation, the swap is allowed.

Whenever a theorem says two quantifiers may be exchanged, it is worth reading as what it is: a statement that a witness which could have depended on something turns out not to need to. Those theorems are never trivial and they always have a hypothesis doing the work.

The habit #

The practical residue of this essay is a reading habit rather than a theorem.

When a mathematical sentence has two quantifiers in it, find out which is on the outside, and then ask what would have to be exhibited to prove it. ∀i ∃j needs a rule that produces a $j$ from an $i$; ∃j ∀i needs a single $j$ and then an argument covering all $i$. Those are different pieces of work, and a proof of one presented as a proof of the other is a specific and common error rather than a vague one.

The grid is the fastest way to hold the distinction, and it keeps working long after the relation stops being drawable, because what it teaches is not a picture but a question: does the second thing get to know the first?