CS 441 Discrete Mathematics for CS

Lecture 21b

Relations

Milos Hauskrecht
[email protected]
5329 Sennott Square

CS 441 Discrete mathematics for CS M. Hauskrecht

Cartesian product (review)

Let A={a1, a2, ..ak} and B={b1,b2,..bm}.
The Cartesian product A x B is defined by a set of pairs
{(a1 b1), (a1, b2), … (a1, bm), …, (ak,bm)}.

Cartesian product defines a product set, or a set of all ordered

arrangements of elements in sets in the Cartesian product.

CS 441 Discrete mathematics for CS M. Hauskrecht

1
 Binary relation
Definition: Let A and B be two sets. A binary relation from A to
B is a subset of a Cartesian product A x B.

• Let R  A x B means R is a set of ordered pairs of the form (a,b)

where a  A and b  B.
• We use the notation a R b to denote (a,b)  R and a R b to
denote (a,b)  R. If a R b, we say a is related to b by R.

Example: Let A={a,b,c} and B={1,2,3}.

• Is R={(a,1),(b,2),(c,2)} a relation from A to B? Yes.
• Is Q={(1,a),(2,b)} a relation from A to B? No.
• Is P={(a,a),(b,c),(b,a)} a relation from A to A? Yes

CS 441 Discrete mathematics for CS M. Hauskrecht

Representing binary relations

• We can graphically represent a binary relation R as follows:
• if a R b then draw an arrow from a to b.
ab

Example:
• Let A = {0, 1, 2}, B = {u,v} and R = { (0,u), (0,v), (1,v), (2,u) }
• Note: R  A x B.
• Graph:
2

0 u
v
1

CS 441 Discrete mathematics for CS M. Hauskrecht

2
 Representing binary relations
• We can represent a binary relation R by a table showing
(marking) the ordered pairs of R.

Example:
• Let A = {0, 1, 2}, B = {u,v} and R = { (0,u), (0,v), (1,v), (2,u) }
• Table:
R | u v or
R | u v
0 | x x 0 | 1 1
1 | x 1 | 0 1
2 | x 2 | 1 0

CS 441 Discrete mathematics for CS M. Hauskrecht

Relations and functions

• Relations represent one to many relationships between
elements in A and B.
• Example: 1
a
2
b
3
• What is the difference between a relation and a function from
A to B?

CS 441 Discrete mathematics for CS M. Hauskrecht

3
 Relations and functions
• Relations represent one to many relationships between
elements in A and B.
• Example: 1
a
2
b
3
• What is the difference between a relation and a function from
A to B? A function defined on sets A,B A  B assigns to each
element in the domain set A exactly one element from B. So it
is a special relation. 1
a
2
b
3
CS 441 Discrete mathematics for CS M. Hauskrecht

Relation on the set

Definition: A relation on the set A is a relation from A to itself.

Example 1:
• Let A = {1,2,3,4} and Rdiv = {(a,b)| a divides b}
• What does Rdiv consist of?
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

• R | 1 2 3 4
1 | x x x x
2 | x x
3 | x
4 | x
CS 441 Discrete mathematics for CS M. Hauskrecht

4
 Relation on the set
Example:
• Let A = {1,2,3,4}.
• Define a R≠ b if and only if a ≠ b.

R≠={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}

• R | 1 2 3 4
1 | x x x
2 | x x x
3 | x x x
4 | x x x

CS 441 Discrete mathematics for CS M. Hauskrecht

Binary relations
• Theorem: The number of binary relations on a set A, where
| A | = n is: 2
2n

• Proof:
. • If | A | = n then the cardinality of the Cartesian product
| A x A | = n2 .
• R is a binary relation on A if R  A x A (that is, R is a subset
of A x A).
• The number of subsets of a set with k elements : 2
k
2
• The number of subsets of A x A is : 2
| AxA|
 2n

CS 441 Discrete mathematics for CS M. Hauskrecht

5
 Binary relations
• Example: Let A = {1,2}
• What is A x A = {(1,1),(1,2),(2,1),(2,2)}
• List of possible relations (subsets of A x A):
•  …. 1
• {(1,1)} {(1,2)} {(2,1)} {(2,2)} …. 4
• {(1,1), (1,2)} {(1,1),(2,1)} {(1,1),(2,2)} …. 6
{(1,2),(2,1)} {(1,2),(2,2)} {(2,1),(2,2)} 16
• {(1,1),(1,2),(2,1)} {(1,1),(1,2),(2,2)} …. 4
{(1,1),(2,1),(2,2)} {(1,2),(2,1),(2,2)}
• {(1,1),(1,2),(2,1),(2,2)} …. 1

• Use formula: 24 = 16
CS 441 Discrete mathematics for CS M. Hauskrecht

Properties of relations
Definition (reflexive relation) : A relation R on a set A is called
reflexive if (a,a)  R for every element a  A.

Example 1:
• Assume relation Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Is Rdiv reflexive?
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Answer: Yes. (1,1), (2,2), (3,3), and (4,4)  A.

CS 441 Discrete mathematics for CS M. Hauskrecht

6
 Reflexive relation
Reflexive relation
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}

1 1 1 1
MRdiv = 0 1 0 1
0 0 1 0
0 0 0 1

• A relation R is reflexive if and only if MR has 1 in every

position on its main diagonal.

CS 441 Discrete mathematics for CS M. Hauskrecht

Properties of relations
Definition (reflexive relation) : A relation R on a set A is called
reflexive if (a,a)  R for every element a  A.

Example 2:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun reflexive?
• No. It is not reflexive since (1,1)  Rfun.

CS 441 Discrete mathematics for CS M. Hauskrecht

7
 Properties of relations
Definition (irreflexive relation): A relation R on a set A is called
irreflexive if (a,a)  R for every a  A.

Example 1:
• Assume relation R≠ on A={1,2,3,4}, such that a R≠ b if and only
if a ≠ b.
• Is R≠ irreflexive?
• R≠ = …

CS 441 Discrete mathematics for CS M. Hauskrecht

Properties of relations
Definition (irreflexive relation): A relation R on a set A is called
irreflexive if (a,a)  R for every a  A.

Example 1:
• Assume relation R≠ on A={1,2,3,4}, such that a R≠ b if and only
if a ≠ b.
• Is R≠ irreflexive?
• R≠={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Answer: Yes. Because (1,1),(2,2),(3,3) and (4,4)  R≠

CS 441 Discrete mathematics for CS M. Hauskrecht

8
 Irreflexive relation
Irreflexive relation
• R≠ on A={1,2,3,4}, such that a R≠ b if and only if a ≠ b.
• R≠={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}

0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0

• A relation R is irreflexive if and only if MR has 0 in every

position on its main diagonal.

CS 441 Discrete mathematics for CS M. Hauskrecht

Properties of relations
Definition (irreflexive relation): A relation R on a set A is called
irreflexive if (a,a)  R for every a  A.

Example 2:
• Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun irreflexive?
• Answer: No. Because (2,2) and (3,3)  Rfun

CS 441 Discrete mathematics for CS M. Hauskrecht

9
 Properties of relations
Definition (symmetric relation): A relation R on a set A is called
symmetric if
 a, b  A (a,b)  R  (b,a)  R.

Example 1:
• Rdiv ={(a b), if a |b} on A = {1,2,3,4}
• Is Rdiv symmetric?
• Rdiv = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
• Answer: No. It is not symmetric since (1,2)  R but (2,1)  R.

CS 441 Discrete mathematics for CS M. Hauskrecht

Properties of relations
Definition (symmetric relation): A relation R on a set A is called
symmetric if
 a, b  A (a,b)  R  (b,a)  R.

Example 2:
• R≠ on A={1,2,3,4}, such that a R≠ b if and only if a ≠ b.
• Is R≠ symmetric ?
• R≠={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}
• Answer: Yes. If (a,b)  R≠  (b,a)  R≠

CS 441 Discrete mathematics for CS M. Hauskrecht

10
 Symmetric relation
Symmetric relation:
• R≠ on A={1,2,3,4}, such that a R≠ b if and only if a ≠ b.
• R≠={(1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)}

0 1 1 1
1 0 1 1
MR = 1 1 0 1
1 1 1 0

• A relation R is symmetric if and only if mij = mji for all i,j.

CS 441 Discrete mathematics for CS M. Hauskrecht

Properties of relations
Definition (symmetric relation): A relation R on a set A is called
symmetric if
 a, b  A (a,b)  R  (b,a)  R.

Example 3:
• Relation Rfun on A = {1,2,3,4} defined as:
• Rfun = {(1,2),(2,2),(3,3)}.
• Is Rfun symmetric?
• Answer: No. For (1,2)  Rfun there is no (2,1)  Rfun

CS 441 Discrete mathematics for CS M. Hauskrecht

11