L’insieme dei numeri naturali naturali è un insieme N che

3.5. GLI ASSIOMI DI PEANO. DEFINIZIONE INSIEMISTICA . . . 181

N1. N è costituito da un elemento, denotato con 0, e da almeno un altro elemento diverso da 0; sia M il s.i. (proprio) di N costituito da tutti gli elementi diversi da 0.

N2. Esiste una biiezione di N su M , f : N −→ M . N3. Ogni sottoinsieme S di N tale che:

(a) 0 ∈ S

(b) f (n) ∈ S ogni qualvolta n ∈ S (n ∈ N), coincide con N. N 3è quindi il cosiddetto postulato di induzione.

Per semplicità possiamo porre f (0) = 1, f (1) = 2, f (2) = 3, . . . quindi l’insieme {0, 1, 2, . . . } è un insieme di numeri naturali e, dato l’assioma N 3, coincide con N.

Inoltre, ∀n ∈ N, f (n) prende il nome di successore di n; poichè f è una biiezione, 0 non è successore di alcun numero (che è quanto afferam il III assioma di Peano). Ancora dal fatto che f è una biiezione segue

f (n) = f (m) ⇒ n = m

(cioè il IV postulato).

Il postulato di induzione (N3) (che equivale a quanto stabilito dal V. as-sioma di Peano) permette di dimostrare il primo ed il secondo principio di induzione matematica; questi vengono applicati nelle cosiddette dimostra-zioni per induzione.

Proposizione 3.5.2 (Primo principio di induzione matematica). Sia A un

insieme di affermazioni (enunciati) ciascuna delle quli può essere vera o falsa (ma non entrambe) ed esista un’applicazione suriettiva g : N −→ A. Posto g(n) = An∈ A, se

1) A0è vera, e

2) A_{f (n)}è vera ogniqualvolta Anè vera, allora Anè vera per ogni n ∈ N.

Dimostrazione. Sia V = {m ∈ N : Amè vera}. Per la 1), 0 ∈ V , dato che A0

è vera; inoltre, f (n) ∈ V ogniqualvolta n ∈ V , per la 2). Segue allora da N 3 che V = N.

Enunceremo e proveremo in seguito il secondo principio di induzione matematica, in quanto è opportuno introdurre prima le consuete operazio-ni di + e · su N; ciò verrà fatto utilizzando quella che prende il nome di definizione ricorsiva. Precisamente, si dice che una proprietà (nozione, con-cetto, ecc.) è definita ricorsivamente se quale che sia il naturale n, essa è definita per f (n) ogniqualvota è definita per n.

Introdurre le operazioni di + e · su N a questo punto, senza aver prima definito, in generale, cosa si intenda per operazione su un insieme, sembra poco opportuno. Pertanto, rinviamo la trattazione al cap. II, dove ver-ranno anche provate rigorosamente le ben note proprietà delle operazioni suddette e verrà introdotto in maniera formale il consueto ordinamento naturale, ≤, su N, che già è stato utilizzato. Comunque, faremo ancora uso di questa relazione d’ordine e delle sue proprietà ben note in alcune delle considerazioni che seguono.

Diamo ora un esempio di applicazione del primo principio di indu-zione matematica, provando che la somma sndei primi n termini di una progressione geometrica < a1, a2, . . . , an, · · · >di ragione q è data da

sn= a1 1 − qⁿ 1 − q ^; si ha s₁ = a₁^{1 − q} 1 − q ^{= a1,} onde s1è vera

(per quanto osservato, si può partire da 1 invece che da 0 nel postulato di induzione).

Proviamo che snvera ⇒ sn+1vera:

s_n+1= s_n+ a_n+1= s_n+ a₁qⁿ= a₁^{1 − q} n 1 − q ^{+ a1q} n= = a1 1 − qⁿ+ qⁿ(1 − q) 1 − q ^{= a1} 1 − qⁿ⁺¹ 1 − q

(si ricordi che, per definizione di progressione geometrica, a2 = a1q, a3 = a₂q = a₁q², . . .).

Come altro esempio di applicazione del principio di induzione matema-tica, proviamo che la somma, sn, dei primi n numeri naturali (zero escluso) è data da s_n= ^{n(n + 1)} 2 ^. Si ha s1 = ^{1 · 2} 2 = 1, onde s1è vera. Proviamo che snvera ⇒ sn+1vera.

In base alla definizione, si ha:

sn+1= sn+ (n + 1) = ^{n(n + 1)} 2 ^{+ n + 1 =} n(n + 1) + 2(n + 1) 2 ⁼ = ^{(n + 1)(n + 2)} 2 ^,

3.5. GLI ASSIOMI DI PEANO. DEFINIZIONE INSIEMISTICA . . . 183

Infine, come altro esempio, dimostriamo che la somma dei primi n nu-meri dispari, cioè degli elementi dell’insieme A = {1, 3, 5, . . . , 2n−1} è data da

sn= n².

Si osservi innanzitutto che l’insieme A si può anche scrivere come

A = {2k − 1 : k ∈ n}.

Si ha quindi

s₁ = 1² = 1 (= 2 · 1 − 1),

onde s1 è vera (dato che la somma del solo primo elemento dell’insieme dato è l’elemento stesso).

Si deve provare che

sk= k² vera ⇒ sk+1 = (k + 1)²vera.

Si ha:

sk+1= sk+ 2(k + 1) − 1 = sk+ 2k + 1 = k²+ 2k + 1 = k²+ 2k + 1 = (k + 1)²

cioè l’asserto.

Osserviamo che l’assioma N 3 si può anche enunciare nella forma se-guente: Sia S un s.i. dell’insieme N dei naturali, tali che

1) 1 ∈ S;

2) n ∈ S ⇒ f (n) ∈ S

allora S = N.

Qualora si ammetta come noto il buon ordinamento di N, si può di-mostrare che tale principio è conseguenza del fatto che l’insieme N è ben ordinato (cfr. n. ?? ed es. ??) ed in questo ordine il principio di induzione matematica si generalizza nel cosidetto

Principio di induzione transfinita: Sia A un insieme ben ordinato e sia S un s.i. di A con le seguenti proprietà:

1) a0 ∈ S, a₀essendo il primo elemento di A;

2) s(a) ∈ S ⇒ a ∈ S, dove s(a) = {x ∈ A : x < a} è il segmento iniziale di a.

Allora S = A.

Dimostrazione. Supponiamo che sia S 6= A, quindi A \ S = T 6= ∅. Poichè A è ben ordinato, T ha un primo elemento, sia esso t0. Se consideriamo s(t₀), ciascun x ∈ s(t0) precede t0 e, pertanto, non può appartanere a T , quindi appartiene ad S. Ne segue che s(t0) ⊂ S. Per la 2), t0 ∈ S. Ciò non

contraddice t0 ∈ A \ S, onde l’affermazione S 6= A non è vera; ne segue S = A. Si noti che la 1) è, di fatto, conseguenza della 2), dato che ∅ = s(a0) è un s.i. di S e perciò a0 ∈ S.

Analogamente si generalizza la nozione di successore immediato: un elemento b di un insieme ben ordinato A si dice successore immediato di a ∈ A(ed a si dice predecessore immediato di b) se a < b e non esiste alcun x ∈ A tale che a < x < b. (Si confronti con la nozione di copertura in un insieme parzialmente ordinato, data nel n.??).

Osserviamo che nell’insieme Q dei numeri razionali nessun elemento ha un successore (o predecessore) immediato; infatti

a, b ∈ Q, a < b ⇒ ^{a + b}

2 ∈ Q e a < ^{a + b} 2 ^{< b.}

Invece ogni elemento, tranne l’ultimo, di un insieme ben ordinato ha un successore immediato. Tale affermazione non è però vera per i predecessori immediati; infatti, esistono elementi di un insieme ben ordinato, oltre al primo, che non hanno un predecessore immediato. Ad esempio, siano

D = {1, 3, 5, 7, . . . } e P = {2, 4, 6, . . . }

rispettivamente gli insiemi ben ordinati dei dispari e dei pari. Definiamo

{D, P} = {1, 3, 5, . . . ; 2, 4, 5, . . . },

cioè {D, P} è D ∪ P ordinato parzialmente da sinistra a destra ed ogni ele-mento di D precede ogni eleele-mento di P (elementi nello stesso insieme con-servano il medesimo ordine); 1 e 2,allora, non hanno predecessori imme-diati.

Non intendiamo approfondire altre questioni legate a quanto detto, stan-ti i limistan-ti che ci siamo proposstan-ti.

Passiamo dunque all’introduzione dei numeri naturali per via insimie-stica.

Consideriamo pertanto l’insieme vuoto e poniamo (simbolicamente):

0 = ∅.

Ricordando poi che {∅} contiene un solo oggetto, poniamo

1 = {∅} = {0}(usando il simbolo già introdotto);

di conseguenza chiameremo

3.5. GLI ASSIOMI DI PEANO. DEFINIZIONE INSIEMISTICA . . . 185

e quindi, in maniera analoga

3 = {0, 1, 2}

4 = {0, 1, 2, 3} · · ·

n = {0, 1, 2, 3, . . . , n − 1}.

Ne segue che ogni naturale n si identifica con l’insieme {0, 1, . . . , n − 1} dei naturali che lo precedono.

Tenendo presente una terminologia già introdotta, possiamo identifica-re n con il segmento iniziale di n (il che è lecito in quanto N è ben ordinato), cioè

n = s(n) = {x ∈ N : x < n}.

In questo modo ogni naturale si identifica con un numero cardinale fini-to, precisamente con quello dell’insieme che lo definisce (ovvero del suo segmento iniziale); in altri termini ha significato la