First-order logic extends the propositional logic of Chapter 2 with two new tools: predicates like Triangle(x) or StudyAt(p, BZU), and quantifiers ∀ (for all) and ∃ (there exists). The pair lets us reason about an entire domain in a single statement.
Where it is used. Quantified statements appear in every later definition and theorem in this course: every integer is rational, some prime is even, for every ε > 0 there exists δ > 0 such that …. They are the language of mathematics, of SQL aggregation, of program contracts, and of model checking.
A statement from Chapter 2 was either true or false. A predicate P(x₁, x₂, …, xₙ) waits to become one until its variables receive values. The number of variables is the predicate's arity.
Two new pieces of vocabulary make the jump from propositional to first-order logic possible:
(1) ∀x ∈ D, x² ≥ 0. Squares: (−2)² = 4, (−1)² = 1, 0² = 0, 1² = 1, 2² = 4. All ≥ 0. True.
(2) ∀x ∈ D, x² > 0. False. Counterexample: x = 0 gives x² = 0, which is not strictly greater than 0.
(3) ∃x ∈ D, x³ = 1. True. Witness: x = 1, since 1³ = 1.
(1) ∀x ∈ ℝ, (x > 0) ∨ (x < 0) ∨ (x = 0).
(2) "No P is a Q" is equivalent to "every P is not a Q":
∀x, Irrational(x) → ∼Integer(x)
Equivalently: ∀x ∈ ℝ, Irrational(x) → x ∉ ℤ.
Reminder: "No X are Y" is the Section 3.1 trap. The formalization is a universal with a negated conclusion, never an existential.
(1) ∀x, Square(x) → Blue(x). Squares in the world: e, g, h, j. False. Counterexample: h is a square but its colour is black, not blue.
(2) ∃x, Circle(x) ∧ Blue(x). True. Witness: b is a blue circle.
(3) ∀x, Triangle(x) → Blue(x). Triangles in the world: d, f, i, k. All blue. True.
How do we deny a quantified claim? The first instinct, "no X are Y" to negate "all X are Y", is wrong. One counterexample is enough to break a universal, and one witness is enough to make an existential true.
The two negation theorems for quantifiers are the workhorses of this section. They look like De Morgan's laws and behave like them.
(1) ∼(∀x ∈ ℝ, x > 1/x) ≡ ∃x ∈ ℝ such that x ≤ 1/x.
(The predicate's domain implicitly excludes x = 0 for 1/x to be defined.)
(2) ∼(∃n ∈ ℤ, Prime(n) ∧ Even(n)) ≡ ∀n ∈ ℤ, ∼Prime(n) ∨ ∼Even(n). In words: every integer is either not prime or not even (or both).
(3) ∼(∀a ∈ ℤ, (a − 1)/a is not an integer) ≡ ∃a ∈ ℤ such that (a − 1)/a is an integer. Witness: a = 1 gives (1 − 1)/1 = 0, which is an integer. So the original is false and its negation is true.
Original: ∀n ∈ ℤ, P(n) → Q(n) where P(n) is "n is even" and Q(n) is "n² is even". True.
Contrapositive: ∀n ∈ ℤ, ∼Q(n) → ∼P(n) · "if n² is not even, then n is not even", equivalently "if n² is odd, then n is odd." True · equivalent to the original.
Converse: ∀n ∈ ℤ, Q(n) → P(n) · "if n² is even, then n is even." Happens to be true, but does not follow from the original; a separate proof is needed.
Inverse: ∀n ∈ ℤ, ∼P(n) → ∼Q(n) · "if n is not even, then n² is not even." Also true, also separate; equivalent to the converse, not to the original.
Key point. Equivalence between the original and its variants is a question of logical form, not whether each individual variant happens to be true. Original ≡ contrapositive always.
The hypothesis Pentagon(x) ∧ Red(x) requires x to be both a pentagon and red.
So the hypothesis is false for every x in the domain. A conditional with a false hypothesis is automatically true (vacuously true), regardless of what the conclusion says.
Sanity check. The statement remains vacuously true even if we replace the conclusion: ∀x, (Pentagon(x) ∧ Red(x)) → ∼SameColor(x, a) is also vacuously true. Both hold at once, because no x ever triggers the hypothesis.
So far one quantifier at a time. Real definitions in mathematics nest them: "for every ε > 0 there exists δ > 0 such that …". The two big ideas of Section 3.3:
(1) Opponent picks any x from D. You respond with y = −x. Check every case:
x = −2 → y = 2, x + y = 0 x = −1 → y = 1, x + y = 0 x = 0 → y = 0, x + y = 0 x = 1 → y = −1, x + y = 0 x = 2 → y = −2, x + y = 0
Every x has a partner. True. The y depends on x: that is what ∀∃ allows.
(2) You commit to one x before any y is offered. Pick x = 0. Then 0 · y = 0 for every y in D. True. Here x is fixed first, the hallmark of ∃∀.
(1) Walk through left-to-right, flipping each quantifier:
The original is true (every x has additive inverse −x), so its negation is false.
(2)
The original claims one universal y zeros out every x, false. The negation is true.
Compare the originals. (1) says "every x has some inverse" (true). (2) says "one y is the inverse of every x" (false). Same predicate, different quantifier order, opposite truth values.
(a) Truth value. Triangles in Figure 3.3.1: d, f, i. Squares: e, g, h, j. Try each triangle:
False. No single triangle is above every square.
(b) Formal notation. ∃x (Triangle(x) ∧ ∀y (Square(y) → Above(x, y)))
(c) Negation · push ∼ all the way in:
In English: "for every triangle x, there is a square y such that x is not above y." This matches the falsity of the original.