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.
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.
is antisymmetric since for each , is not in . Since it is never the case that both and are in , 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 with ,.
Activity5.5.1.Practice with Antisymmetric.
For each of the following relations, determine if it is antisymmetric.
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 . But if is infinite we need to prove the properties more generally. We include a reminder of the other properties as well.
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.
A relation on a set is a partial order if it is reflexive, antisymmetric, and transitive. We will generally use the notation instead of : if and only if .
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 . Given any two real numbers, , either or . This property is what allows us to form the real number line.
Example5.5.10.Subset is Not a Total Order.
The subset order from Example 5.5.7 is generally not a total order on . For example, let . Then for the sets and , and . Thus neither nor is “smaller” than the other and they cannot be ordered relative to each other with the subset order. Similarly, if , and . Once again, we cannot order these sets by .
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 . Let . Then for the sets and ,,, and . Similarly, if ,, and .