PROOF 27

Prove.

One counterexample brings a statement down

In propositional logic.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

∀x P(x) means that P(x) holds for every x in the domain.

Proof.

Unless the domain is specified, this statement has no meaning.convention

∎

Definition D2

A counterexample to ∀x P(x) is an element a of the domain satisfying ¬P(a).

Proof.

A counterexample is a single element, together with the fact that P fails at that one element.convention

∎

Definition D3

A natural number greater than 1 whose only divisors are 1 and itself is called a prime.

Proof.

If it has even one divisor that is neither 1 nor itself, it is not a prime.convention

∎

Theorem T1

∀x P(x) is false if and only if a counterexample exists.

Proof.

(1)Suppose there is a counterexample a; that is, ¬P(a).assumption, D2

(2)∃x ¬P(x)(1), A3

(3)¬∀x P(x)(2), A1

(4)Conversely, suppose ¬∀x P(x).assumption

(5)∃x ¬P(x)(4), A1

(6)There exists an a with ¬P(a), and it is a counterexample.(5), D2

(7)Both directions hold, so the two are equivalent.(3), (6)

∎

Theorem T2

An existential statement is made true by one example, but no number of examples makes a universal statement true.

Proof.

(1)If P(a) holds, then ∃x P(x) holds.A3

(2)Therefore an existential statement is settled by a single example.(1)

(3)∀x P(x) is a claim about every x in the domain.D1

(4)From ∀x P(x), P(a) follows for any a in the domain.A2

(5)Conversely, to obtain ∀x P(x) from P(a₁), …, P(aₙ), the domain must consist of those n elements only.(3), (4)

(6)If the domain is infinite, unchecked x remain.(5)

(7)If one of the remaining x is a counterexample, ∀x P(x) becomes false.(6), T1

(8)An existential statement ends with one example; a universal statement does not end with n examples.(2), (6), (7)

∎

Corollary C

Let P(n) be “n² + n + 41 is prime” with domain the integers ≥ 0. Then ∀n P(n) is false.

Proof.

(1)For n = 0, 1, …, 39, the numbers n² + n + 41 are all prime.N, D3

(2)For n = 40, 40² + 40 + 41 = 1681N

(3)1681 = 41 × 41, so 41 is a divisor that is neither 1 nor 1681.(2), N

(4)Therefore P(40) is false.(3), D3

(5)n = 40 is a counterexample to ∀n P(n).(4), D2

(6)Therefore ∀n P(n) is false.(5), T1

(7)The forty examples of (1) cannot prevent (6).(1), (6), T2

∎

Remark

Can A1 be removed from this proof?

That a counterexample brings a statement down is a rule, not a fact. Check which lines lose their justification when it is removed.