CLASSE DI EQUIVALENZA: DEFINIZIONE, PROPRIETÀ ED ESEMPI

Classe di equivalenza sono il gruppo di elementi di un insieme basato su una specifica nozione di equivalenza definita da una relazione di equivalenza. Una relazione di equivalenza è una relazione che soddisfa tre proprietà: riflessività, simmetria e transitività. Le classi di equivalenza suddividono l'insieme S in sottoinsiemi disgiunti. Ogni sottoinsieme è costituito da elementi che sono correlati tra loro secondo la relazione di equivalenza data.

In questo articolo discuteremo il concetto di Classe di Equivalenza in modo sufficientemente dettagliato, compresa la sua definizione, esempio, proprietà ed esempi risolti.

Tabella dei contenuti

Cosa sono le classi di equivalenza?
Esempi di classi di equivalenza
Proprietà delle classi di equivalenza
Classi di equivalenza e partizione

Cosa sono le classi di equivalenza?

Una classe di equivalenza è il nome che diamo al sottoinsieme di S che comprende tutti gli elementi equivalenti tra loro. L'equivalente dipende da una relazione specificata, chiamata relazione di equivalenza. Se esiste una relazione di equivalenza tra due elementi qualsiasi, sono detti equivalenti.

Definizione della classe di equivalenza

Data una relazione di equivalenza su un insieme S, una classe di equivalenza rispetto a un elemento a in S è l'insieme di tutti gli elementi in S che sono legati ad a cioè,

[a] OR x è correlato ad a

Consideriamo ad esempio l'insieme degli interi ℤ e la relazione di equivalenza definita dalla congruenza modulo n. Due interi a e b sono considerati equivalenti (indicati come (a ≡ b mod(n)) se hanno lo stesso resto quando divisi per n. In questo caso, la classe di equivalenza di un intero a è l'insieme di tutti gli interi che hanno stesso resto di a diviso per n.

creazione di tabelle in lattice

Cos'è la relazione di equivalenza?

Qualsiasi relazione R si dice relazione di equivalenza se e solo se soddisfa le seguenti tre condizioni:

Riflessività: Per ogni elemento a, a è in relazione con se stesso.
Simmetria: Se a è correlato a b, allora b è correlato ad a.
Transitività: Se a è correlato a b e b è correlato a c, allora a è correlato a c.

Leggi di più su Relazione di equivalenza .

Alcuni esempi di relazione di equivalenza sono:

Uguaglianza su un insieme: Sia X un insieme qualsiasi e definiamo una relazione R su X tale che a R b se e solo se a = b per a, b ϵ X.

Riflessività: Per ogni a ϵ X, a = a (banalmente vero).
Simmetria: Se a = b, allora b = a (banalmente vero).
Transitività: Se a = b e b = c, allora a = c (banalmente vero).

Congruenza modulo n: Sia n un intero positivo, e definiamo una relazione R sugli interi ℤ tale che a R b se e solo se a – b è divisibile per n.

Riflessività: Per ogni a ϵ ℤ, a – a = 0 è divisibile per n.
Simmetria: Se a – b è divisibile per n, allora anche -(a – b) = b – a è divisibile per n.
Transitività: Se a – b è divisibile per n e b – c è divisibile per n, allora anche a – c è divisibile per n.

Esempi di classi di equivalenza

L'esempio ben noto di una relazione di equivalenza è la relazione uguale a (=). In altre parole, due elementi dell'insieme dato sono equivalenti tra loro se appartengono alla stessa classe di equivalenza. Le relazioni di equivalenza possono essere spiegate in termini dei seguenti esempi:

Relazione di equivalenza su interi

Relazione di equivalenza: Congruenza modulo 5 (a ≡ b [mod(5)] )

Classe di equivalenza 0: [0] = {. . ., -10, -5, 0, 5, 10, . . .}
Classe di equivalenza 1: [1] = {. . ., -9, -4, 1, 6, 11, . . .}
Classe di equivalenza 2: [2] = {. . ., -8, -3, 2, 7, 12, . . .}
Classe di equivalenza 3: [3] = {. . ., -7, -2, 3, 8, 13, . . .}
Classe di equivalenza 4: [4] = {. . ., -6, -1, 4, 9, 14, . . .}

Relazione di equivalenza sui numeri reali

Relazione di equivalenza: Differenza assoluta (a ~ b se |a – b| <1)

Classe di equivalenza 0: [0] = (-0,5, 0,5)
Classe di equivalenza 1: [1] = (0,5, 1,5)
Classe di equivalenza 2: [2] = (1,5, 2,5)
Classe di equivalenza 3: [3] = (2,5, 3,5)

Per saperne di più,

Numeri reali
Numeri interi
Numeri razionali

Proprietà delle classi di equivalenza

Le proprietà delle classi di equivalenza sono:

Ogni elemento appartiene esattamente ad una classe di equivalenza.
Le classi di equivalenza sono disgiunte, ovvero l'intersezione di due classi di equivalenza qualsiasi è un insieme nullo.
L'unione di tutte le classi di equivalenza è l'insieme originale.
Due elementi sono equivalenti se e solo se le loro classi di equivalenza sono uguali.

Per saperne di più,

Unione di insiemi
Intersezione di insiemi
Insiemi disgiunti

Classi di equivalenza e partizione

Gruppi di elementi in un insieme legati da una relazione di equivalenza, mentre una raccolta di queste classi di equivalenza, che copre l'intero insieme senza sovrapposizioni, è chiamata partizione.

Differenza tra classi di equivalenza e partizione

La differenza fondamentale tra classi di equivalenza e partizione è riportata nella tabella seguente:

Caratteristica	Classi di equivalenza	Partizioni
Definizione	Insiemi di elementi considerati equivalenti in una relazione.	Una raccolta di sottoinsiemi non vuoti, disgiunti a coppie, tale che la loro unione costituisce l'intero insieme.
Notazione	Se UN è una classe di equivalenza, è spesso indicata come [ UN ] o [a] R , dove UN è un elemento rappresentativo e R è la relazione di equivalenza.	Una partizione di un insieme X è indicato come { B ₁, B ₂,..., B _N }, dove B _io sono i sottoinsiemi disgiunti nella partizione.
Relazione	Le classi di equivalenza formano una partizione dell'insieme sottostante.	Una partizione può nascere o meno da una relazione di equivalenza.
Cardinalità	Le classi di equivalenza possono avere cardinalità diverse.	Tutti i sottoinsiemi nella partizione hanno la stessa cardinalità.
Esempio	Consideriamo l'insieme degli interi e la relazione di equivalenza aventi lo stesso resto quando divisi per 5. Le classi di equivalenza sono {…,−5,0,5,…}, {…,−5,0,5,…}, {…,−4,1,6,…} e {…,−4,1 ,6,…}, ecc.	Consideriamo l'insieme degli interi partizionato in numeri pari e dispari: {…,−4,−2,0,2,4,…} e {…,−3,−1,1,3,5,…}.
Intersezione di classi	Le classi di equivalenza sono disgiunte o identiche.	Le partizioni sono costituite da sottoinsiemi disgiunti.

Esempi risolti sulla classe di equivalenza

Esempio 1: Dimostrare che la relazione R è di tipo equivalenza nell'insieme P= { 3, 4, 5,6 } dato dalla relazione R = (p, q):.

Soluzione:

Dato: R = (p, q):. Dove p, q appartiene a P.

Proprietà riflessiva

Dalla relazione fornita |p – p| = | 0 |=0.

E 0 è sempre pari.

Pertanto |p – p| è anche.

Quindi, (p, p) si riferisce a R

Quindi R è riflessivo.

Proprietà simmetrica

Dalla relazione data |p – q| = |q – p|.

Sappiamo che |p – q| = |-(q – p)|= |q – p|

Quindi |p – q| è anche.

Successivamente |q – p| è anche pari.

Pertanto, se (p, q) ∈ R, allora anche (q, p) appartiene a R.

Pertanto R è simmetrico.

Proprietà transitiva

Se |p – q| è pari, allora (p-q) è pari.

Allo stesso modo, se |q-r| è pari, allora anche (q-r) è pari.

La somma dei numeri pari è troppo pari.

Quindi possiamo indirizzarlo come p – q+ q-r è pari.

Successivamente, p – r è ulteriormente pari.

Di conseguenza,

|p – q| e |q-r| è pari, allora |p – r| è anche.

Di conseguenza, se (p, q) ∈ R e (q, r) ∈ R, allora (p, r) si riferisce anche a R.

Quindi R è transitivo.

Esempio 2: Considera A = {2, 3, 4, 5} e R = {(5, 5), (5, 3), (2, 2), (2, 4), (3, 5), ( 3, 3), (4, 2), (4, 4)}.

hashmap in Java

Soluzione:

Dato: A = {2, 3, 4, 5} e

Relazione R = {(5, 5), (5, 3), (2, 2), (2, 4), (3, 5), (3, 3), (4, 2), (4, 4 )}.

Affinché R sia una relazione di equivalenza, R deve soddisfare tre proprietà, ovvero riflessiva, simmetrica e transitiva.

Riflessivo : La relazione R è riflessiva perché (5, 5), (2, 2), (3, 3) e (4, 4) ∈ R.

Simmetrico : La relazione R è simmetrica poiché ogni volta che (a, b) ∈ R, (b, a) si riferisce anche a R cioè (3, 5) ∈ R ⟹ (5, 3) ∈ R.

Transitivo : La relazione R è transitiva poiché ogni volta che (a, b) e (b, c) si riferiscono a R, (a, c) si riferisce anche a R cioè (3, 5) ∈ R e (5, 3) ∈ R ⟹ ( 3, 3) ∈ R.

Di conseguenza, R è riflessiva, simmetrica e transitiva.

Quindi R è una relazione di equivalenza.

Problemi pratici sulla classe di equivalenza

Problema 1: aRb se a+b è pari. Determina se si tratta di una relazione di equivalenza e le sue proprietà.

Problema 2: xSy se xey hanno lo stesso mese di nascita. Analizza se si tratta di una relazione di equivalenza.

Problema 3: Considera A = {2, 3, 4, 5} e R = {(5, 5), (5, 3), (2, 2), (2, 4), (3, 5), (3, 3 ), (4, 2), (4, 4)}. Confermare che R è una relazione di tipo equivalenza.

Problema 4: Dimostrare che la relazione R è di tipo equivalenza nell'insieme P= { 3, 4, 5,6 } dato dalla relazione R = è pari .

Classe di equivalenza: domande frequenti

1. Cos'è la Classe di Equivalenza?

Una classe di equivalenza è un sottoinsieme all'interno di un insieme, formato raggruppando tutti gli elementi equivalenti tra loro secondo una determinata relazione di equivalenza. Rappresenta tutti i membri considerati uguali da tale relazione.

2. Qual è il simbolo della classe di equivalenza?

Il simbolo di una classe di equivalenza è tipicamente scritto come [a], dove a è un elemento rappresentativo della classe. Questa notazione denota l'insieme di tutti gli elementi equivalenti ad a sotto una specifica relazione di equivalenza.

3. Come si trova la classe di equivalenza di un insieme?

Per trovare la classe di equivalenza di un insieme, attenersi alla seguente procedura:
precedenza degli operatori Java

Passo 1: Definire una relazione di equivalenza.

Passo 2: Seleziona un elemento dal set.

Passaggio 3: Identificare gli elementi equivalenti agli elementi selezionati.

Passaggio 4: Forma la Classe di Equivalenza contenente tutti gli elementi equivalenti all'elemento selezionato.

4. Qual è la differenza tra Classe di Equivalenza e Partizione?

Le classi di equivalenza sono sottoinsiemi formati da una relazione di equivalenza, mentre le partizioni sono sottoinsiemi non sovrapposti che coprono l'intero insieme. Ogni classe di equivalenza è un sottoinsieme di una partizione, ma non tutte le partizioni nascono da una relazione di equivalenza.

5. Cos'è una relazione di equivalenza?

Una relazione riflessiva, simmetrica e transitiva, che divide un insieme in sottoinsiemi disgiunti.