Quantifiers and negation · MATH-228 Lesson 3

Propositional logic treats statements as sealed boxes. Most mathematical statements, though, are about objects: every continuous function on a closed interval has a maximum; some integer is both a perfect square and a perfect cube; for every $\varepsilon > 0$ there is a $\delta > 0$ such that something happens. To handle such statements we need predicates, which are sentences with variables, and quantifiers, which say how many values of the variable make the sentence true. This lesson introduces both and shows how to negate quantified statements, a skill you will use every time you write a proof by contradiction or look for a counterexample.

Predicates and domains

A predicate is a sentence containing one or more variables that becomes a statement once the variables are given values. Write $P(x)$ for '$x$ is prime'. Then $P(7)$ is true, $P(8)$ is false, and $P(x)$ by itself is neither. Predicates can have several variables: $D(a, b)$ for '$a$ divides $b$' gives $D(3, 12)$ true and $D(5, 12)$ false.

Every predicate comes with a domain, the set of values the variable may take. The domain matters. '$x^2 = 2$ has a solution' is false if the domain is the rational numbers and true if it is the real numbers. '$x > 0$ implies $x \ge 1$' is true for integers and false for real numbers. In this course we write the standard number sets as $\mathbb{N} = \{1, 2, 3, \dots\}$ for the natural numbers, $\mathbb{Z}$ for the integers, $\mathbb{Q}$ for the rationals and $\mathbb{R}$ for the reals. Some books include 0 in $\mathbb{N}$; we do not, and we write $\mathbb{Z}_{\ge 0}$ when we want it.

The two quantifiers

The universal quantifier $\forall$ means 'for all' or 'for every'. The statement $\forall x \in \mathbb{Z},\ x^2 \ge 0$ says that every integer has a non-negative square, which is true. The existential quantifier $\exists$ means 'there exists' or 'for some'. The statement $\exists x \in \mathbb{Z},\ x^2 = 49$ says that some integer has square 49, which is true because $7^2 = 49$.

A universal statement $\forall x,\ P(x)$ is true when $P(x)$ holds for every $x$ in the domain, and false as soon as one $x$ fails. That one failing value is a counterexample. An existential statement $\exists x,\ P(x)$ is true as soon as one $x$ works, which we call a witness, and false only if every $x$ fails. So to prove a universal statement you must handle an arbitrary element; to disprove it, one counterexample is enough. To prove an existential statement, one witness is enough; to disprove it, you must show that every element fails.

How to prove and disprove quantified statements
Statement	To prove it	To disprove it
$\forall x,\ P(x)$	Let $x$ be arbitrary and show $P(x)$	Find one $x$ with $P(x)$ false
$\exists x,\ P(x)$	Find one $x$ with $P(x)$ true	Show $P(x)$ false for arbitrary $x$

Many quantified statements hide inside ordinary language. 'Squares are non-negative' means $\forall x,\ x^2 \ge 0$. 'There is no largest integer' means $\neg \exists n \in \mathbb{Z}\ \forall m \in \mathbb{Z},\ m \le n$. 'An even number greater than 2 is never prime' means for every $n$, if $n$ is even and $n > 2$, then $n$ is not prime. Part of learning to prove things is learning to translate sentences like these into precise logical form and back.

Universal statements are usually conditionals in disguise. 'Every prime greater than 2 is odd' is $\forall n \in \mathbb{Z},\ (n \text{ is prime} \wedge n > 2) \implies n \text{ is odd}$. Existential statements are usually conjunctions: 'some prime is even' is $\exists n \in \mathbb{Z},\ n \text{ is prime} \wedge n \text{ is even}$. Mixing these up produces nonsense. The statement $\exists n,\ (n \text{ is prime} \implies n \text{ is even})$ is true for a silly reason: take $n = 4$, which is not prime, so the conditional is vacuously true.

Negating quantifiers

The negation of 'every swan is white' is not 'every swan is not white'; it is 'some swan is not white'. In symbols, $\neg \forall x,\ P(x) \equiv \exists x,\ \neg P(x)$ and $\neg \exists x,\ P(x) \equiv \forall x,\ \neg P(x)$. Negation moves inward past a quantifier and flips it from $\forall$ to $\exists$ or back. These rules are the quantifier versions of De Morgan's laws: over a finite domain $\{a, b\}$, '$\forall x,\ P(x)$' is '$P(a) \wedge P(b)$', and its negation is '$\neg P(a) \vee \neg P(b)$', which is '$\exists x,\ \neg P(x)$'.

With several quantifiers the rule applies repeatedly. To negate $\forall x\ \exists y,\ P(x, y)$, move the negation across both quantifiers, flipping each, to get $\exists x\ \forall y,\ \neg P(x, y)$. Then push the negation into $P$ using the rules from lesson 2: negate 'and' to 'or', negate a conditional $A \implies B$ to $A \wedge \neg B$, negate $<$ to $\ge$.

Worked problem

Negating a nested statement

Negate $\forall \varepsilon > 0\ \exists N \in \mathbb{N}\ \forall n \ge N,\ |a_n - L| < \varepsilon$, which says that the sequence $a_n$ converges to $L$.

Show solution

Flip each quantifier from left to right: $\exists \varepsilon > 0\ \forall N \in \mathbb{N}\ \exists n \ge N$, followed by $\neg(|a_n - L| < \varepsilon)$.
Negate the inner inequality: $\neg(|a_n - L| < \varepsilon)$ is $|a_n - L| \ge \varepsilon$.
Note that the restrictions $\varepsilon > 0$, $N \in \mathbb{N}$ and $n \ge N$ are not negated; they describe the domains of the quantifiers.
Read the result in words: there is some positive tolerance $\varepsilon$ such that, however far out you start, some later term is at least $\varepsilon$ away from $L$.

Answer: $\exists \varepsilon > 0\ \forall N \in \mathbb{N}\ \exists n \ge N,\ |a_n - L| \ge \varepsilon$.

This example is the definition of convergence from MATH-241 (Real Analysis I), and its negation is how you show that a sequence does not converge to $L$. Being able to negate such statements mechanically, without having to think hard about the meaning, frees you to concentrate on the mathematics.

Order of quantifiers

When quantifiers of the same kind are next to each other, their order does not matter: $\forall x\ \forall y$ means the same as $\forall y\ \forall x$, and similarly for $\exists$. When the kinds are mixed, order matters a great deal. Compare these two statements about real numbers.

$\forall x\ \exists y,\ y > x$: for every number, there is a bigger number. True: given $x$, take $y = x + 1$.

$\exists y\ \forall x,\ y > x$: there is one number bigger than every number. False: no real number is bigger than itself.

In the first statement $y$ may depend on $x$; a different $x$ can get a different $y$. In the second a single $y$ must work for all $x$ at once. A helpful way to think about nested quantifiers is as a game between two players. The player called 'for all' chooses values for the $\forall$ variables and tries to make the statement false; the player called 'there exists' chooses the $\exists$ variables and tries to make it true. They choose in the order the quantifiers appear, each seeing the earlier choices. The statement is true exactly when the 'there exists' player has a winning strategy.

$Two panels. Left: several x values on a number line, each with its own arrow to a larger y value, labeled for all x there exists y. Right: a single y value with arrows from every x value, but one x value beyond y crossed out, labeled there exists y for all x fails.$

Order matters: each x can have its own y, but no single y works for every x

In the game for $\forall x\ \exists y,\ y > x$, the first player picks $x$, then the second picks $y = x + 1$ and wins every time, so the statement is true. In the game for $\exists y\ \forall x,\ y > x$, the second player must commit to $y$ first, and the first player then picks $x = y$ and wins, so the statement is false.

Proving quantified statements

Proofs of quantified statements follow the structure of the statement. For a universal statement, begin with 'Let $x$ be an arbitrary element of the domain' (or simply 'Let $x \in \mathbb{Z}$') and prove $P(x)$ using only the properties every element has. For an existential statement, produce a witness and check that it works. When quantifiers are nested, these steps nest too: to prove $\forall x\ \exists y,\ P(x, y)$, let $x$ be arbitrary, then construct a $y$, possibly depending on $x$, and verify $P(x, y)$.

Worked problem

A for all, there exists proof

Prove that for every integer $n$ there is an integer $m$ with $m > n$ and $m$ even.

Show solution

Let $n$ be an arbitrary integer. We must find an even integer bigger than $n$.
Scratch work: $n + 1$ is bigger, but may be odd; $n + 2$ has the same parity as $n$. Doubling helps: $2n$ is even but may not be bigger (try $n = -3$). Try $m = 2|n| + 2$.
Check: $m = 2(|n| + 1)$ is even because $|n| + 1$ is an integer. And $m = 2|n| + 2 > |n| \ge n$, since $2|n| + 2 > |n|$ whenever $|n| \ge 0$.
So $m$ is an even integer larger than $n$, and since $n$ was arbitrary the statement holds for all $n$. $\blacksquare$

Answer: Take $m = 2|n| + 2$; it depends on $n$, which is allowed because $\exists m$ comes after $\forall n$.

Note that the witness $m$ was built from $n$. That is exactly what the order $\forall n\ \exists m$ permits. If the statement had been $\exists m\ \forall n$, we would have needed one $m$ larger than every integer, which is impossible.

Unique existence

Sometimes we want to say that exactly one object has a property. We write $\exists! x,\ P(x)$, read 'there is a unique $x$ such that $P(x)$'. It means two things: existence, some $x$ has the property, and uniqueness, any two objects with the property are equal. In symbols, $\exists x\ (P(x) \wedge \forall y\ (P(y) \implies y = x))$. A uniqueness proof usually starts 'Suppose $x_1$ and $x_2$ both have the property' and ends with $x_1 = x_2$.

For example, every real number $a \ne 0$ has a unique multiplicative inverse. Existence: $1/a$ works. Uniqueness: if $ab = 1$ and $ac = 1$, then $b = b \cdot 1 = b(ac) = (ba)c = 1 \cdot c = c$. The same argument shows that inverses in any group are unique, a fact you will use in MATH-322.

Checking quantified statements on finite domains

Over a finite domain, $\forall$ is a long 'and' and $\exists$ is a long 'or', so a computer can decide quantified statements by checking every case. Python's built-in functions all and any do exactly this. The code below checks several statements about the integers from $-20$ to $20$, including both orders of the same quantifiers. A result on a finite domain does not prove anything about all integers, but it is a fast way to test your reading of a statement and to hunt for counterexamples.

all and any are the finite versions of the two quantifiers

D = range(-20, 21)

# for all x there exists y with y > x   (fails only at the top of a finite domain)
s1 = all(any(y > x for y in D) for x in D)
# exists y for all x with y > x
s2 = any(all(y > x for x in D) for y in D)
print("forall x exists y, y > x :", s1)
print("exists y forall x, y > x :", s2)
print("    x values with no larger y in D:", [x for x in D if not any(y > x for y in D)])

# for every n there is an even m > n, using the witness m = 2|n| + 2
print("witness 2|n|+2 always works:", all((2*abs(n)+2) % 2 == 0 and 2*abs(n)+2 > n for n in D))

# negation rule: not (forall x, P) has the same value as (exists x, not P)
P = lambda x: x * x != 2 * x
print("not forall:", not all(P(x) for x in D), " exists not:", any(not P(x) for x in D))
print("counterexamples to x^2 != 2x:", [x for x in D if not P(x)])

Output

forall x exists y, y > x : False
exists y forall x, y > x : False
    x values with no larger y in D: [20]
witness 2|n|+2 always works: True
not forall: True  exists not: True
counterexamples to x^2 != 2x: [0, 2]

The first result shows a trap of finite checking. Over the integers, 'for every $x$ there is a larger $y$' is true, but in the finite domain from $-20$ to $20$ it fails at $x = 20$, because there is nothing larger in the domain. The domain is part of the statement, and changing it can change the answer.

Common mistakes

MistakeNegating "for all $x$, $P(x)$" as "for all $x$, not $P(x)$".
InsteadThe negation is "there exists $x$ with not $P(x)$": one counterexample is enough.
MistakeSwapping the order of mixed quantifiers.
Instead$\forall x\ \exists y$ lets $y$ depend on $x$; $\exists y\ \forall x$ needs one $y$ for all $x$.
MistakeProving a universal statement by checking one convenient value.
InsteadLet the variable be arbitrary and use only properties every element has.
MistakeWriting "there exists a prime $n$ with $n$ even" as $\exists n,\ (n \text{ prime} \implies n \text{ even})$.
InsteadExistential statements use "and": $\exists n,\ n \text{ prime} \wedge n \text{ even}$.
MistakeNegating the domain restriction, turning $\forall \varepsilon > 0$ into $\exists \varepsilon \le 0$.
InsteadOnly the quantifier flips: $\neg \forall \varepsilon > 0,\ P$ is $\exists \varepsilon > 0,\ \neg P$.
MistakeForgetting the domain.
InsteadState it: whether "$x^2 = 2$ has a solution" is true depends on whether $x$ ranges over $\mathbb{Q}$ or $\mathbb{R}$.

Summary and key terms

A predicate is a sentence with variables; it becomes a statement when the variables are given values or are quantified.
$\forall$ means for all and $\exists$ means there exists; the domain of each variable must be clear.
Prove $\forall$ with an arbitrary element, disprove it with one counterexample; prove $\exists$ with one witness.
Negation flips quantifiers: $\neg \forall x\ P \equiv \exists x\ \neg P$ and $\neg \exists x\ P \equiv \forall x\ \neg P$.
The order of mixed quantifiers matters; in $\forall x\ \exists y$ the choice of $y$ may depend on $x$.
$\exists!$ means exactly one: prove existence and then show any two such objects are equal.

predicate: A sentence with variables that becomes true or false when values are substituted.
domain: The set of values a variable may take.
universal quantifier: $\forall$, read "for all".
existential quantifier: $\exists$, read "there exists".
witness: An element showing that an existential statement is true.
counterexample: An element showing that a universal statement is false.
unique existence: $\exists!$: exactly one element has the property.
natural numbers: $\mathbb{N} = \{1, 2, 3, \dots\}$ in this course.
integers: $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$.
rational numbers: $\mathbb{Q}$, the numbers $a/b$ with integers $a$ and $b \ne 0$.

Practice problems

Work each problem on paper first, then reveal the answer to check.

Write in symbols and decide: "every integer is the sum of two odd integers".
Show answer
$\forall n \in \mathbb{Z}\ \exists a, b \in \mathbb{Z},\ n = a + b \wedge a, b \text{ odd}$. False: 3 is not, since a sum of two odd integers is even.
Negate $\forall x \in \mathbb{R}\ \exists y \in \mathbb{R},\ xy = 1$ and decide which is true.
Show answer
Negation: $\exists x\ \forall y,\ xy \ne 1$. It is true (take $x = 0$), so the original is false.
Is $\exists x \in \mathbb{R}\ \forall y \in \mathbb{R},\ xy = 0$ true?
Show answer
Yes: $x = 0$ is a witness, since $0 \cdot y = 0$ for every $y$.
Prove that for every real number $x$ there is a real number $y$ with $x + y = 0$. Is the $y$ unique?
Show answer
Let $x$ be arbitrary and take $y = -x$. If $x + y_1 = 0 = x + y_2$, subtracting gives $y_1 = y_2$, so it is unique.
Negate "every student in the class has read at least one book by every author on the list".
Show answer
Some student in the class has, for some author on the list, read no book by that author.
Explain why $\forall x \in \mathbb{N}\ \exists y \in \mathbb{N},\ y < x$ is false.
Show answer
For $x = 1$ there is no natural number less than 1, so $x = 1$ is a counterexample.

Statement	To prove it	To disprove it
\(\forall x,\ P(x)\)	Let \(x\) be arbitrary and show \(P(x)\)	Find one \(x\) with \(P(x)\) false
\(\exists x,\ P(x)\)	Find one \(x\) with \(P(x)\) true	Show \(P(x)\) false for arbitrary \(x\)