# equivalence and order

eq.rel'n, bin.rel'n, which?, pigeonhole?, birthdays, php-div, posets, min coloring

## equivalence relation

• equivalence relation on a set S: defn

• equivalent elements: in same block

• equivalence class: block

• example     S={a,b,…,g}, partition={ {a,g} {c,d,f} {b} {e} }

example
• let S =     define x ≡ y   iff   x = y (mod 4)

• 5 ≡ 9 ? (yes)     5 ≡ 99 ? (no)

• equivalence classes:

example
• can use any function   f:A→B   to define an eq.rel.

• define x ≡ y   iff   f(x) = f(y)

• example     f:{1,…,6}→{a,b,c,d} with f=(a,c,d,a,b,a)

• here, partition is { {1,4,6} {2} {3} {5} }

## binary relation

• binary relation on a set S: a relation r:S→S (so, subset of S×S) defn

• notation

• usually, R is the set of related order pairs

• xRy means (x,y) ∈ R

• example     S={a,..,f}, R={ (c,b) (d,a) (d,b) (e,e) }

• here, dRb ? (yes)     bRd ? (no)

every equivalence relation is a binary relation
• why ?

## which binary relations are equivalence relations ?

RST
• answer: every binary relation that is reflexive, symmetric, transitive

• reflexive: for all x ∈ S, xRx

• symmetric: for all x,y ∈ S, xRy iff yRx

• transitive: for all x,y ∈ S, (xRy ∧ yRz) ⇒ xRz

exercise

for each relation: is it reflexive ? symmetric ? transitive ? an equivalence relation ? (if no, add the fewest ordered pairs that makes it an eq.rel.)

• S = { a }, R = {   }

• S = { a }, R = { (a,a) }

• S = { a,b }, R = { (a,b) (b,a) }

• S = { a,b }, R = { (a,a) (a,b) (b,b) }

• S = { a,b }, R = { (a,a) (a,b) (b,a) (b,b) }

• S = { a,b,c }, R = { (a,a) (a,b) (b,a) (b,b) (c,c)}

• S = { a,b,c }, R = { (a,b) (b,c) (a,c) }

how many …
• binary relations on a k-set ?   (why ?)

• equivalence relations on a k-set ?   (why ?)

example: fractions
• define S = , where

• define r:S→S by     (a,b) R (c,d)   iff   a ⋅ d = b ⋅ c

• (1,3) ≡ (2,4) ?

• no

• (1,3) ≡ (3,9) ?

• yes

• (0,1) ≡ (0,2) ?

• yes

• (1,0) ≡ (2,0) ?

• no: neither (1,0) nor (2,0) are in S

• exercise: verify that r is an equivalence relation

• how does r represent equality of fractions ?

## pigeonhole principle

theorem

every k-partition of an n-set has some block with at least elements

if there are n pigeons in a total of k holes, some hole has at least pigeons

proof

let pj = number pigeons in hole j. let m = max pj.

notice

so

so some hole has   ≥ n/k   pigeons

so some hole has     pigeons (since each pj) .

## birthdays

birthday problem

how many people in a room so that,   always,   ≥ 2 have same birthday ?

• k = 366 (number of different birthdays)     n = number people

• want smallest n so that n/k > 1

how many people in a room so that,   with probability ≥ .5,   ≥ 2 have same birthday ?

## PHP division problem

notice
• let n = 3

• does n divide any number, or difference of numbers, in {4,5} ?

• does n divide any number, or difference of numbers, in {4,5,7}?

• does n divide any number, or difference of numbers, in {a,b,c}, where a,b,c are fixed integers?

question
• let n ∈

• what is smallest integer k, so that for all S = { t1, ... , tk } ⊆ ,

• n divides some tj or

• n divides some ty - tx ?

notice
• neither property holds if k = n-1 and S = { 1, 2, …, n-1 }

• so k ≥ n

notice
• suppose k = n

• first property holds if n divides some tj

• so assume n divides no tj

• so there are at most n-1 different values for tj (mod n)

• by PHP, exist tx, ty with same remainder (mod n)

• so second property does not hold

conclusion
• smallest integer above is k=n

• for any set S, with k ≥ n, at least one of two properties holds

party trick
• pick any sequence of five integers, eg. (9 -3 7 7 1)

• find consecutive subsequence with sum a multiple of 5: (9 -3 7 7 *)

• always possible ?

theorem

for any n ∈ , any sequence (a1 ... an), some consecutive subsequence has sum a multiple of n

proof
• for each x ∈ {1, … n}, define

• notice

• by above conclusion, for S = { t1, ..., tj }, n divides some tx or n divides some ty - tx

• so, n divides some consecutive subsequence of (a1 ... an)

## partially ordered sets (posets)

what is a poset?
• a binary relation that is

• reflexive

• antisymmetric

• transitive

• e.g. S = subsets of {a,b,c} and relation "is subset of"

• e.g. S = {1,2,…,12} and relation "divides"

what is a Hasse diagram?
• a map of an IKEA store ? no

• a simplified drawing of a poset:

## finding a min coloring of a poset

min coloring of a poset
• stable set: a subset S of points of a poset, such that no two points of S are related

• coloring (of points of poset): partition of points of a poset into stable sets (color classes)

• min coloring: coloring with fewest number of color classes

• finding a min coloring of a poset is easy (below)

• finding min coloring of arbitrary binary relation can be harder

min coloring of poset
```input: poset P
output: min coloring of P

j = 0
while not empty(P):
C[j] = set of all sources of P
remove C[j] from P
j += 1
```
correctness
• 1) algorithm terminates

• 2) the partition is a coloring of P

• 3) the partition is a min coloring of P

the algorithm terminates
• a binary relation with no cycles has a source

• every poset has no cycles

• so every iteration removes at least one point from P

the partition is a coloring
• it suffices to prove that the set C of all sources of a poset is a stable set

• suppose C is not stable

• then it contains points a,b such that aRb

• then b is not a source, and so should not be in C, contradiction

the coloring is minimum
• it suffices to show that P has a chain of the same size as the number of color classes

• to prove this, prove that every maximal chain contains a source

• so the set C[0] intersects every maximal  —  and so also maximum  —  chain

• finally, by induction, construct a chain of P that includes one point from every block (details omitted)