I am trying to solve Exericse 4.4.2 in Tao's real analyis textbook, but am having some trouble finishing it, and was hoping someone could take a look at what I have. Here is a copy of the exercise.
A definition: a sequence of $a_0, a_1, a_2, \ldots$ of numbers (natural numbers, integers, rationals, or reals) is said to be in infinite descent if we have $a_n > a_{n+1}$ for all natural numbers $n$ (i.e., $a_0 > a_1 > a_2 > \ldots)$.
(a) Prove the principle of infinite descent: that it is not possible to have a sequence of natural numbers which is in infinite descent.
(b) Does the principle of infinite descent work if the sequence is allowed to take integer values instead of natural number values? What about if it is allowed to take positive rational values instead of natural numbers? Explain.
Here is my attempt at an answer.
(a) Using Tao's hint, for a contradiction, assume it is possible to have a sequence $(a_n)$ of naturals in infinite descent. We will use induction to prove that $a_n \geq k$ for all $k \in \mathbb{N}$ and all $n \in \mathbb{N}$.
We induct on $k$, holding $n$ fixed.
Base Case: We let $k = 0$. We need to prove that $a_n \geq 0$ for all $n$. This is certainly the case since $a_n \geq 0$ for all $n$ since the $a_n$ are natural numbers.
Induction Hypothesis: We assume that $a_n \geq k$ for all $n$, where $k$ is some fixed natural number.
Induction Step: We must prove $a_n \geq k + 1$.
We have $a_n \geq k$ for all $n$ from our induction hypothesis. Since this holds for all $n$, it holds for $n+1$, so $a_{n+1} \geq k$. Our sequence is in infinite descent, hence $a_n < a_{n+1}$. Hence: \begin{align*} a_n > a_{n+1} \geq k. \end{align*} Therefore, $a_n > k$, which implies that $a_n \geq k+1$, closing the induction. We conclude that $\forall n, k \in \mathbb{N}, a_n \geq k$.
I am not completely sure on how to conclude this proof. I seem to have proved that this sequence is greater than any natural number, which sounds rather absurd since there are an infinite number of natural numbers, but there are are also an infinite number of elements in the sequence, so I can't necessarily invoke "boundedness" without knowing anything further about the sequence. Some insights on this would be great.
I am less sure on part (b), but here is the work I have done so far. This is far less of a formal answer than my scratchwork.
(b) If $(a_n)$ is a sequence of integers, rather than naturals, surely we cannot use induction, nor can we say the $(a_n)$ are all non-negative. Therefore, it does not seem that I can derive the fact that $a_n \geq k$ for all $n, k \in \mathbb{N}$. But this seems to be true for precisely the same reason as for the naturals, being that they are an infinite number of integers and there is no "largest" integer.
As for the positive rationals, my intuition seems to be that such a principle would be allowed, as we could technically cut the positive rationals in half forever. I am unsure as to how to go about proving this fact, though.
I'd greatly appreciate any helpful insights.
For part (a), I don't feel induction is necessary. Simply consider $(a_n)$ starting at some $k \in \Bbb N$. There are only finitely many $\ell \in \Bbb N$ such that $\ell < k$, the least such element being $0$ or $1$ depending on your convention. By this fact, you cannot construct an infinitely-descending sequence, since you only have finitely many elements you could exhaust.
For part (b), both work. For integers consider $a_n = -n$ and for rationals consider $a_n = 1/n$. In the former case we diverge off to $-\infty$ and in the latter case the sequence approaches $0$. These are decreasing since $-n > -(n+1) = -n-1$ and $1/n > 1/(n+1)$ for all (nonzero) naturals $n$.
(We only need a single valid sequence to prove the principle of infinite descent stated; thus a direct example seems the simplest angle of approach.)