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
. 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
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
, which means that you denote it by
for two elements
. For example, the default ordering on
is denoted by
. 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
. 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
. Again, for
, you should immediately accept that.
A third axiom, the axiom of reflexivity
, is less intuitive:
. 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:
- Reflexivity: For all we have .
- Antisymmetry: For all , from and follows .
- Transitivity: For all , from and follows .
Make sure you fully understand that. Use the example
if necessary. We give some further examples.
Of course, there are the canonical examples
Another common example is the divisibility
relation between non-negative integers: For two integers
), if there is an
, or equivalently, if
(where in this case we set
). For example,
, then both
, so clearly,
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,
and vice versa, 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
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
be given. A function
between the domains is called (order-)homomorphism
. If additionally
is bijective, it is called (order-)isomorphism
. If such an
exists, then the ordering relations are called homomorphic
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
, and every occurence of
, then you will (mostly) get a true proposition again.
Let us look at the above examples. Obviously, from
, there is a homomorphism, namely
is just a superset of
. But also,
is a homomorphism, since
is equivalent to
. However, as there cannot be a bijection between
, both orders are clearly not isomorphic.
are also homomorphisms between
, 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.
is also a homomorphism from
(note that the same does not hold for
). To see that
are not isomorphic, notice that there is exactly one element
which has exactly two smaller elements (
), 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
. 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.