Discrete Math · Undergraduate
Predicate Logic: Quantifiers ∀ and ∃ and Their Negations
Quick answer
Propositional logic handles whole statements; predicate logic looks inside them. A predicate P(x) becomes true or false once x is chosen. The universal quantifier ∀x P(x) says P holds for every x in the domain, and the existential quantifier ∃x P(x) says it holds for at least one. Negating flips the quantifier and negates the predicate: ¬∀x P(x) is ∃x ¬P(x). With two quantifiers the order matters: ∀x ∃y (y > x) is true for the integers, but ∃y ∀x (y > x) is false.
What you'll learn
- Translate statements with quantifiers between English and symbols
- Decide the truth of a quantified statement over a given domain
- Negate quantified statements correctly
- Explain how the order of nested quantifiers changes meaning
Statements about every or some
” is even” is neither true nor false until is chosen. Such a sentence is a predicate, written . Quantifiers turn it into a statement:
| Symbol | Read as | True when |
|---|---|---|
| for all , | holds for every in the domain | |
| there exists with | holds for at least one |
The domain is the set ranges over, and it matters. Over the integers, is false; over the rationals, makes it true.
Negation. To deny that everything has a property, it is enough to find one thing that lacks it:
Why the order of quantifiers matters
Over the integers, compare
The first says every integer has some larger integer: true, take . The second says one integer is larger than every integer, itself included: false. In , the choice of may depend on . In , one must be fixed first and then work for every . Swapping a and an can change a true statement into a false one. Two quantifiers of the same kind can be swapped freely.
Worked examples
Common mistakes
Practice problems
-
Over the integers, is true?
Answer
Yes
Full solution
, a product of two consecutive integers, is never negative.
-
Over the real numbers, is true?
Answer
No
Full solution
gives .
Any strictly between and is a counterexample.
-
Negate .
Answer
Full solution
Flip each quantifier from left to right and negate the predicate.
-
Over the integers, is true?
Answer
Yes
Full solution
With .
One fixed works for every , which is what requires.
-
Write “some integer is larger than and even” in symbols.
Answer
Full solution
An statement pairs naturally with “and”.
-
Write “every prime greater than is odd” in symbols.
Answer
Full solution
A statement pairs naturally with “if … then”.
-
Negate “every student in the class has a phone” in plain English.
Answer
Some student in the class does not have a phone.
Full solution
.
-
A student negates “there is a number greater than every other number” as “there is a number less than every other number”. What is wrong?
Answer
The negation is “for every number, some other number is at least as large”.
Full solution
Negating gives . Changing “greater” to “less” does not negate anything.
Frequently asked questions
What do ∀ and ∃ mean?
∀ means 'for all' and ∃ means 'there exists'. ∀x P(x) claims P(x) for every x in the domain; ∃x P(x) claims it for at least one.
How do you negate a statement with a quantifier?
Flip the quantifier and negate what follows: ¬∀x P(x) is ∃x ¬P(x), and ¬∃x P(x) is ∀x ¬P(x).
Does the order of quantifiers matter?
Yes, when they are different. ∀x ∃y means y may depend on x; ∃y ∀x means one y must work for every x at once.
How do you prove or disprove a ∀ statement?
Prove it with an argument that works for an arbitrary x. Disprove it with a single counterexample.
Why does the domain matter?
The same statement can be true over one domain and false over another. ∃x (x² = 2) is true over the reals and false over the rationals.