How do we prove that every decreasing sequence of natural numbers terminates using the well ordering principle?
Every decreasing sequence of natural numbers terminates
3
$\begingroup$
elementary-number-theory
-
0A 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.) – 2011-09-09
2 Answers
6
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.
6
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.