Skip to main content

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. Then
  1. R is reflexive if for all xA, xRx. In ordered pair notation, (x,x)R.
  2. R is symmetric if for all x,yA, if xRy then yRx. In ordered pair notation, if (x,y)R then (y,x)R.
  3. R is transitive if for all x,y,zA, if xRy and yRz then xRz. In ordered pair notation, if (x,y)R and (y,z)R then (x,z)R.
We add a new property to the list, the antisymmetric property.

Definition 5.5.2.

Let R be a relation on A. Then R is antisymmetric if for all x,yA, if xRy and yRx, then x=y. In ordered pair notation, if (x,y)R and (y,x)R, then x=y.
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}, define the relation on A by
R={(1,1),(2,2),(3,3)}.
R is symmetric since if (x,y)R then (y,x)R.
R is antisymmetric since if (x,y)R and (y,x)R then x=y. This is straightforward to check since the only ordered pairs in the relation have x=y.
It is often more useful to use the contrapositive form of the definition of antisymmetric:
R is antisymmetric if for all x,yA, if xy, then (x,y)R or (y,x)R.

Example 5.5.4. Another Look at Antisymmetric.

Let A={1,2,3}, define the relation on A by
R={(1,2),(1,3),(2,3)}.
R is antisymmetric since for each (x,y)R, (y,x) is not in R. Since it is never the case that both (x,y) and (y,x) are in R, 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)R with xy, (y,x)R.

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)}.

(b)

Let A={1,2,3,4} and R={(1,1),(1,3),(2,2),(3,2),(3,3)}.
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. 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 xA. Show (x,x)R.
  • Symmetric.
    Assume (x,y)R. Show (y,x)R.
  • Antisymmetric.
    Assume (x,y)R and (y,x)R. Show x=y.
  • Transitive.
    Assume (x,y),(y,z)R. Show (x,z)R.
To disprove a property, find a specific counterexample.
  • Reflexive.
    Find (x,x)R for some xA.
  • Symmetric.
    Find (x,y)R with (y,x)R.
  • Antisymmetric.
    Find (x,y)R and (y,x)R with xy.
  • Transitive.
    Find (x,y),(y,z)R with (x,z)R.

Example 5.5.5. Proving Antisymmetric.

Let R be the relation on Z+ given by (m,n)Rmn. Prove R is antisymmtric.
Assume (x,y)R and (y,x)R. Then xy and yx. This implies x=yk for some kZ+ and y=xj for some jZ+. Thus, x=xjk, and then 1=jk. But since j,kZ+, j=k=1. Hence, x=y.
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 R by xRyxy. 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 instead of R: (x,y)R if and only if xy.
Furthermore, we call the set A with partial order a partially ordered set, or poset.
The set 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 P(S) be the set of all subsets of S. Let R be the relation given by (A,B)R if and only if AB. Then R is a partial order.
Reflexive: For every subset AP(S), AA.
Antisymmetric: If AB and BA then A=B, by defintion of set equality.
Transitive: If AB and BC then AB, 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)R if and only if xy is a partial order on R.

Definition 5.5.8.

A partially ordered set, A, with order is a totally ordered set if for all a,bA, either ab or ba.
We say that is a total order on A.
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 R. Given any two real numbers, x,y, either xy or yx. 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. For example, let S={1,2,3}. Then for the sets A={1} and B={2}, AB and BA. 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}, AC and CA. Once again, we cannot order these sets by .
The following Theorem is useful when working with orders.

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. Let S={1,2,3}. Then for the sets A={1} and B={2}, AB, BA, and AB. Similarly, if C={2,3}, AC, CA and AC.

Exercises Exercises

1.

Let A=Z+ Define ab if ab.
  1. Prove or disprove is a partial order on Z+.
  2. Prove or disprove is a total order on Z+.

2.

Define (a,b)(c,d) if ac and bd.
  1. Prove or disprove is a partial order on Z×Z.
  2. Prove or disprove is a total order on Z×Z.

3.

Define (a,b)(c,d) if ac and if a=c then bd.
  1. Prove or disprove is a partial order on Z×Z.
  2. Prove or disprove is a total order on Z×Z.
Note, this is often called the lexicographic or dictionary order.

4.

Define (a,b)(c,d) if a+bc+d.
  1. Prove or disprove is a partial order on Z×Z.
  2. Prove or disprove is a total order on Z×Z.

5.

Let A be a partially ordered set with order . Then xA is a greatest element of A if yx for all yA. Prove if A has a greatest element, x, 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.