Naive Set Theory: Relations

Order Relations


Order relations are as common and important as equivalence relations, although rather than express the similarity of elements in a set, they express how elements can be arranged in a particular way. While there are in fact many different kinds of order relations, the plain term "order" by default refers to a strict total order. A strict total order $<$ on a set $S$ is a relation with the following properties:

  • Comparability: For all $x,y \in S$ such that $x \neq y$, either $x < y$ or $y < x$.

  • Irreflexivity: For no $x \in S$ is it true that $x < x$.

  • Transitivity: For all $x,y,z \in S$, if $x < y$ and $y < z$, then $x < z$.

A set equipped with a strict total order is called a totally ordered set (the term "strict" is omitted for reasons that will soon become clear). The use of the $<$ symbol is intentional, as $<$ is used to denote the "usual" order relations on familiar sets such as $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$. The usual order relations on these sets convey what you expect them to: $1<2$, $\dfrac{3}{4} < \dfrac{10}{3}$, and $e < \pi$. These order relations can be rigorously defined once their respective sets have been defined, but for now we can take their familiar properties on good faith.

Because strict total orders are the most commonplace, they have acquired many names. Linear orders and simple orders are additional terms for total orders, whose corresponding sets are said to be linearly ordered or simply ordered, respectively. Fear not - they all mean the same thing. Additionally, in the name of concision, we can use abbreviations like $a < x < b$ to express $a < x$ and $x < b$.

The terms "strict" and "total" are used to clarify what kind of order relation we are talking about, as there are in fact four types. In addition to strict total orders, there are weak total orders. A weak total order $\leq$ on a set $S$ is a relation with the following properties:

  • Comparability: For all $x,y \in S$ such that $x \neq y$, either $x \leq y$ or $y \leq x$.

  • Reflexivity: $x \leq x$ for all $x \in S$

  • Transitivity: For all $x,y,z \in S$, if $x < y$ and $y < z$, then $x < z$.

The only difference between strict total orders and weak total orders is that irreflexivity is swapped out for reflexivity. The choice of the $\leq$ symbol is intentional, as the less than or equal to relation is a weak total order. Weak total orders are often defined in terms of strict total orders, as the "or equal to" part is clear, but the "less than" part must be defined. Thus, from any strict total order you can construct a weak total order by adding all pairs of the form $(x,x)$ for $x \in S$. This is why we don't often use the term "strictly totally ordered," as order part is captured in both instances by the strict total order, and the strictness or weakness part is captured by the use of $<$ or $\leq$, respectively.

In addition to strict and weak order relations, which note the reflexivity or irreflexivity of the relation, respectively, there are total and partial orders. The above two order relations are called "total" because every element in the set is comparable to one another. In contrast, partial order relations do not have this constraint. A strict partial order $<$ on a set $S$ is a relation with the following properties:

  • Asymmetry: For all $x, y \in S$, if $x < y$, then $y \nless x$.

  • Irreflexivity: For no $x \in S$ is it true that $x < x$.

  • Transitivity: For all $x, y, z \in S$, if $x < y$ and $y < z$, then $x < z$.

A set equipped with a strict partial order is said to be partially ordered. A strict partial order is just like a strict total order, except it swaps out the comparability requirement for the weaker asymmetry requirement. Though the two are similar, note that asymmetry contains an important "if" - it says "if $x<y$, then $y \nless x$. It may not be the case that $x < y$. If either $x < y$ or $y < x$, then $x$ and $y$ are said to be comparable, and if not, then they are said to be incomparable. The continued use of the $<$ symbol should not be a problem, as the context of any discussion of orders should remove any ambiguity.

An example of a strict partial order is a biological family tree, where each mother and father pair are less than their children. Parents and their children are comparable, but siblings are not comparable, and neither are half-siblings or parents.

The last main type of order relation is the weak partial order. Given the previous three definitions, you can likely figure out the definition yourself! A weak partial order $\leq$ on a set $S$ is a relation with the following properties:

  • Antisymmetry: For all $x,y \in S$, if $x \leq y$ and $y \leq x$, then $y = x$.

  • Reflexivity: $x \leq x$ for all $x \in S$

  • Transitivity: For all $x,y,z \in S$, if $x < y$ and $y < z$, then $x < z$.

The combinations of strict and weak with total and partial are organized in the below table:

  Strict Weak
Total Comparable and irreflexive Comparable and reflexive
Partial Asymmetric and irreflexive Antisymmetric and reflexive

Order relations can be further generalized by removing properties or refined by adding ones, but these four orders are a good starting point. Preorders are generalizations of orders, and strict weak orderings (regrettably named) refer to strict partial orders where incomparability is transitive. In fact, the study order relations and their friends has an entire field dedicated to them called Order Theory. However, if we are to continue on with Set Theory, we will have to contain our excitement for orders for now.


Problems

  1. Let $S = \{a, b, c\}$, and let $\prec$ be a relation on $S$ such that $\prec = \{ (a,b), (b,c) \}$. Is $\prec$ an order relation? If so, show which three properties it fulfills for the correct one. If not, explain why not.

    $\prec$ is not an order relation because it violates transitivity. $a \prec b$ and $b \prec c$, but the pair $(a, c)$ is missing. In the case of total orders, comparability is violated as well, as neither $(a, c)$ nor $(c, a)$ is present.

    Show Answer
  2. Show that a non-empty relation cannot be both an equivalence relation and a strict order relation of either kind.

    An equivalence relation $R$ on a set $A$ requires reflexivity, namely $aRa$ for all $a \in A$, although this property precludes it from being an order relation, which by irreflexivity prohibits $aRa$ for any $a \in A$.

    Show Answer
  3. Let $R$ be a relation on a set $A$, and let $T$ be a relation defined by $T = \{ (a,b) : (b,a) \in R \}$. Prove that if $R$ is a total order relation, then $T$ is a total order relation.

    Assume $R$ is an order relation. We must show that $T$ fulfills the three properties of order relations.

    Comparability: For each pair of distinct elements $a$ and $b$ in $A$, either $(a,b) \in R$ or $(b, a) \in R$. If $(a,b) \in R$, then $(b,a) \in T$, and if instead $(b,a) \in R$, then $(a,b) \in T$. Therefore $T$ fulfill comparability.

    Irreflexivity: For no $a \in A$ is there a pair $(a, a) \in R$, therefore there is no corresponding pair $(a, a) \in T$. Therefore $T$ is irreflexive.

    Transitivity: If $(a, b) \in R$ and $(b, c) \in R$, then $(b, a) \in T$ and $(c, b) \in T$. By transitivity in $R$, $(a, c) \in R$, so therefore $(c, a) \in T$. Because $(c, b) \in T$ and $(b, a) \in T$ implies $(c, a) \in T$, $T$ is transitive.

    We conclude that $T$ is a total order.

    Show Answer
  4. Trichotomy: Let $<$ be a total order relation on $S$. Show that for all $a, b \in S$ exactly one of the following holds: $a<b$, $a=b$, or $a>b$.

    If $a\neq b$, then by comparability, either $a \nless b$ or $b \nless a$. If $a=b$, then by nonreflexivity $a\nless b$ and $b \nless a$, lest $a < a$ or $b < b$.

    Show Answer
  5. Let $R$ be a strict total order on a set $S$, and let $U = \{(x, x) : x \in S\}$. Show that $R \cup U$ is a weak total order on $A$.

    • Comparability: Let $x, y \in S$. If $x \neq y$, then either $(x, y) \in R$ , in which case $(x, y) \in R \cup U$, or $(y, x) \in R$, in which case $(y, x) \in R \cup U$.

    • Reflexivity: Let $x \in S$. Then $(x, x) \in U$, so $(x, x) \in R \cup U$.

    • Transitivity: Let $x, y, z \in S$, and assume $(x, y) \in R \cup U$ and $(y, z) \in R \cup U$. Then either a) $(x, y) \in R$ or b) $(x, y) \in U$, and either c) $(y, z) \in R$ or d) $(y, z) \in U$. If a and c, then $(x, z) \in R$ by transitivity on $R$, so $(x, z) \in R \cup U$. If a and d, then $y=z$ by definition of $U$, so $(x, z) = (x, y) \in R$, so $(x, z) \in R \cup U$. Likewise, if b and c, then $x = y$ by definition of $U$, so $(x,z) = (y,z) \in R$, so $(x, z) \in R \cup U$. Finally, if b and d, then $a = b = c$ by definition of $U$, and $(x, z) = (x, x) \in U$, so $(x, z) \in R \cup U$.

    Show Answer
  6. Let $<_A$ and $<_b$ be total orders on $A$ and $B$, respectively. Define the lexicographic order $<_L$ on $A \times B$ as

    $$(a_1, b_1) <_L (a_2, b_2) \iff (a_1 <_A a_2) \text{ or } (a_1 = a_2 \text{ and } b_1 <_B b_2).$$

    Show that the lexicographic order is a total relation.

    To show that $<_L$ is a total order, we must show that it fulfills the three requirements.

    Comparability: Let $(a_1, b_1), (a_2, b_2) \in A \times B$, and assume that $(a_1, b_1) \neq (a_2, b_2)$. Then either $a_1 \neq a_2$, $b_1 \neq b_2$, or both. If $a_1 \neq a_2$, then by trichotomy on $<_A$, either $a_1 <_A a_2$ or $a_2 <_A a_1$. If the former, then $(a_1, b_1) <_L (a_2, b_2)$. If the latter, then $(a_2, b_2) <_L (a_1, b_1)$. Conversely, if $a_1 = a_2$, then by trichotomy on $<_B$, either $b_1 <_B b_2$ or $b_2 <_B b_1$. If the former, then $(a_1, b_1) <_L (a_2, b_2)$, and if the latter instead, then $(a_2, b_2) <_L (a_1, b_1)$.

    Irreflexivity: Proof by contradiction. Let $(a, b) \in A \times B$, and assume that $(a, b) <_L (a, b)$. Then either $a <_A a$ or both $a = a$ and $b <_B b$. However, irreflexivity on $<_A$ precludes the first condition, and irreflexivity on $<_B$ precludes the second. Therefore $(a, b) \nless_L (a, b)$ after all.

    Transitivity: Let $(a_1, b_1), (a_2, b_2), (a_3, b_3) \in A \times B$, and assume that $(a_1, b_1) <_L (a_2, b_2)$ and $(a_2, b_2) <_L (a_3, b_3)$. Then there are several cases:

    • If $a_1 <_A a_2$ and $a_2 <_A a_3$, then $(a_1, b_1) <_L (a_3, b_3)$ by transitivity on $<_A$.

    • If $a_1 <_A a_2$ and instead $a_2 = a_3$, then $b_2 < b_3$, and $(a_1, b_1) <_L (a_3, b_3)$ by transitivity on $<_B$.

    • If $a_1 = a_2$, then $b_1 < b_2$. If $a_2 < a_3$, then $(a_1, b_1) <_L (a_3, b_3)$.

    • If $a_1 = a_2$ such that $b_1 < b_2$, and instead $a_2 = a_3$, then $b_2 <_B b_3$, so $(a_1, b_1) <_L (a_3, b_3)$ by transitivity on $<_B$.

    Show Answer