# 6. Orders

### Definition and examples

A relation on a set will be called a partial order if it satisfies the following three conditions:

• reflexivity: ,
• antisymmetry: ,
• transitivity: .

Obviously, on the reals is an example of a partial order. Indeed, it is reflexive, antisymmetric and transitive.

The relation of divisibility on the natural numbers is an another example. It is a partial order, because (reflexivity), and if and , then (antisymmetry), and finally if and , then (transitivity).

Furthermore, on , for any set , is also a partial order.

On the other hand, a relation on defined as , is not a partial order, although it is reflexive and transitive, because it is not antisymmetric: and , but .

For any partial order , we can consider its strict version (which is formally not a partial order, because it is not reflexive), i.e. the order .

### Maximal, minimal, greatest and least elements

Simple orders on finite sets can be easily graphically presented in the form of a Hasse diagram, in which greater elements are placed above the less elements, and neighbouring elements in the order are connected with lines. E.g. the following diagram shows the order of divisibility on .

Let be a partial order on a set . We shall say that is:

• a maximal element, if ,
• a minimal element, if ,
• the greatest element, if ,
• the least element, if .

Notice that in a set there can be many (or none) maximal (or minimal) elements, but there can at most one greatest (or least) element. In particular, if there are more than one maximal (respectively, minimal) elements, they are incomparable, so the greatest (respectively, least) element cannot exist (the reverse implication does not hold).

In the above example, we have three minimal elements: and , and three maximal elements and . Therefore the least and greatest elements do not exist. On the other hand in the order there is one minimal element: and it is also the least element. There are no maximal elements, and the greatest element does not exist.

### Bounds, infimum and supremum

Given an order on a set , we now consider a subset . We shell say that is:

• a lower bound of , if ,
• an upper bound of , if ,
• the infimum of (denoted by ), if it is the greatest element in the set of all lower bounds of ,
• the supremum of (denoted by ), if it is the least element in the set of all upper bounds of .

Notice that the infimum or the supremum of a set may not necessarily be an element of the considered subset . But, if has its greatest element (respectively, the least element), then it is its supremum (respectively, infimum).

E.g. consider the order , and let . The set of its lower bounds has the greatest element, so and it is the least element of . The set of all upper bounds is , so . This time it is not an element of . On the other hand, let . This set has the greatest element, so it is its supremum, . Meanwhile, the set of its lower bounds is empty, so the infimum of does not exist.

### Linear, dense, well founded and well orders

A partial order is dense, if for all such that , there exists such that , but and . E.g. the order is dense, because if , then . On the other hand, is not dense, because there does not exist such for i .

A partial order is linear, if all two elements are comparable, i.e. if . The order is an example of such an order. On the other hand, is not linear, because neither , nor .

A partial order is well founded, if every non-empty subset has a minimal element (or equivalently if there does not exist an infinite sequence of elements of which is strictly decreasing). Therefore, for example, is a well founded order. The same is true for . But neither the order , nor is not well founded.

A partial order is a well order if it is well founded and linear. The order is a well order, but is not, because it is not linear.

### Lexicographical order

Given two partial orders oraz it is easy to define an order on . Namely:

Similarly, one can define an order on or even on .

### Order isomorphism

Given two partially ordered sets: and , a function , will be called an order isomorphism, if it is a bijection, and if for any , iff .

Orders such that there exists an order isomorphism between them, will be called isomorphic. It means that those orders are identical from our point of view. For example, is isomorphic to . The isomorphism is . Indeed, it is a bijection, and iff .

### Invariants

If two partially ordered sets are isomorphic, to prove it, one needs to show an order isomorphism between them. But hoe to prove that two orders are not isomorphic? We will use invariants to do this. An invariant is a property of a partially ordered set which stays invariant under order isomorphisms. An invariant can be any property defined only with notion of order and cardinality. E.g. there exist exactly minimal elements. If an there are exactly minimal elements in a partially ordered set , and there are minimal elements in , then those two orders cannot be isomorphic.

E.g. the partially ordered sets and are not isomorphic. An invariant, which differs them is e.g. the following sentence: there exists an element which has exactly elements less or equal to it. In the first ordered set such an element exists: e.g. has exactly divisors: . In the second there is no such element, because the number of subsets of a finite set is always a power of .

### Zorn’s Lemma

There are a few important statements which are equivalent to the axiom of choice. On of them is Zermelo Theorem, which states that on every set one can define a well order. Other such statement is Zorn’s Lemma. It states that if is a partially ordered set with , such that any chain ( is a chain, if any two elements of are comparable with respect to ) has an upper bound, then there is a maximal element in .

Zorn’s Lemma is an important tool in mathematics which can be used to prove the existence of many important objects. E.g. on can prove that every vector space has a basis (a set of linearly independent vectors which is maximal with respect to inclusion) using Zorn Lemma. Indeed, let be a vector space, and let be the family of all linearly independent sets in ordered by inclusion. is non-empty, because . Now let be a chain in . We will prove that , i.e. that a union of a chain of linearly independent sets is linearly independent. Let . Therefore, there exist , such that . Since is a chain, we among those sets we can find a set which contains all other as its subsets. Let it be . Bu then are elements of a linearly independent set, so are linearly independent. Since those were any vectors from , it is also linearly independent. Thus, is an upper bound of in . Hence, there exists a maximal element in , i.e. a maximal set of linearly independent vectors, in other words a basis.