Proving that there does not exist an infinite descending sequence of naturals using minimal counterexample

Question

This might be a long-winded way of proving something so obvious, but I want to have it checked if it holds up.

Claim: There does not exist a sequence $\{{a}_{n \in \mathbb{N}}\}$ of natural numbers such that $a_{n+1} < a_{n}$ for every $n$.

Proof: This amounts to showing that the set $M = \{ m \in \mathbb{N} : m \leq a_{0}\}$, where $a_{0}$ is the first member from any sequence in infinite descent, is finite. Suppose for the sake of contradiction that there exists an $a_{0}$ such that the set $M$ is infinite. We suppose further that $a_{0}$ is minimal. Clearly $a_{0} \neq 0$, for if it were, the set $M = \{ m \in \mathbb{N} : m \leq 0\}$ = $\{0\}$ is finite.

Consider the set $N = M - \{n \in \mathbb{N}: a_{1} < n \leq a_{0}\}$, which is just the set $M$ with the finitely many naturals deleted. From elementrary set theory, $N$ must be infinite.

But $N = \{ n \in \mathbb{N} : n \leq a_{1}\}$, and we can suppose that $a_{1}$ is the first term in a natural number sequence in infinite descent. Thus we have found another infinite set with the desired property, but with $a_{1} < a_{0}$. This contradicts the minimality of $a_{0}$.

Answer 1

This amounts to showing that the set $M = \{ m \in \mathbb{N} : m \leq a_{0}\}$, where $a_{0}$ is the first member from any sequence in infinite descent, is finite. $ \def\nn{\mathbb{N}} $

This first line of your 'proof' is invalid. You are using merely your intuition to claim that the non-existence of an infinite descending chain of natural numbers follows from the finiteness of some set that you specified. This is circular in this case; proving the equivalence amounts to proving something of roughly the same strength as the original desired theorem.

Instead what you actually need is:

Let $S = \{ n : n \in \nn \land \text{there is a strictly decreasing sequence from $\nn$ starting with $n$ } \}$.

If $S$ is non-empty then let $m = \min(S)$ and (use your other ideas) to prove that there is a strictly decreasing sequence from $\nn$ starting with something less than $m$, which contradicts the definition of $m$.

Therefore $S$ is empty and you are done.

Answer 2

Your proof looks good to me. As @user21820 and others point out, it actually isn't, and the other answers do a better job of explaining this. In fact, even the proof below is inaccurate as the $\dotsb$ implies induction but I haven't stated that, because it's more of an 'intuition' proof. Assuming induction and 'common-sense' properties of natural numbers is not a trivial thing for a very axiomatic question like this. (Thanks @user21820!)

---

Here's another I thought of: since the $a$s are natural numbers, $a_{n + 1} < a_n$ is equivalent to $a_{n + 1} \leq a_n - 1$ because there are no natural numbers between $a_n$ and $a_n - 1$. Then, let $n = a_1$ and you have $$a_{n+1} \leq a_{n} - 1 \leq a_{n-1} - 2 \leq \dotsb \leq a_1 - n = 0$$ but $a_{n+1} \geq 0$ as it is a natural number, so $a_{n+1} = 0$. Beyond that there can be no smaller numbers.

(I use 'natural' to mean 'positive integer' but it works for 'non-negative integer' or even 'set of integers with a lower bound'.)

Answer 3

I would have done it by induction on sequences whose first term $a_0\le n$ instead and the property that they are stationnary from a certain point.

$n=0$ only one sequence, the null sequence, it is stationnary.

For $a_0\le n+1$ then if $a_0\le n$ then we apply induction hypothesis, else since $a_1<a_0$ then $a_1\le n$ and we apply induction hypothesis on the truncated sequence.

Historical note :

Yet we can wonder if the induction principle itself doesn't use the infinite descent to be proved ? In fact Frege demonstrated that it is a consequence of second order logic given the definition of the zero, of a number and the successor operation as defined by Peano.

I found this in this article $§6.4$ (though in french, sorry) : le raisonnement par recurrence, quel fondement ?.

So in the above proof the whole thing holds effectively on these things :

• the definiton of $0$ is used when we say that if $a_0\le0$ then the whole sequence is the null-sequence. (i.e. there is no natural <0).

• the well ordering of $\mathbb N$ is used when we say that $(a_0\le n+1)\land (a_1<a_0)\Rightarrow a_1\le n+1-1=n$, making full use of the successor definition.

In your proof if we want to be scrupulous, when you say finitely many natural deleted, then it is a bit annoying, because you are biting your tail : you want to proove there are no infinite descending sequence of naturals but you invoque an argument of finitness...

Addendum : (from comments)

In all these proofs which are very close to axiomatic material, we should in theory check everything we write to avoid the biting one's tail issue (i.e. using a result proved by mean of the theorem we want to prove).

Yet here, we can set the starting point as Peano axioms and the induction principle and prove that infinite descent as well as well-ordering principle (i.e. every set of naturals has a minimum) are sound. And in fact these can eventually become new forms of induction on their own.

This are indeed principles used in the other contributors' proofs.

Answer 4

Besides the comments in the answers by zwim and user21820, I would emphasize that the proof uses in an essential way the fact (required to be proven in the most common presentations of the naturals) that every set of naturals has a least element.

Answer 5

(I think this response does not reproduce an existing one, although the ideas are all quite similar.)

Suppose for the sake of contradiction that there exists such a sequence, $\{a_n\}_{n \in \mathbb{N}}$. Consider the set containing all of its elements. Since this is a nonempty set of natural numbers, it contains -- by the Well Ordering Principle -- a least element, $a_k \in \mathbb{N}$. Since the sequence is strictly decreasing, $a_{k+1} < a_k$, which contradicts the minimality of $a_k$.

Thus, our supposition was incorrect, and no such sequence exists.