FIXING OLDS

On Infinity 5 - Digression: Orderings
Tue, 31 Jan 2012 15:05:00 GMT

My original intention was to write a post about ordinal numbers, but it turned out that it is a lot harder to give a clear and simple explanation than I expected. So I decided to do a little digression on ordering relations. It is not directly about infinity, but related and needed for the theory of ordinal numbers.

To understand this part 5 of my series, be sure to have read the previous parts 1, 2, 3 and 4. Especially, you should have an idea of what a bijection is, how infinity is defined, what a powerset is, and what countable and uncountable sets are.

And, to make that clear: The following part is hard. You have to say good bye to some of your "intuitive" thoughts on mathematical objects, and have to be open to new concepts that are abstract in a way that non-mathematicians usually decline. We are now entering a world, in which finally there is no place for "calculating" and visual conceptions. I will try to make it as simple as possible, omitting a lot of complicated parts, but still, the objects I will write about are not as intuitive as the objects discussed before were.

However, it should be understandable, but you might need to read a few parts of it at least twice.

So, this post is about the theory of ordering relations. Many parts of applied mathematics are, in the end, about orderings. Sorting algorithms, for example. Whenever you look for a name in an alphabetical list, you apply basic properties of ordering relations.

Every ordering relation has a domain D, which is the set of elements which it compares. Orderings are usually denoted by a relation symbol R in infix-notation, which means that you denote it by aRb for two elements a,b\in D. For example, the default ordering on \mathbb{N} is denoted by a\le b, for a,b\in\mathbb{N}. We denote this ordering as pair (R,D), for example, the default order on \mathbb{N} we denote by (\le,\mathbb{N}).

There are several axioms for several purposes which can be postulated for orderings, but the one thing that all orderings have in common is transitivity: If aRb and bRc, then aRc. This should be pretty clear when looking at the given example (\le,\mathbb{N})! And if you look at other ordering relations, like the alphabetical (lexicographical) ordering of names, you will notice that you implicitly assume this property: When searching in a phone book, you look up one item, then decide whether you have to browse further, and find a second item, and then decide whether the item you search for lies between those two items.

While transitivity is an important property of orderings, it is not sufficient. For example, the relation (=,\mathbb{N}) is also transitive, but it is not an ordering relation (it is a so-called equivalence relation, another class of relations we will not discuss here). We need to give account to the "direction" of the ordering somehow. This is done by the axiom of antisymmetry: If aRb and bRa, then a=b. Again, for (\le,\mathbb{N}), you should immediately accept that.

A third axiom, the axiom of reflexivity, is less intuitive: aRa for all a. It holds for (\le,\mathbb{N}). The problem here is that there are two major concepts of ordering relations, the strict ordering relations and the partial ordering relations. An example for a strict order would be (<,\mathbb{N}). In general, partial orders are orders of the type "less-than-or-equal", while strict orders are of the type "less-than". We will only deal with partial ordering relations, for which reflexivity holds.

So the axioms for (R,D) to an ordering relation are:
  • Reflexivity: For all a\in D we have aRa.
  • Antisymmetry: For all a,b\in D, from aRb and bRa follows a=b.
  • Transitivity: For all a,b,c\in D, from aRb and bRc follows aRc.
Make sure you fully understand that. Use the example (\le,\mathbb{N}) if necessary. We give some further examples.

Of course, there are the canonical examples (\le,\mathbb{Z}), (\le,\mathbb{Q}), (\le,\mathbb{R}).

Another common example is the divisibility relation between non-negative integers: For two integers a,b\in\mathbb{N}_0 we say a|b (a divides b), if there is an x\in\mathbb{N}_0 such that a\cdot x=b, or equivalently, if \frac{b}{a}\in\mathbb{N}_0 (where in this case we set \frac{0}{0}=1). For example, 1|2, 2|4, but 2\not |3. Clearly, a|0 for a\in\mathbb{N}_0, but 0\not |a for a\in\mathbb{N}_0\backslash\{0\}.
Trivially, a|a.
If a|b and b|a, then both \frac{a}{b}\in\mathbb{N}_0 and \frac{b}{a}\in\mathbb{N}_0, so clearly, a=b.
If a|b and b|c, then \frac{b}{a}\in\mathbb{N}_0 and \frac{c}{b}\in\mathbb{N}_0, so \frac{c}{a}=\frac{c}{b}\cdot\frac{b}{a}\in\mathbb{N}_0, therefore a|c.
Thus, (|,\mathbb{N}_0) is an ordering relation.

People familiar with arithmetics will know that we can extend the divisibility relation to negative integers, in the same way. However, this would not be an ordering in our sense anymore (exercise: why?).

Somewhat related to the divisibility relation is the subset relation \subseteq on powersets, which turns out to also be an ordering relation: Say you consider \mathfrak{P}(A), the powerset of A, then of course, by definition, B\subseteq B for B\in\mathfrak{P}(A). Let B\subseteq C, and C\subseteq B, then x\in B implies x\in C and vice versa, so B=C. Let B\subseteq C and C\subseteq D, then x\in B implies x\in C, and x\in C implies x\in D, so B\subseteq D. Therefore, for every set A, (\subseteq,\mathfrak{P}(A)) is an ordering relation.

Something you should basically know from phone books and dictionaries is the lexicographic order. It bases on an already given order (R,O), for example, the set of letters with alphabetical order, but every other ordered set is sufficient, too. You then look at the set O^{<\omega} of finite sequences, and define the ordering (R_{lex},O^{<\omega}) by

  • () R_{lex} a for all sequences a, that is, the sequence of length 0 is smaller than everything else (in dictionaries, however, this is usually not needed, as there is no such word)
  • (a_1,\ldots,a_n) R_{lex} (b_1,\ldots,b_m) if and only if either a_i=b_i for 1\le i \le n and m>n, or for j=\min\{i|a_i\neq b_i\} we have a_i R b_i - in words, either (b_1,\ldots,b_m) starts with (a_1,\ldots,a_n), or for the smallest j in which they differ, we have a_j R b_j
You should convince yourself that this is actually the intuitive lexicographical order.

As mathematicians have to deal with a lot of structures, they try to find similarities between them, and use techniques found for known structures on unknown ones. That is why they rather talk about a general "ordering relation" than about a concrete given order - there are many principles that simply hold for every such structure. From this desire comes the technique of finding morphisms between structures. Morphisms are (usually) structure-preserving functions, that is, functions that you can apply on elements without losing special relations between them. This is a highly abstract concept and we will not discuss it here in detail, but knowing this may be motivating. So, we are going to see certain kinds of morphisms between ordering relations. Keep in mind that this is abstract - if you do not understand its purpose, write it down with concrete given relations for a better chance of understanding.

Now, let two ordering relations (R,D) and (Q,C) be given. A function f:D\rightarrow C between the domains is called (order-)homomorphism, if aRb implies f(a) Q f(b). If additionally f is bijective, it is called (order-)isomorphism. If such an f exists, then the ordering relations are called homomorphic/isomorphic.

An intuitive understanding of this should be best given when thinking about homomorphisms and isomorphisms as some sort of "renamings" of the elements, which is permitted without losing relevant properties. That is, if you have some true proposition about (R,D), and rename every occurence of a\in D by f(a)\in C, and every occurence of R by Q, then you will (mostly) get a true proposition again.

Let us look at the above examples. Obviously, from (\le,\mathbb{N}), there is a homomorphism, namely f(x)=x, into (\le,\mathbb{R}) - as \mathbb{R} is just a superset of \mathbb{N}. But also, g(x)=2\cdot x+9 is a homomorphism, since a\le b is equivalent to 2\cdot a+9\le 2\cdot b+9. However, as there cannot be a bijection between \mathbb{N} and \mathbb{R}, both orders are clearly not isomorphic.

Of course, f and g are also homomorphisms between (\le,\mathbb{Z}) and (\le,\mathbb{Q}), and the question arises, whether these orderings are isomorphic. On the other hand, between two distinct rational numbers there are always infinitely many other rational numbers, and this is not the case for integers, so both orderings cannot be isomorphic.

If a|b, then a\le b for a,b\in\mathbb{N}_1. Thus, f is also a homomorphism from (|,\mathbb{N}_1) into (\le,\mathbb{N}_1) (note that the same does not hold for \mathbb{N}_0). To see that (|,\mathbb{N}_1) and (\le,\mathbb{N}_1) are not isomorphic, notice that there is exactly one element a=2 which has exactly two smaller elements (1 and 2), while there are infinitely many a with exactly two divisors, namely all the primes.

You may have noticed that we did not yet give an example for isomorphic orderings. That is due to the fact that it is rather hard to find such orderings which are mathematically interesting, not overkill, and not somehow "artificial" - mathematically, isomorphic structures need not be distinguished, and most theorems over structures are only "up to isomorphism". However, there are some examples, one is (\le,\mathbb{Q}) and (\le,\mathbb{Q}^{>0}). That is right, they are the same ordering, just that the one's domain is bounded. One isomorphism can be given by

h(x) =\left\{\begin{array}{cl}\frac{1}{1-x} & \mbox{for } x\le 0 \\ x+1 & \mbox{for } x>0 \end{array} \right.

We leave the proof as an exercise (it should be provable by school math).

It turns out that an even more special kind of ordering relations, the well-orderings, are useful to describe infinitary objects, and get a way of "enumerating" them. However, we will discuss this in the next part.