Quantifiers

Nearly every theorem is a claim about all numbers of some kind or about at least one of them, and the connectives of the previous lesson have no way to say either.

That lesson fixed the meaning of "not", "and", "or", "implies" and "if and only if", and closed on a sentence they could not build: "for every integer $n$ , if $n$ is divisible by $4$ , then $n$ is even". This lesson adds "for every" and "there exists", gives the rules for negating them, and shows that their order changes what is said. It ends with the definition of a limit, negated symbol by symbol.

Open sentences and the two quantifiers

A sentence such as " $x^{2} > 4$ " has no truth value until $x$ is fixed: it is true when $x = 3$ and false when $x = 1$ . Such an open sentence is written $P (x)$ , so that $P (3)$ is a true statement and $P (1)$ a false one.

Two quantifiers turn an open sentence into a statement. The universal quantifier $\forall x$ , read "for all $x$ ", makes $\forall x P (x)$ , which is true when $P (x)$ is true for every value of $x$ . The existential quantifier $\exists x$ , read "there exists an $x$ ", makes $\exists x P (x)$ , which is true when $P (x)$ is true for at least one value.

"At least one" is the exact reading of $\exists$ . It does not mean exactly one, and it does not hint that not all: "there is an even integer" is true, though there are infinitely many. As with inclusive "or", the weaker reading is the default.

Often the quantifier is not written at all. "If $n$ is divisible by $4$ , then $n$ is even" is printed as a theorem with no "for all", and every reader supplies "for every integer $n$ ". A proof has to put it back, because "every $n$ " and "some $n$ " call for different proofs.

The domain is part of the claim

"For all $x$ " always means all $x$ in some collection, the domain, and changing the domain changes the claim. Take " $x^{2} \geq x$ for every $x$ ". Over the integers it is true: if $x \leq 0$ then $x^{2} \geq 0 \geq x$ , and if $x \geq 1$ then multiplying $x \geq 1$ by the positive number $x$ gives $x^{2} \geq x$ . Over the reals it is false, since $x = \frac{1}{2}$ gives $x^{2} = \frac{1}{4}$ . Likewise "there is an $x$ with $x^{2} = 2$ " is true over the reals and false over the rationals, which a later lesson proves.

So mathematicians write the domain into the quantifier: $\forall x \in ℤ$ , $\exists x \in ℝ$ , with $ℕ$ , $ℤ$ , $ℚ$ and $ℝ$ for the natural numbers, integers, rationals and reals. This course takes $ℕ$ to start at $1$ .

A claim often concerns part of a domain, as in "every prime greater than $2$ is odd", and the two quantifiers restrict in different ways. A restricted universal uses a conditional: $\forall n (n is prime \land n > 2 \Rightarrow n is odd)$ . A value that fails the restriction makes the conditional vacuously true, so it is let through. A restricted existential uses a conjunction: "some prime is even" is $\exists n (n is prime \land n is even)$ , which needs one value with both properties.

Swapping the connectives destroys the claim. $\forall n (n is prime \land n is odd)$ says every integer is an odd prime, which $4$ refutes. $\exists n (n is prime \Rightarrow n is even)$ is made true by $n = 4$ , which is not prime, so it says nothing about primes at all. The shorthands $\forall x > 0$ and $\exists n \geq N$ abbreviate exactly these patterns: $\forall x > 0 P (x)$ means $\forall x (x > 0 \Rightarrow P (x))$ , and $\exists n \geq N P (n)$ means $\exists n (n \geq N \land P (n))$ .

Negating a quantified statement

To deny that every $x$ has a property is to say that some $x$ lacks it, and to deny that some $x$ has it is to say that every $x$ lacks it:

\neg \forall x P (x) \equiv \exists x \neg P (x) \neg \exists x P (x) \equiv \forall x \neg P (x)

These are the previous lesson's De Morgan laws, stretched. Over a domain of three objects $a$ , $b$ and $c$ , $\forall x P (x)$ is $P (a) \land P (b) \land P (c)$ , and De Morgan turns its negation into $\neg P (a) \lor \neg P (b) \lor \neg P (c)$ , which is $\exists x \neg P (x)$ . The quantifier laws say the same holds when the domain is infinite.

Negation is therefore mechanical: move the $\neg$ inwards, and every quantifier it passes changes kind. When it reaches the open sentence at the end, the previous lesson's rules apply: "and" becomes "or", and $\neg (P \Rightarrow Q)$ becomes $P \land \neg Q$ . The domain and the restrictions do not change. The negation of $\forall x > 0 P (x)$ is $\exists x \neg (x > 0 \Rightarrow P (x))$ , which is $\exists x (x > 0 \land \neg P (x))$ , or $\exists x > 0 \neg P (x)$ : the " $> 0$ " rides along untouched.

The mistake this prevents is turning "not every" into "none". "Not every prime is odd" is true, because of $2$ . "No prime is odd" is false, because of $3$ .

Example. Symbolise "every positive real number $x$ satisfies $x^{2} \geq x$ ", negate it, and decide which of the two is true.

Over the reals, the claim is $\forall x (x > 0 \Rightarrow x^{2} \geq x)$ . Passing the negation through the quantifier gives $\exists x \neg (x > 0 \Rightarrow x^{2} \geq x)$ , and negating the conditional gives $\exists x (x > 0 \land x^{2} < x)$ : some positive real number has a square smaller than itself. The negation is true, because $x = \frac{1}{2}$ is positive and $x^{2} = \frac{1}{4} < \frac{1}{2}$ . So the original claim is false.

Now you. Symbolise "every real number $x$ with $x^{2} = x$ satisfies $x = 1$ ", negate it, and decide which of the two is true.

Answer

The claim is $\forall x (x^{2} = x \Rightarrow x = 1)$ . Its negation is $\exists x \neg (x^{2} = x \Rightarrow x = 1)$ , which is $\exists x (x^{2} = x \land x \neq 1)$ : some real number equals its own square without being $1$ . The negation is true, because $0^{2} = 0$ and $0 \neq 1$ . So the original claim is false.

Counterexamples

The negation of $\forall x P (x)$ is $\exists x \neg P (x)$ , and an existential statement is proved by producing one value. So one value at which $P$ fails, a counterexample, refutes a universal claim however many other values it holds for. For a restricted claim $\forall x (P (x) \Rightarrow Q (x))$ , a counterexample must satisfy the hypothesis and fail the conclusion; a value that fails the hypothesis refutes nothing.

In 1640 Pierre de Fermat wrote that every number $2^{2^{n}} + 1$ is prime. The cases $n = 0$ to $4$ give $3$ , $5$ , $17$ , $257$ and $65537$ , all prime. In 1732 Euler showed that the next, $2^{32} + 1 = 4294967297$ , equals $641 \times 6700417$ , and that one line settles the matter.

The other direction has no such shortcut. No number of examples proves a universal claim over an infinite domain: $n^{2} + n + 41$ is prime for every $n$ from $0$ to $39$ and equals $41^{2}$ at $n = 40$ , and Pólya's conjecture about prime factors held for every number below 906,150,257. Existential claims are the mirror image. One example proves "some prime is one more than a square", namely $5 = 2^{2} + 1$ , while refuting an existential claim needs a proof about every value. Knowing which kind of statement is in hand says in advance whether an example will be enough.

The order of quantifiers

An open sentence in two variables, like " $y > x$ ", needs two quantifiers. Two of the same kind can come in either order; when they are mixed, the order is part of the meaning.

Over the integers, "every integer has a larger one" is $\forall x \exists y (y > x)$ , and "some integer is larger than all of them" is $\exists y \forall x (y > x)$ . The first is true and the second false, and the symbols differ only in order. In $\forall x \exists y$ the $y$ is found after $x$ is known, so it may depend on $x$ : for $7$ take $8$ , for $1000$ take $1001$ . In $\exists y \forall x$ the $y$ is fixed first and must then work against every $x$ at once.

It helps to read quantifiers as a game: a sceptic picks the values under $\forall$ and a prover those under $\exists$ , in the order written, and the statement is true when the prover can always win. Committing early is a handicap, so $\exists y \forall x P (x, y)$ implies $\forall x \exists y P (x, y)$ : one $y$ that beats every $x$ answers each $x$ in turn. The integers show the converse fails. Negation still works one quantifier at a time, so $\neg \forall x \exists y P (x, y)$ is $\exists x \forall y \neg P (x, y)$ .

Example. Over the integers, decide whether $\forall x \exists y (y > x)$ and $\exists y \forall x (y > x)$ are true, and prove each answer.

The first is true. Let $x$ be any integer and take $y = x + 1$ . Then $y$ is an integer and $y - x = 1 > 0$ , so $y > x$ . As $x$ was arbitrary, the statement holds.

The second is false, so prove its negation, $\forall y \exists x (y \leq x)$ . Let $y$ be any integer and take $x = y$ . Then $y \leq x$ . As $y$ was arbitrary, no integer is larger than all integers, not even than itself.

Now you. Over the integers, decide whether $\forall x \exists y (x + y = 0)$ and $\exists y \forall x (x + y = 0)$ are true, and prove each answer. Does the first stay true over $ℕ$ ?

Answer

The first is true: for any integer $x$ , the integer $y = - x$ gives $x + y = 0$ .

The second is false. Suppose some integer $y$ had $x + y = 0$ for every integer $x$ . Then $x = 0$ gives $y = 0$ and $x = 1$ gives $y = - 1$ , a contradiction.

Over $ℕ$ the first is false: $x = 1$ would need $y = - 1$ , which is not a natural number.

The limit of a sequence

Quantifier order is the whole content of the definition calculus rests on. A sequence $a_{1}, a_{2}, a_{3}, \dots$ converges to a real number $L$ when

\forall ε > 0 \exists N \in ℕ \forall n \geq N (| a_{n} - L | < ε)

As a game: the sceptic names a tolerance $ε$ , the prover answers with a position $N$ , the sceptic picks any term from position $N$ on, and the prover wins if it lies within $ε$ of $L$ . Since $\exists N$ follows $\forall ε$ , the position may depend on the tolerance, and it must. For $a_{n} = \frac{1}{n}$ and $L = 0$ , the tolerance $0.01$ is met from $N = 101$ , since $\frac{1}{101} < 0.01$ while $\frac{1}{100}$ is not, and $0.001$ needs $N = 1001$ . Swap the first two quantifiers and one $N$ must serve every $ε$ at once. Then each $| a_{n} - L |$ with $n \geq N$ is below every positive number, so it is $0$ , and the sequence equals $L$ exactly from $N$ on. Under that reading $\frac{1}{n}$ would not converge to $0$ .

To negate the definition, move the $\neg$ in one symbol at a time. $\forall ε > 0$ becomes $\exists ε > 0$ , keeping its restriction. $\exists N \in ℕ$ becomes $\forall N \in ℕ$ . $\forall n \geq N$ becomes $\exists n \geq N$ . Finally $| a_{n} - L | < ε$ becomes $| a_{n} - L | \geq ε$ . So $a_{n}$ does not converge to $L$ when

\exists ε > 0 \forall N \in ℕ \exists n \geq N (| a_{n} - L | \geq ε)

that is, some tolerance is broken by a term beyond every starting point. A disproof must therefore supply one $ε$ , and a way to answer every $N$ with a suitable $n$ .

Example. Prove that $a_{n} = (- 1)^{n}$ does not converge to $1$ .

Prove the negation with $L = 1$ . Take $ε = 1$ . Let $N$ be any natural number and take $n = 2 N + 1$ . Then $n \geq N$ and $n$ is odd, so $a_{n} = - 1$ and $| a_{n} - 1 | = 2 \geq 1$ . Since $N$ was arbitrary, the negation holds.

Now you. Prove that $a_{n} = \frac{1}{n}$ does not converge to $1$ .

Answer

Prove the negation with $L = 1$ . Take $ε = \frac{1}{2}$ . Let $N$ be any natural number and take $n = N + 1$ . Then $n \geq N$ and $n \geq 2$ , so $| a_{n} - 1 | = 1 - \frac{1}{n} \geq 1 - \frac{1}{2} = \frac{1}{2}$ . Since $N$ was arbitrary, the negation holds.

From what a claim says to how to prove it

Any statement in this course can now be written with quantifiers over a stated domain, and its negation computed rather than guessed.

The proofs above had shapes dictated by their quantifiers: a "for all" was met by letting the variable be arbitrary, a "there exists" by naming a value. But each step was a line of arithmetic. Knowing exactly what "the square of every odd integer is one more than a multiple of $8$ " claims does not say how to establish it. The next lesson turns those shapes into a method, the direct proof.