Well orders and the ordinal numbers

Let us learn about well orders and how to count in the ordinals

Before embarking on this essay, some readers may prefer to begin with an elementary introduction to ordinals in my essay How to Count.

A well order is a linear order with the further property that every nonempty subset of the domain has a least element. If the well order has any elements at all, therefore, it will have a global least element, often called 0, and then a next least element, called 1, and a next least element, and so on for as long as there remain elements. Thus, we may begin counting from the bottom of any well-order as though in the natural numbers.

Having counted through those elements at finite distance from the bottom, we may find that some elements still remain—let us call them the infinite elements. If there are such infinite elements, then there will be a least infinite element, labeled ω in the figure, and then a next least element after that, and so on. The general observation in play here is that whatever initial segment of the order we might have currently, whether it consists entirely of finite elements or whether it reaches into the infinite part of the order, nevertheless if it does not yet exhaust all the elements of the order, then there will be a least element among those that remain, a next element in the order. This is the fundamental nature of a well order—if you haven't yet completed the process of counting it out, then there is a particular next element for you to pronounce.

In particular, every element α in a well order, except the greatest element if there is one, has an immediate successor, an element that is least among those above α; we might naturally denote it by α + 1. Concerning predecessors, however, some elements in a well order might not have an immediate predecessor at all. The element ω in the figure, for example, has predecessors, that is, there are elements that precede it in the order, but it has no immediate predecessor. This is what it means to be a limit element in a well order; such objects are the limits of the elements below them. The existence of limit elements has the consequence that well orders with infinite elements are not discrete linear orders.

The elements of a well order can thus be classified into three disjoint types. Namely, there is the zero element, the least element overall; the successor elements are the immediate successors of another element; and the limit elements have predecessors, but no immediate predecessor.

Well orders enable a remarkable generalization of the principle of induction from the natural numbers into the transfinite. That innocent-seeming least-element property thus leads to what has become a profoundly important mathematical tool.