Mathematical Techniques for Computer Science (COMP11120)
Class notes
Lecture Notes on Equivalence Classes and Partial Orders (COMP11120)
6 views 0 purchase
Course
Mathematical Techniques for Computer Science (COMP11120)
Institution
The University Of Manchester (UOM)
Master the concepts of equivalence classes and partial orders with these comprehensive lecture notes for COMP11120. These notes cover key topics such as the definition and properties of equivalence classes, the construction and visualization of partial orders, and their applications in various math...
Mathematical Techniques for Computer Science (COMP11120)
All documents for this subject (9)
Seller
Follow
jpxoi
Content preview
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'
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller jpxoi. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.43. You're not tied to anything after your purchase.
