Lecture Notes on Equivalence Classes and Partial Orders (COMP11120)

Equivalence Classes and Partial Orders

Definition : Given a set S with an equivalence relation R and an elements of S , the
equivalence class with respect to R generated by s
, [S] , is the subset of S
consisting of all elements of S which are related to sby R, that is




[s] =
[5 eS (5 5) , [R]


Quotient Set Partitions
Given a set S with an
equivalence relation
~, the quotient set
of S with
respect
Whenever a set S is
partitioned ,
ie
. .
Split into disjoint subsets , we can define an



equivalence relation
~ such that for S, s'e S
,
~ consists of the equivalence classes of S with respect
to to . This is written as


Sv & ~ S if and only if s and s are in the same
partition
.




The equivalence classes are
exactly the partitions.


Example : The relation between students in the Department (Cab 2 , ,
6,0
,
th)
where two students are related if they have the same
year of birth
.
Example : I partitioned into positive , negative and zero values·


[O]


if We have tree (3) equivalence


in
[ 1]- -
1 O .
classes [1]
1



...
2
L
-
↑




-
P
7




.....
[a] = [b) =
[c] =
(a b, c)
,
-7
~

14
[d]
L

& d CD [d] =




[e] =
If) =
[0 f) ,




[2] [3) (5 [SO]
=


f a [1] I =... =




[0] =
503
& b El] =
[ 2] =
[ 3] = ... =
Ess O]


d C




Binary Relation Over Lists

Consider the binary relation
~ on the set hists of lists
Reflexivity Symmetry
over the set S as
follows Prove the relation is
reflexive using a
proof by induction Prove the relation is symmetric using a
proof by induction
Show that Show that all I , 1't hists if I-I I'v
base case 5) ~[] empty list is related to itself ! for all Le Listsg ,
(v) for ,
ther


Step For Iv)" and S, 5'ES have
basecase : [] [] [] []
base
we
case
- -
case :




1 ws' /
S: :
Step case : For -1 and SeS then ,
Step case : For (v)' and S, S' eS then


S :l ~S : / -S : l -S :

I'v) < ind hyp
So the relation reflexive
. .




is v

What does this relation does ? > Sil ~ Sil

It often good idea to try out examples with We
is a some
give a
proof by induction proving each direction
So the relation is symmetric
the definition to see what the relation does .
separately

First then Ion) Len 1
We have a conjecture that for all lists I I'
,
1 >
if (we' =




11 Then <
if lon) Lond then my
IwI' if
=

and only if len1 = zen 1




Proving for Conjecture I
Proving for Conjective II


base lents Con E Ion[] 0 Cent] < E3-E]
base
=
case : [J-[] <
=
0 = =
case :


Step case : For 1-11 and s ,
seS then Step case : For1 11 E Lists
,
and S, S'ES

S :l ng" / : Ion(s : )) = 1 + len 1


(cn(s: () = 1 + (en) = 1 + (en) ind .

hyp .




=
1 + len I' ind .

hyp .
= len (s' : ()
=
Ien (S' i :
> Silvs'