Relazioni d'ordine, totale e parziale

L’altra grande famiglia di relazioni utili è quella dell’ordine: ci permette di dire ”$a$ viene prima di $b$”. La proprietà chiave è l’antisimmetria: se $a\le b$ e $b\le a$ allora $a=b$ (al posto della simmetria delle equivalenze).

Definizione — Ordine totale e parziale

Una relazione $R$ su $A$ è una relazione d’ordine (parziale) se è riflessiva, antisimmetrica e transitiva. Si dice d’ordine totale se in aggiunta, per ogni $a,b\in A$, vale $a\mathbin{R} b$ oppure $b\mathbin{R} a$ (ogni coppia è confrontabile). Altrimenti l’ordine si dice parziale.

Esempio — Ordine totale su $\mathbb{R}$

La relazione $\le$ su $\mathbb{R}$ è di ordine totale: dati due reali, sai sempre qual è il più piccolo. La retta è un’immagine fisica dell’ordine totale, in cui ogni punto è confrontabile con ogni altro.

Esempio — Ordine parziale: "divide" su $\mathbb{N}$

Su $\mathbb{N}=\{1,2,3,\ldots\}$ poniamo $a\preceq b$ se $a$ divide $b$ (cioè $b=ka$ per qualche $k\in\mathbb{N}$).

• Riflessiva: $a$ divide $a$.
• Antisimmetrica: se $a\mid b$ e $b\mid a$ (con $a,b>0$) allora $a=b$.
• Transitiva: se $a\mid b$ e $b\mid c$ allora $a\mid c$.

Però $2$ non divide $3$ e $3$ non divide $2$: le coppie di “primi diversi” non sono confrontabili. È un ordine parziale.

Esempio — Ordine parziale: inclusione $\subseteq$ tra insiemi

La relazione "$A\subseteq B$" sull’insieme delle parti $\mathcal{P}(X)$ è un ordine parziale. Per esempio $\{1\}\subseteq\{1,2\}$, ma $\{1\}$ e $\{2\}$ non sono confrontabili.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Inclusione · Ordine parziale · Ordine totale · Relazione d ordine