4.3 Aritmetica[0NN]

Definiremo l’operazione di addizione fra numeri naturali, formalmente

\[ ⋅+⋅ : ℕ×ℕ→ℕ \quad ,\quad (h,k)↦ h+k \quad . \]

Definizione 137

[292]Fissato il parametro \(h∈ ℕ\) cominciamo col definire l’operazione \(h+⋅\) che sarà una funzione \(f_ h : ℕ→ℕ \) data da \(f_ h(n)=h+n\); per la definizione ricorsiva vorremo esprimere le regole

  • \( h+0=h\) ,

  • \(∀ n∈ ℕ, h+S(n)=S(h+n)\) .

A questo scopo, poniamo \(A=ℕ\), e \(g(n,a)=S(a)\), riscriviamo le precedenti come regole ricorsive per \(f_ h\)

  • \( f_ h(0)=h\) ,

  • \(∀ n∈ ℕ, f_ h(S(n))=g(n,f_ h(n))=S(f_ h(n))\) .

questo definisce ricorsivamente \(f_ h\). Considerando poi il parametro \(h\) come una variabile, abbiamo costruito l’operazione di addizione, e definiamo l’operazione “+” fra naturali come \(h+n=f_ h(n)\).

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 138

[27N](Svolto il 2022-11-03) \(∀ n,h∈ ℕ, f_{S(h)}(n)=S(f_ h(n))\)

Prova ▼

Ricordiamo che \(S(f_ h(n))=f_ h(S(n))\) per definizione ricorsiva; consideriamo

\[ P(n)≐ ∀ h∈ ℕ, f_{S(h)}(n)=S(f_ h(n))\quad ; \]

\(P(0)\) è la proposizione

\[ ∀ h∈ ℕ, f_{S(h)}(0)=S(f_ h(0))=S(h) \]

che è vera perché è il valore iniziale della definizione ricorsiva di \(f_{S(h)}\) e di \(f_ h\); per il passo induttivo assumiamo che \(P(n)\) sia vera e studiamo \(P(S(n))\) al cui interno possiamo dire

\begin{eqnarray*} f_{S(h)}(S(n)) \stackrel{(1)}{=} S(f_{S(h)}(n)) \stackrel{(2)}{=}\\ SS(f_ h(n)) \stackrel{(3)}{=} S(f_{h}(S(n)) \end{eqnarray*}

dove in (1) abbiamo usato la definizione ricorsiva di \(f_ h\) con \(S(h)\) invece di \(h\), in (2) abbiamo usato la ipotesi induttiva, e in (3) la definizione ricorsiva di \(f_ h\); e questo completa il passo induttivo.

(Notate come nel primo passaggio è importante che nella definizione di \(P(n)\) vi sia \(∀ h∈ ℕ,\ldots \)).

Proposizione 139

[27P](Replaces 27Y) L’addizione è commutativa.

Prova ▼

Per il lemma possiamo scrivere

\begin{equation} S(h) + n = S(h+n)= h + S(n)\label{eq:Shn_ hSN} \end{equation}
140

intuitivamente la formula è simmetrica e dunque anche la definizione di addizione deve avere una simmetria. Precisamente, sia \(\tilde f_ n(h){\stackrel{.}{=}}f_ h(n)\) allora \(\tilde f_ n(0)=n\) (come già notato) e per il lemma 138 \(\tilde f_ n(S(h))=S\Big(\tilde f_ n(h)\Big)\) ma allora \(\tilde f\) soddisfa la stessa relazione ricorsiva di \(f\) e dunque sono identiche, così \(f_ h(n)=f_ n(h)\). (L’idea è che se avessimo definito la addizione ricorsivamente partendo da sinistro invece che da destra, avremmo raggiunto lo stesso risultato).

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 141

[27Q]L’addizione è associativa.

Prova ▼

Consideriamo

\[ P(h)≐ ∀ n,m∈ ℕ, (n+m)+h = n+ (m+h)\quad ; \]

ovviamente \(P(0)\) è vera, inoltre \(P(Sh)\) si dimostra (omettendo “\(∀ n,m∈ ℕ\)”) così

\begin{align*} (n+m)+Sh = S(n+m)+h = (Sn + m) + h \stackrel{P(n)}{=}\\ = Sn + (m + h) = n+ S (m+h)= n+ (m+Sh)\quad \qedhere \end{align*}

Analogamente si definisce la moltiplicazione.

Definizione 142

[28V](Svolto il 2022-11-03) Si fissa il parametro \(m\), e si definisce ricorsivamente \((m× ⋅)\) tramite

  • \( m× 0=0\)

  • \(∀ n∈ ℕ, m× (n+1)=m× n + m\);

poi si possono dimostrare le note proprietà (commutatività, associatività, distributività).

E142

[27R]Riscrivete alcune nozioni viste prima, quale il principio di induzione, e la definizione dell’addizione, usando \(n+1\) invece di \(S(n)\).

E142

[27S] (Svolto il 2022-11-03) Mostrate che la funzione \(f_ h(n)=(h+n)\) è iniettiva. Soluzione nascosta: [UNACCESSIBLE UUID ’27T’]

E142

[27V] Dimostrate la proprietà di eliminazione: se \(n+h=m+h\) allora \(n=m\).

Soluzione nascosta: [UNACCESSIBLE UUID ’286’]

E142

[27W] (Svolto il 2022-11-03) Si ha \(n+m=0\) se e solo se \(n=0∧ m=0\). Soluzione nascosta: [UNACCESSIBLE UUID ’285’]

E142

[27X] (Svolto il 2022-11-03) Si ha \(n× m=0\) se e solo se \(n=0∨ m=0\). Soluzione nascosta: [UNACCESSIBLE UUID ’284’]

E142

[28T]Dimostrate che la moltiplicazione è commutativa. Sugg. dimostrate per induzione in \(n\)

\[ \forall m,n∈ ℕ , (m+1)\times n=m\times n + n\quad , \]

dopodiché ragionate come in Prop. 139. Soluzione nascosta: [UNACCESSIBLE UUID ’28W’]

E142

[281]Dimostrate che l’addizione distribuisce rispetto alla moltiplicazione. Sugg. dimostrate per induzione in \(h\)

\[ ∀ m,n,h∈ ℕ,~ m× (n+h)=m× n + m× h\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’28Y’]

E142

[27Z]Prerequisiti:7.Dimostrate che la moltiplicazione è associativa. Sugg. dimostrate per induzione in \(n\)

\[ ∀ m,n,h ∈ ℕ, (m× n)× h =m× (n× h)\quad . \]

Soluzione nascosta: [UNACCESSIBLE UUID ’28X’]

E142

[280] Dati \(n≠ 0\) e \(h∈ℕ\) scrivete una definizione ricorsiva dell’elevamento a potenza \(n^ h\); indi dimostrate che \(n^{h+k}=n^ nn^ k\) e \((n^ h)^ k=n^{(hk)}\).

Soluzione nascosta: [UNACCESSIBLE UUID ’2DG’]

Nel seguito scriveremo semplicemente \(nm\) invece di \(n× m\).