Non tutto si può mettere in fila. I numeri sì: dati due numeri diversi, uno è sempre più piccolo dell'altro. Ma due compiti in un progetto possono essere indipendenti, due insiemi possono non essere contenuti l'uno nell'altro, due versioni di un documento modificate in parallelo possono non essere l'una «successiva» all'altra. Gli ordini parziali sono la struttura matematica che descrive queste situazioni, in cui alcuni elementi sono confrontabili e altri no.
Definizione
Una relazione ≼ su un insieme A è un ordine parziale se è:
- riflessiva: a ≼ a;
- antisimmetrica: se a ≼ b e b ≼ a, allora a = b;
- transitiva: se a ≼ b e b ≼ c, allora a ≼ c.
La coppia (A, ≼) si chiama insieme parzialmente ordinato, spesso abbreviato in poset. Due elementi a e b sono confrontabili se a ≼ b oppure b ≼ a; altrimenti sono inconfrontabili.
Se tutti gli elementi sono confrontabili a due a due, l'ordine si dice totale (o lineare). ≤ sui numeri è totale; l'inclusione tra insiemi no.
Esempi tipici
- Inclusione su 𝒫(A): {1} ⊆ {1, 2}, ma {1} e {2} sono inconfrontabili.
- Divisibilità sugli interi positivi: 3 divide 12, ma 4 e 6 sono inconfrontabili.
- Ordine lessicografico sulle stringhe: è totale, ed è quello dei dizionari.
- Ordine per componenti sulle coppie: (a, b) ≼ (c, d) se a ≤ c e b ≤ d. (1, 3) e (2, 2) sono inconfrontabili.
- Precedenze tra attività: «a deve essere completato prima di b».
Il diagramma di Hasse
Disegnare tutte le frecce di un ordine parziale produce un groviglio, perché per riflessività e transitività le frecce sono moltissime. Il diagramma di Hasse ne tiene solo l'essenziale:
- si omettono i cappi (la riflessività è sottintesa);
- si omettono le frecce deducibili per transitività, tenendo solo le relazioni di copertura: b copre a se a ≺ b e non c'è nessun c con a ≺ c ≺ b;
- si disegnano gli elementi più «grandi» più in alto, così le frecce diventano semplici segmenti letti dal basso verso l'alto.
Esempio: i divisori di 12 ordinati per divisibilità, {1, 2, 3, 4, 6, 12}. Le relazioni di copertura sono:
- 1 è coperto da 2 e da 3;
- 2 è coperto da 4 e da 6;
- 3 è coperto da 6;
- 4 e 6 sono coperti da 12.
Nel diagramma 1 sta in basso, 2 e 3 al livello successivo, 4 e 6 sopra, 12 in cima. La relazione «1 divide 12» non compare come segmento diretto, ma si legge seguendo un percorso verso l'alto.
Massimale e massimo: non sono la stessa cosa
Questa è la distinzione che crea più confusione.
- Un elemento è massimale se non c'è nessun elemento strettamente più grande di lui.
- Un elemento è massimo se è più grande o uguale a tutti gli altri.
Un massimo, se esiste, è unico ed è anche massimale. Ma gli elementi massimali possono essere tanti, e un massimo può non esistere. Consideriamo l'insieme {2, 3, 4, 6} ordinato per divisibilità: 4 e 6 sono entrambi massimali (nessuno dei due divide un altro elemento più grande dell'insieme), ma non c'è un massimo, perché 4 non divide 6 e 6 non divide 4. Allo stesso modo si definiscono minimale e minimo.
In un progetto, gli elementi minimali dell'ordine di precedenza sono le attività che si possono cominciare subito; quelli massimali sono le attività su cui non dipende nient'altro.
Estremo superiore e reticoli
Un maggiorante di due elementi a e b è un elemento che sta sopra entrambi. Il più piccolo dei maggioranti, se esiste, è l'estremo superiore (o join), a ∨ b. Duale è l'estremo inferiore (o meet), a ∧ b.
Un poset in cui ogni coppia ha sia estremo superiore sia inferiore si chiama reticolo. Esempi:
| Poset | a ∨ b | a ∧ b |
|---|---|---|
| (𝒫(A), ⊆) | A ∪ B | A ∩ B |
| (ℤ⁺, divide) | mcm(a, b) | MCD(a, b) |
| (ℝ, ≤) | max(a, b) | min(a, b) |
I reticoli compaiono in informatica più spesso di quanto si pensi. Nei modelli di sicurezza multilivello, i livelli di classificazione combinati con le categorie formano un reticolo, e un'informazione che unisce due fonti riceve il loro estremo superiore. Nell'analisi statica dei programmi, i valori astratti formano un reticolo e i risultati di rami diversi si combinano con il join.
Ordini parziali nei sistemi distribuiti
Quando più nodi modificano dati in parallelo, gli eventi non hanno un ordine totale naturale. Gli orologi vettoriali assegnano a ogni evento un vettore di contatori, uno per nodo, e li confrontano con l'ordine per componenti visto sopra. Se un vettore è minore o uguale all'altro in ogni posizione, il primo evento precede il secondo; se nessuno dei due domina, gli eventi sono concorrenti, cioè inconfrontabili, e il sistema sa di trovarsi davanti a un possibile conflitto da risolvere.
Per mettere in fila gli elementi di un ordine parziale rispettandone i vincoli si usa l'ordinamento topologico, che estende l'ordine parziale a uno totale compatibile.
In sintesi
- Un ordine parziale è riflessivo, antisimmetrico e transitivo; alcuni elementi possono essere inconfrontabili.
- Il diagramma di Hasse mostra solo le relazioni di copertura, con gli elementi maggiori in alto.
- Massimale non significa massimo: possono esserci più massimali e nessun massimo.
- Un reticolo garantisce estremo superiore e inferiore per ogni coppia, come unione e intersezione.
- Orologi vettoriali e livelli di sicurezza sono applicazioni concrete degli ordini parziali.
