332
Relations, Functions, and Matrices
The following facts about the operations c , d and ′ on relations are immediate consequences of the basic set identities found in Section 4.1. The set S
2
(which
is, after all, a subset of S
2
) is being viewed here as a binary relation on S.
la. r c s = s c r
lb. r d s = s d r
2a. (r c s) c g = r c (s c g)
2b. (r d s) d g = r d (s d g)
3a. r c (s d g) = (r c s) d (r c g) 3b. r d (s c g) = (r d s) c (r d g)
4a. r c [ = r
4b. r d S
2
= r
5a. r c r′ = S
2
5b. r d r′ = [
properties of Relations
A binary relation on a set S may have certain properties. For example, the
relation r of equality on S, (x, y) [ r 4 x = y, has three properties: (1) for
any x [ S, x = x, or (x, x) [ r; (2) for any x, y [ S, if x = y then y = x, or
(x, y) [ r S ( y, x) [ r; and (3) for any x, y, z [ S, if x = y and y = z, then
x = z, or 3(x, y) [ r and (y, z) [ r 4 S (x, z) [ r. These three properties make
the equality relation reflexive, symmetric, and transitive.
RemInDeR
Reflexive—Every x is
related to itself.
Symmetric—If x is related
to y, then y is related to x.
Transitive—If x is related
to y and y is related to z,
then x is related to z.
DefInItIon ReFlexive, SyMMetRic, and tRanSitive RelationS
Let r be a binary relation on a set S. Then
r is reflexive means (4x)(x [ S S (x, x) [ r)
r is symmetric means (4x)(4y)(x [ S ` y [ S ` (x, y) [ r S (y, x) [ r)
r is transitive means (4x)(4y)(4z)(x [ S ` y [ S ` z [ S `
(x, y) [ r ` (y, z) [ r S (x, z) [ r)
example 6
Consider the relation ≤ on the set N. This relation is reflexive because for any
nonnegative integer x, x ≤ x. It is also a transitive relation because for any nonnegative integers x, y, and z, if x ≤ y and y ≤ z, then x ≤ z. However, ≤ is
not symmetric; 3 ≤ 4 does not imply 4 ≤ 3. In fact, for any x, y [ N, if both
x ≤ y and y ≤ x, then x = y. This characteristic is described by saying that ≤ is
antisymmetric.
DefInItIon antiSyMMetRic Relation
Let r be a binary relation on a set S. Then r is antisymmetric means
(4x)(4y)(x [ S ` y [ S ` (x, y) [ r ` ( y, x) [ r S x = y)
example 7
Let S = `(N). Define a binary relation r on S by A r B 4 A # B. Then r is reflexive
because every set is a subset of itself. Also, r is transitive because if A is a subset of
B and B is a subset of C, then A is a subset of C. Finally, r is antisymmetric because
if A is a subset of B and B is a subset of A, then A and B are equal sets.
Relations, Functions, and Matrices
The following facts about the operations c , d and ′ on relations are immediate consequences of the basic set identities found in Section 4.1. The set S
2
(which
is, after all, a subset of S
2
) is being viewed here as a binary relation on S.
la. r c s = s c r
lb. r d s = s d r
2a. (r c s) c g = r c (s c g)
2b. (r d s) d g = r d (s d g)
3a. r c (s d g) = (r c s) d (r c g) 3b. r d (s c g) = (r d s) c (r d g)
4a. r c [ = r
4b. r d S
2
= r
5a. r c r′ = S
2
5b. r d r′ = [
properties of Relations
A binary relation on a set S may have certain properties. For example, the
relation r of equality on S, (x, y) [ r 4 x = y, has three properties: (1) for
any x [ S, x = x, or (x, x) [ r; (2) for any x, y [ S, if x = y then y = x, or
(x, y) [ r S ( y, x) [ r; and (3) for any x, y, z [ S, if x = y and y = z, then
x = z, or 3(x, y) [ r and (y, z) [ r 4 S (x, z) [ r. These three properties make
the equality relation reflexive, symmetric, and transitive.
RemInDeR
Reflexive—Every x is
related to itself.
Symmetric—If x is related
to y, then y is related to x.
Transitive—If x is related
to y and y is related to z,
then x is related to z.
DefInItIon ReFlexive, SyMMetRic, and tRanSitive RelationS
Let r be a binary relation on a set S. Then
r is reflexive means (4x)(x [ S S (x, x) [ r)
r is symmetric means (4x)(4y)(x [ S ` y [ S ` (x, y) [ r S (y, x) [ r)
r is transitive means (4x)(4y)(4z)(x [ S ` y [ S ` z [ S `
(x, y) [ r ` (y, z) [ r S (x, z) [ r)
example 6
Consider the relation ≤ on the set N. This relation is reflexive because for any
nonnegative integer x, x ≤ x. It is also a transitive relation because for any nonnegative integers x, y, and z, if x ≤ y and y ≤ z, then x ≤ z. However, ≤ is
not symmetric; 3 ≤ 4 does not imply 4 ≤ 3. In fact, for any x, y [ N, if both
x ≤ y and y ≤ x, then x = y. This characteristic is described by saying that ≤ is
antisymmetric.
DefInItIon antiSyMMetRic Relation
Let r be a binary relation on a set S. Then r is antisymmetric means
(4x)(4y)(x [ S ` y [ S ` (x, y) [ r ` ( y, x) [ r S x = y)
example 7
Let S = `(N). Define a binary relation r on S by A r B 4 A # B. Then r is reflexive
because every set is a subset of itself. Also, r is transitive because if A is a subset of
B and B is a subset of C, then A is a subset of C. Finally, r is antisymmetric because
if A is a subset of B and B is a subset of A, then A and B are equal sets.