slides

Report
CSE 20
DISCRETE MATH
Prof. Shachar Lovett
http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Clicker
frequency:
CA
Todays topics
• Equivalence relations
• Section 6.2 in Jenkyns, Stephenson
(Binary) Relations
• Model a relation between two families of objects
• Formally:
• U universe set
• Relation:  ⊆  × 
• For ,  ∈  we write:  as a shorthand for "(, ) ∈ “
• Example 1: x<y, formally…
• U=N
• “ < ” represents the relation  =
,  : ,  ∈ ,  < 
• Example 1: x<y, formally…
• U = P(N)
• “ ⊂ ” represents the relation  = { ,  : ,  ∈ (),  ⊂ }
Three important properties of relations
• There are several important properties of relations
• We will focus on the most important three
• A relation R is symmetric if ∀, ,  ⇔ 
• A relation R is reflexive if ∀, 
• A relation R is transitive if ∀, , ,
 ∧  → 
• An equivalence relation is a relation which satisfies all of
them
Examples of equivalence relations
• U=Z (integers)
• xRy = “x=y”
Prove that R is an equivalence relation
Examples of equivalence relations
• U=Z (integers)
• xRy = “|x|=|y|” (absolute value of x = absolute value of y)
Prove that R is an equivalence relation
Examples of equivalence relations
• U=“all students in this class”
• xRy = “x and y have the same birthday”
Prove that R is an equivalence relation
Examples of equivalence relations
• U=Z (integers)
• xRy = “x+y is even”
Prove that R is an equivalence relation
What is so special about equivalence
relations?
• Equivalence relations describe a partition of the universe
U to equivalence classes
Equivalence classes
• Let 1 , 2 , … ,  be a partition of U
• For  ∈ , define   to be the (unique!) part that x
belongs to
• Equivalently, define :  → {1, … , } and equivalence
classes are defined by all elements with same image
 = { ∈ :   = }
• Theorem: let  ⊆  ×  be an equivalence relation. Then
there is a mapping :  →  such that
∀,  ∈ ,  ⇔   = ()
Equivalence classes: example 1
• U=Z (integers)
• xRy = “x=y”
Class(x)=
A. x
B. y
C. U
D. “x=y”
E. Other
Equivalence classes: example 2
• U=Z (integers)
• xRy = “|x|=|y|”
Class(x)=
A. x
B. |x|
C. “x=y”
D. “|x|=|y|”
E. Other
Equivalence classes: example 3
• U=“all students in this class”
• xRy = “x and y have the same birthday”
Class(x)=
A. x
B. Birthday of x
C. “x=y”
D. “|x|=|y|”
E. Other
Equivalence classes: example 4
• U=Z (integers)
• xRy = “x+y is even”
Class(x)=???
Figure this out in your groups
Equivalence classes: proof
• Theorem: let  ⊆  ×  be an equivalence relation. Then
there is a mapping :  →  such that
∀,  ∈ ,  ⇔   = ()
Proof:
For each  ∈ , define: Class  = { ∈ : }
(and so  =   :  ∈  ⊂ () )
We need to show that
∀,  ∈ ,  ⇔   = ()
Equivalence classes: proof (contd)
For each  ∈ , define: Class  = { ∈ : }
(⇐) Assume Class  = (). We will show xRy.
By definition: we need to show  ∈ ().
But  ∈   since R is reflexive (and so )) and
since we assume Class  = () then also  ∈
().
Equivalence classes: proof (contd)
For each  ∈ , define: Class  = { ∈ : }
(⇒) Assume xRy. We need to show Class  = ().
We will first show   ⊆ (). Let  ∈   .
Then y. Since R is transitive,  ∧  imply that x.
So  ∈ ().
Since R is symmetric, we also have yRx. The same
argument as above (with the roles of x,y reversed) then
implies that   ⊆ (). So:   = ().
Next class
• Modular arithmetic
• Section 6.2 in Jenkyns, Stephenson
• Review session for midterm 2

similar documents