Exercise 4.4.2 (Infinite descent)

Proof. (a) Reasoning by contradiction, let ${(a_i)}_{i\in \mathbb{N}}\in {\mathbb{N}}^{\mathbb{N}}$ be some strictly decreasing sequence of natural numbers (a sequence of natural numbers in “infinite descent” : $a_0>a_1>a_2>\cdots$).

Consider the following property $𝒫(k)$ (which depends of $k$, but not of $n$),

• Since the $a_n$ are natural numbers, $a_n\ge 0$ for all $n\in \mathbb{N}$. This shows that $𝒫(0)$ is true.

• Reasoning by induction, assume that $𝒫(k)$ is true for some natural number $k$. Then $a_n\ge k$ for all subscripts $n$.

  Reasoning by contradiction, assume now that $𝒫(k+1)$ is false: there is some index $n_0\in \mathbb{N}$ such that $a_{n_0}<k+1$. By the induction hypothesis $a_{n_0}\ge k$, so $k\le a_{n_0}<k+1$, where $a_{n_0}\in \mathbb{N}$, hence $a_{n_0}=k$. Therefore $k=a_{n_0}>a_{n_0+1}$, but the induction hypothesis implies $a_{n_0+1}\ge k$. This is a contradiction, thus $𝒫(k+1)$ is true (assuming $𝒫(k)$).

• The conclusion of the induction is that $𝒫(k)$ is true for all $k\in \mathbb{N}$, so

  $$\forall <!--\; FUNCTION\; APPLICATION\; -->k\in \mathbb{N},\forall <!--\; FUNCTION\; APPLICATION\; -->n\in \mathbb{N},a_n\ge k.$$

In particular $a_0\ge k$ for all $k\in \mathbb{N}$. By Proposition 4.4.1 (and Exercise 4.4.1), there is some integer $K$ such that $a_0<K$. This is a contradiction, which proves that there is not possible to have a sequence of natural numbers which is in infinite descent.

(This principle was often used by Pierre de Fermat to prove results in Number Theory.)

(b) This principle don’t apply in $\mathbb{Z}$, or in ${\mathbb{Q}}_{\text{+}}^{\text{∗}}$, where we can build strictly decreasing sequences:

The sequence ${(a_n)}_{n\in \mathbb{N}}\in {\mathbb{Z}}^{\mathbb{N}}$ defined by $a_n=-n$ is in “infinite descent”:

The sequence ${(b_n)}_{n\in \mathbb{N}}\in {({\mathbb{Q}}_{\text{+}}^{\text{∗}})}^{\mathbb{N}}$ defined by $a_n=\frac{1}{n+1}$ is in “infinite descent”:

□