CMPUT272 Lecture Notes - Lecture 21: Partially Ordered Set, Covering Relation, Coimage

33 views3 pages

For unlimited access to Class Notes, a Class+ subscription is required.

November 20 2014
ETLC - 2-001
Equivalence relations R on A: reflexive, symmetric, transitive.
Partition of a set A is α, a set of subsets of A such that
1) every element of α is nonempty
2) the union of the elements of α is A, and
3) 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. R) is
[x] = {y A|(y,x) R}∈ ∈
Theorem: If R is an equivilance relation on A,
then α = {[x]|x A} is a partition of A.
Proof:
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] ≠ . Let v [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.∈ ∈
Also, (y,x) R since R is symmetric.
Suppose w [x], Then (w,x) R and (w,y) R since (x,y) R, and R is transitive. ∈ ∈
w [y]
Suppose w [y], Then (w,y) R and (w,x) R since (y,x) R, and R is transitive. ∈ ∈
w [x]
[x] = [y]
Thereom: If α is a partition of set A, then the relation R on A where
x,y A, (x,y) R x and y are in the same block of α
is an equivilance relation
Proof:
reflexive, symmetric, transitive.
The co-image of a function f: A->B
Set of subsets of A which map the values of A with regards to the co-domain,
B
The co-image of f:A->B is a partition of A.
The corresponding equivilance relation is:
x,y A, (x,y) R (x,y) in same block of coimage
R = {(x,y)|f(x) = f(y)}
Partial Order: reflexive, antisymmetric, transitive.
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class