Teorema di ricorsione

Sia X un insieme non vuoto. Sia h:Nร—Xโ†’X e sia cโˆˆX.
Esiste ed รจ unica una funzione f:Nโ†’X t.c.

  1. f(0)=c
  2. f(succ(n))=h(n,f(n))ย โˆ€nโˆˆ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โˆˆN
Definiamo la "funzione somma sulla sinistra con m" ovvero "Nโ†’N", nโ†’m+n.
Poniamo

Esercizio

Trovare X(=N),c(=0),h che sostituiti nel teorema di ricorsione, formalizzino la seguente intuizione:
Nโ†’N
nโ†’mร—nย (mโˆˆNย fissato)

Esercizio 3.1

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

Osservazione

n+1=succ(n)ย โˆ€nโˆˆN

Ordinamento dei numeri naturali

Definizione

ordinamento parziale

Sia X un insieme non vuoto e sia R una relazione binaria su X (cioรจ RโŠ‚Xร—X).
Si dice che R รจ un ordinamento parziale di X se

  1. xย Rย xย ย โˆ€xโˆˆX (riflessiva)
  2. (xย Rย x)ย eย (yย Rย x)โŸนx=y (antisimmetrica)
  3. (xย Rย x)ย eย (yย Rย z)โŸนxย Rย z (transitiva)

Se in aggiunta vale la seguente proprietร  (tricotomica), allora si dice che R รจ un ordinamento totale di X.

  1. โˆ€xโˆˆX,ย xย Rย y vera oppure yย Rย X vera

Usualmente si utilizza R=โ‰ค
Se โ‰ค รจ un ordinamento parziale di X, (X,โ‰ค) si dice insieme parzialmente ordinato.
Se โ‰ค รจ un ordinamento totale di X, (X,โ‰ค) si dice insieme totalmente ordinato.

Definizione

โˆ€n,mโˆˆN, poniamo:

nโ‰คmย ย seย โˆƒย kโˆˆNย t.c.ย m=n+k

Proposizione 3.5

(N,โ‰ค) รจ un insieme totalmente ordinato

Esercizio 3.3

Dimostrare che n,m,kโˆˆN,

  1. nโ‰คm e kโ‰คnโŸนn+kโ‰คm+h
  2. nโ‰คm e kโ‰คnโŸนnkโ‰คmh