I naturali come insieme definito induttivamente

• i naturali sono l'insieme induttivo per eccellenza
• Base: 0 appartiene ai naturali
• Passo: se n è appartiene ai naturali allora anche n+1 appartiene ai naturali,
• Chiusura: nient'altro appartiene ai naturali

Principio di induzione sui naturali

• Per ogni fbf P(n), se valgono:
• Base: P(0)
• Passo: ∀n(P(n)→P(n+1))
• Allora ∀nP(n)

Ricorsione strutturale sui naturali

• Definire una funzione per ricorsione sul suo primo argomento
• Base: ∀y1...∀y(n-1) f(0, y1,...,y(n-1)) = g(y1, ..., y(n-1))
• Passo: ∀y1...∀y(n-1)∀n f(n+1, y1,...y(n-1)) = h(n, y1, ..., y(n-1), f(n, y1, ..., y(n-1)))

Esempio