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?
Best Answer
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:
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.