Use the Well ordering principle to prove Is there a process that is capable of generating an infinitely long sequence of natural numbers $a_1, a_2, a_3, \ldots$ such that for all $n \ge 1, a_n \ge a_{n+1}$?
I know i have to use the well ordering principle to prove this. You assume that there a largest an and prove a contradiction. But isn't WOP used to show that there is a smallest element in a non empty set? How would i start this?
 A: Here is one such sequence...
$$5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...$$
the above is an infinitely long sequence of natural numbers such that $a_n \ge a_{n+1}$ for $n \ge 1$. It is sufficient to use this sequence as proof that such a sequence exists. A proof of this kind would be called a "constructive existence proof," and the above sequence would be a "witness" to the statement you are trying to prove.
If you were searching for an infinitely long sequence of natural numbers $a_1, a_2, a_3, ...$ such that $a_n > a_{n+1}$ for $n \ge 1$, then I would say no such sequence exists by the well ordering principle, which states that every nonempty subset of the natural numbers has a least element. In that event, you would be looking for a way to arrange the natural numbers such that they descend forever without ever encountering a least element beyond which there was no lesser number. Of course, the natural numbers have a least element, that is, the number $0$, so any "process" or function that generates a descending sequence of natural numbers will either terminate before it encounters $0$ or encounter $0$ and have to stop. In either case, the sequence is not infinite.
A: Well, this is a proof where you should just use what you know - you recognize that the well-ordering principle tells you something about a least element, so let's investigate that! There's nothing special about a largest element* (especially since $a_0 \geq a_1 \geq a_2 \ldots$ implies that $a_0$ is the largest... which wasn't very interesting).
So, let's suppose we have a sequence $a_0\geq a_1\geq a_2 \geq \ldots$. To apply the well-ordering principle, we need to come up with a non-empty set - and the set $\{a_0,a_1,a_2,\ldots\}$ is the only thing in sight, so let's use the well-ordering theorem on that! This means that there is some $a_n$ such that $a_n \leq a_m$ for all $m$ - and now we're basically done! Look at any $m\geq n$. We know (or can prove by induction) that since $a_n \geq a_m$ since the sequence is non-increasing. However, we just used this magic principle to choose $n$ so that $a_n \leq a_m$. That means that $a_n=a_m$! In particular, following this line of reasoning gives us the following:

Given any non-increasing sequence of natural numbers, there is some term $a_n$ after which the sequence is constant.

Which says that, no matter how you start, you'll end with something like $c,c,c,c,c,c,c,c,\ldots$ where the term $c$ goes on forever.

*Saying there's nothing special about a largest element is somewhat of a lie. You can prove the statement I highlighted by induction on $a_0$ - if $a_0=0$, we are done because there are no smaller natural numbers. Then, you can note that this implies that if the sequence ever hits $0$, it must be constant - but then if you investigate $a_0=1$, you find that either the sequence eventually hits $0$, or it repeats $1$ forever - and you can twist this into a formal inductive argument. This is not the easiest path, however. You can also do things like suppose that $a_0>a_1>\ldots$ is strictly decreasing and show that it can have at most $1+a_0$ terms, or just look at the finite set $\{0,1,2,\ldots,a_0\}$ and ask how many times each term repeats.
