Skip to main content

Introduction to Proofs: An Active Exploration of Mathematical Language

Jennifer Firkins Nordstrom

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.
We will still need the properies from Section 5.4.

Definition 5.5.1.

Let \(R\) be a relation on \(A\text{.}\) Then
  1. \(R\) is reflexive if for all \(x\in A\text{,}\) \(x R x\text{.}\) In ordered pair notation, \((x, x)\in R\text{.}\)
  2. \(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{.}\)
  3. \(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.
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{.}\)
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{.}\)
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.
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.”
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.
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.
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{.}\)
  1. Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}^+\text{.}\)
  2. 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{.}\)
  1. Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
  2. 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{.}\)
  1. Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
  2. 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{.}\)
  1. Prove or disprove \(\leq\) is a partial order on \(\mathbb{Z}\times\mathbb{Z}\text{.}\)
  2. 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.
<Prev^TopNext>