Lecture 4

• Set relations
 Cartesian product
 Binary relation
• Composition of Relations
• Inverse Relation
• Functions
Set relations
 Cartesian product
• The Cartesian products of sets mean the
product of two non-empty sets in an ordered
way. Or, in other words, the collection of all
ordered pairs obtained by the product of two
non-empty sets. An ordered pair means that
two elements are taken from each set.
• For two non-empty sets (say A & B), the first
element of the pair is from one set A and the
second element is taken from the second set
B. The collection of all such pairs gives us a
Cartesian product.
• The Cartesian product of two non-empty sets
A and B is denoted by A × B. Also, known as
the cross-product or the product set of A and
B. The ordered pairs (a, b) is such that a ∈ A
and b ∈ B. So, A × B = {(a,b): a ∈ A, b ∈ B}.
• For example, Consider two non-empty sets A =
{a1, a2, a3} and B = {b1, b2, b3}

• Cartesian product A×B = {(a1,b1), (a1,b2),

(a1,b3), ( a2,b1), (a2,b2),(a2,b3), (a3,b1), (a3,b2),
(a3,b3)}.
• Example
• Suppose two sets A = {a, b} and B = {1, 2, 3}.
Find A×B and B×A.
• Here, A = {a, b} B = {1, 2, 3} Now, A×B = {(a,1),
(a,2), (a,3), (b,1), (b,2), (b,3)} B×A = {(1,a),
(1,b), (2,a),(2,b), (3,a), (3,b)}
• Example
• If A×B = { (x,1), (x,2), (x,3),(y,1), (y,2), (y,3)}.
Find A and B.
• Since, set A contains first element of each
ordered pair only,
• A = {x, y}Since, set B contain second element
of ordered pair only,
• B = {1, 2, 3}
• We exclude duplicate elements in both sets
(because, set can only contain unique
element).
• Cartesian Product of 3 Sets
• For three sets A, B and C, the
Cartesian product of A, B and C is denoted
by A×B×C and defined as:
• A×B×C = { (p, q, r) | pϵA and qϵB and rϵC }

• Example: Suppose two sets A = {-1, -2}, B =

{1, 2} and C= {0}. Find A×B×C.
• A×B×C = {(-1,1,0), (-1,2,0), (-2,1,0), (-2,2,0)}
• Cartesian Product of Empty Set
• If either of two set is empty, the Cartesian
product of those two set is also an empty.
• If A = {1, 2} and B = ϕ. Then, A×B = ϕ and B×A =
ϕ.
• Condition for Commutative Property
• For two sets A and B, the Cartesian product of
two sets A×B and B×A are equal if either of the
following condition is satisfied:
 either of two set is empty
 both sets are equal
• If A = {1, 2} and B = ϕ. Then,
A×B = ϕ B×A = ϕ
• Hence, A×B = B×A

• If A = B = {1, 2} then,
A×B = {(1,1), (1,2), (2,1), (2,2)} B×A = {(1,1),
(1,2), (2,1), (2,2)} A×A = A2 = {(1,1), (1,2), (2,1),
(2,2)} B×B = B2 ={(1,1), (1,2), (2,1), (2,2)}
• Hence, A×B = B×A = A2 = B2
 Binary relation
Let A and B be two sets. A binary relation from A to B is a
subset of a Cartesian product A x B.
Example: Let 𝐴𝐴 = {1,2,3,4} and 𝐵𝐵 = {3,5} The statement:
" 𝑥𝑥 𝑅𝑅 𝑦𝑦 𝑖𝑖𝑖𝑖 𝑎𝑎𝑎𝑎𝑎𝑎 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑖𝑖𝑖𝑖 𝑦𝑦 − 𝑥𝑥 = 2 "
o where 𝑅𝑅 is the binary relation from 𝐴𝐴 to 𝐵𝐵.
o where 𝑅𝑅 is the binary relation on 𝐴𝐴.
• Since 𝐴𝐴 × 𝐵𝐵 = {(1,3), (1,5), (2,3), (2,5), (3,3), (3,5), (4,3), (4,5)}
and here 𝑅𝑅 = {(1,3), (3,5)}. we can see that 𝑅𝑅 ⊆ 𝐴𝐴 × 𝐵𝐵.
• Since
(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4),
𝐴𝐴 × 𝐴𝐴 = � � and
(3,1), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)
here 𝑅𝑅 = {(1,3), (2,4)}. we can see that 𝑅𝑅 ⊆ 𝐴𝐴2 = 𝐴𝐴 × 𝐴𝐴.
 Identity Relation
For a given set A, I = {(a, a), a A} is called
the Identity relation in A. In identity relation
every element of A is related to itself only.

Example:

If A = {2, 3 ,4} then R = {(2, 2), (3, 3), (4, 4)} is the
identity relation in A.
 Domain and Range
• Def: (Domain and Range) The domain of a
relation 𝑅𝑅 is the set of all first elements of the
ordered pairs which belong to 𝑅𝑅, and the
range (or image) of 𝑅𝑅 is the set of all second
elements.

• Note that 𝒅𝒅𝒅𝒅𝒅𝒅 𝑹𝑹 ⊆

𝑨𝑨 and 𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓𝒓 𝑹𝑹 ⊆ 𝑩𝑩 . Among all
relations between 𝐴𝐴 and 𝐵𝐵, we
• There are three relations that play a special role:

𝑅𝑅 = ∅, the empty relation. Note that 𝑑𝑑𝑑𝑑𝑑𝑑(∅) = 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(∅) = ∅. This is not
a very exciting relation!
When 𝐴𝐴 = 𝐵𝐵, we have the identity relation, 𝐼𝐼𝐴𝐴 = {(𝑎𝑎, 𝑎𝑎) | 𝑎𝑎 ∈ 𝐴𝐴}
The identity relation relates every element to itself, and that's it! Note that
𝑑𝑑𝑑𝑑𝑑𝑑(𝐼𝐼𝐴𝐴 ) = 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(𝐼𝐼𝐴𝐴 ) = 𝐴𝐴.
The relation 𝐴𝐴 × 𝐵𝐵 itself. This relation relates every element of 𝐴𝐴 to every
element of 𝐵𝐵. Note that 𝑑𝑑𝑑𝑑𝑑𝑑(𝐴𝐴 × 𝐵𝐵) = 𝐴𝐴 ; 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(𝐴𝐴 × 𝐵𝐵) = 𝐵𝐵.
Example: Let 𝐴𝐴 = {1,2,3,4} and 𝐵𝐵 = {3,5} The statement:
" 𝑥𝑥 𝑅𝑅 𝑦𝑦 𝑖𝑖𝑖𝑖 𝑎𝑎𝑎𝑎𝑎𝑎 𝑜𝑜𝑜𝑜𝑜𝑜𝑜𝑜 𝑖𝑖𝑖𝑖 𝑦𝑦 − 𝑥𝑥 = 2 "
o where 𝑅𝑅 is the binary relation from 𝐴𝐴 to 𝐵𝐵.
o where 𝑅𝑅 is the binary relation on 𝐴𝐴.
• Since 𝐴𝐴 × 𝐵𝐵 = {(1,3), (1,5), (2,3), (2,5), (3,3), (3,5), (4,3), (4,5)}
and here 𝑅𝑅 = {(1,3), (3,5)}. we can see that 𝑅𝑅 ⊆ 𝐴𝐴 × 𝐵𝐵.
𝑑𝑑𝑑𝑑𝑑𝑑(𝑅𝑅) = {1,3}; 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(𝑅𝑅) = {3,5}.
• Since
(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4),
𝐴𝐴 × 𝐴𝐴 = � � and
(3,1), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)
here 𝑅𝑅 = {(1,3), (2,4)}. we can see that 𝑅𝑅 ⊆ 𝐴𝐴2 = 𝐴𝐴 × 𝐴𝐴.
𝑑𝑑𝑑𝑑𝑑𝑑(𝑅𝑅) = {1,2}; 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(𝑅𝑅) = {3,4}.
 Representing binary relations
Relations can be represented graphically by pictures often called graphs. Here is an
example:
In Figure,
𝐴𝐴 = {𝑎𝑎1 , 𝑎𝑎2 , 𝑎𝑎3 , 𝑎𝑎4 , 𝑎𝑎5 }; 𝐵𝐵 = {𝑏𝑏1 , 𝑏𝑏2 , 𝑏𝑏3 , 𝑏𝑏4 }. Observe
that 𝑎𝑎5 is not related to any element of 𝐵𝐵, 𝑏𝑏3 is not
related to any element of 𝐴𝐴 and that some elements of
𝐴𝐴, namely, 𝑎𝑎1 , 𝑎𝑎3 , 𝑎𝑎4 , are related some several
elements of 𝐵𝐵.

Now, given a relation, R ⊆ A × B, some element a ∈ A may be related to several

distinct elements b ∈ B.
 Composition of Relations
• the composition relations is a concept of forming
a new relation
• 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:
• a (R◦S)c if for some b ∈ B we have aRb and bSc.
• is,
• R ◦ S = {(a, c)| there exists b ∈ B for which (a, b) ∈
R and (b, c) ∈ S}
• The relation R◦S is known the composition of
R and S; it is sometimes denoted simply by RS.

• Let R is a relation on a set A, that is, R is a

relation from a set A to itself. Then R◦R, the
composition of R with itself, is always
represented. Also, R◦R is sometimes denoted
by R2. Similarly, R3 = R2◦R = R◦R◦R, and so on.
Thus Rn is defined for all positive n.
• Example1: Let X = {4, 5, 6}, Y = {a, b, c} and Z =
{l, m, n}. Consider the relation R1 from X to Y
and R2 from Y to Z.
• R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
• R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c,
n)}

• Find the composition of relation R1 o R2

• Solution:
• The composition relation R1 o R2 as shown in
figure:

• R1 o R2 = {(4, l), (4, n), (4, m), (5, l), (5, m), (5,
n), (6, l), (6, m), (6, n)}
• Example:
• Let R1 and R2 be the relations
on {1,2,3,4,5}{1,2,3,4,5} defined by
• R1={(1,1),(2,3),(2,4),(3,5),(5,2),(5,5)}
R2={(1,1),(2,2),(2,3),(2,5),(4,3),(5,5)}
• Find R2∘R1

Solution:
• R2∘R1={(1,1),(2,3),(2,4),(2,5),(4,5),(5,5)}
 Inverse Relation
• The inverse relation of a binary relation is the
relation that occurs when the order of the
elements is switched in the relation.
Functions
• Let A= 𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑
• And B= 1,2,3,4,5
• So the function is:
• F= 𝑎𝑎, 1 , 𝑏𝑏, 3 , 𝑐𝑐, 4 , (𝑑𝑑, 5)
Let 𝐴𝐴 and 𝐵𝐵 be two nonempty sets. A function,
denoted by 𝑓𝑓, from 𝐴𝐴 to 𝐵𝐵 is a relation from 𝐴𝐴 to 𝐵𝐵
such that:
1. 𝑑𝑑𝑑𝑑𝑑𝑑 𝑓𝑓 = 𝐴𝐴, that is, for each 𝑎𝑎 ∈ 𝐴𝐴, 𝑎𝑎, 𝑏𝑏 ∈ 𝑓𝑓 for
some 𝑏𝑏 ∈ 𝐵𝐵. i.e. 𝑓𝑓 is defined at each 𝑎𝑎 ∈ 𝐴𝐴.
2. If 𝑥𝑥, 𝑦𝑦 ∈ 𝑓𝑓 and 𝑥𝑥, 𝑧𝑧 ∈ 𝑓𝑓 then 𝑦𝑦 = 𝑧𝑧. In this
case, we say that 𝑓𝑓 is well-defined or single-valued.
i.e., no element of 𝐴𝐴 is related to two elements of 𝐵𝐵.
𝐴𝐴 called domain, 𝐵𝐵 called codomain of 𝑓𝑓. If 𝑥𝑥, 𝑦𝑦 ∈
𝑓𝑓, then we say that 𝑦𝑦 is the image of 𝑥𝑥 under 𝑓𝑓 and
we write 𝑦𝑦 = 𝑓𝑓 𝑥𝑥 .Image is a subset of 𝐵𝐵 under 𝑓𝑓
 Example:
Which of the following sets of ordered pairs
represent functions?
A = {(0,-2), (1,4), (-3,3), (5,0)}
B = {(-4,0), (2,-3), (2,-5)}
C = {(-5,1), (2,1), (-3,1), (0,1)}
D ={(3,-4),(3,-2),(0,1),(2,-1)}
E ={(1,3)}