Relazioni d'ordine

Note

Una relazione si dice d'ordine se è riflessiva, transitiva e antisimmetrica. Solitamente si utilizzano il simbolo al posto di , e scriviamo o al posto di .

Se una relazione d'ordine soddisfa (cioè e ) sono confrontabili, allora si dice totale. Se per certi elementi non vale tale relazione allora si dicono non confrontabili. In quel caso si dice poset (Partially Ordered Set).

Diagramma di Hasse di un poset

Note

Il diagramma di Hasse è un modo per rappresentare graficamente un poset. Si costruisce in questo modo:

  1. Nel grafo di adiacenza del poset considero solo gli archi con (di copertura)
  2. Oriento gli archi inserendo sopra, sotto, e rimuovendo la freccia.

Pasted image 20241009151156.png

Tip

Dati , si dice che copre se e .

Tip

Dato un diagramma di Hasse è possibile ricostruire la relazione d'origine che lo genera.

Massimi e minimi

Note

Sia un poset. Un elemento può essere definito come:

Il minimo (o massimo) è rispettivamente minimale (o massimale), e se esiste è unico. Se esiste il minimo (o massimo) non esistono altri minimali (o massimali). Infine se è finito, e ha un solo minimale (o massimale) allora è minimo (o massimo).

Minoranti e Maggioranti

Note

Sia e sia . Un elemento si dice maggiorante o minorante di se:

Inoltre definiamo e :

Infine definiamo l'estremo inferiore e superiore di :

Date queste definizioni possiamo definire un reticolo come un poset in cui: