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

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.