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 the two missing words, "for every" and "there exists". It fixes what they mean, shows that the collection a variable ranges over is part of every claim, gives mechanical rules for negating any quantified statement, and shows that the order of two quantifiers can be the whole difference between a true statement and a false one. It then covers "there is exactly one", the translation of mathematical English into symbols and back, and the quantifiers hidden in ordinary sentences. It ends where the subject earns its keep: the definitions of a limit and of continuity, each a string of three alternating quantifiers, read, used and 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, also called a predicate, is written $P(x)$, so that $P(3)$ is a true statement and $P(1)$ a false one. Open sentences can have several variables. "$x<y$" is a predicate $P(x,y)$ in two variables, true for the pair $(2,5)$ and false for $(5,2)$, and "$a$ divides $b$" is another. The set of values that make $P(x)$ true is its truth set: over the real numbers the truth set of $x^2>4$ is everything below $-2$ together with everything above $2$.

Two quantifiers turn an open sentence into a statement.

Definition. The universal quantifier $\forall$ is read "for all" or "for every". The statement $\forall xP(x)$ is true when $P(x)$ is true for every value of $x$ in the domain, and false when at least one value makes $P(x)$ false.

Definition. The existential quantifier $\exists$ is read "there exists" or "for some". The statement $\exists xP(x)$ is true when $P(x)$ is true for at least one value of $x$ in the domain, and false when every value makes $P(x)$ false.

"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, and "some real number satisfies $x^2\ge 0$" is true, though every real number does. As with inclusive "or", the weaker reading is the default, and a stronger one is always spelt out.

When the domain is finite the quantifiers are nothing new. Over the domain $\{1,2,3\}$, $\forall xP(x)$ says the same as $P(1)\wedge P(2)\wedge P(3)$, and $\exists xP(x)$ says the same as $P(1)\vee P(2)\vee P(3)$. So "for all" is a long "and", and "there exists" is a long "or". What the quantifiers add is the ability to take that "and" or "or" over infinitely many cases, which no finite formula built from connectives can do.

A variable governed by a quantifier is bound, and one that is not is free. In $\forall x(x^2\ge 0)$ the $x$ is bound, and the statement is about no particular $x$: renaming it gives $\forall t(t^2\ge 0)$, the same statement. The bound variable is a placeholder, like $k$ in $\sum _{k=1}^{10}{k}^2$ or $t$ in ${\int }_0^{1}tdt$. A sentence with a free variable is still an open sentence. Over the integers, $\exists k(n=2k)$ has $k$ bound and $n$ free, so it is not a statement but a predicate of $n$: it says "$n$ is even". That is how definitions are made. Each definition in this course is an open sentence in the thing being defined, with the other variables bound inside it.

A quantifier governs the formula written directly after it, and brackets say how far that reaches. In $\forall x(P(x)\wedge Q(x))$ the quantifier covers both parts. In $\forall xP(x)\wedge Q(x)$ it covers only $P(x)$, and the $x$ in $Q(x)$ is free, so the whole is an open sentence. When in doubt, bracket.

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\ge x$ for every $x$". Over the integers it is true: if $x\le 0$ then $x^2\ge 0\ge x$, and if $x\ge 1$ then multiplying $x\ge 1$ by the positive number $x$ gives $x^2\ge 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: the lesson on contrapositive and contradiction proves the second, and the lesson on the real numbers the first. And "there is an $x$ with $2x=1$" is false over the integers and true over the rationals.

So mathematicians write the domain into the quantifier: $\forall x\in \mathbb{Z}$, $\exists x\in ℝ$, with $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$ and $ℝ$ for the natural numbers, integers, rationals and reals. This course takes $\mathbb{N}$ to start at $1$, so $\mathbb{N}=\{1,2,3,\dots \}$. When the domain is clear from the context, as in "over the integers" at the head of an argument, it is left out of each quantifier.

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\text{is prime}\wedge n>2\Rightarrow n\text{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\text{is prime}\wedge n\text{is even})$, which needs one value with both properties.

Swapping the connectives destroys the claim. $\forall n(n\text{is prime}\wedge n\text{is odd})$ says every integer is an odd prime, which $4$ refutes. $\exists n(n\text{is prime}\Rightarrow n\text{is even})$ is made true by $n=4$, which is not prime, so it says nothing about primes at all. The rule to remember: $\forall$ goes with $\Rightarrow$, and $\exists$ goes with $\wedge$.

The shorthands $\forall x>0$, $\exists n\ge N$ and $\forall x\in A$ abbreviate exactly these patterns. They are called restricted or bounded quantifiers:

With them, definitions become short formulas. Over the integers, "$a$ divides $b$" is $\exists k(b=ak)$, and "$n$ is a perfect square" is $\exists m(n=m^2)$. "$n$ is prime" says $n>1$ and the only positive divisors of $n$ are $1$ and $n$:

A positive divisor of a positive integer $n$ is at most $n$, so the quantifier could equally be written $\forall d\le n$, with $d$ running over $1,2,\dots ,n$. A quantifier bounded by a number in this way ranges over finitely many values, and a statement all of whose quantifiers are bounded like this can be settled by checking. "$1009$ is prime" is a finite claim, and a computer confirms it by trying every $d$ up to $1009$ (or, with a little more thought, up to $31$, since a factorisation $n=de$ with $1<d\le e$ has $d^2\le 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.

Theorem (negation of quantifiers). For every predicate $P(x)$ over any domain,

Proof. For the first, $\neg \forall xP(x)$ is true exactly when $\forall xP(x)$ is false. By the definition of $\forall$, that happens exactly when at least one value of $x$ makes $P(x)$ false, that is, makes $\neg P(x)$ true, and by the definition of $\exists$ that is exactly when $\exists x\neg P(x)$ is true. For the second, $\neg \exists xP(x)$ is true exactly when no value of $x$ makes $P(x)$ true, that is, when every value makes $\neg P(x)$ true, which is the meaning of $\forall x\neg P(x)$. $\square$

These are the previous lesson's De Morgan laws, stretched. Over a domain of three objects $a$, $b$ and $c$, $\forall xP(x)$ is $P(a)\wedge P(b)\wedge P(c)$, and De Morgan turns its negation into $\neg P(a)\vee \neg P(b)\vee \neg P(c)$, which is $\exists x\neg P(x)$. The theorem says the same holds when the domain is infinite, where there is no finite formula to apply De Morgan to.

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 take over: $\neg (P\wedge Q)$ is $\neg P\vee \neg Q$, $\neg (P\vee Q)$ is $\neg P\wedge \neg Q$, and $\neg (P\Rightarrow Q)$ is $P\wedge \neg Q$. A negated inequality flips completely: $\neg (x<y)$ is $x\ge y$, not $x>y$.

The domain and the restrictions do not change. The negation of $\forall x>0P(x)$ is $\exists x\neg (x>0\Rightarrow P(x))$, which is $\exists x(x>0\wedge \neg P(x))$, or $\exists x>0\neg P(x)$: the "$>0$" rides along untouched. In the other direction, $\neg \exists n\ge NP(n)$ is $\forall n\neg (n\ge N\wedge P(n))$, which is $\forall n(n\ge N\Rightarrow \neg P(n))$, or $\forall n\ge N\neg P(n)$. The restriction says which objects the claim is about, and denying the claim does not change the subject. So the negation of "every positive real has a square root" is "some positive real has no square root", never "some non-positive real ...".

With several quantifiers the rule is applied once per quantifier, from the outside in:

The pattern of the result is easy to remember: every quantifier flips, their order stays, and the $\neg$ lands on the innermost sentence.

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$. The negation of a universal claim is an existential one, which asks for a single exception, not a universal claim of the opposite.

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

Over the reals, the claim is $\forall x(x>0\Rightarrow x^2\ge x)$. Passing the negation through the quantifier gives $\exists x\neg (x>0\Rightarrow x^2\ge x)$, and negating the conditional gives $\exists x(x>0\wedge 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.

The work was in two steps: first get the symbols right, then negate by rule, and only then think about the mathematics. The rule is reliable, and intuition about what "the opposite" of a sentence should be is not.

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

What each kind of claim needs

The shape of a statement says in advance what a proof of it must do and what a disproof must do. For a single quantifier there are four cases.

The table is two facts and their negations. An existential statement is proved by producing a value, called a witness, and checking it. So one value at which $P$ fails, a counterexample, refutes a universal claim however many other values it holds for, because the negation of $\forall xP(x)$ is the existential statement $\exists x\neg P(x)$. 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. Nobody has since found another prime of this form.

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. A universal claim needs an argument about an arbitrary element: name an $x$, assume nothing about it beyond membership of the domain (and the hypothesis, if the claim is a conditional), and derive $P(x)$. Because nothing was assumed about the named $x$, the argument works for each one. The next lesson turns this into a method and explains exactly why it is valid.

Existential claims are the mirror image. One example proves "some prime is one more than a square", namely $5=2^2+1$, and one example proves "some rational $x$ has $x^2-3x+2<0$", namely $x=\frac{3}{2}$, which gives $\frac{9}{4}-\frac{9}{2}+2=-\frac{1}{4}$. Refuting an existential claim needs a proof about every value: "no integer $x$ satisfies $2x=1$" is $\forall x(2x\ne 1)$, and it is proved by noting that for an integer $x$ the number $2x$ is even while $1$ is odd, and no integer is both (a fact the next lesson proves).

When the statement has two quantifiers the table is applied twice, from the outside in. A proof of $\forall x\exists yP(x,y)$ lets $x$ be arbitrary and then exhibits a $y$ that works for that $x$, so its $y$ is typically a formula in $x$. A proof of $\exists y\forall xP(x,y)$ exhibits one $y$ first and then shows it works for an arbitrary $x$, so its $y$ cannot mention $x$ at all. Knowing which kind of statement is in hand says in advance whether an example will be enough, and what shape of argument is needed when it is not.

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: $\forall x\forall yP(x,y)$ and $\forall y\forall xP(x,y)$ both say that $P$ holds for every pair, and $\exists x\exists y$ and $\exists y\exists x$ both say that it holds for at least one pair. When the kinds 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 between two players. A sceptic picks the values under $\forall$ and a prover picks those under $\exists$, in the order written, each seeing the choices already made. The statement is true when the prover has a strategy that wins however the sceptic plays. In $\forall x\exists y(y>x)$ the sceptic names $x$ and the prover answers $x+1$, and wins every time. In $\exists y\forall x(y>x)$ the prover must commit to $y$ first, and the sceptic answers $y$ itself, or anything larger, and wins every time. Every proof in this course of a statement with several quantifiers is a winning strategy for the prover, written down.

Committing early is a handicap, never an advantage, and that makes one direction of the order a theorem.

Theorem. For every predicate $P(x,y)$, $\exists y\forall xP(x,y)$ implies $\forall x\exists yP(x,y)$.

Proof. Suppose $\exists y\forall xP(x,y)$, and let $y_0$ be a value with $\forall xP(x,y_0)$. Let $x$ be arbitrary. Then $P(x,y_0)$ holds, so $y_0$ is a value of $y$ with $P(x,y)$, and $\exists yP(x,y)$ is true. Since $x$ was arbitrary, $\forall x\exists yP(x,y)$. $\square$

In the game, the prover who can win by committing first can win by committing second: play the same $y_0$ whatever $x$ turns out to be. The converse is false, and the integers with $y>x$ show it. A counterexample to a claim about all predicates is one predicate on one domain, and $y>x$ over $\mathbb{Z}$ makes $\forall x\exists y$ true and $\exists y\forall x$ false.

Negation still works one quantifier at a time, so $\neg \forall x\exists yP(x,y)$ is $\exists x\forall y\neg P(x,y)$. The negation of "every integer has a larger one" is "some integer has no larger one", that is, "some integer is at least as large as every integer", and the negation of "some integer is larger than every integer" is "every integer is at most as large as some integer", a clumsy but true sentence.

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\le x)$. Let $y$ be any integer and take $x=y$. Then $y\le x$. As $y$ was arbitrary, no integer is larger than all integers, not even than itself.

In both proofs the witness is a formula in the variable chosen before it: $y=x+1$ in the first, $x=y$ in the second. That is what the order $\forall \exists$ permits, and it is why the proof of the negation could be so short. The sceptic's value came first.

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 $\mathbb{N}$?

Exactly one

The existential quantifier means "at least one", and many theorems claim more: there is exactly one such object. The quotient and remainder on dividing one integer by another, the positive square root of a positive number, the limit of a convergent sequence, each is unique, and each word "the" in those phrases depends on it.

Definition. $\exists !xP(x)$, read "there is a unique $x$ with $P(x)$" or "there is exactly one $x$ with $P(x)$", means

In words: some $x$ has the property, and every object with the property is that $x$. The same claim splits into two independent halves,

existence, that at least one object has the property, and uniqueness, that at most one does. The second half on its own is how "there is at most one" is written. It asserts nothing about existence: over the integers, "at most one $x$ satisfies $x^2=-1$" is true because none does.

The two forms say the same thing. If $x$ witnesses the first form, then $\exists xP(x)$ holds, and whenever $P(u)$ and $P(v)$, both $u=x$ and $v=x$, so $u=v$. Conversely, if both halves hold, take $x$ with $P(x)$; any $y$ with $P(y)$ then has $y=x$ by uniqueness, which is the first form.

The split is also the plan of every proof of unique existence: two separate arguments. Existence is proved like any existential claim, by a witness. Uniqueness is a universal claim, proved by letting two objects with the property be arbitrary and showing they are equal. Finding one object and failing to think of another proves existence only.

Uniqueness shows up hidden in counting. Two variables may take the same value, so $\exists x\exists y(P(x)\wedge P(y))$ is true whenever one object has $P$, and "at least two objects have $P$" needs the inequality written in:

Negating $\exists !xP(x)$ by rule, from the second form, gives $\neg \exists xP(x)\vee \exists x\exists y(P(x)\wedge P(y)\wedge x\ne y)$: either nothing has the property, or at least two things do. A claim of unique existence fails in two quite different ways, and a disproof must say which.

Example. Prove that there is a unique natural number $n$ with $n^2-2n-3=0$. Is there a unique integer with that property?

Existence. Take $n=3$. Then $n^2-2n-3=9-6-3=0$, and $3\in \mathbb{N}$.

Uniqueness. Let $n$ be a natural number with $n^2-2n-3=0$. Factorising, $(n-3)(n+1)=0$, so $n-3=0$ or $n+1=0$. Since $n\ge 1$, the number $n+1$ is at least $2$ and so is not $0$. Hence $n-3=0$, and $n=3$. So every natural number with the property equals $3$.

Over the integers the answer changes: $-1$ also works, since $1+2-3=0$. So there are at least two integers with the property, $3$ and $-1$, and by the negation above, $\exists !n\in \mathbb{Z}$ is false. The uniqueness argument shows where the domain entered: "$n+1\ne 0$" was the only step that used $n\ge 1$.

The uniqueness proof here showed that every solution equals the one already found. The other pattern, taking two arbitrary solutions and showing they are equal, is often cleaner when the solution has no formula, as in the next exercise.

Now you. Prove that there is a unique real number $x$ with $x^3+x=10$.

Translating mathematical English

Mathematics is written in English with symbols mixed in, and most of its quantifiers are words. Translating into symbols is how you find out exactly what a sentence claims, and translating back is how you say it to a reader. The common words are these.

• "for every", "for all", "for each", "for any", "whenever", "always", and the indefinite article in a general claim ("a square is never negative") are universal.
• "there is", "there exists", "for some", "at least one", "can be" ("$6$ can be written as a sum of two primes") and the indefinite article in an existence claim ("$x^2=2$ has a real solution") are existential.
• "no", "none", "never" are $\forall \neg$, which is the same as $\neg \exists$: "no square is negative" is $\forall x(x^2\ge 0)$.
• "only" marks the conclusion of a conditional: "only even numbers are divisible by $4$" is $\forall n(4\mid n\Rightarrow n\text{is even})$.

The word "any" is the dangerous one, because it is universal in some positions and existential in others. "Any square is non-negative" means every square. "If any integer is a counterexample, the conjecture is false" means if some integer is, and "there is not any solution" means no solution. When "any" appears, rewrite with "every" or "some" and check that the meaning survived.

Several phrases in analysis and number theory package two quantifiers at once, and they come in pairs that differ only in order. For a property $P(n)$ of natural numbers:

• "$P(n)$ holds for all sufficiently large $n$", or "eventually", means $\exists N\forall n\ge NP(n)$: from some point on, always.
• "$P(n)$ holds for infinitely many $n$", or "frequently", means $\forall N\exists n\ge NP(n)$: beyond every point, at least once more.

The negation of "eventually $P$" is $\forall N\exists n\ge N\neg P(n)$, "infinitely often not $P$", and the negation of "infinitely often $P$" is "eventually not $P$". Over $\mathbb{N}$, "arbitrarily large" means the same as "infinitely many": "there are arbitrarily large primes" is $\forall N\exists p(p>N\wedge p\text{is prime})$, which says the primes never stop.

Example. Symbolise "between any two distinct real numbers there is a rational number". Then negate the symbolic form, and translate the negation back into English.

The claim is universal in the two numbers and existential in the rational. "Distinct" can be replaced by "$x<y$", since of two distinct reals one is smaller and the sentence does not care which is named first. So the claim is

To negate, flip each quantifier and push the $\neg$ inwards, using $\neg (A\Rightarrow B)\equiv A\wedge \neg B$ and De Morgan on the final conjunction:

In English: there are real numbers $x<y$ such that every rational number lies at or below $x$ or at or above $y$, that is, no rational lies strictly between them. The original is the true one: it is the density of the rationals, which the lesson on the real numbers proves from the completeness axiom.

Now you. A function $f:ℝ\to ℝ$ is bounded if some number $M$ is at least $|f(x)|$ for every real $x$. Symbolise "$f$ is bounded", write the negation "$f$ is unbounded" in symbols and in English, and prove that $f(x)=x^2$ is unbounded.

Hidden quantifiers

Most quantifiers in real writing are not written as quantifiers at all, and a large share of confusion, in mathematics and outside it, comes from supplying the wrong one.

In algebra the sign "$=$" carries a hidden quantifier that changes with the sentence. "$(x+1{)}^2=x^2+2x+1$" is an identity, a claim about every real $x$. "$x^2=2x$" is an equation, an open sentence, and "solve it" means find its truth set, here $\{0,2\}$. "$x^2=2x$ has a solution" is an existential claim. The three look alike on the page, and a proof needs to know which it is holding, because an identity may be used for any value while an equation may be used only for the values that satisfy it.

Properties of functions are quantified statements in the same way. For a function $f:ℝ\to ℝ$:

• $f$ is increasing when $\forall x\forall y(x<y\Rightarrow f(x)\le f(y))$, and strictly increasing with $f(x)<f(y)$ at the end;
• $f$ is constant when $\exists c\forall x(f(x)=c)$, or equivalently $\forall x\forall y(f(x)=f(y))$;
• $f$ is periodic when $\exists p>0\forall x(f(x+p)=f(x))$;
• $f$ has a maximum when $\exists a\forall x(f(x)\le f(a))$.

Each negation is then a matter of rule. "$f$ is not increasing" is $\exists x\exists y(x<y\wedge f(x)>f(y))$: one pair of points where the function goes down. It is not "$f$ is decreasing", which is a universal claim of its own, and most functions, $x^2$ among them, are neither.

The words "let" and "suppose" in a proof also carry quantifiers. "Let $n$ be an integer" introduces an arbitrary object, the first move of a proof of a $\forall$. "Choose $k$ with $n=2k$" introduces a particular one, supplied by an $\exists$ in a hypothesis. The next lesson makes the difference precise, because confusing the two is behind many invalid proofs.

Everyday English is looser still. "All that glisters is not gold", from The Merchant of Venice, literally says $\forall x(\text{glisters}(x)\Rightarrow \neg \text{gold}(x))$: nothing that glisters is gold. It means $\neg \forall x(\text{glisters}(x)\Rightarrow \text{gold}(x))$: not everything that glisters is gold. "Everybody loves somebody" is usually $\forall x\exists y$, each person has someone, but can be heard as $\exists y\forall x$, one person whom everybody loves. A statistic such as "a pedestrian is injured in this city every hour" is $\forall$ hour $\exists$ pedestrian; the old joke replies "that poor pedestrian", reading it as $\exists$ pedestrian $\forall$ hour. None of this is a defect of English, which leans on context. Mathematics cannot, so when a sentence could be read two ways it is rewritten until it cannot.

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$ of real numbers converges to a real number $L$, written $a_n\to L$, when

Read aloud: for every tolerance $\epsilon >0$ there is a position $N$ such that every term from position $N$ on lies within $\epsilon$ of $L$. Here $|a_n-L|$ is the distance from $a_n$ to $L$, so $|a_n-L|<\epsilon$ says $L-\epsilon <a_n<L+\epsilon$.

As a game: the sceptic names a tolerance $\epsilon$, the prover answers with a position $N$, the sceptic picks any term from position $N$ on, and the prover wins if it lies within $\epsilon$ of $L$. Since $\exists N$ follows $\forall \epsilon$, 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 the definition collapses.

Proposition. If $\exists N\in \mathbb{N}\forall \epsilon >0\forall n\ge N(|a_n-L|<\epsilon )$, then $a_n=L$ for every $n\ge N$.

Proof. Take such an $N$, and let $n\ge N$. Then $|a_n-L|<\epsilon$ for every $\epsilon >0$. Suppose $|a_n-L|>0$. Then $\epsilon =|a_n-L|$ is a positive tolerance, and the hypothesis gives $|a_n-L|<|a_n-L|$, which is impossible. So $|a_n-L|=0$, and $a_n=L$. $\square$

So under the swapped reading a sequence would converge only if it were eventually equal to its limit, and $\frac{1}{n}$, which never reaches $0$, would not converge to $0$. The order $\forall \epsilon \exists N$ is what lets a sequence approach a value without arriving.

Proving that a limit is correct means winning the game for every $\epsilon$ at once, so the proof must give $N$ as a rule in terms of $\epsilon$. Finding the rule is scrap work: write $|a_n-L|$, simplify it, and see how large $n$ must be to make it less than $\epsilon$. The proof then needs a natural number beyond any given real number, which is the Archimedean property of the reals: for every real number $x$ there is a natural number $N$ with $N>x$. It is used here as a known fact about $ℝ$, and the lesson on the real numbers derives it from the completeness axiom.

Example. Prove that $\frac{n}{n+1}\to 1$.

Scrap work: $|\frac{n}{n+1}-1|=|\frac{-1}{n+1}|=\frac{1}{n+1}$, and $\frac{1}{n+1}<\epsilon$ exactly when $n+1>\frac{1}{\epsilon }$. So any $N$ beyond $\frac{1}{\epsilon }$ will do.

Proof. Let $\epsilon >0$. By the Archimedean property there is a natural number $N$ with $N>\frac{1}{\epsilon }$. Let $n\ge N$. Then $n+1>n\ge N>\frac{1}{\epsilon }$, so $\frac{1}{n+1}<\epsilon$, and

Since $\epsilon >0$ was arbitrary, $\frac{n}{n+1}\to 1$. $\square$

The proof follows the quantifiers exactly. "Let $\epsilon >0$" answers $\forall \epsilon$, "there is $N$" answers $\exists N$, "let $n\ge N$" answers $\forall n\ge N$, and the displayed line is the sentence at the end. For $\epsilon =0.01$ the rule gives any $N>100$, say $101$, and then $\frac{1}{n+1}\le \frac{1}{102}<0.01$ for every $n\ge 101$. The rule need not give the smallest $N$ that works, only one that does.

Now you. Prove that $\frac{3n}{n+2}\to 3$.

To show that a sequence does not converge to $L$, negate the definition, one symbol at a time. $\forall \epsilon >0$ becomes $\exists \epsilon >0$, keeping its restriction. $\exists N\in \mathbb{N}$ becomes $\forall N\in \mathbb{N}$. $\forall n\ge N$ becomes $\exists n\ge N$. Finally $|a_n-L|<\epsilon$ becomes $|a_n-L|\ge \epsilon$. So $a_n$ does not converge to $L$ when

that is, some tolerance is broken by a term beyond every starting point. In the language of the section on mathematical English: for some $\epsilon$, infinitely many terms lie at distance at least $\epsilon$ from $L$. A disproof must therefore supply one $\epsilon$, 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 $\epsilon =1$. Let $N$ be any natural number and take $n=2N+1$. Then $n\ge N$ and $n$ is odd, so $a_n=-1$ and $|a_n-1|=2\ge 1$. Since $N$ was arbitrary, the negation holds.

Now the roles have changed. The prover of the negation chooses $\epsilon$ and $n$, the sceptic chooses $N$, and the prover's $n$ is allowed to depend on $N$, as $2N+1$ does.

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

A sequence that converges to no real number at all is said to diverge, and that is one more quantifier in front: $\forall L\in ℝ\exists \epsilon >0\forall N\in \mathbb{N}\exists n\ge N(|a_n-L|\ge \epsilon )$. Showing that $(-1{)}^n$ diverges means defeating every candidate $L$, not just $1$ and $-1$, and it is one of the problems at the end. The lesson on limits builds the theory on this definition: that a sequence has at most one limit, that a convergent sequence is bounded, and the rules for limits of sums and products.

Continuity, pointwise and uniform

The definition of continuity has the same three quantifiers, with a fourth that can stand in two places, and its two positions give two different notions.

Definition. A function $f:ℝ\to ℝ$ is continuous at the point $a$ when

It is continuous when it is continuous at every point, $\forall a\forall \epsilon >0\exists \delta >0\forall x(\dots )$, and uniformly continuous when

In the game for continuity at $a$, the sceptic names a tolerance $\epsilon$ for the output, the prover answers with a tolerance $\delta$ for the input, and the sceptic may then pick any $x$ within $\delta$ of $a$; the prover wins if $f(x)$ is within $\epsilon$ of $f(a)$. It says that $f(x)$ can be made as close as you like to $f(a)$ by taking $x$ close enough to $a$. The definitions of continuity and uniform continuity differ only in where $\forall a$ stands. In continuity it comes before $\exists \delta$, so $\delta$ may depend on the point $a$ as well as on $\epsilon$. In uniform continuity it comes after, so one $\delta$ must serve every point at once. By the theorem on quantifier order, moving an $\exists$ later can only weaken a statement, so every uniformly continuous function is continuous. The converse fails, and the standard example shows why.

A linear function is uniformly continuous. For $f(x)=2x+1$, $|f(x)-f(a)|=|2x-2a|=2|x-a|$, so given $\epsilon >0$ take $\delta =\frac{\epsilon }{2}$: whenever $|x-a|<\delta$, $|f(x)-f(a)|=2|x-a|<\epsilon$. The $\delta$ mentions only $\epsilon$, so it serves every $a$ at once. (The calculation uses $|uv|=|u||v|$ and the other school facts about absolute value, which the next lesson proves.)

The squaring function is continuous, but its $\delta$ has to shrink as $a$ grows. Since $x^2-a^2=(x-a)(x+a)$, the output error is the input error multiplied by $|x+a|$, which is about $2|a|$ when $x$ is near $a$.

Proposition. The function $f(x)=x^2$ is continuous at every real number $a$.

Proof. Let $a$ be a real number and let $\epsilon >0$. Take $\delta$ to be the smaller of $1$ and $\frac{\epsilon }{2|a|+1}$, which is positive. Let $x$ be a real number with $|x-a|<\delta$. Since $\delta \le 1$, we have $a-1<x<a+1$, so $2a-1<x+a<2a+1$, and as $2a+1\le 2|a|+1$ and $2a-1\ge -(2|a|+1)$, this gives $|x+a|<2|a|+1$. Therefore

where the strict step uses $|x-a|<\delta$ and $2|a|+1>0$, and the last step uses $\delta \le \frac{\epsilon }{2|a|+1}$. $\square$

The $\delta$ depends on $a$ through the factor $2|a|+1$. That is not a weakness of this proof. No choice of $\delta$ free of $a$ can work, as the negation of uniform continuity shows. By rule, $f$ is not uniformly continuous when

Proposition. The function $f(x)=x^2$ is not uniformly continuous on $ℝ$.

Proof. Take $\epsilon =1$. Let $\delta >0$, and take $a=\frac{1}{\delta }$ and $x=a+\frac{\delta }{2}$. Then $|x-a|=\frac{\delta }{2}<\delta$, and

So $|f(x)-f(a)|\ge 1=\epsilon$. Since $\delta >0$ was arbitrary, $f$ is not uniformly continuous. $\square$

However small the proposed $\delta$, the sceptic goes far enough out along the parabola, to $a=\frac{1}{\delta }$, that the curve is steep enough to turn an input step of $\frac{\delta }{2}$ into an output jump of more than $1$. Both propositions are about the same function, and the only difference between the statements they settle is the position of $\forall a$.

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 shape of the symbols dictates the shape of the proof: a $\forall$ is met by letting the variable be arbitrary, an $\exists$ by naming a value, which may depend on every variable chosen before it, and a disproof is a proof of the negation, with every quantifier flipped.

Take the claim that the square of every odd integer is one more than a multiple of $8$. In symbols it is

and the symbols say what a proof must do: let $n$ be an arbitrary odd integer, and produce an integer $m$, depending on $n$, with $n^2=8m+1$. The examples agree: $1=8\times 0+1$, $9=8\times 1+1$, $25=8\times 3+1$, $49=8\times 6+1$, $81=8\times 10+1$, and $(-3{)}^2=9$ as well. But they are examples, and the claim is universal over an infinite domain. The quantifiers say what a proof must deliver, not how to find the $m$. The next lesson supplies the method, the direct proof, and proves this claim with it.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. Decide whether each statement is true over $\mathbb{N}$, over $\mathbb{Z}$ and over $ℝ$, twelve verdicts in all, and justify each. (a) $\forall x(x^2>0)$. (b) $\exists x(2x=1)$. (c) $\forall x\exists y(x=2y)$. (d) $\exists x\forall y(x\le y)$.