Page 598 - Discrete Mathematics and Its Applications

9.1 Relations and Their Properties 577

In some relations an element is related to a second element if and only if the second element
is also related to the first element. The relation consisting of pairs (x, y), where x and y are
students at your school with at least one common class has this property. Other relations have
the property that if an element is related to a second element, then this second element is not
related to the first. The relation consisting of the pairs (x, y), where x and y are students at your
school, where x has a higher grade point average than y has this property.

DEFINITION 4 A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all a, b ∈ A.
A relation R on a set A such that for all a, b ∈ A,if (a, b) ∈ R and (b, a) ∈ R, then a = b
is called antisymmetric.

Remark: Using quantifiers, we see that the relation R on the set A is symmetric if
∀a∀b((a, b) ∈ R → (b, a) ∈ R). Similarly, the relation R on the set A is antisymmetric if
∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b)).
That is, a relation is symmetric if and only if a is related to b implies that b is related to a.
A relation is antisymmetric if and only if there are no pairs of distinct elements a and b with a
related to b and b related to a. That is, the only way to have a related to b and b related to a is
for a and b to be the same element. The terms symmetric and antisymmetric are not opposites,
because a relation can have both of these properties or may lack both of them (see Exercise
10). A relation cannot be both symmetric and antisymmetric if it contains some pair of the form
(a, b), where a = b.

Remark: Although relatively few of the 2 n 2 relations on a set with n elements are symmetric
or antisymmetric, as counting arguments can show, many important relations have one of these
properties. (See Exercise 47.)

EXAMPLE 10 Which of the relations from Example 7 are symmetric and which are antisymmetric?

Solution: The relations R 2 and R 3 are symmetric, because in each case (b, a) belongs to the
relation whenever (a, b) does. For R 2 , the only thing to check is that both (2, 1) and (1, 2) are
in the relation. For R 3 , it is necessary to check that both (1, 2) and (2, 1) belong to the relation,
and (1, 4) and (4, 1) belong to the relation. The reader should verify that none of the other
relations is symmetric. This is done by finding a pair (a, b) such that it is in the relation
but (b, a) is not.
R 4 , R 5 , and R 6 are all antisymmetric. For each of these relations there is no pair of elements
a and b with a = b such that both (a, b) and (b, a) belong to the relation. The reader should
verify that none of the other relations is antisymmetric. This is done by finding a pair (a, b)
with a = b such that (a, b) and (b, a) are both in the relation. ▲

EXAMPLE 11 Which of the relations from Example 5 are symmetric and which are antisymmetric?

Solution: The relations R 3 , R 4 , and R 6 are symmetric. R 3 is symmetric, for if a = b or a =−b,
then b = a or b =−a. R 4 is symmetric because a = b implies that b = a. R 6 is symmetric
because a + b ≤ 3 implies that b + a ≤ 3. The reader should verify that none of the other
relations is symmetric.
The relations R 1 , R 2 , R 4 , and R 5 are antisymmetric. R 1 is antisymmetric because the
inequalities a ≤ b and b ≤ a imply that a = b. R 2 is antisymmetric because it is impossible
that a> b and b> a. R 4 is antisymmetric, because two elements are related with respect to
R 4 if and only if they are equal. R 5 is antisymmetric because it is impossible that a = b + 1
and b = a + 1. The reader should verify that none of the other relations is antisymmetric. ▲