Method of Infinite Descent/Proof 2

From ProofWiki
Jump to navigation Jump to search


Let $\map P {n_\alpha}$ be a propositional function depending on $n_\alpha \in \N$.

Let $\map P {n_\alpha} \implies \map P {n_\beta}$ such that $0 < n_\beta < n_\alpha$.

Then we may deduce that $\map P n$ is false for all $n \in \N$.

That is, suppose that by assuming the truth of $\map P {n_\alpha}$ for any natural number $n_\alpha$, we may deduce that there always exists some number $n_\beta$ strictly less than $n_\alpha$ for which $\map P {n_\beta}$ is also true, then $\map P {n_\alpha}$ cannot be true after all.

This technique is known as the method of infinite descent.

The process of deducing the truth of $\map P {n_\beta}$ from $\map P {n_\alpha}$ such that $0 < n_\beta < n_\alpha$ is known as the descent step.


Suppose that $\map P {n_\alpha}$ holds.

Then from the descent step, $\exists n_\beta \in \N_{n_\alpha}: \map P {n_\beta}$.

The descent step then tell us we can deduce a smaller positive solution, $n_\gamma$, such that $\map P {n_\gamma}$ is true and $n_\gamma \in \N_{n_\beta}$.

And again, the descent step tells us we can deduce a still smaller positive solution, $n_\delta$, such that $\map P {n_\delta}$ is true and $n_\delta \in \N_{n_\gamma}$.

Now, consider the unending sequence: $n_\alpha > n_\beta > n_\gamma > n_\delta > \cdots > 0$.

The set $S = \set {n_\alpha, n_\beta, n_\gamma, n_\delta, \ldots}$ is not bounded below, as for any $\forall x \in S: \exists y \in S: y < x$.

By the Well-Ordering Principle, any non-empty subset of $\N$ must have a least element.

As $S$ is not bounded below, it has no least element, so must be empty.


Axiom of Choice

Care is required to avoid accidentally using the Axiom of Countable Choice for Finite Sets, which is independent of Zermelo-Fraenkel Set Theory.

Before beginning the descent, construct:

$\set {x : \map P x \land x < m}$

for each $m \leq n_\alpha$.

If it would be empty, define it to be any nonempty set instead.

Applying the Principle of Finite Choice, choose an element from each one.

Now, perform the descent, using the choice function to choose the next element at each step.

Because at each step, there are smaller solutions, it will never be the arbitrary set.

Therefore, the sequence is defined as required.

Historical Note

The Method of Infinite Descent was devised by Pierre de Fermat.

He used it to develop his proof of Fermat's Two Squares Theorem, as he describes in a letter to Pierre de Carcavi:

For a long time I was unable to apply my method to affirmative proposition, because the twist and the trick for getting at them is much more troublesome than that which I use for negative propositions. Thus, when I had to prove that every prime number which exceeds a multiple of $4$ by $1$ is composed of two squares, I found myself in a fine torment. But at last a meditation many times repeated gave me the light I lacked, and now affirmative propositions submit to my method, with the aid of certain new principles which necessarily must be adjoined to it. The course of my reasoning in affirmative propositions is such: if an arbitrarily chosen prime of the form $4 n + 1$ is not a sum of two squares, [I prove that] there will be another of the same nature, less than the one chosen, and [therefore] next a third still less, and so on. Making an infinite descent in this way we finally arrive at the number $5$, the least of all the numbers of this kind [$4 n + 1$]. [By the proof mentioned and the previous argument from it], it follows that $5$ is not a sum of two squares. But it is. Therefore we must infer by a reductio ad absurdum that all numbers of the form $4 n + 1$ are sums of two squares.