Chapter III
RELATIONS
1. Introduction of relations
2. Domain and Range
3. Methods of describing relations
4. Identity and inverse relations
5. Composition of relations
6. Digraph of relations
7. Partitions and cross partition
1. RELATIONS: INTRODUCTION
- Relations can be used to store information in
the computer databases. Relationships
between people, numbers, events, letters,
sets, and many other entities can be
formalized in the idea of a binary relation. It
is a binary relation because it relates two
objects.
A
B
A x B = SUBSETS = UNIVERSAL
R
- If two ordered pair of elements are written, Note on Relations
separated by comma and enclosed by
parentheses like (a, b), they form a binary Try this one!
relation. In a binary relation (a, b), a- - Let R be a relation from a set A to itself. A
coordinate as called the left component or relation on the set A is a subset of A x A.
the domain and the b- coordinate is called
the right component or the range. Let A = {1, 2, 3, 4}, R = {(a, b) | a divides b}.
Which ordered pairs are in the relation R? Also,
Note: (a , b) ≠ (b, a) unless a = b. describe the sets in terms of an arrow diagram and a
(2,3) ≠ (3,2) matrix.
(3,3) = (3,3) ▪AxA=
{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(2,4),(3,1),(3,
2),(3
,3),(3,4),(4,1),(4,2),(4,3),(4,4)}
▪ R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}
ANSWER;
Step 1: Understanding the Relation RRR Identity and Inverse Relations
The relation RRR consists of pairs (a,b)(a, b)(a,b) - Let A be a set. The identity relation on A is
where aaa divides bbb. From the given set denoted by IA , and is given by the symbols
A={1,2,3,4}A = \{1, 2, 3, 4\}A={1,2,3,4}, we :
determine the ordered pairs:
▪ IA = {(a, a) | a ∈ A}.
R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}R =
- Let R be a relation from A to B. The inverse
\{(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3),
of R, denoted by R -1 , is the relation from B
(4,4)\}R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,
to A given by bR-1a if and only if aRb, in
4)}
symbols
• 1 divides every number:
(1,1),(1,2),(1,3),(1,4)(1,1), (1,2), (1,3), ▪ R -1 = {(b, a) | (a, b) ∈ R}
(1,4)(1,1),(1,2),(1,3),(1,4) NOTE:
• 2 divides 2 and 4: (2,2),(2,4)(2,2), - Identity relation is also called equality or
(2,4)(2,2),(2,4) diagonal relation on A. It is denoted by “-“,
• 3 divides itself: (3,3)(3,3)(3,3) sometimes “ΔA ” or simply “Δ”.
• 4 divides itself: (4,4)(4,4)(4,4) Remark:
- If R is any relation, then (R-1 ) -1 = R. The
domain of R -1 is the range of R and vice
Versa. If R is a relation on A, i.e. R is a
subset of A x A, then R -1 is also relation on
A.
Some Examples
1. Let A = {1, 2, 3, 4} and let R be the relation
on A such that R = {(1, 2), (2, 3), (3, 4), (4,
1)}.
Solve for:
▪ The inverse relation R
▪ The identity relation
SOLUTION:
▪ R-1 = {(2, 1), (3, 2), (4, 3), (1, 4)}
▪ IA = {(1, 1), (2, 2), (3, 3), (4, 4)}
2. Let A = {1, 2, 3} and B = {a, b, c}. If R = {(1, a),
(2, b), (3, c)}, find:
▪ The inverse relation
▪ The identity relation IA and IB
SOLUTION:
▪ R -1 = {(a, 1), (b, 2), (c, 3)}
▪ IA = {(1, 1), (2, 2), (3, 3)}
▪ IB = {(a, a), (b, b), (c, c)}
Composition of Relations: Example
Try this!
Suppose A = {1,2,3}, and Let R = {(1,2), (1,3),
(2,2), (3,3)} be a relation from set A to set A.
▪ Visualize the composition using arrow diagrams.
▪ Find the relation R3.
ANSWER:
Step 1: Understanding RRR
The given relation RRR is:
R={(1,2),(1,3),(2,2),(3,3)}R = \{(1,2), (1,3), (2,2),
(3,3)\}R={(1,2),(1,3),(2,2),(3,3)}
This means:
• 1 is related to 2 and 3.
• 2 is related to itself (loop on 2).
• 3 is related to itself (loop on 3).
Final Answer
1. The composition relation remains the same
for R2R^2R2 and R3R^3R3.
2. The arrow diagram is the same as the given
RRR.
Digraph of Relations
Try this!
Let A = {1,2,3,4}; R = {(1,2), (2,2), (2,4), (3,2),
(3,4), (4,1), (4,3)}. Given the relations create a
digraph, list of in-degree and out-degree of all
vertices in a table, and matrix.
ANSWER:
Final Answer
1. Digraph: Shows how elements relate with
arrows.
2. Table: Lists the in-degree and out-degree
of each vertex.
3. Matrix: Represents the relation in a
structured form.
Closure Properties
- The reflexive, symmetric and transitive
closures of a relation R is to be denoted
respectively by: reflexive(R), symmetric
(R), and transitive (R).
▪ Reflexive (R) can be obtained by adding to R
those identity elements (a, a) which do not belong to
R.
▪ Symmetric (R) will be obtained by adding to R all
pairs (b, a) whenever (a, b) belong to R.
