Let Q(x, y) denote “x + y = 0” and let there be two quantifications given as…
2012
Let Q(x, y) denote “x + y = 0” and let there be two quantifications given as (i) ∃y∀x Q(x, y) (ii) ∀x∃y Q(x, y) where x & y are real numbers. Then which of the following is valid?
Answer: B. (i) is false & (ii) is true. — Concept — order of quantifiers. In first-order logic the order in which quantifiers are written changes the claim. The form ∃y∀x P(x, y) demands one single…
- A.
(i) is true & (ii) is false.
- B.
(i) is false & (ii) is true.
- C.
(i) is false & (ii) is also false.
- D.
both (i) & (ii) are true.
Attempted by 13 students.
Show answer & explanation
Correct answer: B
Concept — order of quantifiers. In first-order logic the order in which quantifiers are written changes the claim. The form ∃y∀x P(x, y) demands one single witness y that works for every x: y is fixed before x is looked at. The form ∀x∃y P(x, y) only demands that each x have some witness of its own: y may be chosen after x and may depend on it. The ∃∀ form is the stronger of the two — ∃y∀x P(x, y) always implies ∀x∃y P(x, y), while the converse implication fails in general.
Application — Q(x, y) is "x + y = 0" over the real numbers.
Read (i) ∃y∀x Q(x, y): suppose one fixed real number y = c satisfied x + c = 0 for every real x. That would force x = −c to hold simultaneously for every real x.
But x ranges over all real numbers, so take x = −c + 1. Then x + c = (−c + 1) + c = 1 ≠ 0, and the fixed c fails. No single real number cancels every real number, so (i) is false.
Read (ii) ∀x∃y Q(x, y): take an arbitrary real number x and choose y = −x, which is itself a real number.
Then x + y = x + (−x) = 0, so Q(x, y) holds for that pair. The witness −x depends on x, which is exactly what ∀x∃y permits, so (ii) is true.
Hence the valid reading is: (i) is false and (ii) is true.
Cross-check — the two readings side by side.
Statement | Order of choice | What it demands | Truth over the reals |
|---|---|---|---|
(i) ∃y∀x Q(x, y) | y first, then all x | one fixed real cancels every real | False |
(ii) ∀x∃y Q(x, y) | x first, then y | each real has its own cancelling partner | True |
Because ∃y∀x always implies ∀x∃y, a combination in which the ∃∀ form is true while the ∀∃ form is false can never occur for any predicate. The asymmetry seen here — the weaker form true, the stronger form false — is what uniqueness of additive inverses predicts: −x is the only real number that cancels x, and it moves as x moves, so no single y can serve all of them at once.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2