Rather than focusing on each relation individually (an impossible task
anyway since there are infinitely many different relations), we will develop
a general theory that encompasses all relations.
Understanding this
general theory will give us the conceptual framework and language needed
to understand and discuss any specific relation.
Before stating the theoretical definition of a relation, let’s look at a
motivational example. This example will lead naturally to our definition.
Consider the set A = ©1, 2, 3, 4, 5ª. (There’s nothing special about this
particular set; any set of numbers would do for this example.) Elements of
A can be compared to each other by the symbol “<.” For example, 1 < 4,
2 < 3, 2 < 4, and so on. You have no trouble understanding this because the
notion of numeric order is so ingrained. But imagine you had to explain
it to an idiot savant, one with an obsession for detail but absolutely no
understanding of the meaning of (or relationships between) integers. You
might consider writing down for your student the following set:
R = © (1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5) ª.
176
Relations
The set R encodes the meaning of the < relation for elements in A. An
ordered pair (a, b) appears in the set if and only if a < b. If asked whether
or not it is true that 3 < 4, your student could look through R until he
found the ordered pair (3, 4); then he would know 3 < 4 is true. If asked
about 5 < 2, he would see that (5, 2) does not appear in R, so 5 6< 2. The set
R, which is a subset of A × A, completely describes the relation < for A.
Though it may seem simple-minded at first, this is exactly the idea
we will use for our main definition. This definition is general enough to
describe not just the relation < for the set A = ©1, 2, 3, 4, 5ª, but any relation
for any set A.
Definition 11.1
A relation on a set A is a subset R ⊆ A × A. We often
abbreviate the statement (x, y) ∈ R as xR y. The statement (x, y) ∉ R is
abbreviated as x 6R y.
Notice that a relation is a set, so we can use what we know about sets
to understand and explore relations. But before getting deeper into the
theory of relations, let’s look at some examples of Definition 11.1.
Example 11.1
Let A = ©1, 2, 3, 4ª, and consider the following set:
R = ©(1,1),(2,1),(2,2),(3,3),(3,2),(3,1),(4,4),(4,3),(4,2),(4,1)ª ⊆ A × A.
The set R is a relation on A, by Definition 11.1. Since (1, 1) ∈ R, we have
1R1. Similarly 2R1 and 2R2, and so on. However, notice that (for example)
(3, 4) ∉ R, so 36R 4. Observe that R is the familiar relation ≥ for the set A.
Chapter 1 proclaimed that all of mathematics can be described with
sets. Just look at how successful this program has been! The greater-
than-or-equal-to relation is now a set R. (We might even express this in
the rather cryptic form ≥= R.)
Example 11.2
Let A = ©1, 2, 3, 4ª, and consider the following set:
S = ©(1,1),(1,3),(3,1),(3,3),(2,2),(2,4),(4,2),(4,4)ª ⊆ A × A.
Here we have 1S1, 1S3, 4S2, etc., but 3 6S 4 and 2 6S 1. What does S mean?
Think of it as meaning “has the same parity as. ” Thus 1S1 reads “1 has
the same parity as 1,” and 4S2 reads “4 has the same parity as 2.”
Example 11.3
Consider relations R and S of the previous two examples.
Note that R ∩S = ©(1, 1), (2, 2), (3, 3), (3, 1), (4, 4), (4, 2)ª ⊆ A × A is a relation on A.
The expression x(R ∩ S) y means “x ≥ y , and x, y have the same parity. ”
177
Example 11.4
Let B = ©0, 1, 2, 3, 4, 5ª, and consider the following set:
U = ©(1,3),(3,3),(5,2),(2,5),(4,2)ª ⊆ B × B.
Then U is a relation on B because U ⊆ B × B. You may be hard-pressed
to invent any “meaning” for this particular relation. A relation does not
have to have any meaning. Any random subset of B × B is a relation on B,
whether or not it describes anything familiar.
Some relations can be described with pictures. For example, we can
depict the above relation U on B by drawing points labeled by elements of
B. The statement (x, y) ∈ U is then represented by an arrow pointing from
x to y, a graphic symbol meaning “x relates to y.” Here’s a picture of U:
0
1
2
3
4
5
The next picture illustrates the relation R on the set A = ©a, b, c, dª, where
xR y means x comes before y in the alphabet. According to Definition 11.1,
as a set this relation is R = ©(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)ª. You may
feel that the picture conveys the relation better than the set does. They
are two different ways of expressing the same thing. In some instances
pictures are more convenient than sets for discussing relations.
a
d
c
b
Although such diagrams can help us visualize relations, they do have
their limitations. If A and R were infinite, then the diagram would be
impossible to draw, but the set R might be easily expressed in set-builder
notation. Here are some examples.
Example 11.5
Consider the set R = ©(x, y) ∈ Z × Z : x − y ∈ Nª ⊆ Z × Z. This
is the > relation on the set A = Z. It is infinite because there are infinitely
many ways to have x > y where x and y are integers.
Example 11.6
The set R = ©(x, x) : x ∈ Rª ⊆ R × R is the relation = on the
set R, because xR y means the same thing as x = y. Thus R is a set that
expresses the notion of equality of real numbers.
178
Relations
Exercises for Section 11.0
1. Let A = ©0,1,2,3,4,5ª. Write out the relation R that expresses > on A. Then
illustrate it with a diagram.
2. Let A = ©1,2,3,4,5,6ª. Write out the relation R that expresses | (divides) on A.
Then illustrate it with a diagram.
3. Let A = ©0,1,2,3,4,5ª. Write out the relation R that expresses ≥ on A. Then
illustrate it with a diagram.
4. Here is a diagram for a relation R on a set A. Write the sets A and R.
0
1
2
3
4
5
5. Here is a diagram for a relation R on a set A. Write the sets A and R.
0
1
2
3
4
5
6. Congruence modulo 5 is a relation on the set A = Z. In this relation xR y means
x ≡ y (mod 5). Write out the set R in set-builder notation.
7. Write the relation < on the set A = Z as a subset R of Z × Z. This is an infinite
set, so you will have to use set-builder notation.
8. Let A = ©1,2,3,4,5,6ª. Observe that ; ⊆ A × A, so R = ; is a relation on A. Draw
a diagram for this relation.
9. Let A = ©1,2,3,4,5,6ª. How many different relations are there on the set A?
10. Consider the subset R = (R × R) − ©(x, x) : x ∈ Rª ⊆ R × R. What familiar relation on
R is this? Explain.
11. Given a finite set A, how many different relations are the
re on A?
In the following exercises, subsets R of R2 = R × R or Z2 = Z × Z are indicated by
gray shading. In each case, R is a familiar relation on R or Z. State it.
R
R
12.
13.
14.
15.
Properties of Relations
179
11.1 Properties of Relations
A relational expression xR y is a statement (or an open sentence); it is either
true or false. For example, 5 < 10 is true, and 10 < 5 is false. (Thus an
operation like + is not a relation, because, for instance, 5+10 has a numeric
value, not a T/F value.) Since relational expressions have T/F values, we
can combine them with logical operators; for example, xR y ⇒ yR x is a
statement or open sentence whose truth or falsity may depend on x and y.
With this in mind, note that some relations have properties that others
don’t have. For example, the relation ≤ on Z satisfies x ≤ x for every x ∈ Z.
But this is not so for < because x < x is never true. The next definition
lays out three particularly significant properties that relations may have.
Definition 11.2
Suppose R is a relation on a set A.
1. Relation R is reflexive if xR x for every x ∈ A.
That is, R is reflexive if ∀ x ∈ A, xR x.
2. Relation R is symmetric if xR y implies yR x for all x, y ∈ A
That is, R is symmetric if ∀ x, y ∈ A, xR y ⇒ yR x.
3. Relation R is transitive if whenever xR y and yR z, then also xR z.
That is, R is transitive if ∀ x, y, z ∈ A, ¡(xR y) ∧ ( yR z)¢ ⇒ xR z.
To illustrate this, let’s consider the set A = Z. Examples of reflexive
relations on Z include ≤, =, and |, because x ≤ x, x = x and x | x are all true
for any x ∈ Z. On the other hand, >, <, 6= and - are not reflexive for none
of the statements x < x, x > x, x 6= x and x - x is ever true.
The relation 6= is symmetric, for if x 6= y, then surely y 6= x also. Also,
the relation = is symmetric because x = y always implies y = x.
The relation ≤ is not symmetric, as x ≤ y does not necessarily imply
y ≤ x. For instance 5 ≤ 6 is true, but 6 ≤ 5 is false. Notice (x ≤ y) ⇒ (y ≤ x)
is true for some x and y (for example, it is true when x = 2 and y = 2), but
still ≤ is not symmetric because it is not the case that (x ≤ y) ⇒ ( y ≤ x) is
true for all integers x and y.
The relation ≤ is transitive because whenever x ≤ y and y ≤ z, it also
is true that x ≤ z. Likewise <, ≥, > and = are all transitive. Examine the
following table and be sure you understand why it is labeled as it is.
Relations on Z:
<
≤
=
|
-
6=
Reflexive
no
yes
yes
yes
no
no
Symmetric
no
no
yes
no
no
yes
Transitive
yes
yes
yes
yes
no
no
180
Relations
Example 11.7
Here A = ©b, c, d, eª, and R is the following relation on A:
R = ©(b, b),(b, c),(c, b),(c, c),(d, d),(b, d),(d, b),(c, d),(d, c)ª.
This relation is not reflexive, for although bRb, cR c and dRd, it is not
true that eR e. For a relation to be reflexive, xR x must be true for all x ∈ A.
The relation R is symmetric, because whenever we have xR y, it follows
that yR x too. Observe that bR c and cRb; bRd and dRb; dR c and cRd.
Take away the ordered pair (c, b) from R, and R is no longer symmetric.
The relation R is transitive, but it takes some work to check it. We
must check that the statement (xR y ∧ yR z) ⇒ xR z is true for all x, y, z ∈ A.
For example, taking x = b, y = c and z = d, we have (bR c ∧ cRd) ⇒ bRd,
which is the true statement (T ∧ T) ⇒ T. Likewise, (bRd ∧ dR c) ⇒ bR c is
the true statement (T ∧ T) ⇒ T. Take note that if x = b, y = e and z = c,
then (bR e ∧ eR c) ⇒ bR c becomes (F ∧ F) ⇒ T, which is still true. It’s not
much fun, but going through all the combinations, you can verify that
(xR y ∧ yRz) ⇒ xRz is true for all choices x, y, z ∈ A. (Try at least a few of
them.)
The relation R from Example 11.7 has a meaning. You can think of
xR y as meaning that x and y are both consonants. Thus bRc because b
and c are both consonants; but b 6R e because it’s not true that b and e are
both consonants. Once we look at it this way, it’s immediately clear that R
has to be transitive. If x and y are both consonants and y and z are both
consonants, then surely x and z are both consonants. This illustrates a
point that we will see again later in this section: Knowing the meaning of
a relation can help us understand it and prove things about it.
Here is a picture of R. Notice that we can immediately spot several
properties of R that may not have been so clear from its set description.
For instance, we see that R is not reflexive because it lacks a loop at e,
hence e 6R e.
c
e
d
b
Figure 11.1. The relation R from Example 11.7
Properties of Relations
181
In what follows, we summarize how to spot the various properties of a
relation from its diagram. Compare these with Figure 11.1.
A relation is
1.
reflexive if
x
...there is a
x
loop at x:
for each point x ...
A relation is
symmetric
...there is also
if
an arrow from
2.
whenever there is an
x
y
x
y
y back to x:
arrow from x to y ...
A relation is
transitive
y
...there is also
y
if
an arrow from
whenever there are
x to z:
arrows from x to y
x
z
x
z
and y to z ...
3.
y
(If x = z, this means
y
...there is also
that if there are
a loop from
arrows from x to y
x back to x.)
and from y to x ...
x
x
Consider the bottom diagram in Box 3, above. The transitive property
demands (xR y ∧ yR x) ⇒ xR x. Thus, if xR y and yR x in a transitive relation,
then also xR x, so there is a loop at x. In this case ( yR x ∧ xR y) ⇒ yR y, so
there will be a loop at y too.
Although these visual aids can be illuminating, their use is limited be-
cause many relations are too large and complex to be adequately described
as diagrams. For example, it would be impossible to draw a diagram
for the relation ≡ (mod n), where n ∈ N. Such a relation would best be
explained
in a more theoretical (and less visual) way.
We next prove that ≡ (mod n) is reflexive, symmetric and transitive.
Obviously we will not glean this from a drawing. Instead we will prove it
from the properties of ≡ (mod n) and Definition 11.2. Pay attention to this
example. It illustrates how to prove things about relations.
182
Relations
Example 11.8
Prove the following proposition.
Proposition
Let n ∈ N. The relation ≡ (mod n) on the set Z is reflexive,
symmetric and transitive.
Proof. First we will show that ≡ (mod n) is reflexive. Take any integer x ∈ Z,
and observe that n | 0, so n | (x − x). By definition of congruence modulo n,
we have x ≡ x (mod n). This shows x ≡ x (mod n) for every x ∈ Z, so ≡ (mod n)
is reflexive.
Next, we will show that ≡ (mod n) is symmetric. For this, we must show
that for all x, y ∈ Z, the condition x ≡ y (mod n) implies that y ≡ x (mod n).
We use direct proof. Suppose x ≡ y (mod n). Thus n | (x − y) by definition
of congruence modulo n. Then x − y = na for some a ∈ Z by definition of
divisibility. Multiplying both sides by −1 gives y − x = n(−a). Therefore
n | (y − x), and this means y ≡ x (mod n). We’ve shown that x ≡ y (mod n)
implies that y ≡ x (mod n), and this means ≡ (mod n) is symmetric.
Finally we will show that ≡ (mod n) is transitive. For this we must
show that if x ≡ y (mod n) and y ≡ z (mod n), then x ≡ z (mod n). Again
we use direct proof.
Suppose x ≡ y (mod n) and y ≡ z (mod n).
This
means n | (x − y) and n | ( y − z). Therefore there are integers a and b for
which x − y = na and y − z = nb. Adding these two equations, we obtain
x− z = na+nb. Consequently, x− z = n(a+b), so n | (x− z), hence x ≡ z (mod n).
This completes the proof that ≡ (mod n) is transitive.
The past three paragraphs have shown that ≡ (mod n) is reflexive,
symmetric and transitive, so the proof is complete.
■
As you continue with mathematics you will find that the reflexive,
symmetric and transitive properties take on special significance in a
variety of settings.
In preparation for this, the next section explores
further consequences of these properties.
But first work some of the
following exercises.
Exercises for Section 11.1
1. Consider the relation R = ©(a, a),(b, b),(c, c),(d, d),(a, b),(b, a)ª on set A = ©a, b, c, dª.
Is R reflexive? Symmetric? Transitive? If a property does not hold, say why.
2. Consider the relation R = ©(a, b),(a, c),(c, c),(b, b),(c, b),(b, c)ª on the set A = ©a, b, cª.
Book of Proof Page 25