Lecture 7 — Direct Proof, Counterexample

lecture
discrete-math
proof

Pre-work: Video 009 (Direct Proofs and Counterexamples). First lecture of the number theory and methods of proof topic — see proof-techniques for the reference definitions, proof templates and the catalogue of common proof errors.

Learning goals

  • How to write a direct proof.
  • How to disprove a statement by exhibiting a counterexample.

Student questions and comments

What precise definitions should we know for proofs and disproofs? Know the definitions of even, odd, prime, composite, rational, divides — each is an “if and only if”, usable in both directions. They’re tabulated in proof-techniques.

How much detail to give in a proof? Demonstrate facts using the definitions.

Two facts used throughout, worth naming when you rely on them:

  • Fact: the sum, difference, and product of integers is an integer.
  • Fact: every integer is either even or odd — \(\mathbb{Z}\) splits into \(\mathbb{Z}^{\text{even}}\) and \(\mathbb{Z}^{\text{odd}}\).

Note on “not prime”: for \(n \in \mathbb{Z}^{>1}\), “\(n\) not prime” means “\(n\) composite”. For \(n \in \mathbb{Z}\) generally, “\(n\) not prime” means “composite or \(n \leq 1\)” — the primes and composites together only cover \(\mathbb{Z}^{\geq 2}\).

Proof or disproof of \(\forall x \in D, P(x) \to Q(x)\)

Recall the truth table — the only row that makes \(p \to q\) false is \(p\) true, \(q\) false:

\(p\) \(q\) \(p \to q\)
T T T
T F F
F T T
F F T

Direct proof (shows the statement is true):

Let \(x \in D\) and suppose \(P(x)\). \(\dots\) Hence \(Q(x)\). \(\square\)

Disproof by counterexample (shows the statement is false):

Let \(x = \cdots\). Then \(x \in D\) and \(P(x)\) is true. However, \(Q(x)\) is false. So \(x\) is a counterexample and the statement is false.

Student comment: why do you suppose that \(P(x)\) is true, when \(P(x) \to Q(x)\) would still be true if \(P(x)\) is false? We just need to rule out the case that \(P(x)\) is true and \(Q(x)\) is false — so we suppose \(P(x)\) is true and prove that in this case \(Q(x)\) must also be true. The other rows of the table are true for free.

Q1 from the pre-class questions

Which values for \(m\) and \(n\) give a counterexample disproving: for all integers \(m\) and \(n\), if \(2m + n\) is odd, then \(m\) and \(n\) are both odd?

a. \(m = 3, n = 5\) \(m, n\) both odd — conclusion holds not a counterexample
b. \(m = 3, n = 6\) \(2(3) + 6 = 12\) even — hypothesis fails not a counterexample
c. \(m = 4, n = 5\) \(2(4) + 5 = 13\) odd, and \(m\) is even counterexample
d. \(m = 4, n = 6\) \(2(4)+6 = 14\) even — hypothesis fails not a counterexample

For a counterexample to \(p \to q\) we require \(p\) true and \(q\) false.

Example proof

\(\forall n \in \mathbb{Z}\), if \(n\) is odd then \(3n + 2\) is odd.

Proof. Let \(n \in \mathbb{Z}\) and suppose \(n\) is odd. ← hypothesis Since \(n\) is odd, \(n = 2k + 1\) for some \(k \in \mathbb{Z}\). Now \(3n + 2 = 3(2k+1) + 2 = 6k + 5 = 2(3k + 2) + 1\). Since \(k \in \mathbb{Z}\), we have \(3k + 2 \in \mathbb{Z}\). Hence \(3n + 2\) is odd. ← conclusion \(\square\)

Note the shape: state the hypothesis, unfold the definition, do the algebra so the target definition is visible, confirm the witness is an integer, then state the conclusion.

Activity 1

For any integer \(x\), if \(x + 6 = 4y\) for some integer \(y\), then \(\frac{x}{2}\) is an odd integer.

Proof. Let \(x \in \mathbb{Z}\) and suppose \(x + 6 = 4y\) for some \(y \in \mathbb{Z}\). Now \(x = 4y - 6\), so \(x = 2(2y - 3)\). Hence \(\frac{x}{2} = \frac{2(2y-3)}{2} = 2y - 3 = 2(y-1) - 1\). Thus, because \(y \in \mathbb{Z}\), we have \(2y - 3 \in \mathbb{Z}\) so \(\frac{x}{2} \in \mathbb{Z}\); and \(y - 1 \in \mathbb{Z}\), so by definition \(\frac{x}{2}\) is odd. \(\square\)

Both halves are needed: that \(\frac{x}{2}\) is an integer, and that it has the odd form. (\(2(y-1) - 1\) uses the \(n = 2k - 1\) form of odd; \(2(y-2)+1\) works just as well.)

Activity 2 — prove or disprove

(a) There are distinct integers \(m\) and \(n\) such that \(\frac{1}{m} + \frac{1}{n}\) is an integer.

True. Take \(m = 1\) and \(n = -1\). Then \(\frac{1}{m} + \frac{1}{n} = 1 + (-1) = 0 \in \mathbb{Z}\).

(b) \(\forall n \in \mathbb{Z}^{\geq 2}\), \(n\) is composite or \(n + 1\) is composite.

False. Take \(n = 2\): then \(n = 2\) and \(n + 1 = 3\), which are both prime.

(c) For each integer \(n \geq 2\), the product of the first \(n\) prime numbers minus 1 is prime.

False. (Hint: try \(n = 2, 3, 4, \dots\)) Take \(n = 4\): \(2 \cdot 3 \cdot 5 \cdot 7 - 1 = 209 = 11 \cdot 19\), which is composite.

Note that \(n = 2\) and \(n = 3\) both work, which is exactly why “arguing from examples” is on the list of common proof errors in proof-techniques.

Activity 4 — disprove by proving the negation

Show that \(\exists n \in \mathbb{Z}^+\) such that \(n^2 + 5n + 6\) is prime is false, by proving the negation.

The statement is existential, so a single counterexample won’t do — the negation is universal and must be proved outright:

Negation: \(\forall n \in \mathbb{Z}^+\), \(n^2 + 5n + 6\) is composite.

Proof of the negation. Let \(n \in \mathbb{Z}^+\). Now \(n^2 + 5n + 6 = (n+2)(n+3)\). Since \(n \geq 1\) we have \(n + 2 > 1\) and \(n + 3 > 1\). Thus \(n^2 + 5n + 6\) is composite. \(\square\)

Because \(n \geq 1\) forces \(n^2 + 5n + 6 \geq 2\), “not prime” here really does mean “composite”.

See also