Relazioni d'ordine

Note

Una relazione $R\subseteq A\times A$ si dice d’ordine se è riflessiva, transitiva e antisimmetrica. Solitamente si utilizzano il simbolo $\le$ al posto di $R$, e scriviamo $a\le b$ o $(a,b)\in \le$ al posto di $aRb$.

Se una relazione d’ordine $\le \subseteq A\times A$ soddisfa $\forall a,b\in Aa\le b\text{ o }b\le a$ (cioè $a$ e $b$) sono confrontabili, allora $\le$ 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 $\le$ considero solo gli archi con $a\le b$ (di copertura)
2. Oriento gli archi inserendo $b$ sopra, $a$ sotto, e rimuovendo la freccia.

Tip

Dati $b,a\in A$, si dice che $b$ copre $a$ se $a\le b$ e $\nexists c\in A\setminus \{a,b\}:a\le c\le c$.

Tip

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

Massimi e minimi

Note

Sia $(A,\le )$ un poset. Un elemento $a\in A$ può essere definito come:

|

$$\text{Massimo}$$

  	   |
  	   $$
  	   \text{Minimo}
  	   $$
  	   			   |
  	   			   $$
  	   			   \text{Minimale}
  	   			   $$
  	   			   								|
  	   			   								$$
  	   			   								\text{Massimale}
  	   			   								$$
  	   			   															   |

| -------------------------------- | ------------------------------- | -------------------------------------------------- | -------------------------------------------------- | |

$$\forall x\in Aa\le x$$

|

$$\forall x\in Ax\le a$$

|

$$\forall x\in Ax\le a⟹x=a$$

|

$$\forall x\in Aa\le x⟹x=a$$

   |

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 $A$ è finito, e ha un solo minimale (o massimale) allora è minimo (o massimo).

Minoranti e Maggioranti

Note

Sia $(A,\le )$ e sia $B\subseteq A$. Un elemento $m\in A$ si dice maggiorante o minorante di $B$ se:

|

$$\text{Maggiorante}$$

|

$$\text{Minorante}$$

| | - | - | |

$$\forall x\in Bx\le m$$

|

$$\forall x\in Bm\le x$$

|

Inoltre definiamo $M(B)$ e $m(B)$:

$$\begin{array}{rl}M(B)& =\{m\in A:m\text{ maggiorante di }B\}\\ m(B)& =\{m\in A:m\text{ minorante di }B\}\end{array}$$

Infine definiamo l’estremo inferiore e superiore di $B$:

$$\begin{array}{rl}\sup (B)& =\min (M(B))\\ \min (B)& =\max (m(B))\end{array}$$

Date queste definizioni possiamo definire un reticolo come un poset $(A,\le )$ in cui:

$$\forall a,b\exists \inf (\{a,b\})\exists \{a,b\}$$