# Method of Infinite Descent/Proof 2

## Theorem

There is believed to be a mistake here, possibly a typo.In particular: This technique only works if you can prove that there exists some $n_\gamma$ such that $0 \le n_\gamma < n_\alpha$ for which $\map P {n_\gamma}$ does not work. Otherwise, technically speaking, the proof by Fermat in the historical note is not actually an example of this proof technique. I challenge the student to come up with a proof which genuinely uses the technique as presented here, because I am not sure that it makes logical sense.You can help ProofWiki by reviewing it, and either correcting it or adding some explanatory material as to why you believe it is actually correct after all.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Mistake}}` from the code.If you would welcome a second opinion as to whether your work is correct, add a call to `{{Proofread}}` the page. |

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**.

## Proof

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.

$\blacksquare$

### Axiom of Choice

This article needs to be tidied.In particular: In the proofPlease fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Tidy}}` from the code. |

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.*