An Ordered Set Well-Ordered if and Only if It Does Not Contain Infinite Decreasing Sequences

The concept of an ordered set being well-ordered is a fundamental one in set theory and mathematics. An ordered set is said to be well-ordered if every non-empty subset contains a least element. Interestingly, a well-ordered set can also be characterized in terms of not containing any infinite decreasing sequences. This article delves into the proof that an ordered set is well-ordered if and only if it does not contain any infinite decreasing sequences, and provides detailed explanations and examples to illustrate this concept.

Definition and Key Concepts

Well-Ordered Set

A set ( S ) is well-ordered by a relation ( leq ) if every non-empty subset of ( S ) has a least element with respect to ( leq ). This means that for any non-empty subset ( A subseteq S ), there exists an element ( a in A ) such that for all ( x in A ), ( a leq x ).

Infinite Decreasing Sequence

An infinite decreasing sequence in an ordered set is a sequence ( a_n ) such that ( a_{n 1}

Proof Outline

The proof consists of two parts: (1) If a set is well-ordered, then it does not contain any infinite decreasing sequences. (2) If a set does not contain any infinite decreasing sequences, then it is well-ordered.

Part 1: If a Set is Well-Ordered, Then It Does Not Contain Infinite Decreasing Sequences

Assume ( S ) is well-ordered. Consider any infinite decreasing sequence ( a_n ) in ( S ). The set ( {a_n : n in mathbb{N}} ) is a non-empty subset of ( S ). Since ( S ) is well-ordered, this subset must have a least element ( a_k ). However, since ( a_n ) is decreasing, ( a_{k 1}

Part 2: If a Set Does Not Contain Infinite Decreasing Sequences, Then It is Well-Ordered

Conversely, assume ( S ) does not contain any infinite decreasing sequences. Take any non-empty subset ( T ) of ( S ). If ( T ) does not have a least element, we can construct a sequence starting from any element of ( T ) and repeatedly finding smaller elements in ( T ), which would form an infinite decreasing sequence. This contradicts the assumption that there are no infinite decreasing sequences. Hence, ( T ) must have a least element, and thus ( S ) is well-ordered.

Further Insights

This equivalence provides a useful characterization of well-ordered sets, which might simplify certain proofs and concepts in set theory and abstract algebra. For instance, if a non-empty subset of a well-ordered set does not have a least element, we can immediately conclude that the set contains an infinite decreasing sequence.

It is also worth noting that sequences considered in this context are indexed by the natural numbers ( mathbb{N} ), ensuring that the concept of an infinite decreasing sequence is well-defined and manageable.

Conclusion

Thus, an ordered set is well-ordered if and only if it does not contain any infinite decreasing sequences. This equivalence is a potent tool for understanding the structure and properties of ordered sets, and can be applied in various mathematical contexts.

Keywords: ordered set, well-ordered, infinite decreasing sequence