Well Ordered Set

Definition

A well ordered set is a set $S$ together with a relation $\le$ such that:

1. $(S,\le)$ is a totally ordered set (also called a linear order), meaning for any two elements $a,b \in S$, exactly one of the following holds:
2. $a \le b$

3. $b \le a$

4. Every non-empty subset of $S$ has a least element with respect to $\le$.

Least element

An element $m$ of a subset $A \subseteq S$ is called the least element of $A$ if:

• $m \in A$, and
• $m \le a$ for every $a \in A$

Important distinction

• A least element is the smallest element in a subset.
• A minimal element is an element for which no smaller element exists in the subset.
• In a well ordered set, every non-empty subset has a least element, and therefore also a minimal element.
• In general posets, a subset may have minimal elements without having a least element.

Example

The set $\mathbb{N} = \{1,2,3,\dots\}$ with the usual order is well ordered because every non-empty subset has a smallest natural number.

Non-example

The set of integers $\mathbb{Z}$ with usual order is not well ordered, because the subset $$\{ \dots,-3,-2,-1\}$$ has no least element.

---

Main Content

1. First Concept: Total Order and Well Ordering

A well ordered set must first satisfy the condition of being totally ordered.

Every pair is comparable

• For any two elements $a$ and $b$, either $a \le b$ or $b \le a$.

Order is consistent and complete

• There are no incomparable elements, unlike in a general poset.

Why total order matters

If a set is not totally ordered, then it cannot be well ordered. This is because the definition of well ordering requires the order to decide which of any two elements comes first.

Example

Consider the set: $$\{1,2,3\}$$ with the usual order $1<2<3$. This is totally ordered, and every non-empty subset has a least element.

Example of failure

Consider the power set $P(\{a,b\})$ under inclusion $\subseteq$: $$\emptyset,\{a\},\{b\},\{a,b\}$$ This is a poset, but not a total order because $\{a\}$ and $\{b\}$ are incomparable. So it is not well ordered under inclusion.

---

2. Second Concept: Least Element Property

The defining feature of a well ordered set is that every non-empty subset has a least element.

• This property guarantees that the set has no “descending infinite chain” with no bottom.
• It ensures that any process of repeatedly choosing smaller elements must stop at a minimum point.

Why this is powerful

This property is the basis for well-order induction, a proof method similar to mathematical induction, but stronger in scope.

Example

In $\mathbb{N}$, take any non-empty subset such as: $$A = \{5,7,10,12\}$$ The least element is $5$.

Another subset: $$B = \{n \in \mathbb{N} : n \text{ is even and } n>10\} = \{12,14,16,\dots\}$$ The least element is $12$.

Contrast with other sets

The set $\mathbb{Z}$ fails this property: $$\{ \dots,-5,-4,-3\}$$ has no least element because for every integer there is always a smaller one.

Key consequence

A well ordered set cannot contain an infinite strictly decreasing sequence: $$a_1 > a_2 > a_3 > \cdots$$ If it did, the set of all such elements would have no least element, which is impossible in a well ordered set.

---

3. Third Concept: Order Type, Induction, and Applications in Combinatorics

Well ordered sets are closely connected with order type, transfinite induction, and combinatorial reasoning.

Order type

Two well ordered sets are said to have the same order type if there is an order-preserving bijection between them. This allows mathematicians to compare the structure of different well orders, not just their size.

Common examples of order types

• $\{1,2,3,\dots\}$ has the order type of the natural numbers.
• The set of finite ordinal numbers extends this idea.
• In advanced mathematics, well ordering leads to ordinal numbers.

Well-order induction

If $P(x)$ is a statement about elements of a well ordered set $S$, then to prove $P(x)$ for all $x \in S$, it is enough to show:

• whenever $P(y)$ is true for all $y < x$, then $P(x)$ is true.

This is a generalization of ordinary induction.

Example of induction on $\mathbb{N}$

To prove every natural number $n$ satisfies a property $P(n)$:

1. Prove $P(1)$
2. Assume $P(1),P(2),\dots,P(k)$
3. Prove $P(k+1)$

This works because $\mathbb{N}$ is well ordered.

Combinatorial relevance

Well ordering is useful in:

• counting arguments,
• recursive definitions,
• proving termination of algorithms,
• finding minimal counterexamples.

For example, in combinatorics, if a property fails for some objects, choosing a smallest counterexample often leads to a contradiction.

ASCII diagram for a finite well ordered set

For the set $\{1,2,3,4\}$ under usual order:

1 < 2 < 3 < 4

This shows that every subset has a first element, such as:

• $\{2,4\}$ → least element is $2$
• $\{3,4\}$ → least element is $3$

---

Working / Process

1. Check whether the relation is a total order

• Confirm that every pair of elements is comparable.
• If some pairs are incomparable, the set is not well ordered.
• Example: inclusion on a power set usually fails this step.

2. Test the least element property on non-empty subsets

• Pick arbitrary non-empty subsets.
• Identify whether each subset has a smallest element.
• If even one non-empty subset lacks a least element, the set is not well ordered.
• Example: $\mathbb{N}$ passes; $\mathbb{Z}$ fails.

3. Use the property in proofs and constructions

• Apply induction or minimal counterexample arguments.
• Define sequences or algorithms that always proceed by choosing the least available element.
• This helps establish termination, existence, and uniqueness results.

---

Advantages / Applications

Supports induction and proof by minimal counterexample

• Well ordered sets make rigorous proof methods possible, especially in discrete mathematics and combinatorics.

Ensures predictable structure

• Every subset has a beginning point, which helps in defining recursive processes and ordered algorithms.

Useful in advanced mathematical theory

• Well ordering is foundational for ordinal numbers, transfinite induction, and deeper results in set theory and mathematical logic.

---

Summary

• A well ordered set is a totally ordered set in which every non-empty subset has a least element.
• Natural numbers with the usual order are the classic example.
• The key idea is that no non-empty subset can “go on forever downward” without a smallest element.
• Important terms to remember: well ordered set, total order, least element, minimal element, well-order induction, order type