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

”xx is even” is neither true nor false until xx is chosen. Such a sentence is a predicate, written P(x)P(x). Quantifiers turn it into a statement:

SymbolRead asTrue when
∀x P(x)\forall x\, P(x)for all xx, P(x)P(x)P(x)P(x) holds for every xx in the domain
∃x P(x)\exists x\, P(x)there exists xx with P(x)P(x)P(x)P(x) holds for at least one xx

The domain is the set xx ranges over, and it matters. Over the integers, ∃x (2x=1)\exists x\,(2x = 1) is false; over the rationals, x=12x = \tfrac{1}{2} makes it true.

Negation. To deny that everything has a property, it is enough to find one thing that lacks it:

¬ ∀x P(x)≡∃x ¬P(x)¬ ∃x P(x)≡∀x ¬P(x)\neg\,\forall x\, P(x) \equiv \exists x\, \neg P(x) \qquad \neg\,\exists x\, P(x) \equiv \forall x\, \neg P(x)

Why the order of quantifiers matters

Over the integers, compare

∀x ∃y (y>x)and∃y ∀x (y>x)\forall x\, \exists y\, (y > x) \qquad\text{and}\qquad \exists y\, \forall x\, (y > x)

The first says every integer has some larger integer: true, take y=x+1y = x + 1. The second says one integer is larger than every integer, itself included: false. In ∀x ∃y\forall x\, \exists y, the choice of yy may depend on xx. In ∃y ∀x\exists y\, \forall x, one yy must be fixed first and then work for every xx. Swapping a ∀\forall and an ∃\exists 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

  1. Over the integers, is ∀x (x2≥x)\forall x\, (x^2 \ge x) true?

    Answer

    Yes

    Full solution

    x2−x=x(x−1)x^2 - x = x(x - 1), a product of two consecutive integers, is never negative.

  2. Over the real numbers, is ∀x (x2≥x)\forall x\, (x^2 \ge x) true?

    Answer

    No

    Full solution

    x=12x = \tfrac{1}{2} gives 14<12\tfrac{1}{4} < \tfrac{1}{2}.

    Any xx strictly between 00 and 11 is a counterexample.

  3. Negate ∀x ∃y (x+y=0)\forall x\, \exists y\, (x + y = 0).

    Answer

    ∃x ∀y (x+y≠0)\exists x\, \forall y\, (x + y \ne 0)

    Full solution

    Flip each quantifier from left to right and negate the predicate.

  4. Over the integers, is ∃y ∀x (x+y=x)\exists y\, \forall x\, (x + y = x) true?

    Answer

    Yes

    Full solution

    With y=0y = 0.

    One fixed yy works for every xx, which is what ∃y ∀x\exists y\, \forall x requires.

  5. Write “some integer is larger than 100100 and even” in symbols.

    Answer

    ∃n (n>100∧n is even)\exists n\, (n > 100 \wedge n \text{ is even})

    Full solution

    An ∃\exists statement pairs naturally with “and”.

  6. Write “every prime greater than 22 is odd” in symbols.

    Answer

    ∀p ((p is prime∧p>2)→p is odd)\forall p\, \bigl((p \text{ is prime} \wedge p > 2) \rightarrow p \text{ is odd}\bigr)

    Full solution

    A ∀\forall statement pairs naturally with “if … then”.

  7. 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

    ¬ ∀s P(s)≡∃s ¬P(s)\neg\,\forall s\, P(s) \equiv \exists s\, \neg P(s).

  8. 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 ∃y ∀x≠y (y>x)\exists y\, \forall x \ne y\, (y > x) gives ∀y ∃x≠y (x≥y)\forall y\, \exists x \ne y\, (x \ge y). 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.

What to learn next