Wellorderings

I've already told you what is an ordering, but let me give a quick reminder. A (strict) ordering on some set $X$ is a a binary relation, usually denoted by some variation on the symbol $<$, which is 

• irreflexive, that is for all $x\in X$, it is not the case that $x<x$,
• transitive, that is for all $x,y,z\in X$, if $x<y$ and $y<z$, then $x<z$.

One very important example is the standard ordering on natural numbers. In that case, we have that $X=\omega$ and $<=\in$. To understand the second thing, recall that in Set Theory, natural numbers are coded as $0=\mathrm{\varnothing }$, $1=\{0\}$, $2=\{0,1\}$, $3=\{0,1,2\}$, and so on. Hence, for example, $1<3$ because

$$1\in \{0,1,2\}=3.$$

In addition to the irreflexivity and transitivity, this relation satisfies some other important properties. One of them is being

• total, that is for all $x,y\in X$, one of the options is true: $x<y$ or $x=y$ or $x>y$.

The orderings which are total are called total orderings or even cooler, linear orderings. 

The properties that I listed so far are probably already familiar to you. In addition to them, the standard ordering of natural numbers satisfies a wirder property which is equivalent to the already mentioned principle of the induction. To phrase is properly, let me introduce some terminology. If $Y$ is a subset of $X$ and if $y$ is an element of $X$, then $y$ is said to be the minimum of $Y$ if two conditions are met: (1) $y$ is an element of $Y$ and (2) every other element of $Y$ is bigger than $y$. I said "the" minimum because if it exists, then it is unique: if we had two minima $y_0$ and $y_1$, then the second property would give that both $y_0<y_1$ and $y_1<y_0$,  which with the transitivity would imply that $y_0<y_0$, and contradict the irreflexivity! Of course, the minimum might not exist, but I'll illustrate that a bit later.

For now, let us come back to the case $X=\omega$ and $<=\in$. Here, the empty set does not have a minimum (because nothing belongs to it!), but all other subsets of $\omega$ do have a minimum! This is that additional property equivalent to the induction. We say that a linear ordering is a wellordering if every non-empty subset has a minimum. Thus, the ordering of natural numbers is a wellordering. Other examples of wellorderings are the individual natural numbers, say $X=5$ and $<=\in$. In this case, every subset of $5$ is also a subset of $\omega$, because

$$5=\{0,1,2,3,4\}\subseteq \{0,1,2,3,4,5,6,\dots \}=\omega .$$

Then every such subset has a minimum since that's true for subsets of $\omega$.

An example of a wellordering other than a natural number or $\omega$ is the set

$$\omega \cup \{\omega \}=\{0,1,2,3,4,\dots ,1002345,\dots ,\omega \},$$

again ordered by $\in$. This ordering is called $\omega +1$, but more on that later. Of coure, you are probably curious about linear orderings which are no wellorderings. First, we also have the notion of a maximum: $y\in X$ is the maximum of $Y\subseteq X$ if (1) $y\in Y$ and (2) every other element of $Y$ is smaller than $y$. In the case of natural numbers, the subset $Y:=\omega$ does not have a maximum! Now, to get an example of an ordering without a minimum we just need to transform maxima into minima. Let ${<}^{\ast }$ be the ordering on $\omega$ obtained by "turning around" the standard ordering, that is we say that $m{<}^{\ast }n$ if and only if $m>n$. Then the ordering $(\omega ,{<}^{\ast })$ does not have a minimum!