Recipe
Check a universal claim over a finite domain
Use when: you're given \forall x\, P(x) over a finite, listable domain and must decide whether it's true
Goal: a settled verdict: true only if every domain element checks out, false the moment one counterexample turns up
Taught in The universal quantifier
Quick recipe
-
1
Write out every domain element. Before working through it in order, it can help to test the largest, smallest, or otherwise unusual values first, since a false claim often fails at an edge case.
Example
Domain \{1,2,3,4,5\}, claim \forall x, x^2 < 30. The largest value grows fastest, so check x=5 first: 5^2=25, and 25<30 is true.
Why: catching a fast failure early can settle the claim without scanning the whole domain, though passing at one value never proves the rest.
-
2
Work through the rest of the domain, substituting each value into P(x) and simplifying until its truth value is clear.
Example
x=1: 1<30, true. x=2: 4<30, true. x=3: 9<30, true. x=4: 16<30, true.
Why: a universal claim requires literally every element to pass, so any one left unchecked leaves the claim unverified.
-
3
If every element passed, the universal claim is true. If even one element failed, that element is a counterexample, and the claim is false.
Example
All five elements of \{1,2,3,4,5\} passed x^2<30, so \forall x \in \{1,\ldots,5\}, x^2<30 is true.
- every element passed — the claim is true over this domain.
- at least one element failed — the claim is false; report that element as the counterexample.
Why: \forall x\, P(x) is true exactly when its truth set equals the whole domain, and false the instant one element breaks it.
Common mistakes
- Stopping after checking only a few elements and declaring the claim true without finishing the domain.
- Treating one passing element as proof, the way a witness would for an existential claim, when a universal claim needs all of them.
- Continuing to check further elements after already finding one that fails -- unnecessary once a counterexample turns up.
- Reporting the counterexample as P(c) instead of the actual failing element c itself.