3
$\begingroup$

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

  • 0
    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.)2011-09-09

2 Answers 2

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.