: Definizione per ricorrenza <a class="btn btn-sm" href="/UUID/EDB/274/?lang=ita"><span class="ttfamily"><small class="scriptsize">[274]</small></span></a>

3.2 Definizione per ricorrenza [274]

Teorema 133

Sia $A$ un insieme non vuoto; sia $a \in A$ fissato, siano date funzioni $g_{n} : A \to A$ per ogni $n \in ℕ$ . Allora esiste ed è unica la funzione $f : ℕ \to A$ tale che

$f (0) = a$ , e
per ogni $n \in ℕ$ 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 \in ℕ, m \neq 0$ ricordiamo che $S^{- 1} (m)$ è il precedessore, si veda 130 (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 \subseteq ℕ \times A$ definiamo la proiezione sulla prima componente

𝜋 (R) = {n \in ℕ, \exists x \in A, (n, x) \in R} .

Consideriamo la famiglia $F$ delle relazioni $R \subseteq ℕ \times A$ che soddisfano

\begin{matrix} (*) & (0, a) \in R \end{matrix}

134

\begin{matrix} (**) & \forall n \geq 0, \forall y \in A, (n, y) \in R \Rightarrow (S (n), g_{n} (y)) \in R \end{matrix}

135

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

La famiglia $F$ è non vuota perché $ℕ \times A \in F$ . Sia poi $T$ l’intersezione di tutte le relazioni in $F$ . $T$ è dunque la minima relazione in $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 \in A$ per cui $(n, x) \in T$ .

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

P (n) ≐ | A_{n} | = 1 .

Verifichiamo il passo induttivo.

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

\tilde{T} = T ⧵ {(k, y) : y \in A, y \neq 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} \to A$ , si mostra che esiste ed è unica la funzione $f : ℕ \to A$ tale che $f (0) = a$ e per ogni $n \in ℕ$ si ha $f (S (n)) = g_{n} (f (0), f (1), \dots f (n))$ .

E135

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

a_{0} = 1, a_{1} = 1, a_{n} = a_{n - 1} + a_{n - 2}

per $n \geq 2$ .

Sugg. Non dovete riscrivere tutta la dimostrazione di 133, piuttosto scegliete $A = ℕ^{2}$ e scegliete $g$ con astuzia.

Soluzione nascosta: [UNACCESSIBLE UUID ’1X8’]

E135

[294]Definite l’intervallo di numeri naturali

I_{n} = {0, \dots n}

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

Soluzione nascosta: [UNACCESSIBLE UUID ’295’]