Show Question
Math and science::Analysis::Tao::08. Infinite sets

# Well-ordered sets

Let $$X$$ be a partially ordered set, and let $$Y$$ be a totally ordered subset of $$X$$. We say that $$Y$$ is well-ordered iff every non-empty subset of $$Y$$ has a minimal element, $$\min(Y)$$.

Every finite totally ordered set is well-ordered (proved in Ex. 8.5.8). Every subset of a well-ordered set is also well-ordered (why?)

One advantage of well-ordered sets is that they automatically obey the principle of strong induction.

#### Possible interpretation

Take a table representing an order on $$X$$. There will be missing entries in the table representing an ordered pair of elements of $$X$$ which is not in the domain of the ordering function. Let $$Y$$ be a subset of $$X$$ such that there are no such holes for the elements of $$Y$$. Imagine this by moving all the columns/rows of the table for $$X$$ and it's comparison function such that all of $$Y$$'s elements are bunched together. Then there will be a square in the table that is fully filled with values. All these elements are in $$Y$$. Now, there still can be characteristics of these values. For example: the presence of cycles. This is where well-ordering comes in. Take any set of elements of $$Y$$ and impose that there is a minimal element. Then, there cannot be cycles.

### Example

The natural numbers $$\mathbb{N}$$ are well-ordered (see Prop. 8.1.4). The integers $$\mathbb{Z}$$, the rationals $$\mathbb{Q}$$,and the reals $$\mathbb{R}$$ are not.

p205