Relazione binaria

Una relazione binaria è un tipo particolare di relazione di arità due. Tra le relazioni binarie più tipiche ci sono per esempio minore di, uguaglianza, divisibilità, maggiore di e così via.

Esempi

La relazione binaria è una delle relazioni più tipiche e più frequenti. Ha inoltre alcune proprietà interessanti, che qui descriviamo.

Un esempio di relazione binaria può essere il legame «padre – figlio», la coppia «mezzo di trasporto – numero di ruote» o, più in generale, «oggetto – proprietà dell’oggetto». L’oggetto può essere un animale e la proprietà il numero di zampe, la durata media della vita, il numero di peli sulla testa e così via.

Una relazione binaria R tra gli insiemi M₁ e M₂ possiamo definirla così: R ⊆ M₁ × M₂. Una relazione binaria è dunque un insieme di coppie, e questo insieme è un sottoinsieme del prodotto cartesiano dei due insiemi tra i quali introduciamo la relazione. Così la relazione «padre – figlio» può essere una relazione tra l’insieme di tutte le persone, tra l’insieme di tutte le persone in Europa o a Roma. Possiamo restringere l’insieme anche in un’altra direzione: possiamo dire di definire la relazione tra l’insieme di tutti gli uomini, e non delle persone in generale.

Per le relazioni binarie si usa di solito una notazione speciale. Invece di scrivere (a; b) ∈ R, possiamo scrivere aRb. Per esempio, invece di (3; 1) ∈ > possiamo scrivere 3 > 1. Lo stesso vale per le altre relazioni. La scrittura aSb è quindi equivalente a (a; b) ∈ S.

Relazione inversa

La relazione inversa è la relazione opposta a quella data. (Attenzione, non confonderla con il complemento di una relazione.) Qual è la relazione opposta a «minore di»? «Maggiore di». Se la relazione «minore di» contiene l’elemento (4; 7), cioè 4 < 7, l’elemento inverso sarà quello opposto: 7 > 4, e nella relazione inversa ci sarà la coppia inversa (7; 4).

Data una relazione R ⊆ M₁ × M₂, costruiamo la relazione inversa R⁻¹ prendendo tutti gli elementi (a; b) ∈ R e inserendo in R⁻¹ la loro inversa. Quindi, se la relazione R contiene l’elemento (a; b), la relazione R⁻¹ deve contenere l’elemento (b; a). Vale anche il contrario: se R⁻¹ contiene l’elemento (b; a), allora la relazione R deve contenere l’elemento (a; b).

In forma di definizione: la relazione R⁻¹ è inversa di R se e solo se vale

$$\mathrm{\forall }a\in M_1\mathrm{\forall }b\in M_2:(a;b)\in R\iff (b;a)\in R^{-1}$$

Vale quindi che 6 < 8 se e solo se 8 > 6. Lo stesso vale per le altre coppie.

Composizione di relazioni

Le relazioni binarie si possono comporre tra loro. Prendiamo due relazioni: la prima, R, sarà «essere il padre di suo figlio» e la seconda, S, «essere il fratello di sua sorella». La relazione R contiene quindi coppie (padre; figlio), la seconda relazione contiene coppie (fratello; sorella).

Proviamo ora a comporle. Otteniamo una nuova relazione, che indichiamo con R ∘ S, e che contiene l’elemento (a; c) se e solo se (a; b) ∈ R e allo stesso tempo (b; c) ∈ S. Nota che b compare in entrambi gli elementi, una volta al secondo posto e poi al primo posto della coppia. È una specie di elemento di collegamento della composizione.

Esempio: R = {(Luca; Marco), (Pietro; Matteo)} e S = {(Marco; Giulia), (Marco; Elena), (Matteo; Chiara)}. Luca è il padre di Marco, Pietro è il padre di Matteo. Marco ha due sorelle, Giulia ed Elena, e Matteo ha una sorella, Chiara.

Ora componiamo le relazioni: R ∘ S. Cerchiamo una coppia di R che abbia al posto del figlio qualcuno che compare come fratello nella relazione S. Per esempio queste due coppie: (Luca; Marco) e (Marco; Giulia). Marco è l’elemento di collegamento, che poi non ci serve più, e con i nomi rimasti formiamo una nuova coppia: (Luca; Giulia). La relazione R ∘ S contiene quindi la coppia (Luca; Giulia). Marco ha ancora un’altra sorella, Elena, che aggiungiamo alla relazione composta: (Luca; Elena). Rimane infine il figlio Matteo. Lui ha una sorella, Chiara. Abbiamo quindi due coppie: (Pietro; Matteo) e (Matteo; Chiara). Con queste creiamo un altro elemento: (Pietro; Chiara).

Il risultato è la relazione: R ∘ S = {(Luca; Giulia), (Luca; Elena), (Pietro; Chiara)}. Come potremmo chiamare questa relazione? Con ogni probabilità «essere il padre di sua figlia».

Ancora una volta, la definizione completa:

$$(a;c)\in (R\circ S)\iff \mathrm{\exists }b(a;b)\in R\wedge (b;c)\in S$$

Nota: a volte si usa la scrittura inversa, cioè per la stessa definizione si userebbe S ∘ R al posto di R ∘ S.