Questions: Quantifier Notation and Basic Semantics

Question 1

Over the domain of integers, which of the following statements is TRUE?

• A. ∃y ∀x (y > x) — there exists an integer greater than all integers
• B. ∀x ∃y (y = x + 1) — for every integer, there exists an integer exactly one greater
• C. ∀x ∀y (x < y) — every integer is strictly less than every other integer
• D. ∃x ∀y (x < y) — there exists a smallest integer

Answer: (B)

∀x ∃y (y = x + 1) is true: for any integer x, choose y = x + 1, which satisfies the predicate. The key is that y is chosen after and in terms of x — the existential witness can depend on the universal variable. The other three are false: the integers have no maximum (ruling out option A), no pair satisfies x < y for all y simultaneously (option C), and the integers are unbounded below with no smallest member (option D).

Question 2

The formula ∃x (x² = 2) changes truth value depending on the domain of discourse. Over which domain is it TRUE?

• A. The natural numbers ℕ, since 1² = 1 and 2² = 4 bracket the value 2
• B. The integers ℤ, since both positive and negative values are available
• C. The real numbers ℝ, since √2 is a real number satisfying (√2)² = 2
• D. The rational numbers ℚ, since √2 can be approximated arbitrarily closely by rationals

Answer: (C)

√2 is irrational, so it belongs to neither ℕ, ℤ, nor ℚ. The formula is false over all three of those domains — no element in any of them squares to exactly 2. Over ℝ, the number √2 exists as a real number and satisfies the predicate, making the formula true. This illustrates that quantifiers always range over a specific domain of discourse: the same formula can be true in one domain and false in another, so specifying the domain is part of giving a quantified formula a meaning.

Question 3

In the formula ∀x P(x), substituting a different variable name produces a logically different formula — for instance, ∀z P(z) says something distinct from ∀x P(x).

• T. True
• F. False

Answer: False

False. Bound variables are mere placeholders (dummy variables). The quantifier ∀ binds the variable, and the specific letter chosen carries no semantic content — ∀x P(x) and ∀z P(z) say exactly the same thing: 'for every object in the domain, P holds.' This is analogous to how ∫₀¹ x dx and ∫₀¹ t dt compute the same integral. Only *free* variables — those not bound by any quantifier — carry meaning and affect a formula's truth value under an interpretation.

Question 4

Swapping the order of two different quantifiers in a formula (∀ and ∃) can change whether the formula is true or false.

• T. True
• F. False

Answer: True

True, and this is among the most important structural facts about quantifiers. ∀x ∃y (y > x) says 'for every integer, there is a larger one' — true, since for any x choose y = x + 1. ∃y ∀x (y > x) says 'there exists a single integer larger than every integer' — false, since the integers are unbounded. In the first formula, the existential witness y can depend on the specific choice of x; in the second, one fixed y must exceed all x simultaneously. This dependency structure is precisely what quantifier order encodes.

Question 5

Explain in your own words why ∀x ∃y (y > x) and ∃y ∀x (y > x) make fundamentally different claims, and identify which is true over the integers.

Model answer: ∀x ∃y (y > x) says: for each integer x you choose, I can find some y greater than it. The y is allowed to depend on x — for x = 5, pick y = 6; for x = 1000, pick y = 1001. This is true over the integers. ∃y ∀x (y > x) says: there exists a single fixed y that is greater than every integer simultaneously. This is false, because the integers are unbounded — no finite number exceeds all of them. The order controls whether the existential witness can depend on the universal variable.

The key distinction is dependency: in ∀x ∃y φ(x, y), the witness for y is chosen after x is fixed and may depend on x. In ∃y ∀x φ(x, y), y must be fixed before x ranges over the domain, so one y must satisfy the predicate for every possible x at once. This dependence structure is invisible when the formulas are read in loose English ('for all x there exists y' vs 'there exists y for all x') but is exactly what the quantifier order encodes formally.