4.3 Aritmetica[0NN]
Definiremo l’operazione di addizione fra numeri naturali, formalmente
\[ ⋅+⋅ : ℕ×ℕ→ℕ \quad ,\quad (h,k)↦ h+k \quad . \]
Definizione
11
Questa operazione è commutativa e associativa, come mostrato sotto.
Notiamo che \(h+0=f_ h(0)=h\) (base della ricorsione); inoltre \(0+n=f_ 0(n)=n\) (si mostra facilmente per induzione).
Per dimostrare che è commutativa, mostriamo innanzitutto che
Lemma
12
Proposizione
13
A questo punto possiamo dare un nome a \(1=S(0)\) e notare che \(S(n)=n+1\). Dunque da ora in poi potremmo fare a meno del simbolo \(S\).
Con simili procedure si dimostra che l’addizione è associativa.
Proposizione
14
Analogamente si definisce la moltiplicazione.
Definizione
15
Esercizi
Nel seguito scriveremo semplicemente \(nm\) invece di \(n× m\).