EDB — 090

[090] Traccia della dimostrazione. Notate che la dimostrazione usa solo gli assiomi di Peano e il principio di induzione. Dato $m\in \mathbb{N},m\ne 0$ ricordiamo che $S^{-1}(m)$ è il precedessore, si veda [1YP]↺↻ (usando l’aritmetica potremmo scrivere

ma questo teorema è usato nel definire l’aritmetica...) Data una qualunque $R\subseteq \mathbb{N}\times A$ definiamo la proiezione sulla prima componente

Consideriamo la famiglia $\mathcal{F}$ delle relazioni $R\subseteq \mathbb{N}\times A$ che soddisfano

Mostriamo che sotto queste condizioni $𝜋(R)=\mathbb{N}$; 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 $\mathcal{F}$ è non vuota perché $\mathbb{N}\times A\in \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)=\mathbb{N}$.

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)=\mathbb{N}$ allora $|A_n|\ge 1$ per ogni $n$. Mostreremo che $|A_n|=1$ per ogni $n$. Lo dimostreremo per induzione. Sia

Verifichiamo il passo induttivo.

Supponiamo per assurdo che $|A_m|=1$ ma $|A_{Sm}|\ge 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

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$.