Che cosa sono i diagrammi di Hasse, e come si costruiscono?

Il diagramma di Hasse è uno strumento grafico volto a
rappresentare relazioni di ordine tra elementi di un insieme parzialmente
ordinato. Rivediamo brevemente le definizioni necessarie per fornire una
descrizione formale del diagramma di Hasse.

Ordinamento parziale

Sia X un insieme finito e R una relazione
binaria definita sugli elementi di X. Indichiamo con x,
y, z etc. i generici elementi di X. R è
detta ordinamento parziale sugli elementi di X se è:

• riflessiva, cioè xRx
  per ogni x  X;

• antisimmetrica, cioè
  xRy e yRx valgono assieme se e solo
  se x = y;

• transitiva, cioè ogni volta che xRy e
  yRz si ha anche xRz.

Poset

Siano X un insieme finito e R una relazione
d’ordine parziale sugli elementi di X. La coppia
P = (X, R) è allora detta
insieme finito parzialmente ordinato o poset.

      Per esempio,
P = ({1, 2, 3, 4}, ) è un poset la cui relazione d’ordine definisce una
struttura di ordinamento totale (cioè, dati due qualsiasi elementi
x e y di X vale sempre almeno una tra
xRy e yRx).

Copertura

Sia P = (X, R) un poset e
siano x, y e z elementi di X. Si dice che
y è una copertura di x, se si ha
xRy e non esiste alcun elemento z tale che
xRz e zRy.

      In altri termini,
y è una copertura di x se xRy e non
esiste alcun elemento z che si “frapponga” nella relazione di
ordinamento tra x e y. Costruiamo per esempio un poset definendo
sull’insieme {1, 2, 3, 4, 5, 6, 7, 8} la
relazione xRy <==> x divide
y. Allora:

• 8 è una copertura di 4;
• 4 è una copertura di 2;

• 8 non è una copertura di 2 perché,
  nonostante che 2R8, esiste l’elemento 4 che si frappone tra 8 e 2 nella
  relazione di ordinamento parziale.

Diagramma di Hasse

Il diagramma di Hasse consente di rappresentare graficamente
la relazione d’ordine tra gli elementi di un poset ed è costruito nel
modo seguente:

1. se x e y sono elementi di X e
   xRy, allora x è collocato nel diagramma al
   di sotto di y;

2. si disegna nel diagramma un segmento tra x e
   y se e solo se y è una copertura di x.

Il diagramma di Hasse consente di identificare la relazione
di ordinamento parziale perché illustra graficamente la chiusura
transitiva della relazione di copertura.

Esempio

Usiamo le definizioni date per costruire il diagramma di
Hasse del poset costituito dall’insieme potenza di {1, 2, 3} e dalla
relazione di sottoinsieme ““. Iniziamo
scrivendo l’insieme X, potenza dell’insieme {1, 2, 3},
ricordando che esso ha per elementi tutti i sottoinsiemi di
{1, 2, 3} (compresi l’insieme vuoto e l’insieme {1, 2, 3}
stesso):

      X = 2^{1,2,3} = {, {1}, {2}, {3}, {1, 2}, {2,
3}, {1, 3}, {1, 2, 3}}

Dimostriamo quindi che P è un poset. Si
verifica facilmente che la relazione definisce un ordinamento parziale:
infatti la relazione di sottoinsieme è:

• riflessiva: per ogni A  {1, 2, 3} si ha per forza
  A  A, e questo equivale
  proprio a dire che xRx per ogni x  X;

• antisimmetrica: dire che x e y sono
  due elementi di X tali che xRy e
  yRx significa parlare di due sottoinsiemi A e
  B di {1, 2, 3} tali che A  B e B  A. Questo può avvenire
  solamente se A = B, cioè se
  x = y.

• transitiva: dire che x, y e z
  sono elementi di X tali che xRy e
  yRz significa parlare di tre sottoinsiemi A,
  B e C di {1, 2, 3} tali che A  B e B  C. Ma allora
  A  C, cioè
  xRz.

Costruiamo ora il diagramma di Hasse del poset P.
Dovremo prima di tutto collocare in qualche posizione tutti gli elementi di
X, cioè tutti i possibili sottoinsiemi di {1, 2, 3},
seguendo la regola 1; decideremo poi quali di questo unire con segmenti
seguendo la regola 2. Le regole viste in precedenza si traducono così:

1. l’insieme A appare al di sotto dell’insieme B se e solo se
   A  B;

2. A e B sono uniti da un segmento se e soltanto se B
   è una copertura di A, cioè se e soltanto se non ci sono
   insieme C contenuti propriamente in B e contenenti propriamente
   A, cioè se e soltanto se B si ottiene a partire da
   A aggiungendo un solo elemento dell’insieme {1, 2, 3} non
   contenuto in A (lasciamo al lettore la verifica di quest’ultima
   affermazione).

Il grafico risultante è quindi il seguente:

Diagramma di Hasse di 2^{1,2,3} (fonte)

Notiamo che, per esempio, il grafico non contiene l’arco
{1}–-{1, 2, 3} perché {1, 2, 3} contiene {1}, ma
non ne è una copertura: esistono infatti altri due elementi {1, 2}
e {1, 3} che si frappongono tra i due nella relazione di inclusione
all’interno del poset P.

      Affermavamo che il
diagramma di Hasse consente di visualizzare graficamente la relazione di
ordine parziale in termini della chiusura transitiva della relazione di
copertura: è infatti sufficiente seguire gli archi tra gli elementi per
determinare tutte le coppie possibili della relazione di inclusione. In
particolare, è piuttosto semplice riconoscere il tipo di ordinamento
che caratterizza il poset, perché il diagramma di Hasse assume
struttura lineare nel caso di ordinamento totale e non lineare nel caso di
ordinamento parziale.

      Ricordiamo che, come
già accennato in precedenza, una relazione binaria R
sull’insieme X è detta ordinamento totale (o lineare) se
(X, R) è un poset e se per ogni coppia x,
y di elementi in X esiste in P almeno una delle due
relazioni xRy e yRx. Un esempio di
ordinamento totale è il poset
P = ({1, 2, 3, 4}, ): al lettore l’esercizio di disegnarne il diagramma di
Hasse e di verificarne la struttura lineare.