Questions: Predicates and Quantifiers

Question 1

In the domain of all integers, which statement is true?

• A. ∀x ∃y (y > x) — for every integer, there exists an integer greater than it
• B. ∃y ∀x (y > x) — there exists a single integer that is greater than every integer
• C. Both statements express the same claim — quantifier order affects notation but not meaning
• D. Neither statement is meaningful because y > x requires a fixed comparison value

Answer: (A)

∀x ∃y (y > x) is true: for any integer you pick, you can always find a larger one (just add 1). But ∃y ∀x (y > x) claims there is one fixed integer greater than ALL integers — this would require a largest integer, which doesn't exist. The two statements contain the same predicate and the same quantifiers, but reversing their order changes the truth value. In the first, y can be chosen after x is known and may depend on it; in the second, y must be chosen first and work for every x simultaneously.

Question 2

What is the correct negation of 'Every student in the class passed the exam'?

• A. No student in the class passed the exam
• B. Most students in the class did not pass the exam
• C. At least one student in the class did not pass the exam
• D. Every student in the class failed the exam

Answer: (C)

The negation of ∀x P(x) is ∃x ¬P(x): to falsify 'every student passed,' you only need one counterexample — one student who did not pass. Options A and D assert something far stronger than mere falsity of the original. This is the core negation rule: ¬∀x P(x) ≡ ∃x ¬P(x), and it's the quantifier analogue of De Morgan's laws.

Question 3

The negation of ∀x P(x) is ∀x ¬P(x).

• T. True
• F. False

Answer: False

The correct negation is ∃x ¬P(x) — there exists at least one x for which P fails. ∀x ¬P(x) means P fails for every x, which is a much stronger claim. To negate a universal statement, you flip the quantifier from ∀ to ∃ and negate the predicate: ¬∀x P(x) ≡ ∃x ¬P(x). You cannot simply attach ¬ to P while keeping ∀.

Question 4

In the domain of integers, ∀x ∃y (x + y = 0) and ∃y ∀x (x + y = 0) have different truth values.

• T. True
• F. False

Answer: True

∀x ∃y (x + y = 0) is true: for any integer x, choose y = −x. ∃y ∀x (x + y = 0) is false: it claims one fixed y satisfies the equation for every x simultaneously — but y = −x changes with x, so no single y works for all x. Same predicate, same quantifiers, different order — and the statements go from true to false. This is why quantifier order is not interchangeable.

Question 5

Why does the order of quantifiers matter in nested quantifier expressions? Illustrate with an example showing how reversing the order changes meaning.

Model answer: Quantifier order determines dependency: the inner variable may depend on the outer variable's choice. In ∀x ∃y P(x,y), y is chosen after x is fixed and may depend on it. In ∃y ∀x P(x,y), y must be chosen first and must work for all x. Example: ∀x ∃y (y > x) is true in the integers (for each x, pick y = x + 1), but ∃y ∀x (y > x) is false (no single integer exceeds all integers). The dependency structure changes entirely with the order.

This dependency is fundamental to all quantified mathematics. The definition of a limit — ∀ε > 0 ∃δ > 0 … — requires exactly this reading: δ is chosen in response to ε. Reversing the order would claim a single δ works for all ε, which is false for non-uniform continuity. Reading quantifiers left-to-right as a sequence of choices with dependencies is the core skill.