Algebra e geometria - relazioni e classi di equivalenza

∈A|

NOTA [X]r A[X]r∈P A)

⊆ (

Es. A = {a,b,x} R = {(a,a),(b,b,),(c,c),(a,b),(b,a)}

R è relazione d'equivalenza (riflessiva, simmetrica e transitiva)

[A]r = {a,b} [B]r = {b,a} [C]r = {c}

Es. A = {a,b,c}

|P(A)| = 8 {a} R {b} {a,b} R {b,c}

x P(A)

R = {(X,Y) | |X| = |Y|} {a} !R {b,c} {b} !R {b,c}

⊆P(A) R è riflessiva x∈P A) |X|=|X|

∀ (

R è riflessiva x , y∈ P A) |X|=|Y| allora |Y|=|X|

∀ (

R è transitivo |X| = |Y| e |Y| = |Z| allora |X| = |Z|

[{a}]r = { {a}, {b}, {c} } = [{b}]r = [{c}]r

[{a,b}]r = { {a,b}, {b,c}, {a,c} } = [ {b,c} ]r = [ {a,c} ]r

[ ]r = { } [{a,b,c}]r = { {a,b,c} }

∅ ∅

Def. Una partizione di un insieme A è una famiglia di Sottoinsiemi di A

i∈I Bi⊆ A

F = {Bi} Bi≠∅

Bi∩Bj ≠∅

Bi= A

∪i∈I

Bi è un blocco della partizione

blocchi disgiunti

– unione dei blocchi è A

–

Es. A = {a,b,c,d}

F = { {a,c}, {b}, {d} }

B1 B2 B3

Bi⊆ A

Bi≠∅

Bi∩Bj B1∩B3=∅ B2∩ B3=∅

≠∅ B1∪B2∪B3={a,b,c,d}=A

U Bi = A Es.

a b {a,b}∩{c,d}=∅ {a,b}∪{c,d}=A

F1 = {{a,b}, {c,d}}

C d F2 = {{a,b},{b,c},{d}} non è una partizione

{a,b}∩{b,c}={b}≠∅

F3 = {{a,b}, {c}} non è una partizione {a,b}∪{c}≠ A

Def. Se R è una relazione d'equivalenza su A

insieme QUOZIENTE x }

A/R = { [x]r | è l'insieme delle classi d'equivalenza di elementi di A

∈A

Proprietà A/R è una partizione di A

Es. A= {a,b,c,d}

R1 = {(a,a),(b,b),(c,c),(d,d),(a,b),(b,a)} R è una relazione d'equivalenza

[a]r = {a,b} [b]r = {b,a] [c]r = {c} [d]r = {d} (Classi di equivalenza)

x }={[a]r, [b]r, [c]r, [d]r} = { {a,b}, {c}, {d} }

A/R = {[x]r | ∈A

A/R è una partizione di A

Es.

A = persone in questa aula

R = {(x,y) | x e y stesso colore degli occhi} Relazioni d'equivalenza

[x]r = { y tali che x e y hanno lo stesso colore degli occhi }

A/R = {{occhi marroni},{occhi verdi}, {occhi azzurri}}

A/R è una partizione di A

Es.

x R1 y se x e y avranno lo stesso voto a questo esame

[x]r = {y ha lo stesso voto di x}

A/R = {{studenti con 18}, {studenti 19} ….. {30}, {30 e lode}}

n∈ℕ}

Es. R1 = {(n,n) | [n]r = {n}

n∈ℕ}={{n} | n∈ℕ}

/ R1 = {[n]r1 | è una partizione di

ℕ ℕ

in ogni blocco c'è solo un elemento

Es. A= persone in questa aula

R = {(x,y) | x e y sono fidanzati} R⊆ A x A)

R relazioni d'equivalenza su A (

A| xRy }

[x]r = { y classe d'equivalenza di x

∈ x }

A/R = {[x]r | insieme quoziente è una partizione di A

∈A

P insieme delle parole di 4 lettere scelte tra a,b,c

bacc aaba abbc cabb

R⊆ P x P u R v se e solo se u e v hanno lo stesso numero di lettere a

R = { (u,v) | u e v hanno lo stesso numero di a }

aaba R acaa #(a,u)

abca !R aaca

#(a,u) = # (a,v) //il cancelletto serve per abbreviare, gli elementi hanno lo stesso numero di a

u∈ P

R è riflessiva #(a,u) = #(a,u)

∀ u , v P

R è simmetrica #(a,u) = #(a,v) allora #(a,v) = #(a,u)

∀ ∈

u , v , w∈P

R è transitiva se #(a,u) = #(a,v) e #(a,v) = #(a,w) allora #(a,u) = #(a,w)

∀

[abbc]r = { abbc, abbb, babc, accc, cacb, bbac, …. } tutte le parole con una lettera a (insieme di

equivalenza, insieme delle classi di equivalenza)

[aabc]r = { parole con 2 lettere a } = {aabc, baac, caab, caba, … }

[aaab]r = { parole con 3 lettere a }

Quanti elementi ha P/R ?

[aaaa]r = {aaaa} |P/R| = 5

[bcbc]r ci sono 5 classi d'equivalenza diverse tra loro

Es. ℕ

R = {(x,y) | x+y } 2 R 4 1 R 5 2 !R 5

∈2ℕ

R relazione d'equivalenza 2ℕ 2x

riflessiva x R x x+x VERO

∈ ∈2 ℕ

• 2ℕ => y x∈2 => y R x

simmetrica x R y allora x + y VERO

∈ + ℕ

• 2ℕ e y z 2

transitiva x+y ∈ + ∈ ℕ

•

2R4 4R6 => 2R6

1R5 5R3 => 1R3

2

Nota che se x+y allora o x e y sono pari

∈ ℕ oppure x e y sono dispari

Se x R y e y R z allora o x,y,z sono pari oppure x,y,z sono dispari

=> x R z. Quindi R è una relazione d'equivalenza

[1]r = {1,3,5,7,9,....} = 2 + 1 (insieme dei numeri dispari)

ℕ

[2]r = {0,2,4,6,8,...} = 2 numeri pari

ℕ

[5]r = [1]r = [3]r = …

[4]r = [2]r = …

N/R = {[1]r, [2]r}

è una partizione di ℕ

{2 +1, 2 }

ℕ ℕ , {a}, {b}, {c}, {c}, {a,b}, {b,c}, {a,c}, {a,b,c}}

Es. A = {a,b,c} P(A) = { ∅

R su P(A) R = { (x,y) | |x| = |y| } è una relazione d'equivalenza

r=∅ [{a}] ={a},{b},{c}} [{a,b}] = {{a,b},{b,c},{a,c}}

[∅]

[{a,b,c}] = {{a,b,c}} P(A)/R = {[ ],[{a}],[{(a,b)}], [{a,b,c}]}

∅

è una partizione di P(A)

Es. A = {a,b,c,d}

F = {{a,b},{c},{d}} è una partizione di A