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…

  1. A.

    (i) is true & (ii) is false.

  2. B.

    (i) is false & (ii) is true.

  3. C.

    (i) is false & (ii) is also false.

  4. 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.

  1. 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.

  2. 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.

  3. Read (ii) ∀x∃y Q(x, y): take an arbitrary real number x and choose y = −x, which is itself a real number.

  4. 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.

  5. 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

Loading lesson…