Relations and multiple quantifiers

Everything quantified so far has had one place, so a formula could say what all things are like and never how any two of them stand to each other.

Relations fix that, and they bring the first genuinely hard thing in the subject with them. Once two quantifiers can appear in one formula, their order matters, and the difference between one order and the other is the difference between a triviality and a claim nobody can prove. English marks this distinction badly, which is why "everyone loves someone" is ambiguous in a way that $\forall x \exists y L x y$ is not. This lesson makes the order precise, gives the rules for pushing a negation through a string of quantifiers, and ends with the place where the distinction earns its living, the definition of a limit.

Relations

A two-place predicate takes two names: $L a b$ for " $a$ loves $b$ ", $G a b$ for " $a$ is greater than $b$ ", $R a b$ for " $a$ read $b$ ". Order inside the predicate is fixed by convention and never symmetric by default, so $L a b$ and $L b a$ are different formulas and must be, since love famously runs one way as often as two.

Three-place predicates are equally legal, $B x y z$ for " $x$ is between $y$ and $z$ ", and everything below works the same way for them. Most of the useful cases have two places.

With relations available, properties of relations become formulas rather than English descriptions, and this is where the notation starts to pay. A relation $R$ is reflexive when $\forall x R x x$ , symmetric when $\forall x \forall y (R x y \to R y x)$ , and transitive when $\forall x \forall y \forall z ((R x y \land R y z) \to R x z)$ . "Is the same age as" satisfies all three; "is taller than" is transitive and neither reflexive nor symmetric; "is a sibling of" is symmetric and, on the usual reading, not transitive, since a person is not their own sibling and the relation chains oddly through half-siblings.

Order matters

Take the domain to be the positive integers and $G x y$ to mean $x > y$ . Then

\forall x \exists y G y x

says that for every integer there is a larger one, which is true. Swap the quantifiers:

\exists y \forall x G y x

says that some single integer is larger than every integer, which is false, and not slightly false. The formulas differ only in the order of two symbols, and the reason for the difference is that in the first the choice of $y$ may depend on $x$ , while in the second $y$ is fixed before $x$ is considered and must work for all of them.

That is the whole rule and it is worth stating plainly: an inner quantifier may depend on an outer one, never the reverse. $\exists y \forall x$ is a stronger claim than $\forall x \exists y$ , and it entails it, while the converse fails.

Quantifiers of the same kind do commute. $\forall x \forall y$ and $\forall y \forall x$ say the same thing, and so do $\exists x \exists y$ and $\exists y \exists x$ . Only mixed pairs are order-sensitive, and only those need care.

Example. With a domain of three people, $a$ , $b$ and $c$ , suppose $a$ loves $b$ , $b$ loves $c$ , and $c$ loves $a$ , and nobody loves anyone else. Evaluate $\forall x \exists y L x y$ and $\exists y \forall x L x y$ .

The first says everybody loves somebody. Check each person: $a$ loves $b$ , $b$ loves $c$ , $c$ loves $a$ , so it is true. The second says somebody is loved by everybody, which requires a single person loved by all three. $b$ is loved only by $a$ , $c$ only by $b$ , $a$ only by $c$ , so it is false. One small domain separates the two formulas, and building such a domain is the whole method of the next lesson.

Now you. In the same situation, evaluate $\exists x \forall y L x y$ and say what it claims.

Answer

It claims somebody loves everybody, and it is false: each person loves exactly one other. Note it is a different claim from $\exists y \forall x L x y$ , which was about being loved by everybody. The order of the variables inside $L$ matters as much as the order of the quantifiers.

Pushing a negation through

Two laws relate the quantifiers, and they are De Morgan's laws again in a new setting.

\neg \forall x φ \equiv \exists x \neg φ \neg \exists x φ \equiv \forall x \neg φ

In words: denying that everything is $F$ is asserting that something is not $F$ , and denying that anything is $F$ is asserting that everything is not $F$ . The connection to De Morgan is exact. Over a finite domain of three objects, $\forall x F x$ is $F a \land F b \land F c$ and $\exists x F x$ is $F a \lor F b \lor F c$ , so the quantifier laws are the propositional ones with the conjunction and disjunction stretched to any length, including an infinite one.

Applied repeatedly, they push a negation all the way inside: each quantifier it passes flips, and the negation lands on the matrix at the end. So

\neg \forall x \exists y (F x \to G x y) \equiv \exists x \forall y \neg (F x \to G x y) \equiv \exists x \forall y (F x \land \neg G x y)

using the fifth lesson's rule for negating a conditional at the last step. This is the standard first move in any proof by contradiction involving quantifiers, and doing it mechanically rather than by intuition is what stops "not every" from turning into "none".

Example. Negate "every student read some book on the list", and say what a refutation must produce.

Write it as $\forall x (S x \to \exists y (B y \land R x y))$ . Pushing the negation in: $\exists x \neg (S x \to \exists y (B y \land R x y))$ , then $\exists x (S x \land \neg \exists y (B y \land R x y))$ , then

\exists x (S x \land \forall y (B y \to \neg R x y))

So a refutation must produce one student such that every book on the list went unread by that student. Not a student who missed one book: a student who read none of them. The mechanical negation says exactly what evidence would settle the question, which is usually the reason for doing it.

Now you. Negate $\exists x \forall y (F y \to G x y)$ and read the result in words.

Answer

$\forall x \exists y (F y \land \neg G x y)$ : for every $x$ there is some $F$ that $x$ does not stand in $G$ to. If $G x y$ is " $x$ has read $y$ " and $F y$ is " $y$ is on the list", the original says someone read everything on the list and the negation says everyone missed something on it.

Translating with restrictions

Most English quantification is restricted to a kind of thing, and the eighth lesson's two patterns still do the work: a universal takes a conditional, an existential takes a conjunction. With relations, those patterns nest.

"Every student read a book" is $\forall x (S x \to \exists y (B y \land R x y))$ : the outer universal takes a conditional, the inner existential a conjunction. "Some student read every book" is $\exists x (S x \land \forall y (B y \to R x y))$ , with the same two patterns in the other order. Writing them side by side is the best drill available, since each mistake produces a formula that says something clearly wrong rather than something merely odd.

English is genuinely ambiguous here and the notation is not, which cuts both ways. "Every student read a book" most naturally means each read some book or other, but it can mean there is one particular book they all read, and only the formula distinguishes them. When translating a real document, translating both readings and asking which was meant is often the most useful thing a logician does.

The definition of a limit

The most consequential quantifier order in mathematics is in the definition of continuity, and it is worth seeing because it shows the difference doing real work rather than making a point about love or integers.

A function $f$ is continuous on a set when

\forall ε > 0 \forall x \exists δ > 0 \forall y (| x - y | < δ \to | f (x) - f (y) | < ε)

and uniformly continuous when the $\exists δ$ moves in front of the $\forall x$ :

\forall ε > 0 \exists δ > 0 \forall x \forall y (| x - y | < δ \to | f (x) - f (y) | < ε)

Everything else is identical. In the first, $δ$ may depend on where you are; in the second, one $δ$ must work everywhere at once. By the rule above, uniform continuity implies continuity and not conversely.

The gap is real and numbers show it. Take $f (x) = x^{2}$ on the whole real line with $ε = 1$ . Near $x = 1$ a step of $δ = 0.001$ is ample: ${1.001}^{2} - 1^{2} = 0.002001$ , comfortably under 1. Near $x = 1000$ the same step fails, since ${1000.001}^{2} - 1000^{2} = 2.000001$ , which is over 1. To keep the output change under 1 near $x = 1000$ the step must be under about $1 / 2000$ , and as $x$ grows the required $δ$ shrinks without limit. So no single $δ$ serves every $x$ : the function is continuous everywhere and not uniformly continuous. Squaring is a familiar operation, and the difference between two orderings of two quantifiers is what separates two of its properties.

Example. State, with quantifiers, what it takes for $f$ to fail to be uniformly continuous.

Negate the definition and push the negation in. $\forall ε$ becomes $\exists ε$ , $\exists δ$ becomes $\forall δ$ , the two $\forall$ s become $\exists$ s, and the conditional becomes a conjunction:

\exists ε > 0 \forall δ > 0 \exists x \exists y (| x - y | < δ \land | f (x) - f (y) | \geq ε)

For $f (x) = x^{2}$ this is what the numbers above exhibit: with $ε = 1$ , whatever $δ$ is offered, a pair of points that close together can be found far enough out to move the output by at least 1.

Now you. "Every lock in the building has a key that opens it" and "there is a key that opens every lock in the building". Write both, and say which entails the other.

Answer

With $L x$ for locks, $K y$ for keys and $O y x$ for " $y$ opens $x$ ", the first is $\forall x (L x \to \exists y (K y \land O y x))$ and the second is $\exists y (K y \land \forall x (L x \to O y x))$ . The second entails the first, since a master key opens each lock in turn. The first does not entail the second, as a building with different keys for each door shows.

What is still missing

The language is now expressive enough for the working mathematics of the rest of this course and for most careful English. What has not been said is what any of it means precisely. "True in the domain of positive integers" was used freely above, and "false" was justified by pointing at three people and a loving relation, which is persuasive rather than exact.

The gap matters because the truth table method has quietly died. A formula with quantifiers has no finite list of valuations to run through: the domain may be infinite, and there are infinitely many domains. So the third lesson's decision procedure is gone and something must replace it, both for saying what truth in a structure is and for the practical business of refuting an invalid argument. That is the next lesson.