Relazione di equivalenza

Una relazione di equivalenza è un concetto matematico che esprime in termini formali quello intuitivo di "oggetti che condividono una certa proprietà".

Definizione

Dati due insiemi ${\displaystyle A}$ e ${\displaystyle B}$, il loro prodotto cartesiano è l'insieme delle coppie ordinate definito nel modo seguente:^[1]

${\displaystyle A\times B:=\{(a,b):a\in A\land b\in B\}}$

Si definisce relazione binaria ${\displaystyle R}$ su un insieme ${\displaystyle A}$ un sottoinsieme di ${\displaystyle A\times A}$. Due elementi ${\displaystyle x}$ e ${\displaystyle y}$ sono messi in relazione da ${\displaystyle R}$ se:

${\displaystyle (x,y)\in R}$

ed in tal caso si scrive ${\displaystyle xRy}$.

Una relazione di equivalenza ${\displaystyle \sim }$ (che si legge "equivalente a", procedendo da sinistra verso destra) è una relazione binaria tra elementi di un insieme ${\displaystyle A}$ riflessiva, simmetrica e transitiva.^[2] Esplicitamente, tale relazione soddisfa le seguenti proprietà:

${\displaystyle x\sim x\quad \forall x\in A}$

${\displaystyle x\sim y}$ implica ${\displaystyle y\sim x\quad \forall x,y\in A}$

${\displaystyle x\sim y}$ e ${\displaystyle y\sim z}$ implicano ${\displaystyle x\sim z\quad \forall x,y,z\in A}$

Due elementi tra i quali sussiste una relazione di equivalenza si dicono equivalenti per la relazione ${\displaystyle \sim }$: la proprietà di simmetria consente infatti di prescindere dall'ordine con cui quegli elementi compaiono all'interno della relazione.

Un sottoinsieme di ${\displaystyle A}$ che contiene tutti e soli gli elementi equivalenti a un qualche elemento ${\displaystyle x}$ di ${\displaystyle A}$ prende il nome di classe di equivalenza di ${\displaystyle x}$ per la relazione ${\displaystyle \sim }$. Spesso si indica una classe di equivalenza con ${\displaystyle [x]_{\sim }}$ o con ${\displaystyle \{x\}_{\sim }}$. In una classe di equivalenza tutti gli elementi in essa contenuti sono tra loro equivalenti.

L'insieme delle classi di equivalenza su ${\displaystyle A}$ si chiama insieme quoziente di ${\displaystyle A}$ per la relazione ${\displaystyle \sim }$, e viene talvolta indicato con l'espressione ${\displaystyle A/\sim }$. Si dimostra che esso rappresenta una partizione di ${\displaystyle A}$.

L'importanza della riflessività

A prima vista può sembrare che la riflessività sia implicata dalle altre due proprietà e che sia quindi ridondante. Infatti dato ${\displaystyle a\in A}$, se ${\displaystyle aRb}$ allora per simmetria ${\displaystyle bRa}$ e quindi per transitività ${\displaystyle aRa}$. Questo ragionamento è fallace. Infatti stiamo assumendo che ${\displaystyle \forall a\in A\,\,\exists b\in A}$ tale che ${\displaystyle aRb}$. Questo non è garantito a priori. Infatti ad esempio la relazione su ${\displaystyle \mathbb {R} }$ definita da ${\displaystyle R=\{(x,y)\in \mathbb {R} ^{2}\smallsetminus \{(0,0)\}:x=y\}}$ è simmetrica e transitiva ma non è riflessiva. Infatti ${\displaystyle (0,0)\notin R}$ e quindi non è in relazione con se stesso.

Esempi

• Se ${\displaystyle X}$ è l'insieme di tutte le automobili e ${\displaystyle \sim }$ è la relazione di equivalenza "ha lo stesso colore di", allora una classe di equivalenza sarà quella delle automobili verdi. ${\displaystyle X/\sim }$ potrebbe essere identificata intuitivamente con l'insieme dei colori delle automobili
• Si consideri la relazione di equivalenza "modulo 2" nell'insieme degli interi: ${\displaystyle x\sim y}$ se e solo se ${\displaystyle x-y}$ è un pari. Questa relazione dà origine ad esattamente due classi di equivalenza: [0] contiene tutti i numeri pari, mentre [1] contiene tutti i numeri dispari
• Sia ${\displaystyle X=\{1,2,3,4,5,6,7,8,9\}}$. Si consideri la relazione d'equivalenza così definita: ${\displaystyle x\sim y}$ se e solo se ${\displaystyle x-y}$ è divisibile per 3. Ciò genera tre classi di equivalenza: ${\displaystyle [1]=\{1,4,7\}}$, ${\displaystyle [2]=\{2,5,8\}}$, ${\displaystyle [3]=\{3,6,9\}}$. L'insieme quoziente di ${\displaystyle X}$ rispetto alla relazione d'equivalenza ${\displaystyle \sim }$, denotato ${\displaystyle X/{\sim }}$, è semplicemente l'insieme di tutte le classi d'equivalenza, ovvero: ${\displaystyle X/{\sim }\,=\{[1],[2],[3]\}}$. Scritto in modo ancora più esplicito, ${\displaystyle X/{\sim }\,=\{\{1,4,7\},\{2,5,8\},\{3,6,9\}\}}$
• I numeri razionali possono essere costruiti come l'insieme delle classi di equivalenza delle coppie di interi ${\displaystyle (a,b)}$, con ${\displaystyle b}$ diverso da zero, dove la relazione di equivalenza è definita come:

  ${\displaystyle (a,b)\sim (c,d)}$ se e solo se ${\displaystyle ad=bc}$.

la classe di equivalenza a cui appartiene ${\displaystyle (a,b)}$ può essere identificata con la frazione ${\displaystyle a/b}$.

• Qualunque funzione ${\displaystyle f:X\to Y}$ definisce una relazione di equivalenza su ${\displaystyle X}$ secondo cui ${\displaystyle a\sim b}$ (con ${\displaystyle a,b\in X}$) se e solo se ${\displaystyle f(a)=f(b)}$. La classe di equivalenza di ${\displaystyle a}$ è quindi la controimmagine di ${\displaystyle f(a)}$.
• Dato un gruppo ${\displaystyle G}$ ed un sottogruppo ${\displaystyle H}$, è possibile definire una relazione di equivalenza su ${\displaystyle G}$ come ${\displaystyle x\sim y}$ se e solo se ${\displaystyle xy^{-1}\in H}$. Le classi di equivalenza prendono il nome di laterali destri di ${\displaystyle H}$ in ${\displaystyle G}$. Se ${\displaystyle H}$ è un sottogruppo normale, allora l'insieme di tutti i laterali è esso stesso un gruppo, detto gruppo quoziente
  • Ogni gruppo può essere partizionato in classi di equivalenza dette classi di coniugazione
• La classe di omotopia di una funzione continua ${\displaystyle f}$ è la classe di equivalenza di tutte le funzioni omotopiche a ${\displaystyle f}$
• Nell'elaborazione dei linguaggi naturali, una classe di equivalenza è un insieme di tutti i riferimenti a una singola persona, luogo, cosa, o evento, sia reale che concettuale. Ad esempio, nella frase "gli azionisti di GE voteranno un successore per l'uscente CEO della società Jack Welch", GE e la società sono sinonimi, e quindi costituiscono una classe di equivalenza. Ci sono classi di equivalenza separate per azionisti di GE e Jack Welch

Relazioni di equivalenza e partizioni

Ogni elemento ${\displaystyle a\in A}$ appartiene necessariamente ad almeno una classe di equivalenza (la ${\displaystyle [a]}$, a causa della riflessività). Inoltre non può appartenere a nessun altro insieme, perché tutti gli elementi di una certa classe di equivalenza ${\displaystyle X}$ contenente ${\displaystyle a}$ sarebbero per definizione equivalenti ad un elemento ${\displaystyle b\in X}$: si avrebbe dunque ${\displaystyle a\sim b}$. Ma sempre per definizione:

1. per ogni elemento ${\displaystyle x\in X}$, ${\displaystyle x\sim b\rightarrow x\sim a}$ (per la simmetria e transitività)
2. per ogni elemento ${\displaystyle y\in [a]}$, ${\displaystyle y\sim a\rightarrow y\sim b}$ (per la transitività)

cioè, ogni elemento di ${\displaystyle X}$ apparterrebbe ad ${\displaystyle [a]}$ e viceversa ogni elemento di ${\displaystyle [a]}$ apparterrebbe ad ${\displaystyle X}$: dunque ${\displaystyle X=[a]}$.

In definitiva, ogni elemento di ${\displaystyle A}$ appartiene sicuramente ad una classe di equivalenza (onde per cui l'insieme quoziente definisce come si dice una copertura di ${\displaystyle A}$), e ad una sola di esse, che dunque risulteranno a due a due disgiunte: l'insieme quoziente su ${\displaystyle A}$ definisce quindi una partizione di ${\displaystyle A}$.

Viceversa, si mostra che ad ogni partizione dell'insieme ${\displaystyle A}$ si associa una e una sola relazione di equivalenza, quella definita in maniera tale che due elementi stiano in tale relazione se e solo se appartengono allo stesso insieme della partizione. Detto in altri termini, data una partizione ${\displaystyle S}$, esiste ed è unica la relazione di equivalenza ~ tale che l'insieme quoziente ${\displaystyle A/\sim }$ sia uguale ad ${\displaystyle S}$.^[3][4]: essa è definita in simboli da

${\displaystyle a\sim b\Leftrightarrow \exists P\in S\,{\mbox{ t.c. }}\,a,b\in P}$.

Si è così individuata una sorta di corrispondenza uno-a-uno tra la classe delle relazioni di equivalenza e quella delle possibili partizioni in insiemi. Si dice che tra le relazioni di equivalenza e le partizioni di un insieme esiste un criptomorfismo; in altre parole le due classi, quella delle classi di equivalenza e quella delle partizioni, stanno in una speciale relazione nella quale ogni elemento della prima classe corrisponde ad uno e un solo elemento della seconda. Si può dunque considerare la possibilità di trattare lo stesso problema dal punto di vista delle relazioni di equivalenza o da quello delle partizioni, come è naturale per tutti i criptomorfismi.

Dimostrazione

È abbastanza ovvio che la relazione è sia riflessiva che simmetrica; per quanto riguarda la transitività, basta tener presente che gli elementi della partizione sono a due a due disgiunti. Pertanto è una relazione di equivalenza; evidentemente essa induce la partizione S.

Si consideri ora una relazione di equivalenza ρ che induce la partizione S: se per assurdo fosse diversa da ~, esisterebbe almeno una coppia di elementi in relazione nel senso della ~, ossia appartenenti allo stesso insieme della partizione, ma non nel senso della ρ, dunque non equivalenti e quindi in definitiva appartenenti a due insiemi di S differenti.

Invarianti di classe

Ogni teoria matematica comprende determinate proprietà e relazioni. Data una certa relazione di equivalenza, proprietà e relazioni che non distinguono tra di loro gli oggetti appartenenti ad una medesima classe di equivalenza prendono il nome di invarianti di classe. Il perché di tale denominazione è evidente: si tratta infatti di strutture invarianti rispetto alla relazione di equivalenza o partizione adottata. In simboli, una proprietà ${\displaystyle P}$ è detta un invariante di classe quando ${\displaystyle a\sim b}$ implica necessariamente che ${\displaystyle P(a)}$ e ${\displaystyle P(b)}$ abbiano lo stesso valore di verità; una definizione analoga vale per le relazioni (e quindi ad esempio anche per le funzioni; in particolare, se una funzione ${\displaystyle f}$ è invariante rispetto alla relazione considerata, allora risulterà senz'altro ben definita sull'insieme quoziente la funzione ${\displaystyle g(P)=f(x)}$ dove ${\displaystyle x}$ è un qualsiasi rappresentante della classe ${\displaystyle P}$, in quanto ${\displaystyle f}$ assume lo stesso valore su ogni rappresentante di quella classe. In questo caso, si dice anche che ${\displaystyle f}$ passa al quoziente^[5]).

In un apparato formale costituito unicamente da invarianti di classe, oggetti equivalenti possono a tutti gli effetti essere identificati tra di loro e in un certo senso confusi con la relativa classe di equivalenza. Questo permette di trattare elementi equivalenti come fosse uno solo, prescindendo cioè da dettagli che non interessano, dato che da un punto di vista logico essi risultano indistinguibili.

Nel caso in cui un insieme ha qualche struttura addizionale preservata dalla relazione (ad esempio algebrica: si veda a proposito la voce "relazione di congruenza"), il relativo quoziente diventa un oggetto dello stesso tipo in modo naturale; la funzione che manda ${\displaystyle a}$ in ${\displaystyle [a]}$ è allora un epimorfismo.

L'espressione "a meno di" inserita in un contesto matematico presuppone l'esistenza di un'equivalenza, e sta a indicare che i membri di una stessa classe vengono considerati una sola entità nella trattazione, a meno appunto di differenze che in quella sede non interessano; solo quelle tra classi di oggetti (che vengono trattati come singoli elementi) sono rilevanti. Ad esempio, in geometria proiettiva dire che un punto determina univocamente un insieme di coordinate omogenee "a meno di proporzionalità", vuol dire che tale punto individua un'intera classe di coordinate che differiscono solo per un coefficiente proporzionale, e che ogni membro di quella classe è ugualmente valido per descrivere il punto. Soprattutto in aritmetica modulare, ma anche in altri settori, è spesso usato il termine "modulo" come sinonimo del precedente: un esempio potrebbe essere la frase «3 modulo 2», che sta a indicare tutti i naturali che differiscono da 3 per un multiplo di 2 (essenzialmente tutti i numeri dispari), oppure «la classe dei cammini a valori in ${\displaystyle X}$ modulo l'omotopia».

Note

Bibliografia

• (EN) Michael Reed, Barry Simon, Methods of Modern Mathematical Physics, Vol. 1: Functional Analysis, 2ª ed., San Diego, California, Academic press inc., 1980, ISBN 0-12-585050-6.

Voci correlate

• Anello quoziente
• Gruppo quoziente
• Prodotto cartesiano
• Relazione binaria
• Relazione riflessiva
• Relazione simmetrica
• Relazione transitiva
• Spazio vettoriale quoziente
• Topologia quoziente

Altri progetti

• Wikimedia Commons contiene immagini o altri file sulle relazioni di equivalenza

Collegamenti esterni

• equivalenza, relazione di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) equivalence relation / equivalence, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Relazione di equivalenza, su MathWorld, Wolfram Research.
• (EN) Relazione di equivalenza, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) equivalence relation, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica