4.4 Ordinamento[27K]

Ipotesi 143

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

\begin{align} ∀ x ∈ℕ , & (0≤ x) \quad , \label{eq:caratt_ le_ N_ 0} \\ ∀ x,y ∈ℕ , & (x{\lt} Sy) \iff (x ≤ y ) \quad ; \label{eq:caratt_ le_ N} \end{align}

dove (come al solito)

\[ x{\lt}y ≐ (x≤ y)∧ (x≠ y)\quad . \]
Teorema 146

[26Y] Vi è una unica relazione d’ordine \(≤\) su \(ℕ\) tale che ??,?? in 143 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 4.5; oppure l’ordinamento si può definire usando l’aritmetica, come mostrato in Sezione ??.

E146

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

E146

[271]Sia

\[ P_ x =\{ z∈ ℕ, z{\lt} x\} \]

mostrate che

\[ ∀ x,y∈ ℕ~ ,~ P_ x = P_ y ⇒ x=y \]

usando le proprietà nell’Ipotesi 143.

Soluzione nascosta: [UNACCESSIBLE UUID ’272’]

(Notate la somiglianza con 7).

E146

[276]Impostando \(n=x=y\) in ?? otteniamo che \(n{\lt}Sn\).

E146

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

\[ ∀ n,m∈ ℕ, (n{\lt} m ) ⇒ (Sn{\lt} Sm)\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’278’]

E146

[26X]Se \(⪯\) è un ordinamento totale su \(ℕ\) allora sono equivalenti

\begin{align} ∀ x,y∈ ℕ , & (x⪯ y⪯ Sx ) ⇒ (x=y∨ y=Sx)\quad ,\label{eq:caratt_ le_ N_ mid}\\ ∀ x,y ∈ℕ , & (x≺ Sy) \iff (x ⪯ y ) \quad ; \\ ∀ x,y ∈ℕ , & (x≺ y) \iff (Sx ⪯ y ) \quad . \label{eq:caratt_ le_ N_ alt} \end{align}

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 150

[288] Dati \(n,m∈ ℕ\), si dirà che \(n≤ m\) se esiste \(k∈ℕ\) tale che \(n+k=m\)

Mostreremo che \(≤\) è una relazione di ordine totale, che è un buon ordinamento. Vediamo innanzitutto alcune proprietà elementari ma fondamentali.
Lemma 151

[289] Siano \(n,m,k∈ℕ\).

  1. Per ogni \(n\) si ha \(0\le n\)

  2. \(n≤ m\) se e solo se \(n{\lt} S(m)\).

    Notate che questi due punti soddisfano ??,?? in 143

  3. Per ogni \(n\) si ha \(n{\lt}S(n)\)

  4. \(n{\lt}m\) se e solo se \(S(n)≤ m\).

  5. Se \(n≤ m ≤ 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 152

[28B] \(≤\) è 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 “\(\le \)” definita in 150 soddisfa la regola 143; mostreremo che ogni tale ordinamento è un buon ordinamento; qui presentiamo comunque una dimostrazione per questo caso particolare.

Proposizione 153

[28Z] \(≤\) è una relazione di ordine totale.

Prova ▼

Si considera la proposizione

\[ P(n)≐ ∀ m∈ℕ, n≤ m ∨ m≤ n \]

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

  • se \(m≤ n\) allora \(m≤ S(n)\) per il lemma (punto 2), così \(P(Sn)\) vale;

  • se \(¬ m≤ n\) ma \(P(n)\) vale, allora \(n≤ m\), ma non potendo essere \(n=m\), si ottiene \(n{\lt}m\), che comporta \(S(n)≤ m\) per il lemma (punto 4);

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

Proposizione 154

[297] \(≤\) è un buon ordinamento.

Prova ▼

Traccia della dimostrazione. Per il Lemma 151 (punto 2) sappiamo che questo ordinamento soddisfa il principio forte di induzione 158; 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 155 Sottrazione

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

E155

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

E155

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

E155

[28N] Mostrate che se \(n≠ 0\) allora \(n× m≥ m\). Soluzione nascosta: [UNACCESSIBLE UUID ’28P’]

E155

[28J] Argomenti:Divisione con resto.

Dimostrate che, dati \(d,n∈ℕ,d≥ 1\) esistono e sono unici due numeri \(q,r∈ℕ,0≤ r {\lt} d\) per cui \(n=q×d +r\) (dove \(n\) è il “dividendo” \(d\) è il “divisore” , \(q\) è il “quoziente” e \(r\) è il “resto”) Soluzione nascosta: [UNACCESSIBLE UUID ’28K’]

E155

[28M] (Replaces 282)

Sia \(h≠ 0\), dimostrate che se \(n× h= m× h\) allora \(n= m\). (Sugg. usate la sottrazione)

Soluzione nascosta: [UNACCESSIBLE UUID ’28S’]

In particolare la mappa \(n\mapsto n× h\) è iniettiva.

Ordinamento e aritmetica[28Q]

L’ordinamento è compatibile con l’aritmetica.

Proposizione 156

[28R]

  • (Compatibilità di addizione e ordinamento) Si ha \(n≤ m\) se e solo se \(n+k≤ m+k\).

  • (Compatibilità di moltiplicazione e ordinamento) Quando \(k≠ 0\) si ha \(n≤ m\) se e solo se \(n× k≤ m× k\).

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

Prova ▼

Useremo alcune proprietà lasciate per esercizio.

  • Se \(n≤ m\), per definizione \(m=n+h\), allora \(n+k≤ m+k\) in quanto \(m+k=n+h+k\) (notate che stiamo usando l’associatività). Se \(n+k≤ 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≤ m\) allora \(m=n+h\) dunque \(m× k=n× k+h× k\) così \(n× k≤ m× k\). Viceversa sia \(k≠ 0\) e sia \(n× k≤ m× k\) cioè \(n× k + j= m× k\): dividiamo \(j\) per \(k\) usando la divisione con resto 4, scriviamo \(j=q× k + r\) dunque per associatività \((n+q)× k + r= m× k\), ma per unicità della divisione con resto \(r=0\): infine raccogliendo \((n+q)× k = m× k\) e usando 5 concludiamo che \((n+q) = m\).