Predicates and Quantifiers

Main idea

A statement with a variable in it, like "x > 3," isn't true or false until you say which x you mean. "For all" (∀) and "there exists" (∃) settle that, and negating one turns it into the other: "not every x works" means "some x fails."

Negating quantifiers

\neg\,{\htmlData{sym=0}{\forall}} x\, {\htmlData{sym=2}{P(x)}} \equiv {\htmlData{sym=1}{\exists}} x\, \neg {\htmlData{sym=2}{P(x)}}, \qquad \neg\,{\htmlData{sym=1}{\exists}} x\, {\htmlData{sym=2}{P(x)}} \equiv {\htmlData{sym=0}{\forall}} x\, \neg {\htmlData{sym=2}{P(x)}}

What the symbols mean

$\forall$
For all
The statement holds for every element of the domain.
$\exists$
There exists
The statement holds for at least one element.
$P(x)$
Predicate
A statement about x that is true or false once x is chosen.

Explanation

A quantifier is simply a phrase that says how many things a claim is about: "for all" (every single one) or "there exists" (at least one). The name fits once you see it, since it states the quantity. Quantifiers let you say things like "every request gets a response" precisely, and they tell you exactly what it takes to break such a claim. The formula $\neg\,\forall x\, P(x) \equiv \exists x\, \neg P(x)$ looks scary, but read it piece by piece: $\forall x$ (for every x), $\exists x$ (there's at least one x), $P(x)$ (some claim about x) and $\neg$ (not). Put together it says "not everyone passed" means "someone failed." That's the whole idea, so bear with the upside-down letters.

Back in the first lesson, "x > 3" didn't count as a proposition, because its truth depends on x. Statements like that are called predicates, written $P(x)$ . There are two ways to turn one into an honest true-or-false statement: plug in a specific $x$ , or say how many $x$ 's you're talking about. That second option is what quantifiers do.

$\forall x\, P(x)$ is true when $P(x)$ holds for every $x$ in the domain. One counterexample makes it false.
$\exists x\, P(x)$ is true when $P(x)$ holds for at least one $x$ . It's false only if $P(x)$ fails everywhere.

The answer also depends on the domain, the set $x$ ranges over. " $\exists x\,(x^2 = 2)$ " is true over the real numbers, where $x = \sqrt2$ works, and false over the integers.

Negation pushes through a quantifier and flips it. To see why, picture a small domain $\{1, 2, 3\}$ . Then $\forall x\, P(x)$ is just $P(1) \wedge P(2) \wedge P(3)$ , a giant "and," and $\exists x\, P(x)$ is $P(1) \vee P(2) \vee P(3)$ , a giant "or." Negating them is De Morgan's laws all over again: "not all of them work" becomes "at least one fails."

A common mistake. It's tempting to think you can swap the order of quantifiers freely, since the same words appear either way. You can't. Over the integers, $\forall x\, \exists y\, (y > x)$ says "every number has a bigger one," which is true, because $y$ is allowed to depend on $x$ . But $\exists y\, \forall x\, (y > x)$ says "one single number is bigger than all of them," which is false.

See it

a

5.00

The domain is {1, 2, …, 12} and P(x) says x ≥ a; pink dots are the x's where P fails. Slide a and notice how lopsided the two quantifiers are: ∀x P(x) is true only when a ≤ 1, because a single pink dot kills it, while ∃x P(x) survives all the way up to a = 12.

Worked examples

Example 1

Negate "every bug report gets a reply within a day."

1
In symbols it's $\forall b\, R(b)$ , where $R(b)$ is " $b$ gets a reply within a day."

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Which is the negation of $\forall x\,(x^2 \ge 0)$ ?

Problem 2+5 XP

On the domain $\{1, 2, 3, 4\}$ , is $\exists x\,(x^2 = 9)$ true?

Problem 3+5 XP

Over the integers, is $\forall x\, \exists y\,(x + y = 0)$ true?

Problem 4+5 XP

How many counterexamples does it take to disprove a "for all" statement?

Problem 5+5 XP

A service promises that every request gets a response within 200 ms. Which log entry disproves the promise?

Problem 6+5 XP

Which statement is the negation of $\forall x\,\big(P(x) \to Q(x)\big)$ ?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

In calculus, $\lim_{x \to a} f(x) = L$ means $\forall\varepsilon > 0\;\exists\delta > 0\;\forall x\,\big(0 < |x - a| < \delta \to |f(x) - L| < \varepsilon\big)$ . Which statement says the limit is not $L$ ?

Where it's used

Database queries ("find customers such that every order has shipped") and program specifications are written with quantifiers, and their negations are the test cases that break them.

Logical Equivalence and De Morgan's Laws Boolean Algebra and Logic Gates