3
$\begingroup$

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

  • 0
    If you know the starting value, then you know how many values the sequence can have (finite), which proves it terminates, no?2011-09-09
  • 1
    In other words, show by induction on $n\ge0$ that $x_n\le x_0-n$ and conclude.2011-09-09
  • 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.