Relations
Prepared by:Fouzia Naz
1
Cartesian Product (Cross Product)
A B
Create a new set consisting of all
possible ordered pairs with the first
element taking from A, and second
element taking from B.
A B := {( x, y ) : x A and y B}
2
Ordered Pair ( x, y )
Its just like what you learned about when you learned
about graphing:
(1,2) (2,1)
It’s different from set !
◦ {1,2}={2,1}
x, and y can be numbers, names, anything you can
imagine y
(1,2)
0
(2,1)
3
Example of Cartesian Product
I have two T-shirts: white, black
A={white shirt, black shirt}
I have three jeans: black, blue, green
B={black jeans, blue jeans, green jeans}
All outfits I can make out of these ?
The set of all ordered-pairs, in the form (T-shirt, jeans)…
4
Cartesian Product Examples
{(1, a), (1, b), (1, c), (2, a),
A = {1,2,3} A B =
(2, b), (2, c), (3, a), (3, b), (3, c)}
B = {a, b, c} B A = {( a,1), (a,2), (a,3), (b,1), (b,2),
(b,3), (c,1), (c,2), (c,3)}
5
Cardinality of Cartesian Product
If A has m elements, B has n elements, how many
elements does AxB have ?
For every element of A, we pair it with each of the n elements
in B,. to get n ordered pairs in AxB
So we can form n*m ordered pairs this way
So |AxB| = m*n = |A|*|B|
This is where the name Cartesian product comes from.
6
Overview: relations
Binary relations
Defined as a set of ordered pairs
Graph representations
Properties of relations
Reflexive, Irreflexive
Symmetric, Anti-symmetric
Transitive
7
Relations between people
Two people are related, if there is some family connection
between them
We study more general relations between two people:
“is the same major as” is a relation defined among all college
students
If Jack is the same major as Mary, we say Jack is related to Mary
under “is the same major as” relation
This relation goes both way, i.e., symmetric
“is older than” defined among a set of people
This relation does not go both way
“ is facebook friend with”, …
8
Relations between numbers
Comparison relation
=, <, >, <=, …
Other relations
Add up to 10, e.g., 2 and 8 is related under this relation, and so
is 5 and 5, …
Is divisible by
a is divisible by b, if after dividing a by b, we get a remainder of 0
E.g. 6 is divisible by 2, 5 is not divisible by 2, 5 is divisible by 5, …
9
Relation is a graph
nodes (solid small circle): cities,…
Arcs: connecting two cities, … that are related (i.e., connected
by a direct flight)
with Arrows: the direction of the “relation”…
10
Ex: Relations between sets
Given some sets, {},{1}, {2}, {1,2}, {1,2,3}
“Is a subset of” relation:
{} is a subset of {1}
{1} is a subset of {1,2}, …
Practice: draw the graph for each of above relations
“Has more elements than” relation:
{1} has more elements than {}, …
“Have no common elements with” relation:
{} has no common elements with {1},
{1} has no common elements with {2}…
11
ARROW DIAGRAM OF A RELATION:
12
Binary relations: definition
13
Ways to describe the rule
Consider domain S={1,2,3}, and “smaller than”
relation, R<
Specify rule in English: “a is related to b, if a is smaller
than b”
List all pairs that are related
1 is smaller than 2, 1 is smaller than 3, 2 is smaller than 3.
(1,2),(1,3),(2,3) are all ordered pairs of elements that
are related under R<
i.e., R<={(1,2), (1,3),(2,3)}
14
BINARY RELATION:
15
DOMAIN OF A RELATION:
16
RANGE OF A RELATION:
17
EXERCISE:
18
19
Formal definition of binary relation
For domain S, the set of all possible ordered pairs of
elements from S is the Cartesian product, S x S.
Def: a binary relation R defined on domain S is a
subset of S x S
For example: S={1,2,3}, below are relations on S
R1={(1,2)}
R2={}, no number is related to another number
R3 = {( a, b) | a S and b S and a + b 2}
20
Formal definition of binary
relation(cont’d)
Sometimes relation is between two different sets
“goes to college at” relation is defined from the set of people,
to the set of colleges
Given two sets S and T, a binary relation from S to T is a
subset of SxT.
S is called domain of the relation
T is called codomain of the relation
We focus on binary relation with same domain and
codomain for now.
21
RELATION ON A SET:
22
Domain can be infinite set
Domain: Z
R: {(a, b) is an element of Z x Z : (a - b) is even}
Given any pair of integers a, b, we can test if they are
related under R by checking if a-b is even
e.g., as 5-3=2 is even, 5 is related to 3, or
(5,3) R
e.g., as 5-4 is odd,
(5,4) R
23
REMARK:
24
DIRECTED GRAPH OF A RELATION:
25
MATRIX REPRESENTATION OF A
RELATION:
26
EXAMPLE:
For the relation matrix.
1. List the set of ordered pairs represented by M.
2. Draw the directed graph of the relation.
27
Example
For the following relation defined on set {1,2,3,4,5,6},
write set enumeration of the relation, and draw a graph
representation:
Rd: “is divisible by”: e.g., 6 is divisible by 2
Rd = {(1,1), (2,1), (3,1), (4,1), (5,1), (6,1),
(4,2), (6,2), (6,3)}
28
Some exercises
For each of following relations defined on set {1,2,3,4,5,6},
write set enumeration of the relation, and draw a graph
representation:
R≤: “smaller or equal to”
Ra: “adds up to 6”, e.g., (3,3), (1,5) …
29
Another Example
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 to obtain
30
