Lecture 9 — Proof by Contraposition, Rational Numbers

lecture
discrete-math
proof
rational-numbers

Pre-work: Video 011 (Proof by Contraposition), Video 012 (Rational Numbers). Completes the set of four methods — see proof-techniques for the full comparison, and rational-and-irrational-numbers for the \(\mathbb{Q}\) / \(\overline{\mathbb{Q}}\) definitions and closure results.

Learning goals

  1. Understand the definitions of rational and irrational numbers.
  2. Gain fluency in proof techniques (direct proof, proof by contradiction and proof by contraposition).

Recall: \(r \in \mathbb{Q} \iff r = \frac{a}{b}\) for some \(a, b \in \mathbb{Z}\) where \(b \neq 0\); and \(r \in \overline{\mathbb{Q}} \iff r \notin \mathbb{Q}\), where \(\overline{\mathbb{Q}} = \mathbb{R} \setminus \mathbb{Q}\). So \(\frac{3}{4} \in \mathbb{Q}\), while \(\sqrt{2} \in \overline{\mathbb{Q}}\) and \(\pi \in \overline{\mathbb{Q}}\).

Student questions and comments

What is the relationship between proof by contradiction and proof by contraposition?

How do we decide if we should use a direct proof, proof by contradiction or proof by contraposition?

Both are answered by working the activities below — each one is annotated with which methods work and which get stuck.

The four methods

Method Shape Shows
Direct proof Let \(x \in D\) and suppose \(P(x)\). \(\dots\) Hence \(Q(x)\). true
Disproof by counterexample Let \(x = \cdots\). Then \(x \in D\) and \(P(x)\) is true. However \(Q(x)\) is false. false
Proof by contradiction Suppose \(\exists x \in D\) such that \(P(x)\) is true but \(Q(x)\) is false. \(\dots\) Hence something obviously wrong. true
Proof by contraposition We prove \(\forall x \in D, \sim Q(x) \to \sim P(x)\). Let \(x \in D\) and suppose \(\sim Q(x)\). \(\dots\) Hence \(\sim P(x)\). true

Contraposition is valid because \(p \to q \equiv \sim q \to \sim p\) (see conditional-statements).

The last lemma from Video 12, by contraposition

Lemma: the sum of any rational number and any irrational number is irrational.

Symbolically, either of:

\[\forall r, s \in \mathbb{R}, \text{ if } r \in \mathbb{Q} \text{ and } s \in \overline{\mathbb{Q}} \text{ then } r + s \in \overline{\mathbb{Q}}\] \[\forall r \in \mathbb{Q} \text{ and } \forall s \in \mathbb{R}, \text{ if } s \in \overline{\mathbb{Q}} \text{ then } r + s \in \overline{\mathbb{Q}}\]

  • Direct proof: suppose \(r \in \mathbb{Q}\) and \(s \in \overline{\mathbb{Q}}\). Now we are stuck — \(s \in \overline{\mathbb{Q}}\) gives nothing to substitute.
  • Proof by contradiction: suppose \(\exists r \in \mathbb{Q}\) and \(s \in \mathbb{R}\) such that \(s \in \overline{\mathbb{Q}}\) and \(r + s \in \mathbb{Q}\). (Done in the video.)
  • Proof by contraposition:

The contrapositive is: \(\forall r \in \mathbb{Q}\) and \(\forall s \in \mathbb{R}\), if \(r + s \in \mathbb{Q}\) then \(s \in \mathbb{Q}\).

Suppose \(r \in \mathbb{Q}\), \(s \in \mathbb{R}\) and \(r + s \in \mathbb{Q}\). Since \(r \in \mathbb{Q}\), \(r = \frac{a}{b}\) for some \(a, b \in \mathbb{Z}\) where \(b \neq 0\). Since \(r + s \in \mathbb{Q}\), \(r + s = \frac{c}{d}\) for some \(c, d \in \mathbb{Z}\) where \(d \neq 0\). Now \[s = (r+s) - r = \frac{c}{d} - \frac{a}{b} = \frac{bc - ad}{bd}.\] Since \(a,b,c,d \in \mathbb{Z}\) we know \(bc - ad \in \mathbb{Z}\) and \(bd \in \mathbb{Z}\). Also \(bd \neq 0\) since \(b \neq 0\) and \(d \neq 0\). Thus \(s \in \mathbb{Q}\). \(\square\)

The move that unlocks it is writing \(s = (r+s) - r\) — expressing the unknown in terms of the two things you were handed.

Activity 1

Prove that \(\forall r \in \mathbb{R}\), if \(r^2\) is irrational, then \(r\) is irrational.

What type of proof will work? Direct proof · ✓ contradiction · ✓ contraposition

Proof. We prove the contrapositive: \(\forall r \in \mathbb{R}\), if \(r \in \mathbb{Q}\) then \(r^2 \in \mathbb{Q}\). Suppose \(r \in \mathbb{R}\) where \(r \in \mathbb{Q}\). Then \(r = \frac{a}{b}\) for some integers \(a, b\) with \(b \neq 0\). Now \(r^2 = \left(\frac{a}{b}\right)^2 = \frac{a^2}{b^2}\). Since \(a, b \in \mathbb{Z}\) we have \(a^2, b^2 \in \mathbb{Z}\); also \(b^2 \neq 0\) since \(b \neq 0\). So \(r^2 \in \mathbb{Q}\). \(\square\)

Activity 2

Prove that \(\forall r \in \mathbb{Q}, (2r^2 - 3r + 1) \in \mathbb{Q}\).

What type of proof will work? ✓ direct proof (best) · ✓ contradiction · contraposition (stuck)

Proof. Let \(r \in \mathbb{Q}\). Then \(r = \frac{a}{b}\) for some \(a, b \in \mathbb{Z}\) where \(b \neq 0\). Now \[2r^2 - 3r + 1 = 2\left(\frac{a}{b}\right)^2 - 3\left(\frac{a}{b}\right) + 1 = \frac{2a^2}{b^2} - \frac{3ab}{b^2} + \frac{b^2}{b^2} = \frac{2a^2 - 3ab + b^2}{b^2}.\] Since \(a, b \in \mathbb{Z}\) we have \(2a^2 - 3ab + b^2 \in \mathbb{Z}\) and \(b^2 \in \mathbb{Z}\). Also \(b^2 \neq 0\) since \(b \neq 0\). So \(2r^2 - 3r + 1 \in \mathbb{Q}\). \(\square\)

Contraposition stalls here because the negation of “\(2r^2 - 3r + 1 \in \mathbb{Q}\)” — that it’s irrational — gives nothing to substitute. The direction of the useful information decides the method.

Activity 3

Prove by contraposition: \(\forall m, n \in \mathbb{Z}\), if \(mn\) is odd, then \(m\) and \(n\) are both odd.

What type of proof will work? direct proof (not as easy) · ✓ contradiction · ✓ contraposition

Proof. We prove the contrapositive: \(\forall m, n \in \mathbb{Z}\), if at least one of \(m, n\) is even then \(mn\) is even. Without loss of generality, assume \(m\) is even. So \(m = 2k\) for some \(k \in \mathbb{Z}\). Now \(mn = (2k)n = 2(kn)\). Since \(k, n \in \mathbb{Z}\), \(kn \in \mathbb{Z}\), so \(mn\) is even. \(\square\)

Note that “\(m\) and \(n\) are both odd” negates to “\(m\) is even or \(n\) is even” by De Morgan — hence “at least one of”.

Activity 4 — \(\sqrt{2}\) is irrational

What type of proof will work? Direct proof · ✓ contradiction · contraposition

Two ingredients:

  • Fact: every rational number can be written as a fraction in lowest terms (numerator and denominator have no common factors).
  • Lemma (Video 11): for all integers \(n\), if \(n^2\) is even then \(n\) is even.

Proof. Suppose \(\sqrt{2}\) is rational. Then \(\sqrt{2} = \frac{a}{b}\) for some \(a, b \in \mathbb{Z}\) with \(b \neq 0\), and we assume \(\frac{a}{b}\) is in lowest terms.

Now \((\sqrt{2})^2 = \left(\frac{a}{b}\right)^2\), so \(2 = \frac{a^2}{b^2}\) and hence \(a^2 = 2b^2\); thus \(a^2\) is even. By the lemma, \(a\) is even, so \(a = 2\ell\) for some \(\ell \in \mathbb{Z}\).

Then \(2b^2 = a^2 = (2\ell)^2 = 4\ell^2\), so \(b^2 = 2\ell^2\) and \(b^2\) is even. By the lemma again, \(b\) is even.

This contradicts the assumption that \(\frac{a}{b}\) is in lowest terms — \(a\) and \(b\) share the factor 2.

Therefore \(\sqrt{2} \in \overline{\mathbb{Q}}\). \(\square\)

The “in lowest terms” assumption is what the contradiction lands on; without it the argument has nothing to contradict.

See also