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 formaleSignificato intuitivo
RiflessivaOgni elemento è in relazione con se stesso
Antiriflessiva (o irriflessiva)Nessun elemento è in relazione con se stesso
SimmetricaIl legame è sempre bidirezionale
AntisimmetricaDue elementi distinti non possono essere in relazione in entrambi i versi
AsimmetricaIl legame non è mai reversibile (implica anche l’antiriflessività)
TransitivaIl 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:

  1. riflessiva: ;
  2. simmetrica: ;
  3. 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:

  1. Nessuna classe è vuota: per riflessività , quindi per ogni .
  2. Classi distinte sono disgiunte: per ogni , o (se ) oppure (se ).
  3. 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 .

Classi di equivalenza e diagramma di un ordine parziale

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 è:

    1. riflessiva: ;
    2. antisimmetrica: ;
    3. transitiva: .
      Esempi classici: l’ordine su , l’inclusione su , la divisibilità su .
  • Una relazione su si dice relazione d’ordine stretto se è:

    1. antiriflessiva: ;
    2. 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:

ConcettoDefinizione 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:

  1. Riflessività: per ogni , , quindi . Vale sia su sia su .
  2. Transitività: se () e (), allora , quindi . Vale sia su sia su .
  3. 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 ).
  4. 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:

  1. 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!).
  2. Classi di equivalenza: fissato , cerchiamo tutti gli tali che :

    Pertanto:
    • se , la classe contiene due elementi opposti: ;
    • se , la classe contiene un solo elemento: .
  3. 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

  1. (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 .

  2. (Base - Classificazione di una relazione reale) Sull’insieme si consideri la relazione . Verifica quali proprietà possiede e spiega perché non è una relazione di equivalenza.

  3. (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.

  4. (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 .

  5. (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).

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.