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=\emptyset\), \(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 \(<^*\) be the ordering on \(\omega\) obtained by "turning around" the standard ordering, that is we say that \(m<^* n\) if and only if \(m>n\). Then the ordering \((\omega,<^*)\) does not have a minimum!

Comments

Post a Comment

Popular posts from this blog

Axiom of Powerset

So far, I listed Axioms of the Empty Set, Extensionality, Pairing, Union, Comprehension, Induction, Replacement, and Infinity. This is not the complete list making up the Mathematical Theory of Everything, we have to add two more axioms to the list. These axioms are called Powerset  and Choice . Axiom of Powerset is relatively easy to state: for every set \(x\) in the universe, there exists a set whose elements are exactly all subsets of \(x\) . As usual, Extensionality implies that such object must be unique and we denote it by \(P(x)\). So, the defining characteristic of the set \(P(x)\) is that a given set \(y\) belongs to \(P(x)\) if and only if \(y\) is a subset of \(x\). The other axioms don't imply existence of the powerset. More precise explanation of this will have to wait, but for now, we can kind of see that the set \(P(x)\) is "larger" than \(x\). If \(a\) is an element of \(x\), than \(\{a\}\) is a subset of \(x\), so an element of \(P(x)\). But there are oth...
Read more

Relations

I'll write this post in form of a dialogue between Master (M) and Apprentice (A). A: Say, O Noble Teacher, what are those "relations" that mathematicians always talk about? M: Why, my dear Apprentice, you have already seen one kind of relations! A: How so, O Exalted One? M: Well, \(\in\) is a relation and \(V\) is also a relation! These are class-sized relations. A: Oh, I see! But how does their "relation-ness" manifest? M: In the case of \(\in\), it divides pairs of sets \((x,y)\) into those for which \(x\) belongs to \(y\) and into those for which \(x\) does not belong to \(y\). So, it tells us whether the statement ''\(x\in y\)" is true or false for any particular pair of sets \((x,y)\). In this sense, they are no different from predicates or classes. Class-sized relations are the same thing as predicates. A: I seem to understand now! \(\in\) is a binary predicate, so a class-sized relation. \(V\) is a class, which is the same thing as a unary pr...
Read more