*equivalence relation on a set S*: defn*equivalent*elements: in same block*equivalence class*: blockexample 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 on a set S*: a relation r:S→S (so, subset of S×S) defnnotation

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 ?

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 ?

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 p_{j} = number pigeons in hole j.
let m = max p_{j}.

notice

so

so some hole has ≥ n/k pigeons

so some hole has pigeons (since each p_{j} ∈ ) .

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

answer: n = 367

birthday paradox

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

answer: n = 23

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 = { t

_{1}, ... , t_{k}} ⊆ ,n divides some t

_{j}orn divides some t

_{y}- t_{x}?

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 t

_{j}so assume n divides no t

_{j}so there are at most n-1 different values for t

_{j}(mod n)by PHP, exist t

_{x}, t_{y}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 (a_{1} ... a_{n}), some consecutive subsequence has sum a multiple of n

proof

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

notice

by above conclusion, for S = { t

_{1}, ..., t_{j}}, n divides some t_{x}or n divides some t_{y}- t_{x}so, n divides some consecutive subsequence of (a

_{1}... a_{n})

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:

links that follow by transitivity are omitted

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)