Relazione

relazione

relazione in generale su un insieme A è una → corrispondenza ρ di A in sé stesso. Dati due elementi x e y di A, si scrive x ρ y (e si dice che x è in relazione con y) se y appartiene al sottoinsieme ρ(x) associato a x tramite la corrispondenza ρ; viceversa, se x non è in relazione con y, allora si scrive

La nozione di relazione formalizza il significato che il termine ha nel linguaggio naturale, in cui, per esempio, due individui possono essere o meno in relazione di parentela. Come nel caso delle corrispondenze, una relazione su A è equivalentemente definibile assegnando il sottoinsieme P del prodotto cartesiano A × A, detto grafico della relazione, costituito dalle coppie ordinate (x, y) tali che x ρ y. Il dominio di ρ è l’insieme degli elementi a appartenenti ad A tali che a ρ b per almeno un elemento b di A; il codominio di ρ è l’insieme degli elementi b appartenenti ad A tali che a ρ b per almeno un elemento a di A. Poiché coinvolge coppie di elementi, una relazione così definita è anche detta relazione binaria.

In ogni insieme non vuoto A sono sempre definite le tre seguenti relazioni banali:

• la relazione identica, definita da a ρ b se e solo se a = b, il cui grafico è la “diagonale” di A × A;

• la relazione caotica, definita da a ρ b per ogni a, b appartenenti ad A, il cui grafico è l’intero A × A;

• la relazione vuota, definita da a ρ b per nessun a, b appartenenti ad A, il cui grafico è l’insieme vuoto.

Una relazione ρ su un insieme A è detta:

• riflessiva, se, per ogni elemento a di A, a ρ a (tale è per esempio la relazione di «uguaglianza» in un insieme numerico, mentre non lo è la relazione di «perpendicolarità» nell’insieme delle rette del piano);

• simmetrica, se per ogni a, b ∈ A, a ρ b implica b ρ a (tale è per esempio la relazione di «perpendicolarità» tra le rette del piano, mentre non lo è la relazione «essere minore o uguale» definita in R);

• transitiva, se per ogni a, b, c ∈ A, a ρ b e b ρ c implica a ρ c (tale è per esempio la relazione di «parallelismo» definita nell’insieme delle rette del piano, mentre, nello stesso insieme, non lo è la relazione di «perpendicolarità»);

• antisimmetrica, se per ogni a, b ∈ A, a ρ b e b ρ a implica a = b (tale è per esempio la relazione «essere minore o uguale» definita in R);

• totale, se, comunque presi due elementi a e b di A, allora o si ha a ρ b oppure b ρ a (tale è per esempio la relazione ≤ definita in R).

Una relazione riflessiva, simmetrica e transitiva è detta relazione di → equivalenza; una relazione riflessiva e transitiva è detta relazione di → preordine; una relazione antisimmetrica e transitiva è detta relazione d’ordine o → ordinamento (alcuni autori richiedono che l’ordinamento sia anche riflessivo); una relazione d’ordine che è anche totale è detta relazione d’ordine totale (o anche relazione d’ordine lineare). Per esempio, la relazione di divisibilità definita sull’insieme N dei numeri naturali, indicata con il simbolo | e definita da «a|b se e solo se esiste c tale che b = ac» con a, b e c numeri naturali, è una relazione riflessiva, antisimmetrica e transitiva: essa è dunque una relazione d’ordine (non totale). Diversamente, la stessa relazione definita nell’insieme Z dei numeri interi è riflessiva e transitiva, ma non antisimmetrica, perché due numeri opposti si dividono a vicenda, e quindi la relazione di divisibilità è un preordinamento, ma non definisce un ordinamento in Z.