Relazione binaria su un insieme

Per relazione binaria su un insieme intendiamo una relazione binaria definita tra due insiemi uguali.

Esempi

La relazione binaria su un insieme è un tipo particolare di relazione binaria, in cui i due insiemi di partenza coincidono. Una relazione binaria su un insieme è quindi una relazione R tale che R ⊆ M × M.

La relazione «maggiore di» è una relazione binaria su un insieme, perché da entrambi i lati lavoriamo con numeri. Vale quindi che > ⊆ ℝ × ℝ. La relazione «padre – numero di figli» non è una relazione binaria su un insieme, perché i padri li scegliamo dall’insieme di tutte le persone, mentre il numero di figli lo scegliamo da un insieme numerico.

Proprietà

Una relazione binaria R su un insieme M può avere alcune proprietà interessanti. Diciamo che la relazione R è…

• riflessiva, se per ogni a ∈ M vale (a; a) ∈ R.
• simmetrica, se per ogni a, b ∈ M vale che, se (a; b) ∈ R, allora anche (b; a) ∈ R.
• antisimmetrica, se per ogni a, b ∈ M vale che, se (a; b) ∈ R e allo stesso tempo anche (b; a) ∈ R, allora a = b.
• transitiva, se per ogni a, b, c ∈ M vale che, se (a; b) ∈ R e allo stesso tempo (b; c) ∈ R, allora anche (a; c) appartiene a R.

Esempi di riflessività

La riflessività significa che un elemento è in relazione con se stesso. Un esempio tipico è l’uguaglianza. Se definiamo l’uguaglianza sui numeri naturali, vale certamente che per qualsiasi elemento a: a = a. Un altro esempio può essere la divisibilità. Anche qui vale che il numero a è divisibile per se stesso, quindi la coppia (a; a) appartiene alla relazione di divisibilità (il sette divide il sette).

La relazione minore di invece non è riflessiva, perché non vale a < a. Non è possibile: il sette non può essere minore del sette. Allo stesso modo la relazione essere il padre di un figlio: non posso essere padre di me stesso. Queste relazioni non sono riflessive.

È importante che la riflessività valga per tutti gli elementi: non basta trovarne solo alcuni. Prendiamo per esempio la relazione «voler bene a qualcuno». Posso voler bene a qualcun altro, per esempio al controllore, ma posso anche voler bene a me stesso. Di certo c’è qualcuno che vuole bene a se stesso. Ma allo stesso modo c’è qualcuno che non vuole bene a se stesso. Una relazione di questo tipo non è riflessiva: tutte le persone dovrebbero voler bene a se stesse.

Esempi di simmetria

In una relazione simmetrica, se una coppia appartiene alla relazione, vi appartiene anche la coppia inversa. Per esempio la relazione essere fratello o sorella. Se Marco è fratello di Giulia, allora anche Giulia è sorella di Marco. Tra le relazioni numeriche potrebbe essere la relazione «essere il numero opposto». Intendo le coppie 2 e −2 oppure −7 e 7. Sono due numeri la cui somma è zero. Questa relazione è simmetrica, perché l’ordine semplicemente non conta: (2; −2) e (−2; 2) sono comunque numeri opposti tra loro e la loro somma è zero.

Una relazione che non è simmetrica è minore di (sui numeri reali). Non ha neanche un elemento simmetrico, perché non può mai valere a < b e allo stesso tempo b < a. Se 5 < 15, non può valere 15 < 5. Non è simmetrica nemmeno la relazione «essere il padre di un figlio». Puoi essere il padre di tuo figlio, ma allora il figlio non può essere il padre di suo padre.

Anche questa proprietà deve valere in tutti i casi. Se la relazione «voler bene a qualcuno» (sull’insieme di tutte le persone) fosse simmetrica, allora, se io voglio bene a una cantante famosa, anche lei dovrebbe volere bene a me. E siccome non mi conosce nemmeno, non posso dire che mi voglia bene, il che è un peccato, e la relazione non è simmetrica. E anche questo è un peccato.

Esempi di antisimmetria

Un esempio classico di relazione antisimmetrica è minore o uguale. L’antisimmetria ci dice che, se gli elementi (a; b) e (b; a) sono in relazione, lo sono solo quando sono uguali, a = b. La relazione minore o uguale lo soddisfa. Quando valgono a ≤ b e allo stesso tempo b ≤ a? Solo nel caso a = b. Sostituendo: valgono 3 ≤ 5 e allo stesso tempo 5 ≤ 3? No. Ma valgono 4 ≤ 4 e allo stesso tempo 4 ≤ 4.

Un esempio di relazione che non è antisimmetrica sono le coppie di parole della stessa lunghezza, per esempio (sabato; matita). Questa relazione non è antisimmetrica, perché troviamo una coppia di parole in relazione la cui coppia inversa è anch’essa in relazione, e tuttavia le due parole sono diverse. Prendiamo l’elemento già citato (sabato; matita) e la sua inversa (matita; sabato). Entrambe appartengono evidentemente alla nostra relazione, ma sabato ≠ matita, quindi la relazione non è antisimmetrica.

Esempio di transitività

La relazione minore di è transitiva. La transitività ci dice che, se 3 < 4 e allo stesso tempo 4 < 5, allora deve valere anche 3 < 5. Per molte relazioni è una proprietà piuttosto naturale. Lo stesso vale per l’esempio con la stessa lunghezza delle parole. Se (matita; sabato) è in relazione e (sabato; tavolo) è in relazione, allora sono in relazione anche le parole (matita; tavolo).

La relazione essere il padre di un figlio non è transitiva. Se Luca è il padre di Marco e Marco è il padre di Matteo, Luca non è il padre di Matteo, ne è il nonno. Allo stesso modo non è transitiva la relazione voler bene a qualcuno. Se io voglio bene a quella cantante e lei vuole bene a suo marito, non significa che io voglia bene anche a suo marito.

La transitività si studia anche con i classici dadi. Consideriamo la relazione «il dado A è migliore del dado B», che vale se sul dado A esce più spesso (con probabilità maggiore) un numero più alto che sul dado B. Questa relazione è transitiva? La risposta è nell’articolo sui dadi non transitivi.

Equivalenza e ordine

Alcuni tipi particolari di relazioni binarie hanno anche un nome proprio:

• La relazione di equivalenza è una relazione riflessiva, simmetrica e transitiva.
• La relazione d’ordine è una relazione riflessiva, antisimmetrica e transitiva.