Discrete Mathematics

CSE 0613-1109

Relations
Chapter 02

1
Relations and their properties
• Relationships between elements of sets are
represented using the structure called a
relation
• A subset of Cartesian product of the sets
• Example: a student and his/her ID

2
Binary relation
• The most direct way to express a relationship
between elements of two sets is to use
ordered pairs made up of two related
elements
• Binary relation: Let A and B be sets. A binary
relation from A to B is a subset of A×B
• A binary relation from A to B is a set R of
ordered pairs where the 1st element comes
from A and the 2nd element comes from B
3
Binary relation
• aRb denotes that (a,b)∊R
• When (a,b) belongs to R, a is said to be related
to b by R
• Likewise, n-ary relations express relationships
among n elements
• Let A1, A2, …, An be sets. An n-ary relation of
these sets is a subset of A1×A2×…×An. The
sets A1, A2, ..., An are called the domains of the
relation, and n is called its degree
4
Example
• Let A be the set of students and B be the set
of courses
• Let R be the relation that consists of those
pairs (a, b) where a∊A and b∊B
• If Jason is enrolled only in CSE20, and John is
enrolled in CSE20 and CSE21
• The pairs (Jason, CSE20), (John,CSE20), (John,
CSE 21) belong to R
• But (Jason, CSE21) does not belong to R
5
Example
• Let A be the set of all cities, and let B be the
set of the 50 states in US. Define a relation R
by specifying (a,b) belongs to R if city a is in
state b
• For instance, (Boulder, Colorado), (Bangor,
Maine), (Ann Arbor, Michigan), (Middletown,
New Jersey), (Middletown, New York),
(Cupertino, California), and (Red Bank, New
Jersey) are in R
6
Example
• Let A={0, 1, 2} and B={a, b}. Then {(0, a), (0, b),
(1, a), (2, b)} is a relation from A to B
• That is 0Ra but not 1Rb

7
Functions as relations
• Recall that a function f from a set A to a set B assigns
exactly one element of B to each element of A
• The graph of f is the set of ordered pairs (a, b) such
that b=f(a)
• Because the graph of f is a subset of A x B, it is a
relation from A to B
• Furthermore, the graph of a function has the
property that every element of A is the first element
of exactly one ordered pair of the graph

8
Functions as relations
• Conversely, if R is a relation from A to B such that
every element in A is the first element of exactly one
ordered pair of R, then a function can be defined
with R as its graph
• A relation can be used to express one-to-many
relationship between the elements of the sets A and
B where an element of A may be related to more
than one element of B
• A function represents a relation where exactly one
element of B is related to each element of A
• Relations are a generalization of functions 9
Relation on a set
• A relation on the set A is a relation from A to
A, i.e., a subset of A x A
• Let A be the set {1, 2, 3, 4}. Which ordered
pairs are in the relation R={(a,b)|a divides b}?
• R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}
1 1 R 1 2 3 4
2 2 1 X X X X
3 3 2 X X
3 X
4 4
4 X
10
Example
• How many relations are there on a set with n
elements?
• A relation on a set A is a subset of A x A
• As A x A has n2 elements, there are 2 subsets
n2

• Thus there are 2 relations on a set with n

elements
• That is, there are 2 = 2 = 512 relations on the set
32 9

{a, b, c}
11
Properties of relations: Reflexive
• In some relations an element is always related to
itself
• Let R be the relation on the set of all people
consisting of pairs (x,y) where x and y have the same
mother and the same father. Then x R x for every
person x
• A relation R on a set A is called reflexive if (a,a) ∊ R
for every element a∊A
• The relation R on the set A is reflexive if ∀a((a,a) ∊ R)

12
Example
• Consider these relations on {1, 2, 3, 4}
R1={(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)}
R2={(1,1),(1,2),(2,1)}
R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)}
R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}
R5={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
R6={(3,4)}
Which of these relations are reflexive?
• R3 and R5 are reflexive as both contain all pairs of the (a,a)
• Is the “divides” relation on the set of positive integers
reflexive?
13
Symmetric
• In some relations an element is related to a second
element if and only if the 2nd element is also related
to the 1st element
• A relation R on a set A is called symmetric if (b,a) ∊ R
whenever (a,b) ∊ R for all a, b ∊ A
• The relation R on the set A is symmetric if
∀a ∀b ((a,b)∊R→(b,a) ∊R)
• A relation is symmetric if and only if a is related to b
implies that b is related to a

14
Antisymmetric
• A relation R on a set A such that for all a, b ∊ A, if
(a, b)∊R and (b, a)∊ R, then a=b is called
antisymmetric
• Similarly, the relation R is antisymmetric if
∀a∀b(((a,b)∊R∧(b,a)∊R)→(a=b))
• A relation is antisymmetric if and only if there are no
pairs of distinct elements a and b with a related to b
and b related to a
• That is, the only way to have a related to b and b
related to a is for a and b to be the same element
15
Symmetric and antisymmetric
• The terms symmetric and antisymmetric are
not opposites as a relation can have both of
these properties or may lack both of them
• A relation cannot be both symmetric and
antisymmetric if it contains some pair of the
form (a, b) where a ≠ b

16
Example
• Consider these relations on {1, 2, 3, 4}
R1={(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)}
R2={(1,1),(1,2),(2,1)}
R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)}
R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}
R5={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
R6={(3,4)}
Which of these relations are symmetric or antisymmetric?
• R2 and R3 are symmetric: each (a,b) → (b,a) in the relation
• R4, R5, and R6 are all antisymmetric: no pair of elements a and
b with a ≠ b s.t. (a, b) and (b, a) are both in the relation
17
Example
• Which are symmetric and antisymmetric
R1={(a,b)|a≤b}
R2={(a,b)|a>b}
R3={(a,b)|a=b or a=-b}
R4={(a,b)|a=b}
R5={(a,b)|a=b+1}
R6={(a,b)|a+b≤3}
• Symmetric: R3, R4, R6. R3 is symmetric, if a=b (or a=-b), then b=a (b=-a), R4
is symmetric as a=b implies b=a, R6 is symmetric as a+b≤3 implies b+a≤3
• Antisymmetric: R1, R2, R4, R5 . R1 is antisymmetric as a≤b and b≤a imply
a=b. R2 is antisymmetric as it is impossible to have a>b and b>a, R4 is
antisymmteric as two elements are related w.r.t. R4 if and only if they are
equal. R5 is antisymmetric as it is impossible to have a=b+1 and b=a+1

18
Transitive
• A relation R on a set A is called transitive if
whenever (a,b)∊R and (b,c)∊R then (a,c)∊R for
all a, b, c ∊ A
• Using quantifiers, we see that a relation R is
transitive if we have
∀a∀b∀c (((a,b)∊R ∧ (b,c)∊R)→ (a,c)∊R)

19
Example
• Which one is transitive?
R1={(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)}
R2={(1,1),(1,2),(2,1)}
R3={(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)}
R4={(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)}
R5={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}
R6={(3,4)}
• R4 R5 R6 are transitive
• R1 is not transitive as (3,1) is not in R1
• R2 is not transitive as (2,2) is not in R2
• R3 is not transitive as (4,2) is not in R3
20
Example
• Which are symmetric and antisymmetric
R1={(a,b)|a≤b}
R2={(a,b)|a>b}
R3={(a,b)|a=b or a=-b}
R4={(a,b)|a=b}
R5={(a,b)|a=b+1}
R6={(a,b)|a+b≤3}
• R1 is transitive as a≤b and b≤c implies a≤c. R2 is transitive
• R3 , R4 are transitive
• R5 is not transitive (e.g., (2,1), (1,0)). R6 is not transitive (e.g.
(2,1),(1,2))
21
Combining relations
• Relations from A to B are subsets of A×B, two
relations can be combined in any way that two sets
can be combined
• Let A={1,2,3} and B={1,2,3,4}. The relations
R1={(1,1),(2,2),(3,3)} and R2={(1,1),(1,2),(1,3),(1,4)}
can be combined
• R1⋃R2={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,3)}
• R1∩R2={(1,1)}
• R1–R2={(2,2),(3,3)}
• R2-R1={(1,2),(1,3),(1,4)}
22
Directed Graphs of Relations on
Sets

23
Graph

24
Composite of relations
• Let R be a relation from a set A to a set B, and S a
relation from B to a set C.
• The composite of R and S is the relation consisting of
ordered pairs (a,c) where a∊A, c∊C and for which
there exists an element b∊B s.t. (a,b)∊R and (b,c)∊S.
We denote the composite of R and S by S∘R
• Need to find the 2nd element of ordered pair in R the
same as the 1st element of ordered pair in S

25
Composition of relations

26
Composition of relations

27
Composition of Relations and Matrices

28
Example
• What is the composite of the relations R and
S, where R is the relation from {1,2,3} to
{1,2,3,4} with R={(1,1),(1,4),(2,3),(3,1),(3,4)}
and S is the relation from {1,2,3,4} to {0,1,2}
with S={(1,0),(2,0),(3,1),(3,2),(4,1)}?
• Need to find the 2nd element in the ordered
pair in R is the same as the 1st element of
order pair in S
• S∘R={(1,0),(1,1),(2,1),(2,2),(3,0),(3,1)}
29
Power of relation
• Let R be a relation on the set A. The powers
Rn,n=1,2,3,…, are defined recursively by R1=R,
Rn+1=Rn∘R
• Example: Let R={(1,1),(2,1),(3,2),(4,3)}. Find
the powers Rn, n=2,3,4,…
• R2=R∘R, we find R2={(1,1),(2,1),(3,1),(4,2)},
R3=R2∘R, R3={(1,1),(2,1),(3,1),(4,1)},
R4={(1,1),(2,1),(3,1),(4,1)}.
• It also follows Rn=R3 for n=5,6,7,…
30
 Try
• Solved problems
• Supplementary problems

31
Knowledge will give you power, but your character will give you respect.

Thank You

32