Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.