Assiomi di Peano sui numeri naturali

Assiomi di Peano sui numeri naturali

∈ 1. Esiste un numero naturale 0 N.

2. Ogni numero naturale ha un successore.

3. Numeri diversi hanno successori diversi.

4. 0 non è successore di nessuno.

5. Principio di induzione.

Principio di induzione

Richiede un passo base ed un passo induttivo:

Per i numeri naturali: sia A sottoinsieme di N;

• Passo base: 0 appartiene ad A;
• Passo induttivo: dando per vero che n appartiene ad A, n+1 appartiene ad A (implicato). Di conseguenza, tutte le volte che n appartiene ad A, anche n+1 appartiene ad A, la tesi è che A è uguale all’insieme dei numeri naturali.

Forma equivalente

Se P(0) è vera e P(n) è vera (quindi ciò implica che P(n+1) è vera), allora P(n) è vera per ogni n appartenente a N. Se per un certo n appartenente ad A, allora 0A = {n appartenente a N : n maggiore o uguale di n}

0 va sostituito n+1 ad n nella dimostrazione.

Esempio

[ ]n ( )n n+1 = ∑ k 2k=0

• Passo base: n=0, unico indice, risultato = 0.
• Passo induttivo: supponiamo sia vera la formula, il risultato di n+1 dovrà essere:

[ ]( )( )n+1 n+22

Dimostrando verrà:

[ ] [ ]n+1 n ( ) ( ) ( )n n+1 n+1 n+2∑ ∑ +( )= +n+1=k= k n+1 2 2k=0 k=0

Si è sostituito n+1 a k nell’aggiungerlo alla dimostrazione. Dato che il risultato ottenuto è uguale a quello aspettato, la successione è dimostrata.