Partial orders

People like to compare things – which laptop is better, which film is more interesting, which restaurant has more delicious food. They also like to create different rankings, for example, music charts. This shows that we have an intuitive concept of order. But to use it in a mathematical model, we should formalize it.

What is a partial order?

Definition. A partial order on a set $A$ is a reflexive, anti-symmetric, and transitive relation on $A$.

Let's recall what all these properties mean.

Suppose we have some relation $R$ on $A$ (that is, a subset of $A \times A$). Instead of $(a, b) \in R$, we'll now write $a R b$. For $R$ to be a partial order, it is both necessary and sufficient that:

1. $aRa$ for any $a \in A$

2. if $aRb$ and $bRa$ then $a = b$

3. If $aRb$ and $bRc$, then $aRc$

A set $A$ with a partial order on it is called a partially ordered set, or simply a poset.

Examples of partial orders

Do we know such relations? Of course! For example, a "less or equal" relation on the set of real numbers is a partial order (check all the properties). As with many heavily used relations, it has its own special notation – we don't have to define $R$ and then write $aRb$, we just write $a \leq b$.

A common practice is to use a similar notation $\preceq$ for an arbitrary partial order not popular enough to have its own symbol. If $a \preceq b$ and $a \neq b$, we write $a \prec b$. Note that to completely define a partial order $\preceq$, we may consider only unequal elements and describe when $a \prec b$.

Another example is the relation "$a$ divides $b$" on the set of natural numbers. That means that $b = ak$ for some natural $k$. It is reflexive, because $a = a \cdot 1$ for any $a$. It is anti-symmetric, because, if $b = ak$ and $a = bl$, then $a = (ak)l = a(kl)$ and the only possibility to satisfy this equation for natural numbers is to take $k = l = 1$. It is transitive, because, if $b = ak$ and $c = bm$, then $c = (ak)m = a(km)$.

Let's look at a set of three elements, say $\{1,3,7\}$, and let us define $aRb$ as $a$ is a subset of $b$. In this case, we define the set $A$ as a set of subsets of $\{1,3,7\}$, then we get: $A=\{\{1\},\{3\},\{7\},\{1,3\},\{1,7\},\{3,7\},\{1,3,7\}\}$. You can check yourself that all the required properties are satisfied and so, it is a partial ordering.

Linear orders

Introducing linear orders, often referred to as total orders or full orders, we will look back at the previous examples. What differences can you see between the two given examples of partial orders? They are defined on different sets in different ways, but perhaps the key difference is the following. You can compare any two real numbers and say that one of them is less or equal to the other. But there are pairs of natural numbers where neither of them divides the other one. 3 does not divide 8, but 8 also doesn't divide 3. So we introduce a new definition:

Definition. A linear order $R$ is a partial order with the additional property that for any $a, b \in A$ either $a R b$ or $b R a$.

So our first example is a linear order while the second one is not.

Another example of a linear order is alphabetical order. We can check that it satisfies the three original properties, as well as the additional one. First, we look at a small part of the alphabet, say $\{a,b,c\}$, because if it works just for these three, it will work for the rest. You can imagine that there is a numerical value associated with each of the elements, starting with $1$ for $a$, $2$ for $b$, and so on. Thus, we have a set $\{1,2,3\}$ and $\le$ as our $R$, and we proceed just like with the first example from the previous paragraph.

Covering relations

Let $(A, \preceq)$ be a poset. We say that an element $b \in A$ covers an element $a \in A$ if $a \prec b$ and there is no element $c \in A$ "between them" – such that $a \prec c \prec b$ . The set of pairs $(a, b)$ such that $b$ covers $a$ is called the covering relation of $(A, \preceq)$. Note that if we know just the covering relation we can reconstruct the original order.

Minimal, least, maximal, and greatest elements

An element $a$ of a poset $(A, \preceq)$ is called maximal if it is "not less than any element of the poset" – that means, there is no $b \in A$ such that $a \prec b$. Similarly, an element of a poset is called minimal if there is no $b \in A$ such that $b \prec a$.

The greatest element $a$ of a poset $(A, \preceq)$ is an element that is greater than any other element – that is, $b \prec a$ for any $b \in A$. Similarly, $a$ is the least element if $a \prec b$ for any $b \in A$.

In our common life, we often use the words "maximal" and "greatest" as synonyms, but that's not true in math. Suppose, for example, that we have some set $U$. The set of all its subsets with relation $\subseteq$ is partially ordered, and $U$ itself is both maximal and greatest element. Now let's consider the set of all proper subsets of $U$ with the same relation $\subseteq$. We find out that there appear maximal proper subsets, none of which can be called the greatest. To be more concrete, let's take $U = \{1, 2, 3\}$. The proper subsets $\{1, 2\}$, $\{1, 3\}$ and $\{2, 3\}$ are maximal because none of them is contained in another proper subset. But none of them is the greatest proper subset – for that it should contain the other two. Of course, the same difference exists between concepts of "minimal" and "least" elements.

Lexicographical order

An especially important example of partial orders – or rather a whole class of such examples – is the so-called lexicographical order. Lexicography is the study of some language's vocabulary, and its practical side is creating dictionaries. How are the words in an ordinary English dictionary ordered? Firstly, there are the words starting from the letter A, then those starting from the letter B, and so on. Among the words starting with A, the words with the second letter A (such as the famous 'aardvark') precede the words with second B ('abracadabra'), and the same principle applies to the next letters.

So, to define a lexicographical order, we need to already have some partially ordered set (in most applications, it is even linearly ordered) – an alphabet $\Sigma$. Its elements are usually called symbols. Now we can describe how to compare elements of $\Sigma^n = \Sigma \times \ldots \times \Sigma$ (sometimes called strings of length n)

$(a_1, a_2, \ldots, a_n) \prec (b_1, b_2, \ldots b_n) \text{ if } a_1 = b_1, \ldots, a_i = b_i, a _{i + 1} \prec b_{i + 1} \text { for some } i$An attentive reader may notice that lexicographers need to compare strings (words) of different lengths. That's not a problem – we can add to the alphabet an "empty symbol", which precedes any ordinary symbol. You can think that the shorter string has a "tail" of empty symbols.

It is also worth noting that lexicographical order is linear.

Conclusion

Now we know what is a partial order is and what is a linear order. Here is a quick recap of the main points:

• The partial order on a given set is a reflexive, transitive, and anti-symmetric relation on the set.

• A set that has a partial order on it is called a "partially ordered set" or "poset".

• Linear orders $R$ are partial orders with an additional condition such that for any $a, b \in A$ either $a R b$ or $b R a$.

• An element is called a maximal element if it is not less than any element of the poset and conversely for a minimal element.

• An element is called the greatest element if it is greater than any element of the poset and conversely for the least element.