Logic
Quantifier Negation
How do you refute the claim 'All politicians are corrupt'? You need just one honest politician. How do you defend 'There are no honest politicians'? You'd need to check every single one. This asymmetry between ∀ and ∃ is fundamental to logic - and understanding it sharpens both argumentation and scientific thinking.
- **Science:** A single reproducible counterexample can overturn a universal scientific claim. This is falsification in action - the power of ∃x ¬P(x) against ∀x P(x).
- **Law:** 'The defendant was never at the crime scene' (∀t ¬AtScene(defendant, t)) - a single credible witness placing them there at the relevant time defeats this claim.
- **Mathematics:** Disproving conjectures requires one counterexample; proving them requires general proof. This asymmetry shapes mathematical research strategy.
Quantifier Negation
**Negating quantifiers** is one of the most practically important operations in logic. How do we negate 'All cats are black'? Not 'All cats are not black', but 'Some cat is not black'. The rules for negating ∀ and ∃ follow De Morgan's laws, extended from propositional to predicate logic.
**Intuition:** ¬∀x P(x) - 'not all x satisfy P' - means at least one x fails P, i.e. ∃x ¬P(x). And ¬∃x P(x) - 'no x satisfies P' - means all x fail P, i.e. ∀x ¬P(x). Negation flips the quantifier and moves inside.
What is the correct negation of ∀x (Even(x) → Divisible(x, 2))?
De Morgan For Quantifiers
**Duality of quantifiers:** ∀ and ∃ are duals of each other - just as ∧ and ∨ are duals in propositional logic. Negating one gives the other. This duality is fundamental: every universal statement has an existential counterpart, and vice versa.
**Connection to De Morgan's laws:** If we think of ∀x P(x) as a conjunction P(a) ∧ P(b) ∧ ... over all elements, then ¬∀x P(x) = ¬P(a) ∨ ¬P(b) ∨ ... = ∃x ¬P(x). The laws generalize from finite conjunction/disjunction to the infinite case.
Express ∃x P(x) using only ∀ and ¬.
Counterexamples
**A counterexample** is an instance that refutes a universal claim. Since ¬∀x P(x) ≡ ∃x ¬P(x), to disprove 'All A are B', we only need to find one A that is not B. This is the power of existential witnesses: a single example can defeat an unlimited universal claim.
**Asymmetry of proof burden:** To prove ∀x P(x) - must verify for ALL x (often infinitely many). To disprove ∀x P(x) - need ONE counterexample. This asymmetry explains why 'all' claims are risky and 'some' claims are easy to establish.
Many examples confirm a universal claim
A thousand examples support a universal claim but do not prove it. One counterexample disproves it
For 200 years, every observed swan was white - strengthening 'All swans are white'. One black swan in Australia refuted it. In mathematics, many examples can mislead: the Goldbach conjecture has been verified for billions of numbers but is not yet proven.
To disprove the claim 'All European capitals are also the largest cities in their countries', what do you need?
Key Ideas
- **De Morgan's laws for quantifiers**: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x). Negation flips the quantifier.
- **Duality**: ∀ and ∃ are duals - each can be defined in terms of the other with negation.
- **Counterexamples**: to disprove ∀x P(x), find one x₀ with ¬P(x₀). One example defeats the universal.
- **Asymmetry**: proving ∀ requires checking all cases; disproving requires just one counterexample.
Related Topics
Quantifier negation is central to formal proofs and argumentation:
- Quantifier Scope — Negation interacts with quantifier scope in nested formulas
- Proof by Contradiction — Often involves negating a universal statement to derive a contradiction
Вопросы для размышления
- Think of a universal claim you hold ('All X are Y'). What would a counterexample look like? Have you seriously looked for one?
- Why is the asymmetry between proving and disproving universal claims important for scientific skepticism?
- In everyday arguments, people often treat many confirming examples as proof. How does De Morgan's law expose this fallacy?