Algebra e geometria - relazioni e classi di equivalenza

Relazioni d'equivalenza

Def. Una relazione binaria su A si chiama relazione d'equivalenza se è riflessiva, simmetrica e transitiva.

• Riflessiva: ∀ x ∈ A, (x,x) ∈ R
• Simmetrica: ∀ x, y ∈ A, se x R y allora y R x
• Transitiva: ∀ x, y, z ∈ A, se x R y e y R z allora x R z

Esempi

Es. A = {1,2,3}

R = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)}

R è riflessiva, R è simmetrica, R è transitiva

Es. A = animali

R = {(x,y) | se x e y hanno lo stesso numero di gambe}

• Gatto R cane
• Gallina R struzzo
• Uomo R gallina

È una relazione d'equivalenza? Riflessiva Sì, Simmetrica Sì, Transitiva Sì.

Es. A = {persone in quest'aula}

R = {(x, y) | x è amico di y}

• Riflessiva: ognuno è amico di se stesso
• Simmetrica: se a è amico di b allora b è amico di a
• Transitiva: se a è amico di b e b è amico di c allora a è amico di c

R non è una relazione d'equivalenza

Es. ℕ n ∈ ℕ

R1 = { (n,n) }

R2 = {(n,m) | n ≦ m} ∈ ℕ

R1 è riflessiva, simmetrica e transitiva. La relazione d'uguaglianza = è una relazione d'equivalenza.

Classe d'equivalenza

Def. Se R è una relazione d'equivalenza su A, allora per ogni x ∈ A, [x]_R = {y ∈ A | x R y} è la classe d'equivalenza di x.

Nota: [X]_R ⊆ A

Es. A = {a,b,c} 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}

P(A) R = {(X,Y) | |X| = |Y|}

• {a} !R {b,c}
• {b} !R {b,c}

R è riflessiva, simmetrica e transitiva.

• [{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} }

Partizione di un insieme

Def. Una partizione di un insieme A è una famiglia di sottoinsiemi di A tale che:

• ∀ i ∈ I, B_i ⊆ A
• B_i ≠ ∅
• B_i ∩ B_j = ∅ se i ≠ j
• ∪_i∈IB_i = A

Es. A = {a,b,c,d} F = { {a,c}, {b}, {d} }
B₁ B₂ B₃

B_i ⊆ A

B_i ≠ ∅

B_i ∩ B_j = ∅ se i ≠ j