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 differ in a particular way. An order relation $<$ on a set $S$ is a relation with the following properties:

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

  2. Nonreflexivity: For no $x \in S$ is it true that $x < x$.

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

The use of the $<$ symbol is intentional, as $<$ is used to denote the "usual" order relations on $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$, and so on. The usual order relations on these sets convey what you expect them to: $1<2$, $\dfrac{3}{4} < \dfrac{10}{3}$, and $e < \pi$, and so on. These order relations can be rigorously defined once their respective sets have been defined, but for now we can take their familiar properties on faith.

Given a clean definition for $<$, we can define the other familiar comparison symbols as follows:

  • $a \leq b$ means either $a < b$ or $a = b$. Formally, $\leq \; = \{ (a,b) : a < b \text{ or } a = b \}$.

  • $a > b$ means $b < a$. Formally, $ > \; = \{ (a,b) : b < a \}$.

  • $a \geq b$ means either $a > b$ or $a = b$. Formally, $\geq \; = \{ (a,b) : b < a \text{ or } a = b \}$.

Additionally, we can use abbreviations like $a < x < b$ to express $a < x$ and $x < b$.

There are in fact different kinds of order relations, although they often take on more intricate names to indicate their less common usage. Barring further qualification, "order relations" refer to the kind defined here, and are also called linear order relations or total order relations when contrasted against other kinds of order relations, which are often some kind of partial order relation.


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 that it fulfills the three properties. 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. This also violates comparability, as $(c, a)$ is not present either.

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

    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 nonreflexivity 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 an order relation, then $T$ is an order relation.

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

    Comparability: For each pair of distinct elements $a$ and $b$ in $T$, 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 all elements in $T$ are comparable.

    Nonreflexivity: 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 nonreflexive.

    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.

    $T$ checks all the boxes for an order relation.

    Show Answer