RELATIONS
RELATIONS
RICKY F. RULETE
Department of Mathematics and Statistics
University of Southeastern Philippines
RELATIONS
PRODUCT SETS
Product Sets
An ordered pair of elements a and b, where a is designated as
the first element and b as the second element, is denoted by
(a, b). In particular,
(a, b) = (c, d)
if and only if a = c and b = d. Thus (a, b) 6= (b, a). This
contrasts with sets where the order of elements is irrelevant; for
example, {3, 5} = {5, 3}.
RELATIONS
PRODUCT SETS
Product Sets
Consider two arbitrary sets A and B. The set of all ordered
pairs (a, b) where a A and b B is called the product, or
Cartesian product, of A and B and is denoted by A B. By
definition,
A B = {(a, b) | a A and b B}
One frequently writes A2 instead of A A.
RELATIONS
PRODUCT SETS
Product Sets
Example (2.1)
R2 = R R is the set of ordered pairs of real numbers.
Example (2.2)
Let A = {1, 2} and B = {a, b, c}. Then
A B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
B A = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}
Also, A A = {(1, 1), (1, 2), (2, 1), (2, 2)}.
RELATIONS
PRODUCT SETS
Product Sets
Remark
1
A B 6= B A
For any finite sets A and B, n(A B) = n(A)n(B). This
follows from the observation that, for an ordered pair (a, b)
in A B, there are n(A) possibilities for a, and for each of
these there are n(B) possibilities for b.
RELATIONS
PRODUCT SETS
Product Sets
For any sets A1 , A2 , . . . , An , the set of all ordered n-tuples
(a1 , a2 , . . . , an ) where a1 A1 , a2 A2 , . . . , an An is called
the product of the sets A1 , A2 , . . . , An and is denoted by
A1 A2 An
or
n
Y
Ai
i=1
We write An instead of A A A, where there are n
factors all equal to A. For example, R3 = R R R.
RELATIONS
RELATIONS
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, for each pair a A
and b B, exactly one of the following is true:
1
(a, b) R; we then say a is R-related to b, written aRb.
(a, b)
/ R; we then say a is not R-related to b, written
a
Rb.
If R is a relation from a set A to itself, that is, R is a subset
of A2 = A A, then we say that R is a relation on A.
RELATIONS
RELATIONS
Relations
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.
Example (2.3)
Let 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 B. With 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}.
RELATIONS
RELATIONS
Relations
Example (2.3)
Set inclusion is a relation on any collection of sets. For,
given any pair of sets A and B, either A B or A 6 B.
A familiar relation on the set Z of integers is m divides
n. A common notation for this relation is to write m|n
when m divides n. Thus 6|30 but 7 - 25.
Consider the set L of lines in the plane. Perpendicularity,
written , is a relation on L. That is,given any pair of
lines a and b, either a b or a 6 b. Similarly, is parallel
to, written k, is a relation on L since either a k b or
a b.
RELATIONS
RELATIONS
Relations
Example (2.3)
Let A be any set. An important relation on A is that of
equality,
{(a, a) | a A}
which is usually denoted by =. This relation is also
called the identity or diagonal relation on A and it will be
also denoted by A or simply .
Let A be any set. Then A A and are subsets of A A
and hence are relations on A called the universal relation
and empty relation, respectively.
RELATIONS
RELATIONS
Inverse Relations
Let R be any relation from a set A to a set B. The inverse of
R, denoted by R1 , is the relation from B to A which consists
of those ordered pairs which, when reversed, belong to R; that
is,
R1 = {(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
R1 = {(y, 1), (z, 1), (y, 3)}
RELATIONS
RELATIONS
Inverse Relations
Remark
1
2
If R is any relation, then (R1 )1 = R.
The domain and range of R1 are equal, respectively, to
the range and domain of R.
If R is a relation on A, then R1 is also a relation on A.
RELATIONS
PICTORIAL REPRESENTATIVES OF RELATIONS
Relations on R
Let S be a relation on R of real numbers; that is, S is a subset
of R2 = R R. Frequently, S consists of all ordered pairs of
real numbers which satisfy some given equation E(x, y) = 0
(such as x2 + y 2 = 25). The pictorial representation of the
relation is sometimes called the graph of the relation. For
example, the graph of the relation x2 + y 2 = 25 is a circle
having its center at the origin and radius 5.
RELATIONS
PICTORIAL REPRESENTATIVES OF RELATIONS
.
...
....
........
.........
... .... ...
.....
..
.....
.
....
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
..
....
...
....
..
....
...
....
..
....
...
....
..
........
.....
.........
...............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
.....................
...
........
....
...
...
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
...
....
..
....
2
2
....5...............
............ .................x. + y = 25
.
.
.
.
.
.....
..
....
....
...
.. ...
...
...
...
...
...
...
....
x
...
5
O
..
...
.. .
...
....
.
.....
...
.
.
.
.
.......
...........
.......
...............................
RELATIONS
PICTORIAL REPRESENTATIVES OF RELATIONS
Consider the relation R on the set A = {1, 2, 3, 4}:
R = {(1, 2), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)}
.......................
...
....
...
.....
.
....
...
.
......
...
.
.
.
.
.
.
.
...................
.................
.........
.....
................................................................................................. 2 ......................
.... 1 .............
.
.
.................
.
.
.
.
........... .......
.
.
.
.
.........
......... . .....
.........
.........
.........
...
.......................
..
..... .............
.
.
.
.
.
.
.
....
.
.........
.
.
.
.
.
.
.
.
.
.
.
.........
.
......
......... ...................
.........
.........
..... .............
...................... ......
...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... 3 ....... .
... 4 .
............. ........
.......... ................
. .............
....................................................
RELATIONS
PICTORIAL REPRESENTATIVES OF RELATIONS
Pictures of Relations on Finite Sets
Suppose A and B are finite sets. There are two ways of
picturing a relation R from A to B.
1
Form a rectangular array (matrix) whose rows are labeled
by the elements of A and whose columns are labeled by the
elements of B. Put 1 or 0 in each position of the array
according as a A is or is not related to b B. This array
is called the matrix of the relation.
Write down the elements of A and the elements of B in two
disjoint disks, and then draw an arrow from a A to b B
whenever a is related to b. This picture will be called the
arrow diagram of the relation.
RELATIONS
PICTORIAL REPRESENTATIVES OF RELATIONS
Pictures of Relations on Finite Sets
R = {(1, y), (1, z), (3, y)}
x y z
1 0 1 1
2 0 0 0
3 0 1 0
RELATIONS
PICTORIAL REPRESENTATIVES OF RELATIONS
Pictures of Relations on Finite Sets
R = {(1, y), (1, z), (3, y)}
.....
.................
...... .........
....
...
...
...
.
...
...
...
..............................
.
.....
.
...
........... ....................
..
...................
..
..............
..
..
...................
.
..
.. .........
...
.
...................
.
..
..
.
.
.
.
.
.
.
.
...
.
.
................... ...
.........
..
..
................
.........
..
..
..
.........
..
.
..
...
.
.........
..
..
.
..
.
.
.
.
.........
..
..
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.........
..
..
.............
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
..
.
.
.
.
.
.
.
..
.... .............
.
.
.
.
.
.
..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
......... ..
..
.
.
.................
..........
...
..
..
...................
..............
..
...
... ....................
...
...
....................
...
...
.
..
.
.
....
.
.
....
.
...................
.................
RELATIONS
COMPOSITION OF RELATIONS
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}
The relation R S is called composition of R and S.
RELATIONS
COMPOSITION OF RELATIONS
Composition of Relations
Remark
1
If R is a relation on a set A, then R R , the composition
of R with itself, is always defined.
R R is sometimes denoted by R2 . Similarly,
R3 = R2 R = R R R. Thus Rn is defined for all
positive n.
Many texts denote the composition of relations R and S
by S R rather than R S.
RELATIONS
COMPOSITION OF RELATIONS
Composition of Relations
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)}
Then R S = {(2, z), (3, x), (3, z)}.
RELATIONS
COMPOSITION OF RELATIONS
Composition of Relations
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 )
RELATIONS
COMPOSITION OF RELATIONS
Composition of Relations
Proof.
Suppose (a, d) belongs to (R S) T . Then there exists c C
such that (a, c) R S and (c, d) T . Since (a, c) R S,
there exists b B such that (a, b) R and (b, c) S. Since
(b, c) S and (c, d) T , we have (b, d) S T ; and since
(a, b) R and (b, d) S T , we have (a, d) R (S T ).
Therefore, (R S) T R (S T ). Similarly
R (S T ) (R S) T . Both inclusion relations prove
(R S) T = R (S T ).
RELATIONS
COMPOSITION OF RELATIONS
Composition of Relations and Matrices
Let MR and MS denote respectively the matrix
of the relations R and S. Then
1 0 0 0
0
0 0 0 1
1
MR =
1 1 0 1 and MS = 0
0 0 0 0
0
Multiplying MR and MS we obtain the matrix
0 0 0
0 0 1
MR MS =
1 0 2
0 0 0
representation
0
0
1
0
0
1
0
1
RELATIONS
TYPES OF RELATIONS
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.
RELATIONS
TYPES OF RELATIONS
Reflexive Relations
Example (2.5)
Consider the following five relations on the set A = {1, 2, 3, 4}:
R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
R3 = {(1, 3), (2, 1)}
R4 = , the empty relation
R5 = A A, the universal relation
Determine which of the relations are reflexive.
RELATIONS
TYPES OF RELATIONS
Reflexive Relations
Example (2.6)
Consider the following five relations:
1
Relation (less than or equal) on the set Z of integers.
Set inclusion on a collection C of sets.
Relation (perpendicular) on the set L of lines in the
plane.
Relation k (parallel) on the set L of lines in the plane.
Relation | of divisibility on the set Z+ of positive integers.
(Recall x | y if there exists z such that xz = y.)
Determine which of the relations are reflexive.
RELATIONS
TYPES OF RELATIONS
Symmetric Relations
A relation 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.
RELATIONS
TYPES OF RELATIONS
Symmetric Relations
Example (2.7)
Determine which of the following five relations on the set
A = {1, 2, 3, 4} are symmetric.
R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
R3 = {(1, 3), (2, 1)}
R4 = , the empty relation
R5 = A A, the universal relation
RELATIONS
TYPES OF RELATIONS
Symmetric Relations
Example (2.7)
2
Determine which of the following five relations are
symmetric.
Relation (less than or equal) on the set Z of integers.
Set inclusion on a collection C of sets.
Relation (perpendicular) on the set L of lines in the
plane.
4 Relation k (parallel) on the set L of lines in the plane.
5 Relation | of divisibility on the set Z+ of positive integers.
(Recall x | y if there exists z such that xz = y.)
1
2
3
RELATIONS
TYPES OF RELATIONS
Antisymmetric Relations
A relation R on a set A is antisymmetric if whenever aRb and
Ra. Thus R is
bRa then a = b, that is, if a 6= b and aRb then b
not antisymmetric if there exists distinct elements a and b in A
such that aRb and bRa.
RELATIONS
TYPES OF RELATIONS
Antisymmetric Relations
Example (2.8)
Determine which of the following five relations on the set
A = {1, 2, 3, 4} are antisymmetric.
R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
R3 = {(1, 3), (2, 1)}
R4 = , the empty relation
R5 = A A, the universal relation
RELATIONS
TYPES OF RELATIONS
Antisymmetric Relations
Example (2.8)
2
Determine which of the following five relations are
antisymmetric.
Relation (less than or equal) on the set Z of integers.
Set inclusion on a collection C of sets.
Relation (perpendicular) on the set L of lines in the
plane.
4 Relation k (parallel) on the set L of lines in the plane.
5 Relation | of divisibility on the set Z+ of positive integers.
(Recall x | y if there exists z such that xz = y.)
1
2
3
RELATIONS
TYPES OF RELATIONS
Remark
The properties of being symmetric and being antisymmetric
are not negatives of each other. For example, the relation
R = {(1, 3), (3, 1), (2, 3)} is neither symmetric nor
antisymmetric. On the other hand, the relation
R0 = {(1, 1), (2, 2)} is both symmetric and antisymmetric.
RELATIONS
TYPES OF RELATIONS
Transitive Relations
A relation 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 exists a, b, c A such that
(a, b), (b, c) R but (a, c)
/ R.
RELATIONS
TYPES OF RELATIONS
Transitive Relations
Example (2.9)
1
Determine which of the following five relations on the set
A = {1, 2, 3, 4} are transitive.
R1 = {(1, 1), (1, 2), (2, 3), (1, 3), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
R3 = {(1, 3), (2, 1)}
R4 = , the empty relation
R5 = A A, the universal relation
RELATIONS
TYPES OF RELATIONS
Transitive Relations
Example (2.9)
2
Determine which of the following five relations are
transitive.
Relation (less than or equal) on the set Z of integers.
Set inclusion on a collection C of sets.
Relation (perpendicular) on the set L of lines in the
plane.
4 Relation k (parallel) on the set L of lines in the plane.
5 Relation | of divisibility on the set Z+ of positive integers.
(Recall x | y if there exists z such that xz = y.)
1
2
3
RELATIONS
EQUIVALENCE RELATIONS
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.
If aRb, then bRa.
If aRb and bRc, then aRc.
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations
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.
If a = b, then b = a.
If a = b and b = c, then a = c.
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations
Example (2.10)
1
Let L be the set of lines and let T be the set of triangles in
the Euclidean plane.
The relation is parallel to or identical to is an equivalence
relation on L.
The relations of congruence and similarity are equivalence
relations on T .
The relation of set inclusion is not an equivalence
relation. It is not symmetric.
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations and Partitions
Suppose R is an equivalence relation on a set S. For each
a S, let [a] denote the set of elements of S to which a is
related under R; that is:
[a] = {x | (a, x) R}
We call [a] the equivalence class of a in S; any b [a] is called a
representative of the equivalence class. The collection of all
equivalence classes of elements of S under an equivalence
relation R is denoted by S/R, that is,
S/R = {[a] | a S}
It is called the quotient set of S/R.
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations and Partitions
Theorem (2.2)
Let R be an equivalence relation on a set S. Then S/R is a
partition of S. Specifically:
1
For each a in S, we have a [a].
[a] = [b] if and only if (a, b) R.
If [a] 6= [b], then [a] and [b] are disjoint.
Conversely, given a partition {Ai } of the set S, there is an
equivalence relation R on S such that the sets Ai are the
equivalence classes.
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations and Partitions
Proof
1
Since R is reflexive, (a, a) R for every a A and
therefore a [a].
Suppose (a, b) R. We want to show that [a] = [b]. Let
x [b]; then (b, x) R. But by hypothesis (a, b) R
and so, by transitivity, (a, x) R. Accordingly x [a].
Thus [b] [a]. To prove that [a] [b] we observe that
(a, b) R implies, by symmetry, that (b, a) R. Then, by
a similar argument, we obtain [a] [b]. Consequently,
[a] = [b]. On the other hand, if [a] = [b], then by (1),
b [b] = [a]; hence (a, b) R.
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations and Partitions
Proof
3
We prove that equivalent contrapositive statement:
If [a] [b] 6= then
[a] = [b]
If [a] [b] 6= then there exists an element x A with
x [a] [b]. Hence (a, x) R and (b, x) R. By
symmetry, (x, b) R and by transitivity, (a, b) R.
Consequently by (2), [a] = [b].
RELATIONS
EQUIVALENCE RELATIONS
Equivalence Relations and Partitions
Example (2.11)
Consider the relation R = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)} on
S = {1, 2, 3}. Observe that R is an equivalence relation. Also:
[1] = {1, 2},
[2] = {1, 2},
[3] = {3}
Observe that [1] = [2] and that S/R = {[1], [3]} is a partition
of S.
RELATIONS
EQUIVALENCE RELATIONS
Partial Ordering Relations
A relation R on a set S is called partial ordering or a partial
order of S if R is reflexive, antisymmetric, and transitive. A set
S together with a partial ordering R is called a partially ordered
set or poset.
RELATIONS
EQUIVALENCE RELATIONS
Partial Ordering Relations
Example (2.12)
1
The relation of set inclusion is a partial ordering on any
collection of sets since set inclusion has the three desired
properties. That is,
A A for any set A.
If A B and B A, then A = B.
If A B and B C, then A C.
RELATIONS
EQUIVALENCE RELATIONS
Partial Ordering Relations
Example (2.12)
The relation on the set R of real numbers is reflexive,
antisymmetric, and transitive. Thus is a partial
ordering on R.
The relation a divides b, written a | b, is a partial
ordering on the set Z+ of positive integers. However, a
divides b is not a partial ordering on the set Z of integers
since a | b and b | a need not imply a = b. For example,
3 | 3 and 3 | 3 but 3 6= 3.
RELATIONS
EQUIVALENCE RELATIONS
THANK YOU!!!
