Vai al contenuto
Topos Uranos
Italiano

Operazioni di base sui numeri naturali e relazioni d’ordine

Riepilogo

Questa lezione definisce la somma, il prodotto e la potenza di numeri naturali a partire dal successore degli assiomi di Peano, con il teorema di ricorsione, che garantisce che le definizioni ricorsive determinano un’unica operazione; ne ammette la parte di esistenza, ne dimostra per induzione la parte di unicità e deduce le proprietà delle operazioni: commutatività, associatività, distributività e cancellazione. Definisce poi la relazione d’ordine mediante la somma, con le sue proprietà di tricotomia, transitività e monotonia, e le operazioni inverse, la sottrazione e la divisione, insieme alle condizioni in cui esistono. Il principio di induzione è lo strumento di tutte le dimostrazioni.

Obiettivi di apprendimento

  1. Enunciare il teorema di ricorsione e scrivere con esso le definizioni ricorsive della somma, del prodotto e della potenza di numeri naturali.
  2. Dimostrare per induzione proprietà delle operazioni a partire dalle loro definizioni.
  3. Definire l’ordine dei naturali mediante la somma e applicarne le proprietà di tricotomia, transitività e monotonia.
  4. Riconoscere quando esistono la sottrazione e la divisione di due naturali, e operare con esse senza uscire dai naturali.

La somma

Le operazioni con i numeri naturali sono note fin dalla scuola; qui si tratta di fondarle con precisione matematica. Nella lezione sugli assiomi di Peano i naturali sono stati definiti a partire dall’11 e dall’operazione successore, che associa a ogni naturale nn il seguente, S(n)S(n). La somma si definisce a partire dal successore mediante due regole: sommare 11 è prendere il successore, e sommare il successore di mm è prendere il successore della somma con mm.

n+1=S(n),n+S(m)=S(n+m)n + 1 = S(n), \qquad n + S(m) = S(n + m)

Una definizione di questo tipo si dice ricorsiva: la prima regola fissa il valore per 11 e la seconda riconduce ogni caso al precedente. Ora, che due regole siffatte definiscano davvero un’operazione racchiude due affermazioni distinte: che esiste una funzione che le soddisfa per tutti i naturali (esistenza) e che non ci sono due funzioni distinte che le soddisfino (unicità). Entrambe formano il teorema di ricorsione, dovuto a Dedekind: questo corso ammette la parte dell’esistenza, come si spiega dopo il riquadro, e dimostra quella dell’unicità. Lo si enuncia in una forma generale perché serva anche al prodotto, alla potenza e alle definizioni ricorsive delle lezioni seguenti.

Fatto ammesso (teorema di ricorsione). Siano XX un insieme e cc un elemento di XX, e supponiamo data, per ogni naturale nn, una regola gng_n che associa a ogni elemento di XX un elemento di XX. Allora esiste una funzione ff da N\mathbb{N} in XX tale che f(1)=cf(1) = c e f(S(n))=gn(f(n))f(S(n)) = g_n(f(n)) per ogni naturale nn, e tale funzione è unica.

L’esistenza si ammette in questo corso senza dimostrazione. La sua dimostrazione richiede di costruire la funzione ff come un insieme di coppie: il più piccolo insieme di coppie che contiene (1,c)(1, c) e che, con ogni coppia (n,x)(n, x), contiene (S(n),gn(x))(S(n), g_n(x)); e di verificare poi, per induzione, che a ogni naturale corrisponde in esso un unico secondo elemento. Tale costruzione appartiene alla teoria degli insiemi e non aggiunge nulla all’aritmetica che segue. L’unicità, invece, è una conseguenza diretta del quinto assioma di Peano.

LemmaUnicità della funzione definita per ricorsione

Se due funzioni ff e hh da N\mathbb{N} in XX soddisfano le due condizioni del teorema di ricorsione, allora sono uguali. La figura rappresenta i valori di entrambe sui primi naturali.

Dimostrazione

  1. A={n∈N:f(n)=h(n)}\dato{A}{A = \{ n \in \mathbb{N} : f(n) = h(n) \}}

    Sia AA l’insieme dei naturali in cui le due funzioni coincidono. Basta provare che AA è l’insieme di tutti i naturali.

  2. f(1)=c=h(1)f(1) = \resaltar{c} = h(1)

    L’11 appartiene ad AA, perché entrambe le funzioni valgono cc in 11.

  3. f(S(k))=gk(f(k))=gk(h(k))=h(S(k))f(S(k)) = g_k(\resaltar{f(k)}) = g_k(\resaltar{h(k)}) = h(S(k))

    Se kk appartiene ad AA, vi appartiene anche S(k)S(k): entrambe le funzioni applicano la stessa regola gkg_k allo stesso valore.

  4. A=N,(∀n∈N) (f(n)=h(n))A = \mathbb{N}, \quad (\forall n \in \mathbb{N})\,(f(n) = h(n))

    Per il quinto assioma di Peano, AA è l’insieme di tutti i naturali: le due funzioni sono uguali.

La somma si ottiene dal teorema fissando il primo addendo nn e prendendo X=NX = \mathbb{N}, c=S(n)c = S(n) e, per ogni mm, la regola gmg_m che associa a ogni naturale il suo successore: la funzione ff fornita dal teorema è quella che associa a ogni mm il numero n+mn + m, e le due regole della somma sono le due condizioni del teorema. Allo stesso modo, con c=nc = n e la regola che somma nn, si ottiene il prodotto, e con c=bc = b e la regola che moltiplica per bb, la potenza. Sommare mm equivale, in definitiva, ad applicare mm volte il successore.

EsempioDue più due fa quattro

L’affermazione più nota dell’aritmetica è un teorema che si dimostra con le due regole della somma e i nomi 2=S(1)2 = S(1), 3=S(2)3 = S(2) e 4=S(3)4 = S(3).

Dimostrazione

  1. 2+2=2+S(1)2 + 2 = 2 + S(1)

    Scriviamo il secondo addendo come successore di 11.

  2. 2+S(1)=S(2+1)2 + S(1) = S(2 + 1)

    Per la seconda regola, sommare un successore è prendere il successore della somma.

  3. S(2+1)=S(S(2))S(2 + 1) = S(S(2))

    Per la prima regola, sommare 11 è prendere il successore.

  4. S(S(2))=S(3)=4S(S(2)) = S(3) = 4

    Poiché S(2)=3S(2) = 3 e S(3)=4S(3) = 4, si ottiene il risultato.

Dalle regole della somma si deducono, per induzione, le sue proprietà. Per tutti i naturali aa, bb e cc:

  1. Commutatività: a+b=b+aa + b = b + a.
  2. Associatività: (a+b)+c=a+(b+c)(a + b) + c = a + (b + c). Per questo si può scrivere a+b+ca + b + c senza parentesi.
  3. Cancellazione: se a+c=b+ca + c = b + c, allora a=ba = b.

La commutatività è stata dimostrata nel problema risolto 5 della lezione sugli assiomi di Peano, e l’associatività vi è uno dei problemi proposti. La cancellazione si dimostra nel problema risolto 1 di questa lezione.