Special Types of Relations
171
Definition 4. Let R be a binary relation on a set X. R is antisymmetric if (y, x) 0 R
whenever (x, y) c R and x 0 y.
The relation defined on 1, 2, 31 as R = {(1, 2), (2, 1), (3, 2)} is neither symmetric,
because (3, 2) E R but (2, 3) 0 R, nor antisymmetric, because both (1, 2) and (2, 1) are
in R.
The relations =, <, and < are all antisymmetric. A logically equivalent statement of
the definition of antisymmetric is the following: If (x, y) and (y, x) are both in R, then
y = x. To see this in terms of the logical notation introduced in Chapter 2, let p1 be the
statement "(x, y) E R,"p 2 the statement "(y, x) E R," and P3 the statement "x = y." The
definition is of the form (pl A -P3) -+ -•P2, which is logically equivalent to the formula
(P1 A P2) -- P3.
Example 3. See Section 3.1 for the examples and the definitions of the relations IsParentOf and HigherValue.
(a) In the family tree example, the relation IsParentOf is antisymmetric. For example,
(Mary, Elaine) E IsParentOf but (Elaine, Mary) 0 IsParentOf.
(b) In the card example, HigherValue is antisymmetric. We see this as (Jack of Hearts, 10
of Hearts) E HigherValue, but (10 of Hearts, Jack of Hearts) g HigherValue.
Suppose that a binary relation R is written as a table T, as in Table 3.7(a), which
repeats the information contained in Table 3.4. Now, suppose that a new table, T', is formed
by interchanging the two columns of T. The resulting Table 3.7(b) corresponds to the
relation R1 . Theorem 3 says that R is symmetric if and only if T and T' have the same
rows. The order of the rows may be different, but exactly the same rows are present. Since
any n-ary relation is a set of ordered n-tuples for some n E N, the order in which the
n-tuples are written in the table does not matter.
Table 3.7 IsMarriedTo (a) and IsMarriedTo
1
(b) Relations
T
T'
John
Mary
Mary
John
Mary
John
John
Mary
Peter
Elaine
Elaine
Peter
Elaine
Peter
Peter
Elaine
Maude Harold
Harold Maude
Harold Maude
Maude Harold
(a)
(b)
An examination of the two tables shows that T = T'.
Example 4.
(a) For any set X, equality is a symmetric, antisymmetric, and reflexive relation
on X.
171
Definition 4. Let R be a binary relation on a set X. R is antisymmetric if (y, x) 0 R
whenever (x, y) c R and x 0 y.
The relation defined on 1, 2, 31 as R = {(1, 2), (2, 1), (3, 2)} is neither symmetric,
because (3, 2) E R but (2, 3) 0 R, nor antisymmetric, because both (1, 2) and (2, 1) are
in R.
The relations =, <, and < are all antisymmetric. A logically equivalent statement of
the definition of antisymmetric is the following: If (x, y) and (y, x) are both in R, then
y = x. To see this in terms of the logical notation introduced in Chapter 2, let p1 be the
statement "(x, y) E R,"p 2 the statement "(y, x) E R," and P3 the statement "x = y." The
definition is of the form (pl A -P3) -+ -•P2, which is logically equivalent to the formula
(P1 A P2) -- P3.
Example 3. See Section 3.1 for the examples and the definitions of the relations IsParentOf and HigherValue.
(a) In the family tree example, the relation IsParentOf is antisymmetric. For example,
(Mary, Elaine) E IsParentOf but (Elaine, Mary) 0 IsParentOf.
(b) In the card example, HigherValue is antisymmetric. We see this as (Jack of Hearts, 10
of Hearts) E HigherValue, but (10 of Hearts, Jack of Hearts) g HigherValue.
Suppose that a binary relation R is written as a table T, as in Table 3.7(a), which
repeats the information contained in Table 3.4. Now, suppose that a new table, T', is formed
by interchanging the two columns of T. The resulting Table 3.7(b) corresponds to the
relation R1 . Theorem 3 says that R is symmetric if and only if T and T' have the same
rows. The order of the rows may be different, but exactly the same rows are present. Since
any n-ary relation is a set of ordered n-tuples for some n E N, the order in which the
n-tuples are written in the table does not matter.
Table 3.7 IsMarriedTo (a) and IsMarriedTo
1
(b) Relations
T
T'
John
Mary
Mary
John
Mary
John
John
Mary
Peter
Elaine
Elaine
Peter
Elaine
Peter
Peter
Elaine
Maude Harold
Harold Maude
Harold Maude
Maude Harold
(a)
(b)
An examination of the two tables shows that T = T'.
Example 4.
(a) For any set X, equality is a symmetric, antisymmetric, and reflexive relation
on X.