Class 18

Discrete Structures
Lecture 18
Relations
Composite of relations
Definition: Let R be a relation on a set A. The powers Rn, n =
1,2,3,... is defined inductively by
• R1 = R and Rn+1 = Rn o R.
Examples
• R = {(1,2),(2,3),(2,4), (3,3)} is a relation on A = {1,2,3,4}.
• R 1 = R = {(1,2),(2,3),(2,4), (3,3)}
• R 2 = {(1,3), (1,4), (2,3), (3,3)}
• R 3 = {(1,3), (2,3), (3,3)}
• R 4 = {(1,3), (2,3), (3,3)}
• R k = R 3, k > 3.
CS 441 Discrete mathematics for CS M. Hauskrecht

Transitive relation
Definition (transitive relation): A relation R on a set A is called
transitive if
• [(a,b) ∈ R and (b,c) ∈ R] → (a,c) ∈ R for all a, b, c ∈ A.
• Example 1:
• 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)}
• Is Rdiv transitive?
• Answer: Yes.
Connection to Rn
Theorem: The relation R on a set A is transitive if and only if
Rn ⊆ R for n = 1,2,3,... .
Proof: biconditional (if and only if)
Suppose Rn ⊆ R, for n =1,2,3,... .

• Let (a,b) ∈ R and (b,c) ∈ R
• by the definition of R º R, (a,c) ∈ R º R ⊆ R →
• R is transitive.

Connection to Rn
Theorem: The relation R on a set A is transitive if and only if Rn ⊆
R for n = 1,2,3,... .
Proof: biconditional (if and only if)

Suppose R is transitive. Show Rn ⊆ R, for n =1,2,3,... .
• Let P(n) : Rn ⊆ R. Math induction.
• Basis Step: P(1) says R1 = R so, R1 ⊆ R is true.
• Inductive Step: show P(n) → P(n+1)
• Want to show if Rn ⊆ R then Rn+1 ⊆ R.
• Let (a,b) ∈ Rn+1 then by the definition of Rn+1 = Rn { R there is
an element x ∈ A so that (a,x) ∈ R and (x,b) ∈ Rn ⊆ R (inductive
hypothesis). In addition to (a,x) ∈ R and (x,b) ∈ R, R is
transitive; so (a,b) ∈ R.
• Therefore, Rn+1 ⊆ R.
Representing binary relations with graphs

• We can graphically represent a binary relation R from A to B as
follows:
• if a R b then draw an arrow from a to b.
a→b
Example:
• Relation Rdiv (from previous lectures) 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
2 2
3 3
4 4

Representing relations on a set with digraphs
Definition: A directed graph or digraph consists of a set of
vertices (or nodes) together with a set E of ordered pairs of
elements of V valled edges (or arcs). The vertex a is called the
initial vertex of the edge (a,b) and vertex b is the terminal vertex
of this edge. An edge of the form (a,a) is called a loop.
Example
• Relation Rdiv ={(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
1 1
digraph 1 3
2 2
3 3
2 4
4 4
Closures of relations
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Is this relation reflexive?
• Answer: ?

• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• Answer: No. Why?
• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ⊇ R that is

reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: ?

• Let R={(1,1),(1,2),(2,1),(3,2)} on A ={1 2 3}.
• (2,2) and (3,3) is not in R.
• The question is what is the minimal relation S ⊇ R that is

reflexive?
• How to make R reflexive with minimum number of additions?
• Answer: Add (2,2) and (3,3)
• Then S= {(1,1),(1,2),(2,1),(3,2),(2,2),(3,3)}
• R⊆ S
• The minimal set S ⊇ R is called the reflexive closure of R
Reflexive closure
The set S is called the reflexive closure of R if it:
– contains R
– has reflexive property
– is contained in every reflexive relation Q that contains R (R
⊆ Q) , that is S ⊆ Q

Closures on relations
• Relations can have different properties:
• reflexive,
• symmetric
• transitive
• Because of that we can have:

• symmetric,
• reflexive and
• transitive
closure.
Closures
Definition: Let R be a relation on a set A. A relation S on A with
property P is called the closure of R with respect to P if S is a
subset of every relation Q (S ⊆ Q) with property P that contains
R (R ⊆ Q).

Closures
R (R ⊆ Q).
Example (symmetric closure):

• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S=?
Closures
R (R ⊆ Q).
Example (symmetric closure):

• Assume R={(1,2),(1,3), (2,2)} on A={1,2,3}.
• What is the symmetric closure S of R?
• S = {(1,2),(1,3), (2,2)}  {(2,1), (3,1)}
= {(1,2),(1,3), (2,2),(2,1), (3,1)}

Closures
R (R ⊆ Q).
• Example (transitive closure):

• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive?
Closures
R (R ⊆ Q).

• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S=?

Closures
R (R ⊆ Q).

• Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
• Is R transitive? No.
• How to make it transitive?
• S = {(1,2), (2,2), (2,3)}  {(1,3)}
= {(1,2), (2,2), (2,3),(1,3)}
• S is the transitive closure of R
Transitive closure
We can represent the relation on the graph. Finding a transitive
closure corresponds to finding all pairs of elements that are
connected with a directed path (or digraph).
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
Transitive closure S = {(1,2), (2,2), (2,3),(1,3)}.
R
1 3

Transitive closure
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
R
1 3
Transitive closure
Example:
Assume R={(1,2), (2,2), (2,3)} on A={1,2,3}.
R S
1 3 1 3
2 2

Transitive closure
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b)  Rn.
Proof (math induction):
a b
Path of length 1
a x b
Path of length 1 Path of length n
Path of length n+1
Transitive closure
Theorem: Let R be a relation on a set A. There is a path of length
n from a to b if and only if (a,b)  Rn.
Proof (math induction):
• P(1): There is a path of length 1 from a to b if and only if (a,b) 
R1, by the definition of R.
• Show P(n) → P(n+1): Assume there is a path of length n from
a to b if and only if (a,b)  Rn → there is a path of length n+1
from a to b if and only if (a,b)  Rn+1.
• There is a path of length n+1 from a to b if and only if there
exists an x  A, such that (a,x)  R (a path of length 1) and (x,b)
 Rn is a path of length n from x to b.
a x b
Path of length n
• (x,b)  Rn holds due to P(n). Therefore, there is a path of length

n + 1 from a to b. This also implies that (a,b) Rn+1.
Connectivity relation
Definition: Let R be a relation on a set A. The connectivity
relation R* consists of all pairs (a,b) such that there is a path (of
any length, i.e. 1 or 2 or 3 or ...) between a and b in R.
∞
R* = UR k
k =1
1 4
Example:
• A = {1,2,3,4} 2 3
• R = {(1,2),(1,4),(2,3),(3,4)}
Note: Rk consists of the pairs (a,b)* such that there is a path of

length k from a to b, it follows that R is the union of all the sets Rk
any length, ie. 1 or 2 or 3 or ...) between a and b in R.
∞
R* = UR k
k =1
1 4
Example:
• A = {1,2,3,4} 2 3
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = ?
•

∞
R* = UR k
k =1
1 4
Example:
• A = {1,2,3,4} 2 3
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = {(1,3),(2,4)}
• R3 = ?
•
∞
R* = UR k
k =1
1 4
Example:
• A = {1,2,3,4} 2 3
• R = {(1,2),(1,4),(2,3),(3,4)}
• R2 = {(1,3),(2,4)}
• R3 = {(1,4)}
• R4 = ?

∞
R* = UR k
k =1
Example: 1 4
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)} 2 3
• R2 = {(1,3),(2,4)}
• R3 = {(1,4)}
• R4 = 
• ...
• R* = ?
∞
R* = UR k
k =1
Example: 1 4
• A = {1,2,3,4}
• R = {(1,2),(1,4),(2,3),(3,4)} 2 3
• R2 = {(1,3),(2,4)}
• R3 = {(1,4)}
• R4 = 
• ...
• R* = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

Transitivity closure and connectivity relation
Theorem: The transitive closure of a relation R equals the
connectivity relation R*.
Based on the following Lemma.
Lemma 1: Let A be a set with n elements, and R a relation on A.

If there is a path from a to b, then there exists a path of length
< n in between (a,b). Consequently:
n
R* = UR k
k =1
Connectivity
If there is a path from a to b, then there exists a path of length <
n in between (a,b). Consequently:
n
R* = UR k
k =1
Proof (intuition):
• There are at most n different elements we can visit on a path if
the path does not have loops
x0=a x1 x2 xm=b
• Loops may increase the length but the same node is visited more
than once
x0=a x1 x2 xm=b
Connectivity
If there is a path from a to b, then there exists a path of length <
n in between (a,b). Consequently:
n
R* = UR k
k =1
Proof (intuition):
• There are at most n different elements we can visit on a path if
the path does not have loops
x0=a x1 x2 xm=b
• Loops may increase the length but the same node is visited more
than once
x0=a x1 x2 xm=b
Equivalence relation
Definition: A relation R on a set A is called an equivalence
relation if it is reflexive, symmetric and transitive.
Example: Let A = {0,1,2,3,4,5,6} and

• R= {(a,b)| a,b  A, a  b mod 3} (a is congruent to b modulo 3)
Congruencies:
• 0 mod 3 = ?

Example: Let A = {0,1,2,3,4,5,6} and

Congruencies:
• 0 mod 3 = 0 1 mod 3 = ?
Note: if and only if 3 divides a - b
Example: Let A = {0,1,2,3,4,5,6} and

Congruencies:
• 0 mod 3 = 0 1 mod 3 = 1 2 mod 3 = 2 3 mod 3 = ?

Example: Let A = {0,1,2,3,4,5,6} and

Congruencies:
• 0 mod 3 = 0 1 mod 3 = 1 2 mod 3 = 2 3 mod 3 = 0
• 4 mod 3 = ?
Example: Let A = {0,1,2,3,4,5,6} and

Congruencies:
• 0 mod 3 = 0 1 mod 3 = 1 2 mod 3 = 2 3 mod 3 = 0
• 4 mod 3 = 1 5 mod 3 = 2 6 mod 3 = 0
Relation R has the following pairs:
?

Example: Let A = {0,1,2,3,4,5,6} and

Congruencies:
• 0 mod 3 = 0 1 mod 3 = 1 2 mod 3 = 2 3 mod 3 = 0
• 4 mod 3 = 1 5 mod 3 = 2 6 mod 3 = 0
Relation R has the following pairs:
• (0,0) (0,3), (3,0), (0,6), (6,0)
• (3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
• (2,2), (2,5), (5,2), (5,5)
• Relation R on A={0,1,2,3,4,5,6} has the following pairs:
(0,0) (0,3), (3,0), (0,6), (6,0)
(3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
(2,2), (2,5), (5,2), (5,5)
• Is R reflexive?

(0,0) (0,3), (3,0), (0,6), (6,0)
(3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
(2,2), (2,5), (5,2), (5,5)
• Is R reflexive? Yes.
• Is R symmetric?
(0,0) (0,3), (3,0), (0,6), (6,0)
(3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
(2,2), (2,5), (5,2), (5,5)
• Is R symmetric? Yes.
• Is R transitive?
1 4
2 5
3 6

(0,0) (0,3), (3,0), (0,6), (6,0)
(3,3), (3,6) (6,3), (6,6) (1,1),(1,4), (4,1), (4,4)
(2,2), (2,5), (5,2), (5,5)
• Is R symmetric? Yes.
• Is R transitive. Yes.
1 4
Then 2 5
• R is an equivalence relation. 3 6
Equivalence class
Definition: Let R be an equivalence relation on a set A. The set { x
 A | a R x} is called the equivalence class of a, denoted by
[a]R or simply [a] when there is only one relation R. If b  [a]
then b is called a representative of this equivalence class.
Example:
• Assume R={(a,b) | a  b mod 3} for A={0,1,2,3,4,5,6}
• Pick an element a =0.
• [0]R = {0,3,6}
• Element 1: [1]R= ?

Equivalence class
 A  a R x} is called the equivalence class of a, denoted by
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
Equivalence class
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}

Equivalence class
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
Equivalence class
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6}= [0]R = [6]R

Equivalence class
 A | a R x} is called the equivalence class of a, denoted by
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6} = [0]R = [6]R
• Element 4: [4]R= {1,4} = [1]R
Equivalence class
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6}= [0]R = [6]R
• Element 4: [4]R= {1,4} = [1]R
• Element 5: [5]R= {2,5} = [2]R

Equivalence class
Example:
• [0]R = {0,3,6}
• Element 1: [1]R= {1,4}
• Element 2: [2]R= {2,5}
• Element 3: [3]R= {0,3,6} = [0]R = [6]R
• Element 4: [4]R= {1,4} = [1]R
• Element 5: [5]R= {2,5} = [2]R
Equivalence class
Example:
Three different equivalence classes all together:

• [0]R = [3]R =[6]R = {0,3,6}
• [1]R= [4]R= {1,4}
• [2]R= [5]R= {2,5}

Class 18

Uploaded by

Copyright:

Available Formats

Class 18

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Class 18

Uploaded by

Copyright:

Available Formats

Discrete Structures

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

Proof: biconditional (if and only if)

Suppose Rn ⊆ R, for n =1,2,3,... .

CS 441 Discrete mathematics for CS M. Hauskrecht

Proof: biconditional (if and only if)

Representing binary relations with graphs

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

• The question is what is the minimal relation S ⊇ R that is

CS 441 Discrete mathematics for CS M. Hauskrecht

• The question is what is the minimal relation S ⊇ R that is

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

• Because of that we can have:

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

Example (symmetric closure):

CS 441 Discrete mathematics for CS M. Hauskrecht

Example (symmetric closure):

CS 441 Discrete mathematics for CS M. Hauskrecht

• Example (transitive closure):

CS 441 Discrete mathematics for CS M. Hauskrecht

• Example (transitive closure):

CS 441 Discrete mathematics for CS M. Hauskrecht

• Example (transitive closure):

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

Path of length 1 Path of length n

Path of length n+1

CS 441 Discrete mathematics for CS M. Hauskrecht

• (x,b)  Rn holds due to P(n). Therefore, there is a path of length

Note: Rk consists of the pairs (a,b)* such that there is a path of

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

CS 441 Discrete mathematics for CS M. Hauskrecht

Based on the following Lemma.

Lemma 1: Let A be a set with n elements, and R a relation on A.

CS 441 Discrete mathematics for CS M. Hauskrecht

Example: Let A = {0,1,2,3,4,5,6} and

CS 441 Discrete mathematics for CS M. Hauskrecht

Example: Let A = {0,1,2,3,4,5,6} and

Note: if and only if 3 divides a - b

CS 441 Discrete mathematics for CS M. Hauskrecht

Example: Let A = {0,1,2,3,4,5,6} and

Note: if and only if 3 divides a - b

CS 441 Discrete mathematics for CS M. Hauskrecht

Example: Let A = {0,1,2,3,4,5,6} and

Note: if and only if 3 divides a - b

CS 441 Discrete mathematics for CS M. Hauskrecht

Example: Let A = {0,1,2,3,4,5,6} and