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* , which is the set of elements which it compares. Orderings are usually denoted by a *relation symbol* in *infix-notation*, which means that you denote it by for two elements . For example, the default ordering on is denoted by , for . We denote this ordering as pair , for example, the default order on we denote by .

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 and , then . This should be pretty clear when looking at the given example ! 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 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 and , then . Again, for , you should immediately accept that.

A third axiom, the axiom of*reflexivity*, is less intuitive: for all . It holds for . 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 . 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 to an ordering relation are:

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 and be given. A function between the domains is called (order-)*homomorphism*, if implies . If additionally is bijective, it is called (order-)*isomorphism*. If such an 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 , and rename every occurence of by , and every occurence of by , then you will (mostly) get a true proposition again.

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

And, to make that clear: The following part is

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

Every ordering relation has a

There are several axioms for several purposes which can be postulated for orderings, but the one thing that all orderings have in common is

While transitivity is an important property of orderings, it is not sufficient. For example, the relation is also transitive, but it is not an ordering relation (it is a so-called

A third axiom, the axiom of

So the axioms for to an ordering relation are:

*Reflexivity:*For all we have .*Antisymmetry:*For all , from and follows .*Transitivity:*For all , from and follows .

Of course, there are the canonical examples , , .

Another common example is the *divisibility* relation between non-negative integers: For two integers we say ( divides ), if there is an such that , or equivalently, if (where in this case we set ). For example, , , but . Clearly, for , but for .

Trivially, .

If and , then both and , so clearly, .

If and , then and , so , therefore .

Thus, 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 on powersets, which turns out to also be an ordering relation: Say you consider , the powerset of , then of course, by definition, for . Let , and , then implies and vice versa, so . Let and , then implies , and implies , so . Therefore, for every set , 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 , for example, the set of letters with alphabetical order, but every other ordered set is sufficient, too. You then look at the set of finite sequences, and define the ordering by

- for all sequences , that is, the sequence of length is smaller than everything else (in dictionaries, however, this is usually not needed, as there is no such word)
- if and only if either for and , or for we have - in words, either starts with , or for the smallest in which they differ, we have

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

Now, let two ordering relations and be given. A function between the domains is called (order-)

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 , and rename every occurence of by , and every occurence of by , then you will (mostly) get a true proposition again.

Let us look at the above examples. Obviously, from , there is a homomorphism, namely , into - as is just a superset of . But also, is a homomorphism, since is equivalent to . However, as there cannot be a bijection between and , both orders are clearly not isomorphic.

Of course, and are also homomorphisms between and , 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 , then for . Thus, is also a homomorphism from into (note that the same does not hold for ). To see that and are not isomorphic, notice that there is exactly one element which has exactly two smaller elements ( and ), while there are infinitely many 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 and . That is right, they are the same ordering, just that the one's domain is bounded. One isomorphism can be given by

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.