# Every decreasing sequence of natural numbers terminates

How do we prove that every decreasing sequence of natural numbers terminates using the well ordering principle?

-
If you know the starting value, then you know how many values the sequence can have (finite), which proves it terminates, no? –  TMM Sep 9 '11 at 16:42
In other words, show by induction on $n\ge0$ that $x_n\le x_0-n$ and conclude. –  Did Sep 9 '11 at 16:44
A small nitpick. I usually take decreasing to mean non-increasing rather than strictly decreasing. Under this more liberal definition, an infinite sequence of $1$s is decreasing, but it does not terminate. (I understand that the OP means the strict version.) –  Srivatsan Sep 9 '11 at 16:48

Assume that $(n_i)_{i\in\mathbb{N}}$ is a strictly decreasing infinite sequence of natural numbers. Then $\{n_i:i\in\mathbb{N}\}$ is a nonempty subset of natural numbers which has no smallest element. This contradicts the well-ordering principle. Thus there can be no strictly decreasing infinite sequences of natural numbers. In other words, every strictly decreasing sequence of natural numbers must be finite.
By the well ordering principle, your list of natural numbers must have a smallest element, call it $n$. If the sequence did not terminate, then the entry after $n$ must be smaller than $n$ (since the sequence is decreasing), which contradicts the definition of $n$ as the smallest element in the sequence.