6. Orders

Definition and examples

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

  • reflexivity: \forall_{a\in A} a\preceq a,
  • antisymmetry: \forall_{a,b\in A} a\preceq b \land b\preceq a\rightarrow a=b,
  • transitivity: \forall_{a,b,c\in A} a\preceq b\land b\preceq c\rightarrow a\preceq c.

Obviously, \leq 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 n|n (reflexivity), and if n|m and m|n, then n=m (antisymmetry), and finally if n|m and m|k, then n|k (transitivity).

Furthermore, \subseteq on \mathcal{P}(X), for any set X, is also a partial order.

On the other hand, a relation r on \oP(\mathbb{N})\setminus\{\varnothing\} defined as A r B\leftrightarrow \min A\leq \min B, is not a partial order, although it is reflexive and transitive, because it is not antisymmetric: \{0\} r \{0,1\} and \{0,1\} r \{0\}, but \{0\}\neq \{0,1\}.

For any partial order \preceq, we can consider its strict version \preceq\setminus = (which is formally not a partial order, because it is not reflexive), i.e. the order a\prec b\leftrightarrow a\preceq b\land a\neq b.

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 \{2,3,4,5,6,8,9,12,24\}.

Let \preceq be a partial order on a set A. We shall say that m\in A is:

  • a maximal element, if \forall_{a\in A} m\preceq a \rightarrow a=m,
  • a minimal element, if \forall_{a\in A} a\preceq m \rightarrow a=m,
  • the greatest element, if\forall_{a\in A} a\preceq m,
  • the least element, if \forall_{a\in A} m\preceq a.

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: 2,3 and 5, and three maximal elements 5,9 and 24. Therefore the least and greatest elements do not exist. On the other hand in the order \langle \mathbb{N},\leq\rangle there is one minimal element: 0 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 \preceq on a set A, we now consider a subset B\subseteq A. We shell say that a\in A is:

  • a lower bound of B, if \forall_{b\in B} a\preceq b,
  • an upper bound of B, if \forall_{b\in B} b\preceq a,
  • the infimum of B (denoted by \inf B), if it is the greatest element in the set of all lower bounds of B,
  • the supremum of B (denoted by \sup B), if it is the least element in the set of all upper bounds of B.

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

E.g. consider the order \{2,3,4,5,6,8,9,12,24\},|, and let B=\{4,8,12\}. The set of its lower bounds \{2,4\} has the greatest element, so \inf B=4 and it is the least element of B. The set of all upper bounds is \{24\}, so \sup B=24. This time it is not an element of B. On the other hand, let C=\{2,3,6\}. This set has the greatest element, so it is its supremum, \sup C=6. Meanwhile, the set of its lower bounds is empty, so the infimum of B does not exist.

Linear, dense, well founded and well orders

A partial order \langle A,\preceq\rangle is dense, if for all a,b\in A such that a\neq b, there exists c\in A such that a\preceq c\preceq b, but c\neq a and c\neq b. E.g. the order \langle\mathbb{Q},\leq\rangle is dense, because if a,b\in\mathbb{Q}, then (a+b)/2\in\mathbb{Q}. On the other hand, \langle\mathbb{N},\leq\rangle is not dense, because there does not exist such c for a=0 i b=1.

A partial order \langle A,\preceq\rangle is linear, if all two elements are comparable, i.e. if \forall_{a,b\in A} a\preceq b\lor b\preceq a. The order \langle\mathbb{N},\leq\rangle is an example of such an order. On the other hand, \langle\mathcal{P}(\mathbb{N}),\subseteq\rangle is not linear, because neither \{0\}\subseteq \{1\}, nor \{1\}\subseteq\{0\}.

A partial order \langle A,\preceq\rangle is well founded, if every non-empty subset B\subseteq A has a minimal element (or equivalently if there does not exist an infinite sequence of elements of A which is strictly decreasing). Therefore, for example, \langle\mathbb{N},\leq\rangle is a well founded order. The same is true for \langle\mathbb{N},|\rangle. But neither the order \langle\mathbb{Z},\leq\rangle, nor \langle[0,1],\leq\rangle is not well founded.

A partial order is a well order if it is well founded and linear. The order \langle\mathbb{N},\leq\rangle is a well order, but \langle\mathbb{N},|\rangle is not, because it is not linear.

Lexicographical order

Given two partial orders \langle A,\leq_A\rangle oraz \langle B,\leq_B\rangle it is easy to define an order on A\times B. Namely:

    \[\langle a,b\rangle\leq_{lex}\langle a',b'\rangle \leftrightarrow (a\leq_A a' \land a\neq a')\lor (a=a'\land b\leq_B b').\]

Similarly, one can define an order on A^n or even on A^\N.

    \[\langle x_n\rangle\leq_{\lex}\langle y_n\rangle \leftrightarrow \langle x_n\rangle=\langle y_n\rangle \land \exists_k \left(\forall_{m< k} x_m=y_m \land (x_k\leq_A y_k\land x_k\neq y_k)\right).\]

Order isomorphism

Given two partially ordered sets: \langle A,\leq_A\rangle and \langle B,\leq_B\rangle, a function f\colon A\to B, will be called an order isomorphism, if it is a bijection, and if for any a,b\in A, a\leq_A b iff f(a)\leq_B f(b).

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, \langle \mathbb{N},\leq\rangle is isomorphic to \langle \mathbb{Z}\setminus\mathbb{N},\geq\rangle. The isomorphism is f(n)=-n-1. Indeed, it is a bijection, and n\leq m iff -n-1\geq -m-1.

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 3 minimal elements. If an there are exactly 3 minimal elements in a partially ordered set \langle A,\leq_A\rangle, and there are 5 minimal elements in \langle B,\leq_B\rangle, then those two orders cannot be isomorphic.

E.g. the partially ordered sets \langle\mathbb{N}\setminus\{0\},|\rangle and \langle \mathcal{P}(\mathbb{N}),\subseteq \rangle are not isomorphic. An invariant, which differs them is e.g. the following sentence: there exists an element which has exactly 3 elements less or equal to it. In the first ordered set such an element exists: e.g. 4 has exactly 3 divisors: 1,2,4. In the second there is no such element, because the number of subsets of a finite set is always a power of 2.

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 \langle A,\preceq\rangle is a partially ordered set with A\neq\varnothing, such that any chain (L\subseteq A is a chain, if any two elements of L are comparable with respect to \preceq) has an upper bound, then there is a maximal element in A.

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 V be a vector space, and let A be the family of all linearly independent sets in V ordered by inclusion. A is non-empty, because \varnothing\in A. Now let L be a chain in A. We will prove that \bigcup L\in A, i.e. that a union of a chain of linearly independent sets is linearly independent. Let v_1,\ldots v_n\in \bigcup L. Therefore, there exist U_1,\ldots U_n\in L, such that v_1\in U_1,\ldots v_n\in U_n. Since L is a chain, we among those n sets we can find a set which contains all other as its subsets. Let it be U_k. Bu then v_1,\ldots, v_n\in U_k are elements of a linearly independent set, so are linearly independent. Since those were any vectors from \bigcup L, it is also linearly independent. Thus, \bigcup L is an upper bound of L in A. Hence, there exists a maximal element in A, i.e. a maximal set of linearly independent vectors, in other words a basis.