significato · proprietà · equivalenza · ordine
Intuitivamente una relazione esprime un legame tra gli elementi di due insiemi: «è minore di», «è divisibile per», «ha la stessa parità di». In modo rigoroso tutto questo si riduce a un solo oggetto insiemistico: un insieme di coppie ordinate.
Dati due insiemi \(A\) e \(B\), il loro prodotto cartesiano è l'insieme di tutte le coppie ordinate con primo elemento in \(A\) e secondo in \(B\):
\[ A\times B=\{(a,b)\mid a\in A,\ b\in B\}. \]Se \(A\) e \(B\) sono finiti, \(\lvert A\times B\rvert=\lvert A\rvert\cdot\lvert B\rvert\).
Una relazione \(\mathcal R\) da \(A\) a \(B\) è un sottoinsieme del prodotto cartesiano:
\[ \mathcal R\subseteq A\times B. \]Si scrive \(a\,\mathcal R\,b\) (si legge «\(a\) è in relazione con \(b\)») per indicare che \((a,b)\in\mathcal R\), e \(a\,\cancel{\mathcal R}\,b\) quando \((a,b)\notin\mathcal R\).
Quando \(A=B\) si parla di relazione (binaria) su \(A\): è un sottoinsieme di \(A\times A\). È questo il caso centrale per equivalenza e ordine.
La stessa relazione si può descrivere in modi diversi — tutti equivalenti. Prendiamo «\(\le\)» su \(\{1,2,3\}\).
{(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}
Una crocetta nella riga \(a\), colonna \(b\) quando \(a\,\mathcal R\,b\):
| ≤ | 1 | 2 | 3 |
|---|---|---|---|
| 1 | × | × | × |
| 2 | × | × | |
| 3 | × |
Ogni elemento è un nodo; si disegna una freccia \(a\to b\) quando \(a\,\mathcal R\,b\). Una freccia che torna sul nodo stesso (un cappio) rappresenta \((a,a)\). Nella sezione Simulazione puoi costruire tu una relazione e vederne contemporaneamente matrice e grafo.
Per una relazione \(\mathcal R\) su un insieme \(A\) si definiscono alcune proprietà. Qui \(\forall\) significa «per ogni».
Una relazione \(\mathcal R\) su \(A\) è una relazione di equivalenza se è
riflessiva + simmetrica + transitiva
Spesso si usa il simbolo \(\sim\). Serve a formalizzare l'idea di «avere in comune una certa caratteristica»: stessa parità, stesso resto nella divisione, stessa direzione.
Dato \(a\in A\), la sua classe di equivalenza è l'insieme di tutti gli elementi equivalenti ad \(a\):
\[ [a]=\{\,x\in A \mid x\sim a\,\}. \]Vale un fatto fondamentale: due classi o sono identiche o sono disgiunte. Di conseguenza le classi di equivalenza partizionano \(A\): lo suddividono in «caselle» che non si sovrappongono e che insieme ricoprono tutto \(A\).
L'insieme di tutte le classi di equivalenza si chiama insieme quoziente e si indica
\[ A/\!\sim\ =\ \{\,[a]\mid a\in A\,\}. \]Una relazione \(\mathcal R\) su \(A\) è una relazione d'ordine (ordine parziale) se è
riflessiva + antisimmetrica + transitiva
Il prototipo è «\(\le\)»: serve a disporre in fila gli elementi, a dire quale «viene prima». Si usa spesso il simbolo \(\preceq\).
Due elementi \(a,b\) si dicono confrontabili se \(a\preceq b\) oppure \(b\preceq a\). Allora:
| riflessiva | simmetrica | antisimmetrica | transitiva | |
|---|---|---|---|---|
| Equivalenza | ✓ | ✓ | — | ✓ |
| Ordine | ✓ | — | ✓ | ✓ |
Simmetria e antisimmetria sono ciò che distingue i due concetti: l'equivalenza «identifica» elementi diversi mettendoli nella stessa classe, l'ordine li «separa» stabilendo chi precede chi.
Scegli l'insieme \(A=\{1,\dots,n\}\) e clicca le celle della matrice per aggiungere o togliere coppie: la cella nella riga \(a\), colonna \(b\) rappresenta \((a,b)\). Il grafo a frecce e l'analisi delle proprietà si aggiornano in tempo reale. Prova i modelli pronti per vedere relazioni notevoli.
Le celle sulla diagonale (in azzurro tenue) sono le coppie \((a,a)\): governano la riflessività. Un bordo ambrato segnala gli elementi che violano una proprietà.
Rispondi con un numero intero, poi premi Verifica. Se sei bloccato usa Aiuto: i suggerimenti diventano via via più espliciti.