Teorema di ricorsione

Sia $X$ un insieme non vuoto. Sia $h:\mathbb{N}\times X\to X$ e sia $c\in X$.
Esiste ed è unica una funzione $f:\mathbb{N}\to X$ t.c.

1. $f(0)=c$
2. $f(succ(n))=h(n,f(n))\mathrm{\forall }n\in \mathbb{N}$
3. $f(1)=h(0,c)$
4. $f(2)=h(1,f(1))=h(1,h(0,c))$

Applicazione del teorema di ricorsione

Sia $n\in \mathbb{N}$
Definiamo la "funzione somma sulla sinistra con m" ovvero "$\mathbb{N}\to \mathbb{N}$", $n\to m+n$.
Poniamo

• $X:=\mathbb{N}$
• $c_i=?$ formalizzare il seguente concetto: $c="f(0)=m+n")$
• $h:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$
  $(a,b)⟼succ(n)$
  $m+succ(n)=h(n,m+n)$
  $m+(n+1)$
  $h(a,b):=succ(b)$
  Grazie al teorema di ricorsione esiste unica
  $f:\mathbb{N}\to \mathbb{N}$ t.c. $f(0)=m,f(succ(n))=h(n,f(n))=succ(f(n))\mathrm{\forall }n\in \mathbb{N}$
  $f(n)=m+nm+0=m$
  $m+succ(n)=succ(m+n)\mathrm{\forall }n\in \mathbb{N}$

Esercizio

Trovare $X(=\mathbb{N}),c(=0),h$ che sostituiti nel teorema di ricorsione, formalizzino la seguente intuizione:
$\mathbb{N}\to \mathbb{N}$
$n\to m\times n(m\in \mathbb{N}fissato)$

Esercizio 3.1

$0+n=n$
$1+n=n+1$
dove $1:=succ(0)$

Osservazione

$n+1=succ(n)\mathrm{\forall }n\in \mathbb{N}$

Ordinamento dei numeri naturali

Definizione

Definizione

$\mathrm{\forall }n,m\in \mathbb{N}$, poniamo:

Proposizione 3.5

$(\mathbb{N},\le )$ è un insieme totalmente ordinato

Esercizio 3.3

Dimostrare che $n,m,k\in \mathbb{N},$

1. $n\le m$ e $k\le n⟹n+k\le m+h$
2. $n\le m$ e $k\le n⟹nk\le mh$