6.9: Infinite descent

In this final section we touch upon an important variation on mathematical induction. This variation is well-illustrated by the next (probably familiar) problem.

Problem 267 Write out for yourself the following standard proof that $\sqrt{2}$ is irrational.

(i) Suppose to the contrary that $\sqrt{2}$ is rational. Then $\sqrt{2}=\frac{m}{n}$ for some positive integers m, n. Prove first that m must be even.

(ii) Write $m=2m^{\prime }$, where $m^{\prime }$ is also an integer. Show that n must also be even.

(iii) How does this lead to a contradiction?

Problem 267. has the classic form of a proof which reaches a contradiction by infinite descent.

1. We start with a claim which we wish to prove is true. Often when we do not know how to begin, it makes sense to ask what would happen if the claim were false. This then guarantees that there must be some counterexample, which satisfies the given hypothesis, but which fails to satisfy the asserted conclusion.
2. Infinite descent becomes an option whenever each such counterexample gives rise to some positive integer parameter n (such as the denominator in Problem 267.(i)).
3. Infinite descent becomes a reality, if one can prove that the existence of the initial counterexample leads to a construction that produces a counterexample with a smaller value $n^{\prime }$ of the parameter n, since repeating this step then gives rise to an endlessly decreasing sequence $$n>n^{\prime }>n\text{'}\text{'}>\dots >0$$ of positive integers, which is impossible (since such a chain can have length at most n).
4. Hence the initial assumption that the claim was false must itself be false – so the claim must be true (as required).

Proof by “infinite descent” is an invaluable tool. But it is important to realise that the method is essentially a variation on proof by mathematical induction. As a first step in this direction it is worth reinterpreting Problem 267. as an induction proof.

Problem 268 Let $P(n)$ be the statement:

“$\sqrt{2}$ cannot be written as a fraction with positive denominator $\le n$”.

(i) Explain why $P(1)$ is true.

(ii) Suppose that $P(k)$ is true for some $k\ge 1$. Use the proof in Problem 267. to show that $P(k+1)$ must then be true as well.

(iii) Conclude that $P(n)$ is true for all $n\ge 1$, whence $\sqrt{2}$ must be irrational.

Problem 268. shows that, in the particular case of Problem 267. one can translate the standard proof that “$\sqrt{2}$ is irrational” into a proof by induction. But much more is true. The contradiction arising in step 3. above is an application of an important principle, namely

The Least Element Principle: Every non-empty set S of positive integers has a smallest element.

The Least Element Principle is equivalent to The Principle of Mathematical Induction which we stated at the beginning of the chapter:

The Principle of Mathematical Induction: If a subset S of the positive integers

• contains the integer “1”, and has the property that
• whenever an integer k is in the set S, then the next integer $k+1$ is always in S too,

then S contains all positive integers.

Problem 269

(a) Assume the Least Element Principle. Suppose a subset T of the positive integers contains the integer “1”, and that whenever k is in the set T, then $k+1$ is also in the set T. Let S be the set of all positive integers which are not in the set T. Conclude that S must be empty, and hence that T contains all positive integers.

(b) Assume the Principle of Mathematical Induction. Let T be a non-empty set of positive integers, and suppose that T does not have a smallest element. Let S be the set of all positive integers which do not belong to the set T. Prove that “1” must belong to S, and that whenever the positive integer k belongs to S, then so does $k+1$. Derive the contradiction that T must be empty, contrary to assumption. Conclude that T must in fact have a smallest element.

To round off this final chapter you are invited to devise a rather different proof of the irrationality of $\sqrt{2}$.

Problem 270 This sequence of constructions presumes that we know – for example, by Pythagoras' Theorem – that, in any square $$OPQR, the ratio

“diagonal: side” $=OQ:OP=\sqrt{2}:1$.

Let $$OPQR be a square. Let the circle with centre Q and passing through P meet $\underset{¯}{OQ}$ at $P^{\prime }$. Construct the perpendicular to $\underset{¯}{OQ}$ at $P^{\prime }$, and let this meet $\underset{¯}{OR}$ at $Q^{\prime }$.

(i) Explain why $\underset{¯}{O{P}^{\prime }}=\underset{¯}{P^{\prime }{Q}^{\prime }}$. Construct the point $R^{\prime }$ to complete the square $O{P}^{\prime }{Q}^{\prime }{R}^{\prime }$.

(ii) Join $\underset{¯}{Q{Q}^{\prime }}$. Explain why $\underset{¯}{P^{\prime }{Q}^{\prime }}=\underset{¯}{R{Q}^{\prime }}$.

(iii) Suppose $\underset{¯}{OQ}:\underset{¯}{OP}=m:n$. Conclude that $\underset{¯}{O{Q}^{\prime }}:\underset{¯}{O{P}^{\prime }}=2n-m:m-n$.

(iv) Prove that $n<m<2n$, and hence that $0<m-n<n$, $0<2n-m$.

(v) Explain how, if m, n can be chosen to be positive integers, the above sequence of steps sets up an “infinite descent” – which is impossible.