2Well-orderings and ordinals
II Logic and Set Theory
2 Well-orderings and ordinals
In the coming two sections, we will study different orderings. The focus of this
chapter is well-orders, while the focus of the next is partial orders.
A well-order on a set
S
is a special type of total order where every non-empty
subset of
S
has a least element. Among the many nice properties of well-orders,
it is possible to do induction and recursion on well-orders.
Our interest, however, does not lie in well-orders itself. Instead, we are
interested in the “lengths” of well-orders. Officially, we call them them the order
types of the well-orders. Each order type is known as an ordinal.
There are many things we can do with ordinals. We can add and multiply
them to form “longer” well-orders. While we will not make much use of them in
this chapter, in later chapters, we will use ordinals to count “beyond infinity”,
similar to how we count finite things using natural numbers.