: Ordinamento<a class="btn btn-sm" href="/UUID/EDB/27K/?lang=ita"><span class="ttfamily"><small class="scriptsize">[27K]</small></span></a>

3.4 Ordinamento[27K]

Ipotesi 142

[26H] Studieremo una relazione d’ordine (possibilmente parziale) $\leq$ su $ℕ$ tale che

\begin{aligned} \forall x \in ℕ, & (0 \leq x), \\ \forall x, y \in ℕ, & (x < S y) ⟺ (x \leq y); \end{aligned}

dove (come al solito)

x < y ≐ (x \leq y) \land (x \neq y) .

Teorema 145

[26Y] Vi è una unica relazione d’ordine $\leq$ su $ℕ$ tale che ??,?? in 142 valgano, e questo è un buon ordinamento.

Questo teorema sarà dimostrato in seguito: unicità in 1, buon ordinamento in 3. L’esistenza di una tale relazione deriva dal modello Z-F, come visto in precedenza e ricapitolato in Sezione 3.5; oppure l’ordinamento si può definire usando l’aritmetica, come mostrato in Sezione ??.

E145

[267]Supponiamo che $\leq$ sia una relazione di ordine (possibilmente parziale) su $ℕ$ soddisfacente 142 allora $\leq$ è unico. Soluzione nascosta: [UNACCESSIBLE UUID ’270’]

E145

[271]Sia

P_{x} = {z \in ℕ, z < x}

mostrate che

\forall x, y \in ℕ, P_{x} = P_{y} \Rightarrow x = y

usando le proprietà nell’Ipotesi 142.

Soluzione nascosta: [UNACCESSIBLE UUID ’272’]

(Notate la somiglianza con 7).

E145

[276]Impostando $n = x = y$ in ?? otteniamo che $n < S n$ .

E145

[277]Prerequisiti:3,142.Usando le proprietà in 142 e assumendo che $\leq$ sia una relazione d’ordine totale (come effettivamente dimostreremo), mostrate che

\forall n, m \in ℕ, (n < m) \Rightarrow (S n < S m) .

Soluzione nascosta: [UNACCESSIBLE UUID ’278’]

E145

[26X]Se $⪯$ è un ordinamento totale su $ℕ$ allora sono equivalenti

\begin{aligned} \forall x, y \in ℕ, & (x ⪯ y ⪯ S x) \Rightarrow (x = y \lor y = S x), \\ \forall x, y \in ℕ, & (x ≺ S y) ⟺ (x ⪯ y); \\ \forall x, y \in ℕ, & (x ≺ y) ⟺ (S x ⪯ y) . \end{aligned}

Notate l’analogia con 3

Soluzione nascosta: [UNACCESSIBLE UUID ’296’]

[UNACCESSIBLE UUID ’293’]

Ordinamento dall’aritmetica[287]

Avendo già definito l’aritmetica, una definizione comoda di ordinamento è come segue.

Definizione 149

[288] Dati $n, m \in ℕ$ , si dirà che $n \leq m$ se esiste $k \in ℕ$ tale che $n + k = m$

Mostreremo che

\leq

è una relazione di ordine totale, che è un buon ordinamento. Vediamo innanzitutto alcune proprietà elementari ma fondamentali.

Lemma 150

[289] Siano $n, m, k \in ℕ$ .

Per ogni $n$ si ha $0 \leq n$
$n \leq m$ se e solo se $n < S (m)$ .

Notate che questi due punti soddisfano ??,?? in 142
Per ogni $n$ si ha $n < S (n)$
$n < m$ se e solo se $S (n) \leq m$ .
Se $n \leq m \leq S (n)$ allora $m = n$ oppure $m = S (n)$ .

Le dimostrazioni sono lasciate per esercizio 1. (Una volta dimostrato che la relazione è totale, allora per 5 le ultime due sono equivalenti).

Proposizione 151

[28B] $\leq$ è una relazione di ordine.

Prova ▼

Proprietà riflessiva: $n + 0 = n$ . Proprietà antisimmetrica: se $n + k = m$ e $m + h = n$ allora $n + k + h = n$ dunque per eliminazione 3 $h + k = 0$ , e per 4 $h = k = 0$ così $n = m$ . Proprietà transitiva: se $n + k = m$ e $m + h = p$ allora $n + k + h = p$ .

[298]Dunque questa relazione “ $\leq$ ” definita in 149 soddisfa la regola 142; mostreremo che ogni tale ordinamento è un buon ordinamento; qui presentiamo comunque una dimostrazione per questo caso particolare.

Proposizione 152

[28Z] $\leq$ è una relazione di ordine totale.

Prova ▼

Si considera la proposizione

P (n) ≐ \forall m \in ℕ, n \leq m \lor m \leq n

Si ha che $P (0)$ è vera. Diamo per vera $P (n)$ ; prendiamo un $m$ ;

se $m \leq n$ allora $m \leq S (n)$ per il lemma (punto 2), così $P (S n)$ vale;
se $\neg m \leq n$ ma $P (n)$ vale, allora $n \leq m$ , ma non potendo essere $n = m$ , si ottiene $n < m$ , che comporta $S (n) \leq m$ per il lemma (punto 4);

in ogni caso $P (S (n))$ è dimostrata partendo da $P (n)$ .

Proposizione 153

[297] $\leq$ è un buon ordinamento.

Prova ▼

Traccia della dimostrazione. Per il Lemma 150 (punto 2) sappiamo che questo ordinamento soddisfa il principio forte di induzione 157; così possiamo provare (come in Esercizio 2) che ogni sottoinsieme non vuoto ha un elemento minimale; ma sappiamo che l’ordinamento è totale, dunque l’elemento minimale è il minimo.

Definizione 154 Sottrazione

[28C] Se $m \geq n$ , esiste ed è unico $h$ tale che $m = n + h$ (l’unicità segue da 3); indicheremo questo $h$ come $m - n$ .

E154

[28D] Mostrate le proprietà in 150. Soluzione nascosta: [UNACCESSIBLE UUID ’28F’]

E154

[28G]Mostrate che se $n \leq m$ allora $m - n \leq m$ . Soluzione nascosta: [UNACCESSIBLE UUID ’28H’]

E154

[28N] Mostrate che se $n \neq 0$ allora $n \times m \geq m$ . Soluzione nascosta: [UNACCESSIBLE UUID ’28P’]

E154

[28J] Argomenti:Divisione con resto.

Dimostrate che, dati $d, n \in ℕ, d \geq 1$ esistono e sono unici due numeri $q, r \in ℕ, 0 \leq r < d$ per cui $n = q \times d + r$ (dove $n$ è il “dividendo” $d$ è il “divisore” , $q$ è il “quoziente” e $r$ è il “resto”) Soluzione nascosta: [UNACCESSIBLE UUID ’28K’]

E154

[28M] (Replaces 282)

Sia $h \neq 0$ , dimostrate che se $n \times h = m \times h$ allora $n = m$ . (Sugg. usate la sottrazione)

Soluzione nascosta: [UNACCESSIBLE UUID ’28S’]

In particolare la mappa $n \mapsto n \times h$ è iniettiva.

Ordinamento e aritmetica[28Q]

L’ordinamento è compatibile con l’aritmetica.

Proposizione 155

[28R]

(Compatibilità di addizione e ordinamento) Si ha $n \leq m$ se e solo se $n + k \leq m + k$ .
(Compatibilità di moltiplicazione e ordinamento) Quando $k \neq 0$ si ha $n \leq m$ se e solo se $n \times k \leq m \times k$ .

In particolare (ricordando 5) la mappa $n \mapsto n \times h$ è strettamente crescente (e dunque iniettiva).

Prova ▼

Useremo alcune proprietà lasciate per esercizio.

Se $n \leq m$ , per definizione $m = n + h$ , allora $n + k \leq m + k$ in quanto $m + k = n + h + k$ (notate che stiamo usando l’associatività). Se $n + k \leq m + k$ sia allora $j$ l’unico naturale tale che $n + k + j = m + k$ ma allora $n + j = m$ per eliminazione 3.
Se $n \leq m$ allora $m = n + h$ dunque $m \times k = n \times k + h \times k$ così $n \times k \leq m \times k$ . Viceversa sia $k \neq 0$ e sia $n \times k \leq m \times k$ cioè $n \times k + j = m \times k$ : dividiamo $j$ per $k$ usando la divisione con resto 4, scriviamo $j = q \times k + r$ dunque per associatività $(n + q) \times k + r = m \times k$ , ma per unicità della divisione con resto $r = 0$ : infine raccogliendo $(n + q) \times k = m \times k$ e usando 5 concludiamo che $(n + q) = m$ . □