Relazione d’ordine

La relazione d’ordine è una relazione binaria su un insieme che è riflessiva, antisimmetrica e transitiva.

Motivazione

L’ordine è un concetto comune, con cui lavoriamo anche nella vita di tutti i giorni. Molte cose possiamo ordinarle in qualche modo: le parole in ordine alfabetico, gli alunni a scuola per altezza, le merci per prezzo. Tutto questo è descritto dalla relazione d’ordine, che di solito indichiamo con il simbolo ≤. I simboli collegati sono: <, >, ≥. Il loro significato è evidente.

Che cosa ci aspetteremmo da una relazione di questo tipo? Già dal simbolo è chiaro che nella relazione d’ordine ci saranno anche elementi uguali: ci interessa quindi definire le proprietà della relazione minore o uguale. Una relazione di questo tipo dovrebbe essere riflessiva. Deve valere a ≤ a.

E poi? Di sicuro non varrà la simmetria: se ordiniamo per prezzo e l’auto costa meno del pane, di certo il pane non costerà allo stesso tempo meno dell’auto. Che cosa ci aspetteremmo in generale se capitasse che a ≤ b e allo stesso tempo b ≤ a? Avrebbe senso? Sì, se valesse a = b. L’unico caso in cui l’ordine degli elementi inseriti nella relazione non conta è quando quegli elementi sono uguali: l’ordine è quindi antisimmetrico.

Infine, se sappiamo che l’auto costa più del pane e l’aereo costa ancora più dell’auto, ci aspettiamo che l’aereo costi certamente più del pane. Questo descrive la transitività.

Ordine parziale

Quello che abbiamo appena definito è in realtà soltanto un ordine parziale, non è totale. Perché non è totale? Proviamo a definire un ordine sugli insiemi. In che modo potremmo confrontare due insiemi?

Diciamo che l’insieme A è minore o uguale all’insieme B se A ⊆ B, cioè se A è un sottoinsieme di B. Ha senso, perché se A = {1, 2} e B = {1, 2, 3}, di A potremmo dire che è minore: B contiene gli stessi elementi di A e in più contiene il numero tre. Per esempio varrà:

• {a, c} ≤ {a, b, c, d}
• ∅ ≤ {5, n, x}
• {x, e, s} ≤ {x, e, s}

Il problema nasce però quando vogliamo confrontare questi insiemi: A = {a, b} e B = {a, c}. Quale dei due è minore o maggiore? Il problema è che entrambi gli insiemi contengono l’elemento a, ma il secondo elemento è sempre diverso. Nessuno dei due insiemi è un sottoinsieme dell’altro, quindi non vale né A ≤ B né B ≤ A. Questi insiemi sono non confrontabili rispetto al nostro ordine.

Definiamo quindi insieme totalmente ordinato, o anche catena, un insieme in cui due elementi qualsiasi sono confrontabili. Tali insiemi sono per esempio gli insiemi numerici con l’ordine classico. Per due numeri reali qualsiasi a, b sei in grado di decidere se a ≤ b oppure b ≤ a.

Esempi dalla vita quotidiana

Un esempio in cui conviene non confrontare potrebbe essere l’ordine secondo la bellezza, in cui la relazione < significherebbe «essere più brutto». Forse dovremmo definirla al contrario, > come «essere più bello», per essere più corretti :-). Probabilmente ha senso confrontare tra loro due donne, per esempio «Elena» < «Chiara» nel senso che Chiara è più bella di Elena. Oppure due uomini: «Luca» < «Marco» nel senso che Marco è più bello di Luca.

Il problema è che difficilmente possiamo confrontare la bellezza di un uomo e di una donna. È più bella Chiara o Marco? È più brutta la nostra cara Elena o l’affascinante Luca? Meglio non indagare…

Se nell’ultimo esempio ci limitiamo, poniamo, alle sole donne, possiamo dire di avere un insieme totalmente ordinato, perché sappiamo confrontare la bellezza di tutte le donne.

Elemento minimale e massimale, minimo e massimo

Dato un insieme ordinato M, un elemento min ∈ M si dice minimale se non esiste alcun x ∈ M tale che x < min. Cioè non riusciamo a trovare un elemento che sia minore dell’elemento min.

Un elemento max ∈ M si dice massimale se non esiste alcun x ∈ M tale che x > max. Cioè non riusciamo a trovare un elemento che sia maggiore.

Questi due concetti sono diversi da quelli di minimo e di massimo.

Un elemento a ∈ M si dice minimo se per ogni x ∈ M vale a ≤ x. Quindi il minimo a è minore o uguale a tutti gli altri elementi dell’insieme M.

Un elemento b ∈ M si dice massimo se per ogni x ∈ M vale b ≥ x. Il massimo b è maggiore o uguale a tutti gli altri elementi dell’insieme M.

Qual è la differenza tra il massimo e un elemento massimale? Gli elementi massimali possono essere più di uno, perché l’insieme non deve necessariamente essere totalmente ordinato. Se torniamo all’esempio del confronto tra persone in base all’aspetto, possiamo dire che Chiara è la donna più bella e Marco è l’uomo più bello. Ma queste due persone non siamo più in grado di confrontarle tra loro: non sappiamo se sia più bella Chiara o Marco.

Entrambi gli elementi sono quindi massimali. Non riusciamo a trovare una persona più bella di Marco: Marco è più bello di tutti gli altri uomini e con le donne non possiamo confrontarlo. Lo stesso vale per Chiara: è più bella di tutte le donne e con gli uomini non possiamo confrontarla.

Ma nessuno dei due è il massimo, in questo senso la persona più bella. Perché, per essere la persona più bella/il massimo, Marco dovrebbe essere più bello di tutte le persone, comprese tutte le donne. Ma abbiamo già detto che con le donne non possiamo confrontarlo, perciò non può essere la persona più bella, è soltanto, nella terminologia della teoria dell’ordine, massimale.

È facile vedere che, se un insieme ha un massimo, questo elemento è anche massimale. Se l’elemento a è maggiore di tutti gli altri elementi dell’insieme (definizione di massimo), di certo non troveremo un elemento ancora più grande (definizione di elemento massimale).

Un esempio di insieme che ha massimo e minimo è l’intervallo chiuso [0; 1]. Se scegliamo lo stesso intervallo ma aperto, non avrebbe né massimo né minimo: (0; 1).

Se volessimo infiniti elementi minimali, potremmo definire l’ordine R così. Prima definiamo degli insiemi ausiliari M_x. Gli insiemi avranno questa forma: per ogni x dell’intervallo (0; 1) definiamo l’insieme M_x = {y | y = x + n}, dove n è un numero intero non negativo. Otteniamo per esempio questi insiemi:

$$\begin{array}{rcl}{M}_{0,5}& =& \{0,5;1,5;2,5;3,5;\dots \}\\ M_{0,7}& =& \{0,7;1,7;2,7;3,7;\dots \}\\ M_{0,8}& =& \{0,8;1,8;2,8;3,8;\dots \}\end{array}$$

Su ogni insieme M_x definiamo l’ordine classico, che indichiamo con R_x. Alla fine uniamo semplicemente questi ordini: R = ∪ R_x. In questo ordine possiamo quindi confrontare sempre soltanto all’interno delle catene originali. Possiamo scoprire se 0,5 ≤ 2,5, ma non possiamo scoprire se 0,5 ≤ 2,7, perché questi numeri non si trovavano nello stesso insieme M_x e quindi il loro confronto non è definito.

In questa relazione d’ordine ogni elemento dell’intervallo (0; 1) è un elemento minimale.

Diagrammi di Hasse

Gli insiemi ordinati possiamo rappresentarli con un diagramma di Hasse. Si tratta di un grafo in cui i vertici rappresentano gli elementi dell’insieme e un arco (segmento) tra i vertici (a; b) ci dice che a < b e allo stesso tempo non esiste alcun c tale che a < c < b. Cioè tra gli elementi a e b non c’è nessun altro elemento. Inoltre nel grafo il vertice a deve trovarsi più in basso del vertice b. Esempio di diagramma di Hasse:

Questo diagramma di Hasse rappresenta l’insieme ordinato {A, B, C, D, E, F}. Vale: A < B, B < E, e naturalmente vale anche A < E, ma tra questi vertici non c’è un arco, perché esiste il vertice B per cui vale A < B < E. Gli elementi E e D non sono confrontabili, perché nessuno dei due sta sopra o sotto l’altro.

Anche se i diagrammi di Hasse si disegnano di solito in modo così ordinato, non è strettamente necessario. Il diagramma di Hasse precedente può avere anche questo aspetto:

Un altro esempio può essere l’insieme: A = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. Sono i divisori naturali del numero 60. L’ordine per divisibilità può essere rappresentato così:

L’ordine per divisibilità significa che (a; b) ∈ R se e solo se a divide b. Dal diagramma notiamo che sopra ogni numero ci sono i numeri che lo hanno come divisore. Per esempio sopra il numero 6 ci sono i numeri 12, 30 e 60. Sopra il numero 4 ci sono i numeri 12, 20 e 60. Eccetera. Invece sopra il numero 3 non c’è il numero 10, perché non lo divide – attenzione, il numero 10 è visivamente sopra il numero 3, ma nessuna linea sale dal 3 fino al 10. Se dal numero 3 ci muoviamo solo verso l’alto, possiamo andare ai numeri 15 e 6 e da questi al numero 30. Al numero 10 potremmo arrivare solo scendendo, e questo non è permesso.