4.2 Definizione per ricorrenza [274]

Teorema 134

[08Z]

Sia \(A\) un insieme non vuoto; sia \(a∈ A\) fissato, siano date funzioni \(g_ n:A→ A\) per ogni \(n∈ℕ\). Allora esiste ed è unica la funzione \(f:ℕ→ A\) tale che

  • \(f(0)=a\), e

  • per ogni \(n∈ℕ\) si ha \(f(S(n))=g_ n(f(n))\).

Si dice che la funzione \(f\) è definita per ricorrenza dalle due precedenti condizioni.

Prova ▼

[090] Traccia della dimostrazione. Notate che la dimostrazione usa solo gli assiomi di Peano e il principio di induzione. Dato \(m∈ℕ,m≠ 0\) ricordiamo che \(S^{-1}(m)\) è il precedessore, si veda 131 (usando l’aritmetica potremmo scrivere

\[ S^{-1}(m)=m-1 ~ ~ ,~ ~ S(k) = k+1 \]

ma questo teorema è usato nel definire l’aritmetica...) Data una qualunque \(R⊆ ℕ× A\) definiamo la proiezione sulla prima componente

\[ 𝜋(R)=\{ n∈ℕ,∃ x∈ A, (n,x)∈ R \} ~ . \]

Consideriamo la famiglia \({\mathcal F}\) delle relazioni \(R⊆ ℕ× A\) che soddisfano

\begin{equation} (0,a)∈ R \tag {*} \end{equation}
135

\begin{equation} ∀ n≥ 0,∀ y∈ A,~ ~ (n,y)∈ R⇒ (S(n),g_ n(y))∈ R \tag {**} \end{equation}
136

Mostriamo che sotto queste condizioni \(𝜋(R)=ℕ\); sappiamo che \(0∈ 𝜋(R)\); se \(m\in 𝜋(R)\), allora esiste \(x∈ A\) per cui \((m,x)∈ R\) ma allora da ** segue che \((S(m),g_{m}(x))∈ R\), e otteniamo \(S(m)∈ 𝜋(R)\).

La famiglia \({\mathcal F}\) è non vuota perché \(ℕ× A∈ {\mathcal F}\). Sia poi \(T\) l’intersezione di tutte le relazioni in \({\mathcal F}\). \(T\) è dunque la minima relazione in \({\mathcal F}\).

Si può verificare che \(T\) soddisfa le precedenti proprietà * e **. In particolare \(𝜋(T)=ℕ\).

Dobbiamo ora mostrare che \(T\) è il grafico di una funzione (che è la funzione \(f\) desiderata), cioè che per ogni \(n\) esiste un unico \(x∈ A\) per cui \((n,x)∈ T\).

Sia \(A_ n=\{ x∈ A, (n,x)∈ T \} \); scriviamo \(|A_ n|\) per indicare il numero di elementi in \(|A_ n|\); siccome \(𝜋(T)=ℕ\) allora \(|A_ n|≥ 1\) per ogni \(n\). Mostreremo che \(|A_ n|=1\) per ogni \(n\). Lo dimostreremo per induzione. Sia

\[ P(n) \doteq |A_ n| = 1\quad . \]

Verifichiamo il passo induttivo.

Supponiamo per assurdo che \(|A_{m}|=1\) ma \(|A_{Sm}|≥ 2\); moralmente in \(m\) il grafico della \(f\) “biforca” e la funzione diventa “multivoca”. Definiamo per comodità \(w=g_{m}(x),k=Sm\); potremmo togliere alcuni elementi a \(T\) (quelli che non hanno un “predecessore” secondo la relazione **) definendo

\[ \tilde T=T⧵ \{ (k,y) : y∈ A, y≠ w \} \]

si mostra che \(\tilde T\) soddisfa * e **, ma \(\tilde T\) sarebbe più piccola di \(T\), contro la minimalità di \(T\). Per provare che \(P(0)\), si definisce \(k=0,w=a\) e si procede allo stesso modo.

Il precente ragionamento mostra anche che la funzione è unica, perché se il grafico \(G\) di una qualsiasi funzione soddisfacente a * e ** deve contenere \(T\), allora \(T=G\).

Più in generale date \(g_ n:A^{n+1}→ A\), si mostra che esiste ed è unica la funzione \(f:ℕ→ A\) tale che \(f(0)=a\) e per ogni \(n∈ℕ\) si ha \(f(S(n))=g_ n(f(0),f(1),\ldots f(n))\).

E136

[1X7]Prerequisiti:134.Adattate l’esercizio 134 per definire la successione di Fibonacci, che soddisfa alla regola

\[ a_ 0=1\quad ,\quad a_ 1=1\quad ,\quad a_ n=a_{n-1}+a_{n-2} \]

per \(n≥ 2\).

Sugg. Non dovete riscrivere tutta la dimostrazione di 134, piuttosto scegliete \(A=ℕ^ 2\) e scegliete \(g\) con astuzia.

Soluzione nascosta: [UNACCESSIBLE UUID ’1X8’]

E136

[294]Definite l’intervallo di numeri naturali

\[ I_ n = \{ 0,\ldots n\} \]

usando una definizione ricorsiva (senza fare uso di una relazione d’ordine)

Soluzione nascosta: [UNACCESSIBLE UUID ’295’]