CHAPTER 7

Introduction to Relations

1. Relations and Their Properties

1.1. Definition of a Relation. Definition: A binary relation from a set A

to a set B is a subset
R ⊆ A × B.
If (a, b) ∈ R we say a is related to b by R.

A is the domain of R, and

B is the codomain of R.

If A = B, R is called a binary relation on the set A.

Notation:

• If (a, b) ∈ R, then we write aRb.

• If (a, b) 6∈ R, then we write a R

6 b.

Discussion

Notice that a relation is simply a subset of A × B. If (a, b) ∈ R, where R is

some relation from A to B, we think of a as being assigned to b. In these senses
students often associate relations with functions. In fact, a function is a special case
of a relation as you will see in Example 1.2.4. Be warned, however, that a relation
may differ from a function in two possible ways. If R is an arbitrary relation from A
to B, then

• it is possible to have both (a, b) ∈ R and (a, b0 ) ∈ R, where b0 6= b; that is,

an element in A could be related to any number of elements of B; or
• it is possible to have some element a in A that is not related to any element
in B at all.
204
 1. RELATIONS AND THEIR PROPERTIES 205

Often the relations in our examples do have special properties, but be careful not to
assume that a given relation must have any of these properties.

1.2. Examples.
Example 1.2.1. Let A = {a, b, c} and B = {1, 2, 3, 4}, and let R1 = {(a, 1), (a, 2), (c, 4)}.
Example 1.2.2. Let R2 ⊂ N × N be defined by (m, n) ∈ R2 if and only if m|n.
Example 1.2.3. Let A be the set of all FSU students, and B the set of all courses
offered at FSU. Define R3 as a relation from A to B by (s, c) ∈ R3 if and only if s is
enrolled in c this term.

Discussion

There are many different types of examples of relations. The previous examples
give three very different types of examples. Let’s look a little more closely at these
examples.

Example 1.2.1. This is a completely abstract relation. There is no obvious reason

for a to be related to 1 and 2. It just is. This kind of relation, while not having any
obvious application, is often useful to demonstrate properties of relations.

Example 1.2.2. This relation is one you will see more frequently. The set R2 is
an infinite set, so it is impossible to list all the elements of R2 , but here are some
elements of R2 :
(2, 6), (4, 8), (5, 5), (5, 0), (6, 0), (6, 18), (2, 18).
Equivalently, we could also write
2R2 6, 4R2 8, 5R2 5, 5R2 0, 6R2 0, 6R2 18, 2R2 18.
Here are some elements of N × N that are not elements of R2 :
(6, 2), (8, 4), (2, 5), (0, 5), (0, 6), (18, 6), (6, 8), (8, 6).

Example 1.2.3. Here is an element of R3 : (you, MAD2104).

Example 1.2.4. Let A and B be sets and let f : A → B be a function. The graph
of f , defined by graph(f ) = {(x, f (x))|x ∈ A}, is a relation from A to B.

Notice the previous example illustrates that any function has a relation that is
associated with it. However, not all relations have functions associated with them.
Exercise 1.2.1. Suppose f : R → R is defined by f (x) = bx/2c.

(1) Find 5 elements of the relation graph(f ).

 1. RELATIONS AND THEIR PROPERTIES 206

(2) Find 5 elements of R × R that are not in graph(f ).

Exercise 1.2.2. Find a relation from R to R that cannot be represented as the
graph of a functions.

Exercise 1.2.3. Let n be a positive integer. How many binary relations are there
on a set A if |A| = n? [Hint: How many elements are there in |A × A|?]

1.3. Directed Graphs.

Definitions 1.3.1.
• A directed graph or a digraph D from A to B is a collection of vertices
V ⊆ A ∪ B and a collection of edges R ⊆ A × B.
• If there is an ordered pair e = (x, y) in R then there is an arc or edge from
x to y in D.
• The elements x and y are called the initial and terminal vertices of the
edge e = (x, y), respectively.

Discussion

A digraph can be a useful device for representing a relation, especially if the

relation isn’t “too large” or complicated.

The digraph that represents R1 in Example 1.2.1 is:

a 1

2
b
3

c 4

Discussion

If R is a relation on a set A, we simplify the digraph D representing R by having

only one vertex for each a ∈ A. This results, however, in the possibility of having
loops, that is, edges from a vertex to itself, and having more than one edge joining
distinct vertices (but with opposite orientations).
 1. RELATIONS AND THEIR PROPERTIES 207

A digraph for R2 in Example 1.2.2 would be difficult to illustrate (and impossible

to draw completely), since it would require infinitely many vertices and edges. We
could draw a digraph for some finite subset of R2 . It is possible to indicate what the
graph of some infinite relations might look like, but this one would be particularly
difficult.

Example 1.3.1. Let R5 be the relation from {0, 1, 2, 3, 4, 5, 6} defined by mR5 n if

and only if m ≡ n(mod 3). The digraph that represents R5 is

0 1 2

3 6 4 5

1.4. Inverse Relation.

Definition 1.4.1. Let R be a relation from A to B. Then R−1 = {(b, a)|(a, b) ∈
R} is a relation from B to A.

R−1 is called the inverse of the relation R.

Discussion

The inverse of a relation R is simply the relation obtained by reversing the ordered
pairs of R. The inverse relation is also called the converse relation.
Example 1.4.1. Recall Example 1.2.1 A = {a, b, c} and B = {1, 2, 3, 4} and
R1 = {(a, 1), (a, 2), (c, 4)}. Then R−1 = {(1, a), (2, a), (4, c)}.
Exercise 1.4.1. Recall Example 1.2.4. A and B are sets and f : A → B is a
function. The graph of f , graph(f ) = {(x, f (x))|x ∈ A} is a relation from A to B.

(1) What is the inverse of this relation?

(2) Does f have to be invertible for the inverse of this relation to exist?
(3) If f is invertible, find the inverse of the relation graph(f ) in terms of the
inverse function f −1 .
 1. RELATIONS AND THEIR PROPERTIES 208

1.5. Special Properties of Binary Relations.

Definitions 1.5.1. Let A be a set, and let R be a binary relation on A.

(1) R is reflexive if
∀x[(x ∈ A) → ((x, x) ∈ R)].
(2) R is irreflexive if
∀x[(x ∈ A) → ((x, x) 6∈ R)].
(3) R is symmetric if
∀x∀y[((x, y) ∈ R) → ((y, x) ∈ R)].
(4) R is antisymmetric if
∀x∀y[([(x, y) ∈ R] ∧ [(y, x) ∈ R]) → (x = y)].
(5) R is asymmetric if
∀x∀y[((x, y) ∈ R) → ((y, x) 6∈ R)].
(6) R is transitive if
∀x∀y∀z[([(x, y) ∈ R] ∧ [(y, z) ∈ R]) → ((x, z) ∈ R)].

Discussion

Study the definitions of the definitions of the properties given above. You must
know these properties, be able to recognize whether or not a relation has a particular
property, and be able to prove that a relation has or does not have a particular
property. Notice that the definitions of reflexive and irreflexive relations are not
complementary. In fact, a relation on a set may be neither reflexive nor irreflexive.
The same is true for the symmetric and antisymmetric properties, as well as the
symmetric and asymmetric properties. Some texts use the term antireflexive for
irreflexive.
Exercise 1.5.1. Before reading further, find a relation on the set {a, b, c} that is
neither

(a) reflexive nor irreflexive.

(b) symmetric nor antisymmetric.
(c) symmetric nor asymmetric.

1.6. Examples of Relations and Their Properties.

Example 1.6.1. Suppose A is the set of FSU students and R is the relation given
by aRb if students a and b have the same last name. This relation is. . .

• reflexive
• not irreflexive
• symmetric
• not antisymmetric
 1. RELATIONS AND THEIR PROPERTIES 209

• not asymmetric
• transitive
Example 1.6.2. Suppose T is the relation on the set of integers given by xT y if
2x − y = 1. This relation is. . .

• not reflexive
• not irreflexive
• not symmetric
• antisymmetric
• not asymmetric
• not transitive
Example 1.6.3. Suppose A = {a, b, c, d} and R is the relation {(a, a)}. This
relation is. . .

• not reflexive
• not irreflexive
• symmetric
• antisymmetric
• not asymmetric
• transitive

Discussion

The examples above illustrate three rather different relations. Some of the rela-
tions have many of the properties defined on Section 1.5, whereas one has only one
of the property. It is entirely possible to create a relation with none of the properties
given in Section 1.5.
Exercise 1.6.1. Give an example of a relation that does not satisfy any property
given in Section 1.5.

1.7. Proving or Disproving Relations have a Property.

Example 1.7.1. Suppose T is the relation on the set of integers given by xT y if
2x − y = 1. This relation is

• not reflexive
Proof. 2 is an integer and 2 · 2 − 2 = 2 6= 1. This shows that ∀x[x ∈
Z → (x, x) ∈ T ] is not true. 
• not irreflexive
Proof. 1 is an integer and 2 · 1 − 1 = 1. This shows that ∀x[x ∈ Z →
(x, x) 6∈ T ] is not true. 
 1. RELATIONS AND THEIR PROPERTIES 210

• not symmetric
Proof. Both 2 and 3 are integers, 2 · 2 − 3 = 1, and 2 · 3 − 2 = 4 6= 1.
6 2; that is, ∀x∀y[(x, y) ∈ Z → (y, x) ∈ T ] is not
This shows 2R3, but 3 R
true. 
• antisymmetric
Proof. Let m, n ∈ Z be such that (m, n) ∈ T and (n, m) ∈ T . By the
definition of T , this implies both equations 2m − n = 1 and 2n − m = 1
must hold. We may use the first equation to solve for n, n = 2m − 1, and
substitute this in for n in the second equation to get 2(2m − 1) − m = 1. We
may use this equation to solve for m and we find m = 1. Now solve for n
and we get n = 1.
This shows that the only integers, m and n, such that both equations
2m − n = 1 and 2n − m = 1 hold are m = n = 1. This shows that
∀m∀n[((m, n) ∈ T ∧ (n, m) ∈ T ) → m = n]. 
• not asymmetric
Proof. 1 is an integer such that (1, 1) ∈ T . Thus ∀x∀y[((x, y) ∈ T →
(b, a) 6∈ T ] is not true (counterexample is a = b = 1). 
• not transitive
Proof. 2, 3, and 5 are integers such that (2, 3) ∈ T , (3, 5) ∈ T , but
(2, 5) 6∈ T . This shows ∀x∀y∀z[(x, y) ∈ T ∧ (y, z) ∈ T → (x, z) ∈ T ] is not
true. 
Example 1.7.2. Recall Example 1.2.2: R2 ⊂ N × N was defined by (m, n) ∈ R2
if and only if m|n.

• reflexive
Proof. Since n|n for all integers, n, we have nR2 n for every integer.
This shows R2 is reflexive. 
• not irreflexive
Proof. 1 is an integer and clearly 1R2 1. This shows R2 is not irreflexive.
(you could use any natural number to show R2 is not irreflexive). 
• not symmetric
Proof. 2 and 4 are natural numbers with 2|4, but 4 6 |2, so 2R2 4, but
6 2 2. This shows R2 is not reflexive.
4R 
• antisymmetric
Proof. Let n, m ∈ N be such that nR2 m and mR2 n. By the definition
of R2 this implies n|m and m|n. Hence we must have m = n. This shows R2
is antisymmetric. 
 1. RELATIONS AND THEIR PROPERTIES 211

• not asymmetric
Proof. Let m = n be any natural number. Then nR2 m and mR2 n,
which shows R2 is not asymmetric. (You may use a particular number to
show R2 is not asymmetric. 
• transitive
Proof. Let p, q, r ∈ N and assume pR2 q and qR2 r. By the definition of
R2 this means p|q and q|r. We have proven in Integers and Division that
this implies p|r, thus pR2 r. This shows R2 is transitive. 

Discussion

When proving a relation, R, on a set A has a particular property, the property

must be shown to hold for all possible members of the set. For example, if you wish to
prove that a given relation, R, on A is reflexive, you must take an arbitrary element
x from A and show that xRx. Some properties, such as the symmetric property, are
defined using implications. For example, if you are asked to show that a relation, R,
on A is symmetric, you would suppose that x and y are arbitrary elements of A such
that xRy, and then try to prove that yRx. It is possible that a property defined by
an implication holds vacuously or trivially.
Exercise 1.7.1. Let R be the relation on the set of real numbers given by xRy if
and only if x < y. Prove R is antisymmetric.

When proving R does not have a property, it is enough to give a counterexample.

Recall ¬[∀x∀yP (x, y)] ⇔ ∃x∃y¬P (x, y).

Exercise 1.7.2. Prove whether or not each of the properties in Section 1.5 holds
for the relation in Example 1.6.1.
Exercise 1.7.3. Prove whether or not each of the properties in Section 1.5 holds
for the relation in Example 1.6.3.

1.8. Combining Relations. Important Question: Suppose property P is one

of the properties listed in Section 1.5, and suppose R and S are relations on a set A,
each having property P . Then the following questions naturally arise.

(1) Does R (necessarily) have property P ?

(2) Does R ∪ S have property P ?
(3) Does R ∩ S have property P ?
(4) Does R − S have property P ?
 1. RELATIONS AND THEIR PROPERTIES 212

1.9. Example of Combining Relations.

Example 1.9.1. Let R1 and R2 be transitive relations on a set A. Does it follow
that R1 ∪ R2 is transitive?

Solution: No. Here is a counterexample:

A = {1, 2}, R1 = {(1, 2)}, R2 = {(2, 1)}

Therefore, R1 ∪ R2 = {(1, 2), (2, 1)}

Notice that R1 and R2 are both transitive (vacuously, since there are no two ele-
ments satisfying the conditions of the property). However R1 ∪ R2 is not transitive.
If it were it would have to have (1, 1) and (2, 2) in R1 ∪ R2 .

Discussion

Example 1.9.1 gives a counterexample to show that the union of two transitive
relations is not necessarily transitive. Note that you could find an example of two
transitive relations whose union is transitive. However, the question asks if the given
property holds for two relations must it hold for the binary operation of the two
relations. This is a general question and to give the answer “yes” we must know it is
true for every possible pair of relations satisfying the property.

Here is another example:

Example 1.9.2. Suppose R and S are transitive relations on the set A. Is R ∩ S
transitive?

Solution: Yes.

Proof. Assume R and S are both transitive and let (a, b), (b, c) ∈ R ∩ S. Then
(a, b), (b, c) ∈ R and (a, b), (b, c) ∈ S. It is given that both R and S are transitive,
so (a, c) ∈ R and (a, c) ∈ S. Therefore (a, c) ∈ R ∩ S. This shows that for arbitrary
(a, b), (b, c) ∈ R ∩ S we have (a, c) ∈ R ∩ S. Thus R ∩ S is transitive. 

1.10. Composition.
Definitions 1.10.1.
(1) Let
• R1 be a relation from A to B, and
• R2 be a relation from B to C.
 1. RELATIONS AND THEIR PROPERTIES 213

Then the composition of R1 with R2 , denoted R2 ◦ R1 , is the relation from

A to C defined by the following property:
(x, z) ∈ R2 ◦ R1 if and only if there is a y ∈ B such that (x, y) ∈ R1 and
(y, z) ∈ R2 .
(2) Let R be a binary relation on A. Then Rn is defined recursively as follows:
Basis: R1 = R
Recurrence: Rn+1 = Rn ◦ R, if n ≥ 1.

Discussion

The composition of two relations can be thought of as a generalization of the

composition of two functions, as the following exercise shows.
Exercise 1.10.1. Prove: If f : A → B and g : B → C are functions, then
graph(g ◦ f ) = graph(g) ◦ graph(f ).

Exercise 1.10.2. Prove the composition of relations is an associative operation.

Exercise 1.10.3. Let R be a relation on A. Prove Rn ◦ R = R ◦ Rn using the
previous exercise and induction.
Exercise 1.10.4. Prove an ordered pair (x, y) ∈ Rn if and only if, in the digraph
D of R, there is a directed path of length n from x to y.

Notice that if there is no element of B such that (a, b) ∈ R1 and (b, c) ∈ R2 for
some a ∈ A and c ∈ C, then the composition is empty.

1.11. Example of Composition.

Example 1.11.1. Let A = {a, b, c}, B = {1, 2, 3, 4}, and
C = {I, II, III, IV }.

• R1 = {(a, 4), (b, 1)}

• R2 = {(1, II), (1, IV ), (2, I)}
• Then R2 ◦ R1 = {(b, II), (b, IV )}

Discussion

It can help to consider the following type of diagram when discussing composition
of relations, such as the ones in Example 1.11.1 as shown here.
 1. RELATIONS AND THEIR PROPERTIES 214

a 1 I

2 II
b
3 III

c 4 IV
Example 1.11.2. If R and S are transitive binary relations on A, is R ◦ S tran-
sitive?

Solution: No. Here is a counterexample: Let

R = {(1, 2), (3, 4)}, and S = {(2, 3), (4, 1)}.
Then both R and S are transitive (vacuously). However,
R ◦ S = {(2, 4), (4, 2)}
is not transitive. (Why?)
Example 1.11.3. Suppose R is the relation on Z defined by aRb if and only if
a|b. Then R2 = R.
Exercise 1.11.1. Let R be the relation on the set of real numbers given by xRy
x
if and only if = 2.
y

(1) Describe the relation R2 .

(2) Describe the relation Rn .
Exercise 1.11.2. Let P be a property given below and let R and S be relations
on A satisfying property P . When does the relation obtained by combining R and S
using the operation given satisfy property P ?

(1) P is the reflexive property.

(a) R ∪ S
(b) R ∩ S
(c) R ⊕ S
(d) R − S
(e) R ◦ S
(f ) R−1
(g) Rn
(2) P is the symmetric property.
 1. RELATIONS AND THEIR PROPERTIES 215

(a) R ∪ S
(b) R ∩ S
(c) R ⊕ S
(d) R − S
(e) R ◦ S
(f ) R−1
(g) Rn
(3) P is the transitive property.
(a) R ∪ S
(b) R ∩ S
(c) R ⊕ S
(d) R − S
(e) R ◦ S
(f ) R−1
(g) Rn

1.12. Characterization of Transitive Relations.

Theorem 1.12.1. Let R be a binary relation on a set A. R is transitive if and
only if Rn ⊆ R, for n ≥ 1.

Proof. To prove (R transitive) → (Rn ⊆ R) we assume R is transitive and prove

n
R ⊆ R for n ≥ 1 by induction.

Basis Step, n = 1. R1 = R, so this is obviously true.

Induction Step. Prove Rn ⊆ R → Rn+1 ⊆ R.

Assume Rn ⊆ R for some n ≥ 1. Suppose (x, y) ∈ Rn+1 . By definition Rn+1 =

R ◦ R, so there must be some a ∈ A such that (x, a) ∈ R and (a, y) ∈ Rn . However,
n

by the induction hypothesis Rn ⊆ R, so (a, y) ∈ R. R is transitive, though, so

(x, a), (a, y) ∈ R implies (x, y) ∈ R. Since (x, y) was an arbitrary element of Rn+1 ,
this shows Rn+1 ⊆ R.

Now we must show the other direction : Rn ⊆ R, for n ≥ 1, implies R is transitive.

We prove this directly.

Assume (x, y), (y, z) ∈ R. But by the definition of composition, this implies
(x, z) ∈ R2 . But R2 ⊆ R, so (x, z) ∈ R. This shows R is transitive.

Discussion
 1. RELATIONS AND THEIR PROPERTIES 216

Theorem 1.12.1 gives an important theorem characterizing the transitivity rela-

tion. Notice that, since the statement of the theorem was a property that was to be
proven for all positive integers, induction was a natural choice for the proof.
Exercise 1.12.1. Prove that a relation R on a set A is transitive if and only if
R2 ⊆ R. [Hint: Examine not only the statement, but the proof of Theorem 1.12.1.]