Training Set Theory & Logic Quantifiers & Predicate Logic
3 / 5

Quantifiers & Predicate Logic

24 min Set Theory & Logic
Quantifiers extend propositional logic to predicate logic, which can express statements about all elements or the existence of elements in a domain. The universal quantifier ∀x P(x) means 'for every x, P(x) holds,' while the existential quantifier ∃x P(x) means 'there exists at least one x for which P(x) holds.' Negating quantifiers swaps them: ¬(∀x P(x)) ≡ ∃x ¬P(x), and ¬(∃x P(x)) ≡ ∀x ¬P(x). Nested quantifiers like ∀x ∃y allow expressing relationships (e.g., 'for every person, there exists someone they admire'), and the order of mixed quantifiers matters—swapping ∀ and ∃ can change the meaning entirely. Predicate logic forms the foundation of mathematical proof and formal verification in computer science.

Quantifiers & Predicate Logic

Predicate

A statement containing a variable: $P(x)$ = "$x$ is even." Becomes a proposition when $x$ is assigned a value or quantified.

Quantifiers
  • Universal: $\forall x\, P(x)$ — "For all $x$, $P(x)$"
  • Existential: $\exists x\, P(x)$ — "There exists an $x$ such that $P(x)$"
Negating Quantifiers

$$\lnot (\forall x\, P(x)) \equiv \exists x\, \lnot P(x)$$

$$\lnot (\exists x\, P(x)) \equiv \forall x\, \lnot P(x)$$

Example 1

Symbolize: "Every integer is either even or odd."

  1. $\forall n \in \mathbb{Z}, \; (2 \mid n) \lor (2 \nmid n)$.
Example 2

Negate: "All students passed the exam."

  1. Original: $\forall s\, P(s)$.
  2. Negation:
  3. $\exists s\, \lnot P(s)$ — "Some student did not pass."
Example 3

Negate: $\exists x\,(x^2 < 0)$.

  1. $\forall x\,(x^2 \geq 0)$ — true for real numbers.

Practice Problems

1. Symbolize: "There exists a prime number greater than 100."
2. Negate: $\forall x\,(x > 0)$.
3. Is $\forall x \in \mathbb{R},\, x^2 \geq 0$ true?
4. Negate: "No dog can fly."
5. Symbolize: "For every $\epsilon > 0$, there exists $\delta > 0$..."
6. True or false: $\exists x \in \mathbb{R},\, x^2 = -1$.
7. Negate: $\exists x\, (x > 5 \land x < 3)$.
8. What is the domain of discourse?
9. Translate: $\forall x\, (P(x) \to Q(x))$.
10. Negate: $\forall x\, \exists y\, (x+y=0)$.
11. Is $\exists x\, (x = x+1)$ true for reals?
12. Write using quantifiers: "Between any two reals there is a rational."
Show Answer Key

1. $\exists p\,(\text{prime}(p) \land p > 100)$

2. $\exists x\,(x \leq 0)$

3. True

4. "There is a dog that can fly." ($\exists d\, F(d)$)

5. $\forall \epsilon > 0\, \exists \delta > 0\, ...$

6. False (in $\mathbb{R}$)

7. $\forall x\, (x \leq 5 \lor x \geq 3)$

8. The set of values $x$ can take

9. "For all $x$, if $P(x)$ then $Q(x)$"

10. $\exists x\, \forall y\, (x+y \neq 0)$

11. False

12. $\forall a,b \in \mathbb{R}\,(a < b \to \exists q \in \mathbb{Q},\, a < q < b)$

∀ Quantifier Evaluator
Domain {1, …, N}
Satisfying elements
Result
Propositional Logic & Truth Tables Methods of Proof