CMPUT272 Lecture Notes - Lecture 21: Partially Ordered Set, Covering Relation, Coimage
4 Dec 2014
School
Department
Course
Professor
Document Summary
Equivalence relations r on a: reflexive, symmetric, transitive. Partition of a set a is , a set of subsets of a such that: every element of is nonempty, the union of the elements of is a, and, forall x,y , x=y or x y= The elements of a partition are referred to as the "blocks" of a partition. For each x a, the equivilance class of x (wrt. equiv. rel. Theorem: if r is an equivilance relation on a, then = {[x]|x a} is a partition of a. Since r is reflexive, x [x] for all x a. Property (1) and (2) of the definition of partition are satisfied by . Let [x], [y] such that [x] [y] . Then, (v,x),(v,y) r, so (x,v) r since r is symmetric. Then, (x,v),(v,y) r, so (x,y) r since r is transitive. Suppose w [x], then (w,x) r and (w,y) r since (x,y) r, and r is transitive. w [y] .
