# Calculus

## Set Theory # Partial Orders

### Definitions

A binary relation $$R$$ on a non-empty set $$A$$ is called a (non-strict) partial order relation or partial ordering if and only if the relation is

• reflexive
• antisymmetric, and
• transitive.

To denote a partial order relation we use the notation $$\require{AMSsymbols}{\preccurlyeq,}$$ so instead of $$aRb$$ we often write $$a \preccurlyeq b.$$

If $$a \preccurlyeq b$$ and $$a \ne b,$$ then we usually write $$a \prec b.$$ In this case, the relation is called a strict partial order on set $$A.$$ It is irreflexive, antisymmetric, and transitive.

A set $$A$$ together with a partial order relation $$\preccurlyeq$$ is called a partially ordered set or poset and is denoted by $$\left( {A, \preccurlyeq } \right).$$

Two elements $$a$$ and $$b$$ of a partially ordered set $$\left( {A, \preccurlyeq } \right)$$ are said to be comparable, if and only if, either $$a \preccurlyeq b$$ or $$b \preccurlyeq a.$$ Otherwise we say that $$a$$ and $$b$$ are noncomparable or incomparable.

In a partially ordered set, it is not necessary that every pair of elements $$a$$ and $$b$$ be comparable. When all the elements of a set $$A$$ are comparable, the relation is called a total ordering.

Examples of Partial Order Relations

#### Subset Relation

The subset relation is denoted by $$\subseteq$$ and is defined on the power set $$\mathcal{P}\left( A \right),$$ where $$A$$ is any set of elements.

For any subset $$A_i$$ of $$\mathcal{P}\left( A \right),$$ the following is true: $${A_i} \subseteq {A_i}.$$ Hence, the relation $$\subseteq$$ is reflexive.

Suppose $${A_1}, {A_2}$$ are two any subsets of $$\mathcal{P}\left( A \right).$$ If $${A_1} \subseteq {A_2}$$ and $${A_2} \subseteq {A_1},$$ then by definition of set equality, $${A_1} = {A_2}.$$ This means that the subset relation is antisymmetric.

Let $${A_1} \subseteq {A_2}$$ and $${A_2} \subseteq {A_3}.$$ Consider an arbitrary element $$a \in {A_1}.$$ Since $${A_1} \subseteq {A_2},$$ we have $$a \in {A_2}.$$ Similarly, since $${A_2} \subseteq {A_3},$$ we have $$a \in {A_3}.$$ Hence, the relation $$\subseteq$$ is transitive.

We see that the subset relation on the power set $$\mathcal{P}\left( A \right)$$ is reflexive, antisymmetric, and transitive. So it is a partial ordering.

#### Divisibility Relation

The divisibility relation, denoted by “|”, on the set of natural numbers $$\mathbb{N} = \left\{ {1,2,3, \ldots } \right\}$$ is another classic example of a partial order relation.

The relation “|” is reflexive, because any $$a \in \mathbb{N}$$ divides itself.

The relation “|” is antisymmetric. Indeed, if $$a \mid b,$$ then $$ak = b,$$ where $$k$$ is an integer. Similarly, if $$b \mid a,$$ then $$b\ell = a,$$ where $$\ell$$ is an integer. Hence,

$ak\ell = a,\;\; \Rightarrow k\ell = 1.$

The last equation holds if only $$k = \ell =1,$$ which means that $$a = b.$$

The relation “|” is transitive. Suppose $$a \mid b$$ and $$b \mid c.$$ Then $$ak = b$$ and $$b\ell = c,$$ where $$k, \ell$$ are certain integers. Hence $$ak\ell = c,$$ and $$k\ell$$ is an integer. This means that $$a \mid c.$$

#### Some Other Examples

The following relations are partial orders:

• “The “less than or equal to” relation, denoted by $$\le,$$ on the set of real numbers $$\mathbb{R}$$ (which is in fact a total order);
• Similarly, the “greater than or equal to” relation, denoted by $$\ge,$$ on the set of real numbers $$\mathbb{R}$$;
• $$R = \left\{ {\left( {a,b} \right) \mid a,b \in Z, a = b + 1} \right\};$$
• “$$a$$ is an ancestor of $$b$$” is a partial order relation on the set of all people (provided each person is an ancestor of himself/herself);
• The set of events in special relativity is described by a partial order. An event $$b$$ can only be casually affected by an event $$a,$$ if $$a \preccurlyeq b$$ and both the events are in the future light cone.

## Solved Problems

Click or tap a problem to see the solution.

### Example 1

Which of these relations on the set $$A = \left\{ {1,2,3,4} \right\}$$ are partial orders?
1. $${R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.$$ $$\kern-2pt\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,4} \right)} \right\}.$$
2. $${R_2} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.$$ $$\kern-2pt\left.{\left( {3,3} \right),\left( {3,4} \right)} \right\},$$ $$\kern-2pt\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.$$
3. $${R_3} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.$$ $$\kern-2pt\left.{\left( {3,2} \right),\left( {3,4} \right),\left( {4,4} \right)} \right\}$$
4. $${R_4} = \left\{ {\left( {1,1} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {2,4} \right),} \right.$$ $$\kern-2pt\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\},$$ $$\kern-2pt\left.{\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.$$

### Example 2

Determine whether the relation $$R$$ represented by the matrix is a partial order. ${{M_R} = \left[ {{a_{ij}}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0\\ 0&1&0&0&0\\ 1&1&1&1&1\\ 0&0&0&1&0\\ 0&0&0&1&1 \end{array}} \right]}$

### Example 3

The divisibility relation is given on the set $$A = \left\{ {2,3,4,6,8,10} \right\}.$$ List all the non-comparable pairs of elements of $$A.$$

### Example 4

Suppose $$R$$ is a partial order on a set $$A.$$ Prove that $$R^{-1}$$ is also a partial order.

### Example 5

Let $$R$$ and $$S$$ be partial orders on a set $$A.$$ Determine whether the intersection relation $$R \cap S$$ is also a partial order on $$A.$$

### Example 6

Let $$R$$ and $$S$$ be partial orders on a set $$A.$$ Determine whether the union relation $$R \cup S$$ is also a partial order on $$A.$$

### Example 1.

Which of these relations on the set $$A = \left\{ {1,2,3,4} \right\}$$ are partial orders?
1. $${R_1} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.$$ $$\kern-2pt\left.{\left( {2,4} \right),\left( {3,3} \right),\left( {4,4} \right)} \right\}.$$
2. $${R_2} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,1} \right),\left( {2,2} \right),} \right.$$ $$\kern-2pt\left.{\left( {3,3} \right),\left( {3,4} \right)} \right\},$$ $$\kern-2pt\left.{\left( {4,2} \right),\left( {4,4} \right)} \right\}.$$
3. $${R_3} = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {1,4} \right),\left( {2,2} \right),} \right.$$ $$\kern-2pt\left.{\left( {3,2} \right),\left( {3,4} \right),\left( {4,4} \right)} \right\}$$
4. $${R_4} = \left\{ {\left( {1,1} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {2,4} \right),} \right.$$ $$\kern-2pt\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\},$$ $$\kern-2pt\left.{\left( {3,4} \right),\left( {4,3} \right),\left( {4,4} \right)} \right\}.$$

Solution.

1. $$R_1$$ is a partial order since it is reflexive, antisymmetric, and transitive.
2. $$R_2$$ is not transitive: $${\left( {1,3} \right), \left( {3,4} \right)} \in {R_2},$$ but $${\left( {1,4} \right)} \notin {R_2}.$$ Hence, $$R_2$$ is not a partial order.
3. $$R_3$$ is reflexive, antisymmetric, and transitive, so it is a partial order.
4. $$R_4$$ is not antisymmetric since $${\left( {2,3} \right)} \in {R_4}$$ and $${\left( {3,2} \right)} \in {R_4}.$$ This means that $$R_4$$ is not a partial order.

### Example 2.

Determine whether the relation $$R$$ represented by the matrix is a partial order. ${{M_R} = \left[ {{a_{ij}}} \right] }={ \left[ {\begin{array}{*{20}{c}} 1&1&0&0&0\\ 0&1&0&0&0\\ 1&1&1&1&1\\ 0&0&0&1&0\\ 0&0&0&1&1 \end{array}} \right]}$

Solution.

$$R$$ is reflexive since the matrix $$M_R$$ contains all diagonal elements

$\left( {1,1} \right),\left( {2,2} \right), \ldots ,\left( {5,5} \right).$

$$R$$ is antisymmetric since all non-reflexive elements of the matrix symmetric about the main diagonal are not equal to each other:

${a_{ij}} \ne {a_{ji}} \text{ for } i \ne j.$

For example,

${a_{12}} \ne {a_{21}},\;{a_{31}} \ne {a_{13}}.$

The relation $$R$$ is transitive:

${a_{31}} = 1, {a_{12}} = 1, \text{ and }{a_{32}} = 1;$

${a_{35}} = 1, {a_{54}} = 1, \text{ and }{a_{34}} = 1.$

Hence, the relation $$R$$ is a partial order.

### Example 3.

The divisibility relation is given on the set $$A = \left\{ {2,3,4,6,8,10} \right\}.$$ List all the non-comparable pairs of elements of $$A.$$

Solution.

Recall that the divisibility relation $$“a\mid b”$$ is defined as follows: the ordered pair $$\left( {a,b} \right)$$ belongs to the relation “|” if and only if $$a \lt b$$ and $$a$$ divides $$b.$$

The set $$A$$ contains the following non-comparable pairs of elements:

${\left( {2,3} \right),\left( {3,4} \right),\left( {3,8} \right),\left( {3,10} \right),}\kern0pt{\left( {4,6} \right),}\kern0pt{\left( {4,10} \right),}\kern0pt{\left( {6,8} \right),\left( {6,10} \right),}\kern0pt{\left( {8,10} \right).}$

### Example 4.

Suppose $$R$$ is a partial order on a set $$A.$$ Prove that $$R^{-1}$$ is also a partial order.

Solution.

Since $$R$$ is reflexive, we have $$\left( {a,a} \right) \in R$$ for all $$a \in A.$$ By interchanging the first and second element, we obtain the same identity pair $$\left( {a,a} \right) \in R.$$ Hence, $$\left( {a,a} \right) \in {R^{ – 1}},$$ so the relation $${R^{ – 1}}$$ is also reflexive.

The original relation $$R$$ is antisymmetric:

${\text{If} \left( {a,b} \right) \in R \text{ and} \left( {b,a} \right) \in R,\;}\kern0pt{ \text{then } a = b.}$

Using the definition of $${R^{ – 1}},$$ we can replace here $$\left( {a,b} \right) \in R$$ with $$\left( {b,a} \right) \in {R^{ – 1}}$$ and $$\left( {b,a} \right) \in R$$ with $$\left( {a,b} \right) \in {R^{ – 1}}.$$ Then the previous statement is written as

${\text{If} \left( {b,a} \right) \in R^{-1} \text{ and} \left( {a,b} \right) \in R^{-1},\;}\kern0pt{ \text{then } a = b,}$

which means that the inverse relation $${R^{ – 1}}$$ is antisymmetric.

Suppose that $$\left( {a,b} \right) \in {R^{ – 1}}$$ and $$\left( {b,c} \right) \in {R^{ – 1}}.$$ By definition of $${R^{ – 1}},$$ we can write

$\left( {b,a} \right) \in R \text{ and} \left( {c,b} \right) \in R.$

Since $$R$$ is transitive, we have

${\left( {c,a} \right) \in R,}\; \Rightarrow {\left( {a,c} \right) \in {R^{ – 1}}.}$

This proves the transitivity of $$R^{-1}.$$

Thus, the inverse relation $$R^{-1}$$ is a partial order.

### Example 5.

Let $$R$$ and $$S$$ be partial orders on a set $$A.$$ Determine whether the intersection relation $$R \cap S$$ is also a partial order on $$A.$$

Solution.

We need to consider three properties for the intersection relation $$R \cap S:$$ reflexivity, antisymmetry, and transitivity.

Since $$R$$ and $$S$$ are reflexive relations, then for any $$a \in A$$ we have

$\left( {a,a} \right) \in R \text{ and } \left( {a,a} \right) \in S.$

Hence

$\left( {a,a} \right) \in R \cap S$

for any $$a \in A,$$ so $$R \cap S$$ is also reflexive.

We prove the antisymmetry property by contradiction. Suppose that $$R \cap S$$ is not antisymmetric. Then

${\left( {a,b} \right) \in R \cap S \text{ and }}\kern0pt{ \left( {b,a} \right) \in R \cap S,}$

where $$a \ne b.$$ This means that

$\left( {a,b} \right) \in R,\;\left( {b,a} \right) \in R, \text{ and }$

$\left( {a,b} \right) \in S,\;\left( {b,a} \right) \in S,$

where $$a \ne b,$$ which is false since both relations $$R$$ and $$S$$ are antisymmetric. Hence, the assumption is false and the intersection relation $$R \cap S$$ is antisymmetric.

Let now

${\left( {a,b} \right) \in R \cap S \text{ and }}\kern0pt{\left( {b,c} \right) \in R \cap S.}$

Then

$\left( {a,b} \right) \in R,\;\left( {b,c} \right) \in R, \text{ and }$

$\left( {a,b} \right) \in S,\;\left( {b,c} \right) \in S.$

Both relations $$R$$ and $$S$$ are transitive (as they are partial orders). Therefore,

$\left( {a,c} \right) \in R \text{ and } \left( {a,c} \right) \in S,$

so we have

$\left( {a,c} \right) \in R \cap S,$

that is $$R \cap S$$ is a transitive relation on set $$A.$$

This proves that the intersection relation $$R \cap S$$ is a partial order. In other words, the property of partial ordering is closed under intersection.

### Example 6.

Let $$R$$ and $$S$$ be partial orders on a set $$A.$$ Determine whether the union relation $$R \cup S$$ is also a partial order on $$A.$$

Solution.

For any $$a \in A,$$ we have

$\left( {a,a} \right) \in R \text{ and } \left( {a,a} \right) \in S,$

because the relations $$R$$ and $$S$$ are reflexive. Hence,

$\left( {a,a} \right) \in R \cup S,$

that is the union relation $$R \cup S$$ is reflexive.

Using a counterexample, we can show that the union relation $$R \cup S$$ is not antisymmetric. Consider the set $$A = \left\{ {1,2,3} \right\}$$ and two relations on it:

${R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {2,3} \right),\left( {3,3} \right)} \right\},}$

${S = \left\{ {\left( {1,1} \right),\left( {2,1} \right),\left( {2,2} \right),\left( {3,1} \right),}\right.}\kern0pt{\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\}.}$

The relations $$R$$ and $$S$$ are partial orders since they are reflexive, antisymmetric, and transitive. Their union is given by

${R \cup S = \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {1,3} \right),\left( {2,1} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right),}\right.}\kern0pt{\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\}.}$

As it can be seen, every non-reflexive element has the corresponding reverse pair: $${\left( {1,2} \right)}$$ and $${\left( {2,1} \right)},$$ $${\left( {1,3} \right)}$$ and $${\left( {3,1} \right)},$$ $${\left( {2,3} \right)}$$ and $${\left( {3,2} \right)}.$$ This implies that $$R \cup S$$ is not antisymmetric.

Consider now two other relations on the same set $$A = \left\{ {1,2,3} \right\}:$$

$X = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,2} \right),\left( {3,3} \right)} \right\},$

$Y = \left\{ {\left( {1,1} \right),\left( {2,2} \right),\left( {3,2} \right),\left( {3,3} \right)} \right\}.$

The relations $$X$$ and $$Y$$ are partial orders. The union relation $$X \cup Y$$ is written in the form

${X \cup Y = \left\{ {\left( {1,1} \right),\left( {1,3} \right),\left( {2,2} \right),}\right.}\kern0pt{\left.{\left( {3,2} \right),\left( {3,3} \right)} \right\}.}$

As it can be seen, $$\left( {1,3} \right) \in X \cup Y,$$ $$\left( {3,2} \right) \in X \cup Y,$$ but $$\left( {1,2} \right) \notin X \cup Y,$$ so the union relation in this example is not transitive.

Thus, the union of partial orders does not need to be a partial order.