Computer mathematics
Chapter 4 Relations
Course Outline: Chapter 4
Relations
Relations
Identity Relation
Inverse Relation
Reflexive Relation
Irreflexive Relation
Symmetric Relation
Antisymmetric Relation:
Transitive Relations:
Equivalence Relation
Course Outline:
Relations
Domain and Range of Relation
Equivalence Relations
Complement of a Relation
Composition of Relations
Relations
In discrete mathematics, the relation can be
described as a collection of ordered pairs. It
is used to relate an object from one set to the
other set, and the sets must be non-empty. The
relation can contain two or more than two sets.
Relations
A relation in mathematics defines the
relationship between two different sets of
information. If two sets are considered, the
relation between them will be established if
there is a connection between the elements of
two or more non-empty sets.
Sets and Relations
Sets and relation are interconnected with each
other. The relation defines the relation between
two given sets.
If there are two sets available, then to check if
there is any connection between the two sets,
we use relations.
Types of Relations
Identity Relation
Inverse Relation
Reflexive Relation
Irreflexive Relation
Symmetric Relation
Antisymmetric Relation:
Transitive Relations:
Equivalence Relation
Identity Relation
In an identity relation, every element of a set is
related to itself only. For example, in a set A =
{a, b, c}, the identity relation will be I = {a, a},
{b, b}, {c, c}. For identity relation,
I = {(a, a), a ∈ A}
Reflexive Relation
Reflexive relation is a relation of elements of
a set A such that each element of the set is
related to itself. As it suggests, the image of
every element of the set is its own reflection.
Reflexive relation is an important concept in set
theory
Reflexive Relation
Cont..
If there is a single element of the set that is not
related to itself, then R is not a reflexive
relation. For example, if for b ∈ A and b is not
related to itself (it is denoted by (b, b) ∉ R or
'not bRb') then R is NOT reflexive.
Reflexive Relation Example
aRa or (a,a)εR
A={1,2,3}
R1 ={(1,1),(2,2)}
R2={((1,1),(2,2),(3,3)}
R3={(1,1),(2,2),(3,3),(1,2)}
R4={(1,1),(2,2),(3,2)}
Irreflexive Relation
Symmetric Relation
Symmetric Relation
In a symmetric relation, if a=b is true then b=a is also true.
In other words, a relation R is symmetric only if (b, a) ∈ R is
true when (a,b) ∈ R. An example of symmetric relation will
be R = {(1, 2), (2, 1)} for a set A = {1, 2}. So, for a
symmetric relation,
aRb ⇒ bRa, ∀ a, b ∈ A
Symmetric Relation
Cont..
Symmetric:
“arrows back”
If (x,y) then (y,x)
Antisymmetric Relation:
Asymmetric Relation
Transitive relations
Transitive relations are binary relations
defined on a set such that if the first element is
related to the second element, and the second
element is related to the third element of the
set, then the first element must be related to
the third element.
Transitive relations
A A
B B
C C
D D
Cont..
For example, if for three elements a, b, c in set
A, if a = b and b = c, then a = c. Here, equality
'=' is a transitive relation. There are mainly
three types of relations in discrete mathematics,
namely reflexive, symmetric and transitive
relations among many others.
Transitive Relations
Transitive Relations: A Relation R on set A is
said to be transitive iff (a, b) ∈ R and (b, c) ∈ R
⟺ (a, c) ∈ R.
Equivalence Relation
If a relation is reflexive, symmetric and
transitive at the same time, it is known as an
equivalence relation.
Domain and Range of Relation
Domain of Relation: The Domain of relation R
is the set of elements in P which are related to
some elements in Q, or it is the set of all first
entries of the ordered pairs in R. It is denoted by
DOM (R).
Domain and Range of Relation
Range of Relation: The range of relation R is
the set of elements in Q which are related to
some element in P, or it is the set of all second
entries of the ordered pairs in R. It is denoted by
RAN (R).
Example:
Let A = {1, 2, 3, 4}
B = {a, b, c, d}
R = {(1, a), (1, b), (1, c), (2, b), (2, c), (
2, d)}.
Solution:
DOM (R) ={1,2}
RAN (R) ={a,b,c,d}
Equivalence Relations
A relation R on a set A is called an equivalence
relation if it satisfies following three properties:
1. Relation R is Reflexive, i.e. aRa ∀ a∈A.
2. Relation R is Symmetric, i.e., aRb ⟹ bRa
3. Relation R is transitive, i.e., aRb and bRc ⟹
aRc.
Example:
Let A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2,
2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}.
Show that R is an Equivalence Relation.
Solution:
Reflexive: Relation R is reflexive as (1, 1), (2, 2), (3, 3) and (4,
4) ∈ R.
Symmetric: Relation R is symmetric because whenever (a, b)
∈ R, (b, a) also belongs to R.
Example: (2, 4) ∈ R ⟹ (4, 2) ∈ R.
Cont..
Transitive: Relation R is transitive because
whenever (a, b) and (b, c) belongs to R, (a, c) also
belongs to R.
Example: (3, 1) ∈ R and (1, 3) ∈ R ⟹ (3, 3) ∈ R.
So, as R is reflexive, symmetric and transitive,
hence, R is an Equivalence Relation.
Complement of a Relation
Consider a relation R from a set A to set B. The
complement of relation R denoted by R is a
relation from A to B such that
Example:
Consider the relation R from X to Y
X = {1, 2, 3}
Y = {8, 9}
R = {(1, 8) (2, 8) (1, 9) (3, 9)}
Find the complement relation of R.
Solution:
X x Y ={(1,8),(2,8),(3,8),(1,9),(2,9),(3,9)}
Now we find the complement relation R from X
xY
R={(3,8),(2,9)}
Matrix
8 9
1 1 1
2 1 0
3 0 1
Example:
Now we find the complement relation R from A x
A
A={1,2,3}
R={(1,2),(1,3),(2,1)}
A x A ={(1,1),(1,2),(1,3),(2,1)(2,2),(2,3),(3,1),
(3,2),(3,3)}
Solution:
Now we find the complement relation R from A x
R={(1,1),(2,2),(2,3),(3,1),(3,2),(3,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 indicated by R◦S and defined by:
Cont..
The relation R◦S is known the composition of R
and S; it is sometimes denoted simply by RS.
Example1: Let X = {4, 5, 6}, Y = {a, b, c} and
Z = {l, m, n}. Consider the relation R 1 from X to
Y and R2 from Y to Z.
Example:
R = {(4, a), (4, b), (5, c), (6, a), (6, c)}
1
R = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}
2
Find the composition of relation (i) R1 o R2
Solution:
The composition relation R1 o R2 as shown in fig:
R1 o R2 = {(4, l), (4, n), (4, m),
(5, l), (5, m), (5, n), (6, l), (6, m),
(6, n)}
Example
What is the composite of the relations R and S,
where R is the relation from set A={1,2,3} to
set B={3,4,5} with
R={(1,3),(1,4),(1,5),(2,3),(3,3)} and S is the
relation from set
B={3,4,5} to set C={1,2,3,4} with
S={(3,1),(3,2),(3,3),(4,3),(4,4)}
Solution:
SoR={(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),
(2,3),(3,1),(3,2),(3,3)}
Thanks