s
Section 5.1 Relations
333
All four relational properties involve the implication connective. The universal quantifiers mean that the implications must be true for arbitrary choices of
variables. Recall that to prove an implication true, we assume that the antecedent
is true and prove that the consequent must also be true. For the reflexive property,
the antecedent just chooses an arbitrary element in S; the consequent says that
this element must be related to itself. For a relation r on a set to be reflexive, then,
every element in the set must be related to itself, which specifies certain ordered
pairs that must belong to r.
However, in the symmetric, transitive, and antisymmetric properties, the antecedent does not say only that the elements are in S. To prove that a relation is
symmetric, for example, we must show that if x and y are arbitrary elements in S
and if in addition x is related to y, then it must be the case that y is related to x. This
says that if certain ordered pairs are found in r, then certain other ordered pairs
must also be in r in order for r to be symmetric. In other words, knowledge of the
set S is critical to determining whether reflexivity holds, while to determine the
other properties, it is sufficient just to look at the ordered pairs in r.
At any rate, the question of whether a given relation on a set S has a certain property requires a yes or no answer. The property either holds or it doesn’t.
RemInDeR
Antisymmetric—If x is related to y and y is related
to x, then x = y.
PRaCtiCe 4 Let S = 51, 2, 36.
a. If a relation r on S is reflexive, what ordered pairs must belong to r?
b. If a relation r on S is symmetric, what ordered pairs must belong to r? (This is a trick question; see
the answer at the back of the book.)
c. If a relation r on S is symmetric and if (a, b) [ r, then what other ordered pair must belong to r?
d. If a relation r on S is antisymmetric and if (a, b) and (b, a) belong to r, what must be true?
e. Is the relation r = 5(1, 2)6 on S transitive? (Hint: Remember the truth table for implication.)
■
The properties of symmetry and antisymmetry for binary relations are not
precisely opposites. Antisymmetric does not mean “not symmetric.” A relation
is not symmetric if some (x, y) belongs to the relation but (y, x) does not. More
formally, not symmetric means
((4x)(4y) 3x [ S ` y [ S ` (x, y) [ r S (y, x) r 4)′
4 ( E x)( E y) 3x [ S ` y [ S ` (x, y) [ r S (y, x) r 4′
4 ( E x)( E y) 3(x [ S ` y [ S ` (x, y) [ r)′ ~ (y, x) [ r 4′
4 ( E x)( E y) 3(x [ S ` y [ S ` (x, y) [ r) ` (y, x) o r 4
Relations can therefore be symmetric and not antisymmetric, antisymmetric and
not symmetric, both, or neither.
The equality relation on a set S is both symmetric and antisymmetric. However,
the equality relation on S (or a subset of this relation) is the only relation having
both these properties. To illustrate, suppose r is a symmetric and antisymmetric relation on S, and let (x, y) [ r. By symmetry, it follows that ( y, x) [ r. But
by antisymmetry, x = y. Thus, only equal elements can be related. The relation
r = 5(1, 2), (2, 1), (1, 3)6 on the set S = 51, 2, 36 is neither symmetric—(1, 3) belongs but (3, 1) does not—nor antisymmetric—(1, 2) and (2, 1) belong, but 1 ∙ 2.
Section 5.1 Relations
333
All four relational properties involve the implication connective. The universal quantifiers mean that the implications must be true for arbitrary choices of
variables. Recall that to prove an implication true, we assume that the antecedent
is true and prove that the consequent must also be true. For the reflexive property,
the antecedent just chooses an arbitrary element in S; the consequent says that
this element must be related to itself. For a relation r on a set to be reflexive, then,
every element in the set must be related to itself, which specifies certain ordered
pairs that must belong to r.
However, in the symmetric, transitive, and antisymmetric properties, the antecedent does not say only that the elements are in S. To prove that a relation is
symmetric, for example, we must show that if x and y are arbitrary elements in S
and if in addition x is related to y, then it must be the case that y is related to x. This
says that if certain ordered pairs are found in r, then certain other ordered pairs
must also be in r in order for r to be symmetric. In other words, knowledge of the
set S is critical to determining whether reflexivity holds, while to determine the
other properties, it is sufficient just to look at the ordered pairs in r.
At any rate, the question of whether a given relation on a set S has a certain property requires a yes or no answer. The property either holds or it doesn’t.
RemInDeR
Antisymmetric—If x is related to y and y is related
to x, then x = y.
PRaCtiCe 4 Let S = 51, 2, 36.
a. If a relation r on S is reflexive, what ordered pairs must belong to r?
b. If a relation r on S is symmetric, what ordered pairs must belong to r? (This is a trick question; see
the answer at the back of the book.)
c. If a relation r on S is symmetric and if (a, b) [ r, then what other ordered pair must belong to r?
d. If a relation r on S is antisymmetric and if (a, b) and (b, a) belong to r, what must be true?
e. Is the relation r = 5(1, 2)6 on S transitive? (Hint: Remember the truth table for implication.)
■
The properties of symmetry and antisymmetry for binary relations are not
precisely opposites. Antisymmetric does not mean “not symmetric.” A relation
is not symmetric if some (x, y) belongs to the relation but (y, x) does not. More
formally, not symmetric means
((4x)(4y) 3x [ S ` y [ S ` (x, y) [ r S (y, x) r 4)′
4 ( E x)( E y) 3x [ S ` y [ S ` (x, y) [ r S (y, x) r 4′
4 ( E x)( E y) 3(x [ S ` y [ S ` (x, y) [ r)′ ~ (y, x) [ r 4′
4 ( E x)( E y) 3(x [ S ` y [ S ` (x, y) [ r) ` (y, x) o r 4
Relations can therefore be symmetric and not antisymmetric, antisymmetric and
not symmetric, both, or neither.
The equality relation on a set S is both symmetric and antisymmetric. However,
the equality relation on S (or a subset of this relation) is the only relation having
both these properties. To illustrate, suppose r is a symmetric and antisymmetric relation on S, and let (x, y) [ r. By symmetry, it follows that ( y, x) [ r. But
by antisymmetry, x = y. Thus, only equal elements can be related. The relation
r = 5(1, 2), (2, 1), (1, 3)6 on the set S = 51, 2, 36 is neither symmetric—(1, 3) belongs but (3, 1) does not—nor antisymmetric—(1, 2) and (2, 1) belong, but 1 ∙ 2.