s
Section 5.1 Relations
329
analogue is to distinguish certain ordered pairs of objects from other ordered pairs
because the components of the distinguished pairs satisfy some relationship that
the components of the other pairs do not.
example 1
Remember (Section 4.1) that the Cartesian product of a set S with itself, S × S
or S
2
, is the set of all ordered pairs of elements of S. Let S = 51, 2, 36; then
S × S = 5(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)6
If we were interested in the relationship of equality, then (1, 1), (2, 2), (3, 3) would
be the distinguished elements of S × S, that is, the only ordered pairs whose components are equal. If we were interested in the relationship of one number being
less than another, we would choose (1, 2), (1, 3), and (2, 3) as the distinguished
ordered pairs of S × S.
In Example 1, we could pick out the distinguished ordered pairs (x, y) by saying that x = y or that x < y. Similarly, the notation x r y indicates that the ordered
pair (x, y) satisfies a relation r. The relation r may be defined in words or by an
equation or simply by listing the ordered pairs that satisfy r.
As in Example 2, one way to define the binary relation r is to specify a subset
of S × S. Formally, this is the definition of a binary relation on a set.
example 2
Let S = 51, 2, 46. On the set S × S = 5(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4),
(4, 1), (4, 2), (4, 4)6, a relation r can be defined by x r y if and only if x = y∙2,
abbreviated x r y 4 x = y∙2 Thus (1, 2) and (2, 4) satisfy r. Alternatively, the
same r could be defined by saying that 5(1, 2), (2, 4)6 is the set of ordered pairs
satisfying r.
DefInItIon BinaRy Relation on a Set S
A binary relation on a set S is a subset of S × S (a set of ordered pairs of
elements of S ).
Now that we know that a binary relation r is a subset, we see that
x r y 4 (x, y) [ r
Generally, a binary relation is defined by describing the relation rather than by listing the ordered pairs. The description gives a characterizing property of elements
of the relation; that is, it is a binary predicate satisfied by certain ordered pairs.
A binary relation implies a yes/no result—an ordered pair either does or does not
satisfy the binary predicate and either does or does not belong to the relation.
Section 5.1 Relations
329
analogue is to distinguish certain ordered pairs of objects from other ordered pairs
because the components of the distinguished pairs satisfy some relationship that
the components of the other pairs do not.
example 1
Remember (Section 4.1) that the Cartesian product of a set S with itself, S × S
or S
2
, is the set of all ordered pairs of elements of S. Let S = 51, 2, 36; then
S × S = 5(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)6
If we were interested in the relationship of equality, then (1, 1), (2, 2), (3, 3) would
be the distinguished elements of S × S, that is, the only ordered pairs whose components are equal. If we were interested in the relationship of one number being
less than another, we would choose (1, 2), (1, 3), and (2, 3) as the distinguished
ordered pairs of S × S.
In Example 1, we could pick out the distinguished ordered pairs (x, y) by saying that x = y or that x < y. Similarly, the notation x r y indicates that the ordered
pair (x, y) satisfies a relation r. The relation r may be defined in words or by an
equation or simply by listing the ordered pairs that satisfy r.
As in Example 2, one way to define the binary relation r is to specify a subset
of S × S. Formally, this is the definition of a binary relation on a set.
example 2
Let S = 51, 2, 46. On the set S × S = 5(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (2, 4),
(4, 1), (4, 2), (4, 4)6, a relation r can be defined by x r y if and only if x = y∙2,
abbreviated x r y 4 x = y∙2 Thus (1, 2) and (2, 4) satisfy r. Alternatively, the
same r could be defined by saying that 5(1, 2), (2, 4)6 is the set of ordered pairs
satisfying r.
DefInItIon BinaRy Relation on a Set S
A binary relation on a set S is a subset of S × S (a set of ordered pairs of
elements of S ).
Now that we know that a binary relation r is a subset, we see that
x r y 4 (x, y) [ r
Generally, a binary relation is defined by describing the relation rather than by listing the ordered pairs. The description gives a characterizing property of elements
of the relation; that is, it is a binary predicate satisfied by certain ordered pairs.
A binary relation implies a yes/no result—an ordered pair either does or does not
satisfy the binary predicate and either does or does not belong to the relation.