RELATIONS
Definition 2.1: Let A and B be sets. A binary relation or, simply, relation from A to B is a
subset of
A × B.
Suppose R is a relation from A to B. Then R is a set of ordered pairs where each first
element comes from A and each second element comes from B. That is, for each pair a ∈
A and b ∈ B, exactly one of the following is true:
(i) (a, b) ∈ R; we then say “a is R-related to b”, written aRb.
(ii) (a, b) / ∈ R; we then say “a is not R-related to b”, written a_Rb.
The domain of a relation R is the set of all first elements of the ordered pairs which
belong to R, and the range is the set of second elements.
Although n-ary relations, which involve ordered n-tuples, are introduced in Section 2.10,
the term relation shall then mean binary relation unless otherwise stated or implied.
EXAMPLE 2.3
(a) A = (1, 2, 3) and B = {x, y, z}, and let R = {(1, y), (1, z), (3, y)}. Then R is a relation
from A to B since R is a subset of A × [Link] respect to this relation,
1Ry, 1Rz, 3Ry, but 1_Rx, 2_Rx, 2_Ry, 2_Rz, 3_Rx, 3_Rz
The domain of R is {1, 3} and the range is {y, z}.
Inverse Relation
Let R be any relation from a set A to a set B. The inverse of R, denoted by R−1, is the
relation from B to A which consists of those ordered pairs which, when reversed, belong
to R; that is, R−1 = {(b, a) | (a, b) ∈ R}
For example, let A = {1, 2, 3} and B = {x, y, z}. Then the inverse of
R = {(1, y), (1, z), (3, y)} is R−1 = {(y, 1), (z, 1), (y, 3)}
COMPOSITION OF RELATIONS
Let A, B and C be sets, and let R be a relation from A to B and let S be a relation from B
to C. That is, R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a
relation from A to C denoted by R◦S and defined by:
a(R◦S)c if for some b ∈ B we have aRb and bSc.
That is ,
R ◦ S = {(a, c) | there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S}
EXAMPLE 2.4 Let A = {1, 2, 3, 4}, B = {a, b, c, d}, C = {x, y, z} and let
R = {(1, a), (2, d), (3, a), (3, b), (3, d)} and S = {(b, x), (b, z), (c, y), (d, z)}
EXAMPLE 2.4 Let A = {1, 2, 3, 4}, B = {a, b, c, d}, C = {x, y, z} and let
R = {(1, a), (2, d), (3, a), (3, b), (3, d)} and S = {(b, x), (b, z), (c, y), (d, z)}
Consider the arrow diagrams of R and S as in Fig. 2-4. Observe that there is an arrow
from 2 to d which is followed by an arrow from d to z. We can view these two arrows as a
“path” which “connects” the element 2 ∈ A to the element z ∈ C. Thus:
2(R ◦ S)z since 2Rd and dSz
Similarly there is a path from 3 to x and a path from 3 to z. Hence
3(R◦S)x and 3(R◦S)z
No other element of A is connected to an element of C. Accordingly,
R ◦ S = {(2, z), (3, x), (3, z)}
Our first theorem tells us that composition of relations is associative.
Theorem 2.1: Let A, B, C and D be sets. Suppose R is a relation from A to B, S is a
relation from B to C, and T is a relation from C to D. Then
(R ◦ S) ◦ T = R ◦ (S ◦ T )
Composition of Relations and Matrices
There is another way of finding R◦S. Let MR and MS denote respectively the matrix
representations of the relations R and S. Then
TYPES OF RELATIONS
This section discusses a number of important types of relations defined on a set A.
Reflexive Relations
A relation R on a set A is reflexive if aRa for every a ∈ A, that is, if (a, a) ∈ R for every a
∈ A. Thus R is not reflexive if there exists a ∈ A such that (a, a) / ∈ R.
Symmetric Relations
Arelation R on a set A is symmetric if whenever aRb then bRa, that is, if whenever (a, b)
∈ R then (b, a) ∈ R. Thus R is not symmetric if there exists a, b ∈ A such that (a, b) ∈ R
but (b, a) / ∈ R.
Transitive Relations
Arelation R on a set A is transitive if whenever aRb and bRc then aRc, that is, if whenever
(a, b), (b, c) ∈ R then (a, c) ∈ R. Thus R is not transitive if there exist a, b, c ∈ R such
that (a, b), (b, c) ∈ R but (a, c) / ∈ R.
EQUIVALENCE RELATIONS
Consider a nonempty set S. A relation R on S is an equivalence relation if R is reflexive,
symmetric, and transitive. That is, R is an equivalence relation on S if it has the following
three properties:
(1) For every a ∈ S, aRa. (2) If aRb, then bRa. (3) If aRb and bRc, then aRc.
The general idea behind an equivalence relation is that it is a classification of objects
which are in some way “alike.” In fact, the relation “=” of equality on any set S is an
equivalence relation; that is:
(1) a = a for every a ∈ S. (2) If a = b, then b = a. (3) If a = b, b = c, then a = c.