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}}\). The barred \(\overline{\mathbb{Q}}\) is this course’s symbol for the irrationals — see rational-and-irrational-numbers for the picture.

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

This is the table from 2026-08-13-proof-by-contradiction, grown by one row. Contraposition is valid because

\[p \to q \equiv \sim q \to \sim p\]

(see conditional-statements). Contraposition does not assume the statement is false. It is a direct proof of a different statement — one that happens to be logically equivalent to the one you were asked about. That is the practical difference from proof by contradiction, which assumes \(P(x) \land \sim Q(x)\) and hunts for an absurdity.

Choosing a method

What is the relationship between proof by contradiction and proof by contraposition? As above: contraposition is a direct proof of an equivalent statement, while contradiction assumes \(P(x) \land \sim Q(x)\) and hunts for an absurdity.

How do we decide if we should use a direct proof, proof by contradiction or proof by contraposition? Empirically rather than by a rule: for each statement, ask what type of proof will work, and see which methods move and which ones stall. The verdicts for the statements proved below are collected in Figure 1.

Figure 1: Which type of proof works for each statement proved below. A tick is a method that works and a cross is one that stalls, with a short remark in red where there is one; a plain bullet is a method given neither. Reading down the columns: contradiction is the only method never ruled out, which is what ‘most versatile’ means in practice — but it is also never the one labelled ‘Best’.

The pattern that emerges: a method works when it hands you something you can substitute for. A direct proof needs the hypothesis to be a positive, unfoldable statement; contraposition needs the negated conclusion to be one; contradiction gets both at once, which is why its column never gets a cross.

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}}\]

The second is the form to work with, because it puts the whole conditional in terms of one unknown \(s\): the antecedent is \(s \in \overline{\mathbb{Q}}\) and the consequent is \(r + s \in \overline{\mathbb{Q}}\), so the contrapositive is a clean swap.

  • 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}\). (Worked in Video 012.)
  • 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\) — a new pair of variables, since nothing says the two fractions are related. 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. The closing three checks (integer numerator, integer denominator, non-zero denominator) are what the definition of \(\mathbb{Q}\) actually demands, and every rational-number proof in this course ends with them.

Worked: if \(r^2\) is irrational then \(r\) is irrational

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

Which type of proof will work: contradiction and contraposition both work; a direct proof does not.

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\)

Both negations do real work here. “\(r^2\) is irrational” is a statement about what \(r^2\) is not, and so is “\(r\) is irrational” — the contrapositive turns both into positive membership claims, and a positive claim is one you can substitute a fraction into.

Worked: \(2r^2 - 3r + 1\) is rational when \(r\) is

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

Which type of proof will work: a direct proof works and is the best; contradiction also works; contraposition gets 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\)

In the middle step everything is put over the common denominator \(b^2\) before the numerator is inspected, so that the final expression is visibly one integer over one non-zero integer.

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.

Worked: if \(mn\) is odd then \(m\) and \(n\) are both odd

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

Which type of proof will work: contradiction and contraposition both work; a direct proof is not as easy.

Label the two halves of the statement \(p\) and \(q\) first, and only then write the contrapositive underneath: forming a contrapositive is a mechanical two-step operation on those labelled parts, not a fresh piece of thinking (Figure 2).

Figure 2: Forming the contrapositive of ‘if mn is odd then m and n are both odd’, with the parts labelled p and q. Two things happen at once and both are needed: each half is negated, and the two halves swap sides. The crossing arrows are what ‘swap’ looks like. The negation of q is the De Morgan step — ‘m and n are both odd’ becomes ‘at least one of m, n is even’ — which is where this kind of proof is most often got wrong.

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\)

“\(m\) and \(n\) are both odd” negates to “\(m\) is even or \(n\) is even” by De Morgan — hence “at least one of”. The WLOG is what lets one line cover both disjuncts: the roles of \(m\) and \(n\) in \(mn\) are interchangeable, so the case “\(n\) is even” is the case above with the two names swapped.

The contrapositive needs very little algebra — three lines, and \(n\) is never unfolded at all. That is the payoff, and why the direct proof is “not as easy”.

Worked: \(\sqrt{2}\) is irrational

Which type of proof will work: contradiction. A direct proof does not work. Contraposition does not apply, because \(\sqrt 2 \in \overline{\mathbb{Q}}\) is not a conditional at all, so there is no antecedent and consequent to swap.

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 \((\Rightarrow\Leftarrow)\).

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. The whole chain — including the two separate applications of the lemma — is drawn out in rational-and-irrational-numbers.

See also