La divisibilità è un ordine parziale

Testo

Per $a,b \in \mathbb{N}$ diciamo che $a \mid b$ (a divide b) se esiste $k \in \mathbb{N}$ con $b = ak$. Dimostra che $(\mathbb{N}, \mid)$ è un insieme parzialmente ordinato, ma non totalmente ordinato.

Soluzione

Verifichiamo le tre proprietà di un ordine parziale.

• Riflessiva: $a = a \cdot 1$, quindi $a \mid a$.
• Antisimmetrica: se $a \mid b$ e $b \mid a$ con $a,b \in \mathbb{N}$, allora $b = ak$ e $a = bh$, da cui $a = akh$. Se $a \ne 0$ segue $kh = 1$, cioè $k = h = 1$ e $a = b$; se $a = 0$ allora $b = 0$. In ogni caso $a = b$.
• Transitiva: se $a \mid b$ e $b \mid c$, allora $b = ak$ e $c = bh = a(kh)$, quindi $a \mid c$.

Dunque $(\mathbb{N},\mid)$ è un ordine parziale. Non è totale: ad esempio $2$ e $3$ non sono confrontabili, perché $2 \nmid 3$ e $3 \nmid 2$. $\blacksquare$

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Divisibilita · Ordine parziale · Relazione d ordine
Competenze: Dimostrare
Tipo di esercizio: Dimostrazione