Relazioni di ordine e di equivalenza
In matematica una relazione formalizza il concetto di legame o confronto tra gli elementi di due insiemi (o di uno stesso insieme): «essere uguale a», «essere minore o uguale di», «avere lo stesso resto nella divisione per », «essere divisore di». Analizzando le proprietà strutturali di una relazione possiamo distinguere due grandi famiglie fondamentali: le relazioni di equivalenza (che ripartiscono un insieme in classi di oggetti simili) e le relazioni d’ordine (che dispongono gli elementi secondo una gerarchia).
Definizione di relazione binaria
Dati due insiemi non vuoti e , una relazione binaria da a è un qualunque sottoinsieme del prodotto cartesiano :
Se la coppia ordinata appartiene a , si scrive in notazione infissa:
e si legge « è in relazione con ». Poiché le coppie sono ordinate, in generale da non segue affatto .
Quando , si dice che è una relazione definita su .
Esempio introduttivo
Sull’insieme finito definiamo la relazione . Allora, come sottoinsieme di , la relazione è:
Si ha ad esempio , mentre e .
Proprietà delle relazioni su un insieme
Sia una relazione definita su un insieme . Le proprietà fondamentali che può soddisfare sono:
| Proprietà | Definizione formale | Significato intuitivo |
|---|---|---|
| Riflessiva | Ogni elemento è in relazione con se stesso | |
| Antiriflessiva (o irriflessiva) | Nessun elemento è in relazione con se stesso | |
| Simmetrica | Il legame è sempre bidirezionale | |
| Antisimmetrica | Due elementi distinti non possono essere in relazione in entrambi i versi | |
| Asimmetrica | Il legame non è mai reversibile (implica anche l’antiriflessività) | |
| Transitiva | Il legame si propaga a catena |
Attenzione: simmetria e antisimmetria non sono una la negazione dell'altra!
- La relazione «avere la stessa età» è simmetrica ma non antisimmetrica (due persone diverse possono avere la stessa età).
- La relazione su è antisimmetrica ( e implicano ) ma non simmetrica.
- La relazione di uguaglianza «» su è sia simmetrica sia antisimmetrica.
- Esistono relazioni che non sono né simmetriche né antisimmetriche (basta avere una coppia bidirezionale tra elementi distinti e una coppia unidirezionale).
Relazioni di equivalenza, classi e insieme quoziente
Definizione
Una relazione su un insieme si dice relazione di equivalenza (spesso indicata con o ) se è contemporaneamente:
- riflessiva: ;
- simmetrica: ;
- transitiva: .
Intuitivamente, una relazione di equivalenza formalizza un criterio di «somiglianza» o «uguaglianza rispetto a una caratteristica scelta», ignorando le altre differenze tra gli oggetti.
Classi di equivalenza e partizioni
Data una relazione di equivalenza su e fissato un elemento , si chiama classe di equivalenza di (rispetto a ) il sottoinsieme di tutti gli elementi di equivalenti a :
Ogni elemento si dice un rappresentante della classe, e vale .
Le classi di equivalenza soddisfano tre proprietà fondamentali:
- Nessuna classe è vuota: per riflessività , quindi per ogni .
- Classi distinte sono disgiunte: per ogni , o (se ) oppure (se ).
- L’unione di tutte le classi ricopre : .
Una famiglia di sottoinsiemi non vuoti, a due a due disgiunti e la cui unione è tutto si chiama partizione di . Vale una corrispondenza biunivoca fondamentale: ogni relazione di equivalenza su induce una partizione di (le sue classi di equivalenza), e viceversa ogni partizione di definisce una relazione di equivalenza («appartenere allo stesso blocco della partizione»).
Insieme quoziente e aritmetica modulare
L’insieme i cui elementi sono tutte le diverse classi di equivalenza di rispetto a si chiama insieme quoziente di modulo e si indica con:
Attenzione alla natura degli oggetti: gli elementi di sono sottoinsiemi di (cioè ). Passare da ad significa «incollare» in un unico punto tutti gli elementi tra loro equivalenti.
Esempio fondamentale: la congruenza modulo e l’insieme
Fissato un intero , definiamo su la relazione di congruenza modulo :
Due interi sono congrui modulo se e solo se la loro differenza è un multiplo di , ovvero se e solo se danno lo stesso resto nella divisione euclidea per .
Verifichiamo che è una relazione di equivalenza su :
- Riflessiva: , quindi e .
- Simmetrica: se con , allora con , quindi .
- Transitiva: se e , sommando si ha , dunque .
Poiché i possibili resti della divisione per sono esattamente , vi sono esattamente classi di equivalenza distinte (dette classi resto modulo ):
L’insieme quoziente si indica con (oppure ) ed è un insieme finito con elementi:
Per esempio, per , e si ha .
Relazioni d’ordine e insiemi parzialmente ordinati (poset)
Ordine largo e ordine stretto
-
Una relazione su si dice relazione d’ordine largo (o non stretto) se è:
- riflessiva: ;
- antisimmetrica: ;
- transitiva: .
Esempi classici: l’ordine su , l’inclusione su , la divisibilità su .
-
Una relazione su si dice relazione d’ordine stretto se è:
- antiriflessiva: ;
- transitiva: .
(Dall’antiriflessività e dalla transitività segue automaticamente l’asimmetria: se fosse e , per transitività avremmo , assurdo). Esempi: su e su .
Ad ogni ordine largo corrisponde un ordine stretto ponendo , e viceversa .
Ordine totale, ordine parziale e diagrammi di Hasse
Una coppia formata da un insieme e da una relazione d’ordine largo su si chiama insieme parzialmente ordinato o poset (partially ordered set).
Due elementi si dicono confrontabili se vale oppure ; altrimenti si dicono incomparabili.
- Se ogni coppia di elementi di è confrontabile (), l’ordine si dice totale (o lineare), come .
- Se esistono almeno due elementi incomparabili, l’ordine si dice parziale, come quando oppure .
Un poset finito si rappresenta graficamente mediante il diagramma di Hasse:
- gli elementi si dispongono come vertici dal basso verso l’alto in modo che se allora sia disegnato più in alto di ;
- si omettono i cappi relativi alla proprietà riflessiva ();
- si traccia un segmento tra e (con ) solo se copre immediatamente , ossia se non esiste alcun elemento intermedio tale che (omettendo i lati deducibili per transitività).
Minimo, massimo, elementi minimali e massimali
In un insieme parzialmente ordinato , dove non tutti gli elementi sono confrontabili tra loro, è fondamentale distinguere tra minimo/massimo globale ed elementi minimali/massimali:
| Concetto | Definizione formale in | Significato ed esistenza |
|---|---|---|
| Minimo | tale che | È più piccolo di tutti gli elementi di (confrontabile con tutti). Se esiste, è unico. |
| Massimo | tale che | È più grande di tutti gli elementi di (confrontabile con tutti). Se esiste, è unico. |
| Elemento minimale | tale che (cioè ) | Nessun elemento di è strettamente minore di . Possono essercene più d’uno. |
| Elemento massimale | tale che (cioè ) | Nessun elemento di è strettamente maggiore di . Possono essercene più d’uno. |
Differenza chiave tra minimale/massimale e minimo/massimo
- Se un poset possiede un minimo , allora è anche l’unico elemento minimale.
- Il viceversa non vale in un ordine parziale: se ci sono due o più elementi minimali distinti, essi sono tra loro incomparabili e quindi il minimo non esiste.
Esempio chiarificatore: Consideriamo l’insieme ordinato mediante la relazione di divisibilità :
- Elementi minimali: e , perché nessun altro elemento di divide o divide . Poiché e , nessuno dei due precede tutti gli elementi di : quindi non ha minimo.
- Elemento massimale e massimo: è divisibile per tutti gli elementi di (, , , , ). Pertanto è l’unico elemento massimale ed è anche il massimo di . Se invece togliessimo considerando , gli elementi massimali sarebbero e (nessuno dei due divide l’altro) e non avrebbe né minimo né massimo!
Esempi guidati
Esempio 1: Studio della relazione di divisibilità su vs
Studiamo la relazione () prima su e poi su tutto .
Passaggi:
- Riflessività: per ogni , , quindi . Vale sia su sia su .
- Transitività: se () e (), allora , quindi . Vale sia su sia su .
- Antisimmetria su : se e con , sostituendo si ha . Poiché , anche , dunque e . Su la divisibilità è una relazione d’ordine largo parziale (con minimo , poiché per ogni ).
- Fallimento dell’antisimmetria su : in possiamo scegliere e . Si ha e , ma ! Quindi su la divisibilità non è antisimmetrica e non è una relazione d’ordine.
Esempio 2: Relazione di equivalenza definita da una funzione ()
Su definiamo la relazione:
Dimostriamo che è una relazione di equivalenza, determiniamo la classe di equivalenza di un generico e descriviamo l’insieme quoziente .
Passaggi:
- Verifica delle tre proprietà:
- Riflessiva: , , quindi .
- Simmetrica: , se allora , quindi .
- Transitiva: , se e , allora , quindi .
(Nota: più in generale, per qualsiasi funzione , la relazione è sempre di equivalenza!).
- Classi di equivalenza: fissato , cerchiamo tutti gli tali che :
Pertanto:- se , la classe contiene due elementi opposti: ;
- se , la classe contiene un solo elemento: .
- Insieme quoziente: ogni classe è univocamente individuata dal suo unico rappresentante non negativo . Quindi l’insieme quoziente è in corrispondenza biunivoca con la semiretta .
Errori frequenti
- Dimostrare una proprietà generale con un solo esempio numerico: per provare che è transitiva non basta controllare e , occorre ragionare su elementi generici . Invece, per dimostrare che una proprietà non vale, basta ed è necessario esibire un solo controesempio esplicito.
- Confondere classi di equivalenza e elementi: in , la scrittura non indica solo il numero , ma l’intero insieme infinito , e vale .
- Confondere elemento minimale con minimo: in un poset con più rami separati sul fondo del diagramma di Hasse ci sono più elementi minimali e nessun minimo.
- Pensare che transitività + simmetria implichino riflessività: questo argomento () fallisce se esiste un elemento «isolato» che non è in relazione con alcun . La riflessività va sempre verificata a parte per ogni .
Esercizi di prova
-
(Base - Proprietà di una relazione) Sull’insieme si consideri la relazione . Stabilisci se è riflessiva, simmetrica, antisimmetrica, transitiva. È una relazione di equivalenza o d’ordine? Se è di equivalenza, determina le classi e l’insieme quoziente .
Soluzione
Analizziamo le proprietà:
- Riflessiva: per ogni , è pari, quindi . (Sì)
- Simmetrica: se è pari, poiché , anche è pari, quindi . (Sì)
- Antisimmetrica: per e si ha (pari), quindi e , ma . (No)
- Transitiva: se e con , allora:
che è pari. Quindi . (Sì)
Essendo riflessiva, simmetrica e transitiva, è una relazione di equivalenza (coincide con la congruenza modulo ). La somma di due interi è pari se e solo se i due interi hanno la stessa parità (entrambi pari o entrambi dispari). Vi sono quindi esattamente due classi di equivalenza:
- (insieme dei numeri pari);
- (insieme dei numeri dispari).
L’insieme quoziente è .
-
(Base - Classificazione di una relazione reale) Sull’insieme si consideri la relazione . Verifica quali proprietà possiede e spiega perché non è una relazione di equivalenza.
Soluzione
- Riflessiva: per ogni . (Sì)
- Simmetrica: se , allora . (Sì)
- Antisimmetrica: per e vale e , ma . (No)
- Transitiva: No! Scegliamo come controesempio , , . Si ha:
ma , quindi . Poiché non è transitiva (la «vicinanza entro distanza » non si conserva concatenando più passi), non è una relazione di equivalenza.
-
(Intermedio - Poset, elementi minimali/massimali e minimo/massimo) Sia dotato della relazione di divisibilità , e sia (ottenuto rimuovendo e dai divisori di ). Determina per ciascuno dei due poset e gli elementi minimali, gli elementi massimali, il minimo e il massimo.
Soluzione
Studio di con :
- Elementi minimali: i numeri primi non sono divisibili per alcun altro elemento di . Quindi gli elementi minimali sono .
- Minimo: poiché ci sono tre elementi minimali distinti (incomparabili tra loro), il minimo non esiste (mancherebbe l’elemento ).
- Elementi massimali e massimo: tutti gli elementi di dividono (). Quindi è l’unico elemento massimale ed è anche il massimo di .
Studio di con :
- Elementi minimali: ancora ; il minimo non esiste.
- Elementi massimali: in non c’è più , quindi i multipli di due primi distinti (, , ) non dividono nessun altro elemento di . Pertanto gli elementi massimali sono , e il massimo non esiste.
-
(Intermedio - Relazione di equivalenza nel piano cartesiano) Sul piano si definisca la relazione . Dimostra che è una relazione di equivalenza e descrivi geometricamente la classe di equivalenza del punto e l’insieme quoziente .
Soluzione
Posta , la relazione si scrive .
- Riflessiva: è sempre vera.
- Simmetrica: se , allora .
- Transitiva: se e , per transitività dell’uguaglianza .
Classe di equivalenza di : per si ha . Quindi:
Geometricamente, la classe di è la retta di coefficiente angolare passante per .
Insieme quoziente : al variare del valore reale , le classi di equivalenza sono tutte le rette del fascio improprio di rette parallele di equazione . Ogni retta del fascio costituisce un singolo elemento dell’insieme quoziente . -
(Esame - Ordine lessicografico su ) Su si definisca la relazione ponendo:
Dimostra che è un insieme totalmente ordinato (detto ordine lessicografico, simile all’ordine alfabetico del vocabolario).Soluzione
Verifichiamo le tre proprietà di ordine largo più la totalità:
- Riflessiva: per ogni vale e , quindi .
- Antisimmetrica: siano e . Non può essere (altrimenti la seconda relazione sarebbe falsa) né . Dunque necessariamente , e dalla seconda parte della definizione segue e , da cui . Pertanto .
- Transitiva: siano e . Allora :
- se almeno una delle due disuguaglianze sulle ascisse è stretta, allora e quindi ;
- se invece , allora valgono e , da cui e ancora .
- Totalità: presi comunque due punti , per tricotomia dei reali vale (allora ), oppure (allora ), oppure ; in quest’ultimo caso, essendo totale su , vale oppure . Quindi ogni coppia di punti è confrontabile.
Provenienza del materiale
Sintesi ragionata ed estesa della lezione C1MAT1U2L2_Relazioni_di_ordine_e_di_equivalenza.pdf e degli Appunti_di_fine_Unità_2.pdf (Corso di Matematica 1, CdL in Sicurezza Informatica / SecAI - Università degli Studi di Milano), con approfondimenti su insieme quoziente , classi resto ed elementi minimali/massimali nei poset.