Questions: Existential Quantification: Meaning and Scope

Question 1

In a domain of 1,000 objects, the formula ∃x P(x) has been shown to be false. What must be true?

• A. Exactly one object fails to satisfy P(x)
• B. A majority of objects fail to satisfy P(x)
• C. Every object in the domain fails to satisfy P(x)
• D. The predicate P is undefined for some objects in the domain

Answer: (C)

∃x P(x) is true if and only if at least one object in the domain satisfies P. Therefore, for ∃x P(x) to be *false*, it must be the case that no object satisfies P — P(a) must be false for every a in the domain. This is captured by the dual law: ¬∃x P(x) ≡ ∀x ¬P(x). Finding a single counterexample is enough to disprove a universal statement (∀x P(x)), but disproving an existential requires checking all objects. The asymmetry between existential and universal is central to logic and mathematics.

Question 2

Consider two formulas: (A) ∃x (P(x) ∧ Q(x)) and (B) (∃x P(x)) ∧ (∃x Q(x)). For formula B to be true but formula A to be false, what must be the case?

• A. This is impossible — if B is true then A must also be true
• B. The domain must contain fewer than two objects
• C. Some object satisfies P and some object satisfies Q, but no single object satisfies both
• D. The predicate P must be a subset of ¬Q

Answer: (C)

Formula A requires a single witness that simultaneously satisfies both P and Q. Formula B only requires that some object satisfies P (possibly different from the one satisfying Q) and some object satisfies Q. If P is satisfied only by object a and Q is satisfied only by object b, and a ≠ b, then B is true but A is false — no single object satisfies both. This illustrates the critical difference in scope: in ∃x (P(x) ∧ Q(x)), x is bound once and must serve as a common witness, while in (∃x P(x)) ∧ (∃x Q(x)), the two occurrences of x are independently bound.

Question 3

The formula ¬∃x P(x) is logically equivalent to ∀x ¬P(x) — saying 'nothing has property P' means the same as saying 'everything lacks property P.'

• T. True
• F. False

Answer: True

True. This is the quantifier dual law, analogous to De Morgan's law for propositional logic. If no object has property P (¬∃x P(x)), then every object in the domain lacks P (∀x ¬P(x)), and vice versa. The dual laws — ¬∃x φ ≡ ∀x ¬φ and ¬∀x φ ≡ ∃x ¬φ — allow you to push negation through quantifiers by flipping the quantifier type. Just as ¬(A ∨ B) ≡ ¬A ∧ ¬B in propositional logic, negating an existential gives a universal and vice versa.

Question 4

In the formula ∃x (P(x) ∧ Q(x)), the variable x is bound twice — once for P and once for Q — so the witness satisfying P may be different from the witness satisfying Q.

• T. True
• F. False

Answer: False

False. There is only one binding of x in this formula, governed by the single quantifier ∃x. The scope of ∃x is the entire formula P(x) ∧ Q(x), and x refers to the same object throughout. The single witness must satisfy both P and Q simultaneously. This is in contrast to (∃x P(x)) ∧ (∃x Q(x)), where two separate quantifiers each independently bind x, allowing different witnesses for P and Q. Scope determines whether a witness is shared — one quantifier means one (shared) witness.

Question 5

A logician claims: 'I can disprove ∃x P(x) by finding a single object a in the domain for which P(a) is false.' What is wrong with this reasoning, and what would a correct disproof require?

Model answer: The logician is confusing the rules for disproving existential and universal statements. Finding one object that fails P(a) disproves ∀x P(x) (universal) — a single counterexample refutes a universal claim. But ∃x P(x) only requires one witness to make it true; finding one object that fails P says nothing about whether some other object might satisfy P. To disprove ∃x P(x), you must show P(a) is false for every object a in the domain — no exceptions. This is equivalent to proving ∀x ¬P(x).

The asymmetry is fundamental: universal claims are easy to refute (one counterexample) but hard to prove (must cover all cases). Existential claims are easy to prove (one witness) but hard to refute (must rule out all possible witnesses). This asymmetry underlies many deep results in logic and mathematics, including why some mathematical existence proofs are non-constructive — you prove a witness exists without exhibiting one.