Section 5.5 Ordered Sets
In this section we look at an additional property of a relation. In particular, we define the antisymmetric property. We will then look at how a relation can be used to define ways to order elements of a set.
Definition 5.5.1.
Let \(R\) be a relation on \(A\text{.}\) Then
\(R\) is reflexive if for all \(x\in A\text{,}\) \(x R x\text{.}\) In ordered pair notation, \((x, x)\in R\text{.}\)
\(R\) is symmetric if for all \(x, y\in A\text{,}\) if \(x R y\) then \(y R x\text{.}\) In ordered pair notation, if \((x, y)\in R\) then \((y, x)\in R\text{.}\)
\(R\) is transitive if for all \(x, y, z\in A\text{,}\) if \(x R y\) and \(y R z\) then \(x R z\text{.}\) In ordered pair notation, if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
We add a new property to the list, the antisymmetric property.
Definition 5.5.2.
Let \(R\) be a relation on \(A\text{.}\) Then \(R\) is antisymmetric if for all \(x, y\in A\text{,}\) if \(x R y\) and \(y R x\text{,}\) then \(x=y\text{.}\) In ordered pair notation, if \((x, y)\in R\) and \((y, x)\in R\text{,}\) then \(x=y\text{.}\)
It is important to note, that “antisymmetric” is not the negation of “symmetric.” It is possible for a relation to be both symmetric and antisymmetric (thought this happens only in a special case). It is also possible for a relation to be neither symmetric nor antisymmetric.
Example 5.5.3. Symmetric and Antisymmetric.
Let \(A=\{1, 2, 3\}\text{,}\) define the relation on \(A\) by
\begin{equation*}
R=\{(1, 1), (2, 2), (3, 3)\}.
\end{equation*}
\(R\) is symmetric since if \((x, y)\in R\) then \((y, x)\in R\text{.}\)
\(R\) is antisymmetric since if \((x, y)\in R\) and \((y, x)\in R\) then \(x=y\text{.}\) This is straightforward to check since the only ordered pairs in the relation have \(x=y\text{.}\)
It is often more useful to use the contrapositive form of the definition of antisymmetric:
\(R\) is antisymmetric if for all \(x, y\in A\text{,}\) if \(x\neq y\text{,}\) then \((x, y)\notin R\) or \((y, x)\notin R\text{.}\)
Example 5.5.4. Another Look at Antisymmetric.
Let \(A=\{1, 2, 3\}\text{,}\) define the relation on \(A\) by
\begin{equation*}
R=\{(1, 2), (1, 3), (2, 3)\}.
\end{equation*}
\(R\) is antisymmetric since for each \((x, y)\in R\text{,}\) \((y, x)\) is not in \(R\text{.}\) Since it is never the case that both \((x, y)\) and \((y, x)\) are in \(R\text{,}\) the “if” part of the definition is always false, meaning, the conditional is always true.
By using the contrapositive form it is easier to check that for each pair \((x, y)\in R\) with \(x\neq y\text{,}\) \((y, x)\notin R\text{.}\)
Activity 5.5.1. Practice with Antisymmetric.
For each of the following relations, determine if it is antisymmetric.
(a)
Let \(A=\{1, 2, 3\}\) and \(R=\{(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)\}\text{.}\)
(b)
Let \(A=\{1, 2, 3, 4\}\) and \(R=\{(1, 1), (1, 3), (2, 2), (3, 2), (3, 3)\}\text{.}\)
Checking that a relation is antisymmetric on a small finite set can be done by checking that the property holds for all the elements of \(R\text{.}\) But if \(A\) is infinite we need to prove the properties more generally. We include a reminder of the other properties as well.
Proving Properties of Relations.
To prove
-
Reflexive.
Let \(x\in A\text{.}\) Show \((x, x)\in R\text{.}\)
-
Symmetric.
Assume \((x, y)\in R\text{.}\) Show \((y, x)\in R\text{.}\)
-
Antisymmetric.
Assume \((x, y)\in R\) and \((y, x)\in R\text{.}\) Show \(x=y\text{.}\)
-
Transitive.
Assume \((x, y), (y, z)\in R\text{.}\) Show \((x, z)\in R\text{.}\)
To disprove a property, find a specific counterexample.
-
Reflexive.
Find \((x, x)\notin R\) for some \(x\in A\text{.}\)
-
Symmetric.
Find \((x, y)\in R\) with \((y, x)\notin R\text{.}\)
-
Antisymmetric.
Find \((x, y)\in R\) and \((y, x)\in R\) with \(x\neq y\text{.}\)
-
Transitive.
Find \((x, y), (y, z)\in R\) with \((x, z)\notin R\text{.}\)
Example 5.5.5. Proving Antisymmetric.
Let \(R\) be the relation on \(\mathbb{Z}^+\) given by \((m, n)\in R\Leftrightarrow m\mid n\text{.}\) Prove \(R\) is antisymmtric.
Assume \((x, y)\in R\) and \((y, x)\in R\text{.}\) Then \(x\mid y\) and \(y \mid x\text{.}\) This implies \(x=yk\) for some \(k\in\mathbb{Z}^+\) and \(y=xj\) for some \(j\in \mathbb{Z}^+\text{.}\) Thus, \(x=xjk\text{,}\) and then \(1=jk\text{.}\) But since \(j, k \in \mathbb{Z}^+\text{,}\) \(j=k=1\text{.}\) Hence, \(x=y\text{.}\)
We leave it as an exercise to show \(R\) is reflexive and transitive, but not symmetric.
Activity 5.5.2. The Less Than or Equal Relation.
Define the relation on \(\mathbb{R}\) by \(xRy \iff x \leq y\text{.}\) Prove or disprove \(R\) is antisymmetric.
We’ve seen examples of relations that are functions and that are equivalence relations. We introduce another type of relation, that of an ordered set. Equivalence relations arise in mathematics as a way to equate element in a set, whereas orders give us a way to compare the “size” of elements in a set.
Definition 5.5.6.
A relation \(R\) on a set \(A\) is a partial order if it is reflexive, antisymmetric, and transitive. We will generally use the notation \(\leq\) instead of \(R\text{:}\) \((x, y)\in R\) if and only if \(x \leq y\text{.}\)
Furthermore, we call the set \(A\) with partial order \(\leq\) a partially ordered set, or poset.
The set
\(\mathbb{Z}^+\) with relation “divides” given in
Activity 5.5.2 is a partially ordered set.
Example 5.5.7. Subset Order.
Let \(S\) be a set and \(\mathcal{P}(S)\) be the set of all subsets of \(S\text{.}\) Let \(R\) be the relation given by \((A, B)\in R\) if and only if \(A\subseteq B\text{.}\) Then \(R\) is a partial order.
Reflexive: For every subset \(A\in \mathcal{P}(S)\text{,}\) \(A\subseteq A\text{.}\)
Antisymmetric: If \(A\subseteq B\) and \(B\subseteq A\) then \(A=B\text{,}\) by defintion of set equality.
Transitive: If
\(A\subseteq B\) and
\(B\subseteq C\) then
\(A\subseteq B\text{,}\) which is an exercise,
Exercise 5.2.3.8.
Activity 5.5.3. Greater Than or Equal.
Show that the relation given by \((x, y)\in R\) if and only if \(x\geq y\) is a partial order on \(\mathbb{R}\text{.}\)
Definition 5.5.8.
A partially ordered set, \(A\text{,}\) with order \(\leq\) is a totally ordered set if for all \(a, b\in A\text{,}\) either \(a\leq b\) or \(b\leq a\text{.}\)
We say that \(\leq\) is a total order on \(A\text{.}\)
The idea behind a total order is that every element in the set is comparable. So if we take any two elements, one must be less than the other. This, along with the transitive property allows us to order every element in the set, from “smallest” to “largest.”
Example 5.5.9. Total Order on the Reals.
The less than or equal to order from
Activity 5.5.3 is a total order on
\(\mathbb{R}\text{.}\) Given any two real numbers,
\(x, y\text{,}\) either
\(x\geq y\) or
\(y\geq x\text{.}\) This property is what allows us to form the real number line.
Example 5.5.10. Subset is Not a Total Order.
The subset order from
Example 5.5.7 is generally not a total order on
\(S\text{.}\) For example, let
\(S=\{1, 2, 3\}\text{.}\) Then for the sets
\(A=\{1\}\) and
\(B=\{2\}\text{,}\) \(A\nsubseteq B\) and
\(B\nsubseteq A\text{.}\) Thus neither
\(A\) nor
\(B\) is “smaller” than the other and they cannot be ordered relative to each other with the subset order. Similarly, if
\(C=\{2, 3\}\text{,}\) \(A\nsubseteq C\) and
\(C\nsubseteq A\text{.}\) Once again, we cannot order these sets by
\(\subseteq\text{.}\)
The following Theorem is useful when working with orders.
Theorem 5.5.11.
A set \(A\) with order \(\leq\) is a totally ordered set if and only if exactly one of the following is true:
\(a < b\text{,}\)
\(b < a\text{,}\)
\(a = b\text{.}\)
Example 5.5.12. Again Subset is Not a Total Order.
If we check the conditions of
Theorem 5.5.11, we can see again that the subset order from
Example 5.5.7 is generally not a total order on
\(S\text{.}\) Let
\(S=\{1, 2, 3\}\text{.}\) Then for the sets
\(A=\{1\}\) and
\(B=\{2\}\text{,}\) \(A\nsubseteq B\text{,}\) \(B\nsubseteq A\text{,}\) and
\(A\neq B\text{.}\) Similarly, if
\(C=\{2, 3\}\text{,}\) \(A\nsubseteq C\text{,}\) \(C\nsubseteq A\) and
\(A\neq C\text{.}\)
Exercises Exercises
1.
Let \(A=\mathbb{Z}^+\) Define \(a\leq b\) if \(a \mid b\text{.}\)
Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}^+\text{.}\)
Prove or disprove \(\leq\) is a total order on \(\mathbb{Z}^+\text{.}\)
2.
Define \((a, b)\leq (c, d)\) if \(a\leq c\) and \(b\leq d\text{.}\)
Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
Prove or disprove \(\leq\) is a total order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
3.
Define \((a, b)\leq (c, d)\) if \(a\leq c\) and if \(a=c\) then \(b\leq d\text{.}\)
Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
Prove or disprove \(\leq\) is a total order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
Note, this is often called the lexicographic or dictionary order.
4.
Define \((a, b)\leq (c, d)\) if \(a+b\leq c+d\text{.}\)
Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
Prove or disprove \(\leq\) is a total order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
5.
Let \(A\) be a partially ordered set with order \(\leq\text{.}\) Then \(x\in A\) is a greatest element of \(A\) if \(y\leq x\) for all \(y\in A\text{.}\) Prove if \(A\) has a greatest element, \(x\text{,}\) then \(x\) is unique.
Hint.
Since the problem assumes existence, you just need to do a uniqueness proof. Start by assuming \(A\) has two greatest elements.
