Sebbene le proprietà dei numeri naturali dovrebbero essere intuitivamente già ben note, la loro formalizzazione non è banale. In particolare alcune dimostrazioni risulteranno complicate perché quando dobbiamo dimostrare molti fatti ovvi, bisogna fare attenzione a non utilizzare proprietà che ci risultano ovvie ma che ancora non sono state dimostrate. Per questo motivo è perfettamente legittimo se in prima lettura saltiamo le dimostrazioni per capire il senso generale del discorso e poi, se necessario, torniamo indietro per approfondire i dettagli.
I numeri naturali sono i numeri che utilizziamo per contare o per fare le iterazioni. C’è un primo numero naturale, che per noi sarà , e poi per ogni numero naturale ce n’è uno successivo che chiameremo . Partendo da e passando al successivo si raggiungono tutti i numeri naturali.
Definizione 1.45 (assiomi di Peano). Giuseppe Peano (1858–1932) vedi note storiche a pag. 186 Dato un insieme , un elemento e una funzione diremo che soddisfa gli assiomi di Peano, o più semplicemente che è un insieme di numeri naturali, se valgono le seguenti proprietà: La funzione ci dà il successore di ogni numero. Definiremo , , , …Il primo assioma di Peano dice che numeri diversi hanno numeri successori diversi. Il secondo assioma ci dice che il primo numero naturale, per noi lo , non è il successore di nessun’altro mentre ogni altro numero ne ha uno precedente. Il terzo assioma, il principio di induzione, ci dice che ogni numero naturale può essere raggiunto dallo facendo un numero finito di passaggi al successore.
se e
allora .
D’ora in avanti, quando utilizziamo il simbolo , supporremo sempre che sia un insieme che soddisfa la precedente definizione. Vedremo nel Teorema 1.65 che due diversi insiemi che soddisfano gli assiomi di Peano sono isomorfi, cioè possono essere messi in corrispondenza biunivoca mantenendo la stessa struttura. In questo senso possiamo dire che gli assiomi di Peano caratterizzano univocamente l’insieme dei numeri naturali. Diremo quindi che è l’insieme dei numeri naturali piuttosto che un insieme di numeri naturali.
Dato il numero si chiama il successoresuccessore di . Il numero , che per assioma non è il successore di nessun’altro numero naturale, si chiama zerozero. Per comodità diamo un nome anche alle altre cifre decimali cifre decimaliovvero ai primi numeri naturali (più avanti introdurremo la notazione posizionale per poter rappresentare ogni numero naturale con una sequenza di cifre decimali): e osserviamo che è l’usuale operazione del contare:
I primi due assiomi di Peano (definizione 1.45) servono a garantire che in questo processo del contarecontare troviamo sempre numeri diversi (non si torna mai indietro) in quanto nessun numero può avere come successore o un numero già incontrato in precedenza (che se non è zero è il successore di un altro numero). Questa proprietà è per certi versi paradossale (paradosso di Galileo, o paradosso dell’hotel Hilbert) e per Dedekind è la definizione di insieme infinito (tra poco la andremo a introdurre).Galileo Galilei (1564–1642) vedi note storiche a pag. 186
Gli assiomi della teoria degli insiemi che abbiamo visto nei capitoli precedenti non garantiscono l’esistenza di insiemi infiniti, e dunque se vogliamo garantire che l’insieme dei numeri naturali effettivamente esiste, dobbiamo aggiungere un ulteriore assioma.
Potremmo semplicemente richiedere per assioma che esiste un insieme che soddisfa gli assiomi di Peano 1.45. Ad esempio potremmo richiedere che esista l’insieme degli ordinali di Von Neumann (1.14). Se denotiamo con il predicato allora l’assioma che garantisce l’esistenza dell’insieme degli ordinali finiti può essere scritto nella forma: . La funzione sarebbe quindi .
Ma sembra più naturale richiedere più semplicemente che esista almeno un insieme infinito, vedremo infatti che questo è sufficiente a garantire l’esistenza dell’insieme dei numeri naturali (teorema 1.48, dove si dimostra che ogni insieme infinito contiene un insieme che soddisfa gli assiomi di Peano).
Investighiamo quindi per un attimo cosa significa che un insieme sia infinito. Per dare una definizione indipendente dall’esistenza dei numeri naturali possiamo usare una idea dovuta a Dedekind: un insieme è infinito se può essere messo in corrispondenza biunivoca con un suo sottoinsieme proprio: esiste tale che è iniettiva ma non suriettiva. Intuitivamente questo non può succedere su un insieme finito: se è finito ci aspettiamo che ogni suo sottoinsieme sia strettamente più piccolo di e quindi non possa essere messo in corrispondenza con tutto .
Definizione 1.46 (insieme infinito). Diremo che un insieme è finito (più precisamente: Dedekind-finito) se ogni funzione iniettiva è anche suriettiva. insieme finito
Diremo che un insieme è infinito (più precisamente Dedekind-infinito) se non è finito ovvero se esiste iniettiva ma non suriettiva. insieme infinito
Come abbiamo già osservato gli assiomi di Peano (definizione 1.45) richiedono che la funzione sia iniettiva ma non suriettiva. Risulta quindi che deve essere un insieme infinito.
Ma non si può escludere che tutti gli insiemi siano finiti (e che quindi non esista) se non introduciamo il seguente assioma.
Grazie al precedente assioma il teorema seguente garantisce l’esistenza di un insieme che soddisfa gli assiomi di Peano.
Teorema 1.48 (esistenza dei numeri naturali). Se è un qualunque insieme infinito (definizione 1.46) esistono , e che soddisfano gli assiomi di Peano (definizione 1.45).
Dimostrazione. Se è infinito esiste iniettiva ma non suriettiva. Scegliamo arbitrariamente . Preso un sottoinsieme diremo che è induttivo induttivose . Possiamo quindi definire: Si verifica facilmente che è anch’esso un sottoinsieme induttivo di . Nella definizione 1.27 viene introdotto il simbolo per la restrizione di funzione. Dunque per ogni si ha e quindi possiamo definire come la restrizione di ad : .
Osserviamo quindi che soddisfa gli assiomi di Peano. Il primo assioma è conseguenza dell’iniettività di . Il secondo è verificato per come abbiamo scelto . Per verificare il terzo assioma consideriamo un qualunque insieme tale che e tale che se anche . Per definizione è induttivo e quindi certamente visto che , per come è definito, è sottoinsieme di ogni insieme induttivo. □
La costruzione precedente ci dice che l’insieme è il più piccolo insieme infinito nel senso che: se è infinito allora contiene una copia isomorfa di . Grazie al teorema 1.30, potremmo dire che se abbiamo due insiemi che soddisfano gli assiomi di Peano, essendoci una immersione iniettiva di ognuno nell’altro (teorema 1.48), allora esiste una corrispondenza biunivoca tra i due insiemi. Nel teorema 1.65 vedremo che non solo esiste una corrispondenza biunivoca ma anche che esiste una tale corrispondenza che preserva la struttura (cioè l’operazione e l’elemento ).
L’ultimo degli assiomi di Peano ci dice che se un sottoinsieme dei numeri naturali contiene lo zero e contiene il successore di ogni suo elemento, allora contiene tutti i numeri naturali. Serve a garantire che il processo del contare esaurisca tutti i numeri naturali, e che quindi non ci siano dei naturali irraggiungibili partendo da zero. Questa proprietà viene usualmente utilizzata mediante il seguente.
Formalmente dovremmo dire che è una funzione da in dove , sono due valori distinti che interpretiamo come vero e falso. Infatti il concetto di predicato non è definito all’interno del sistema formale, ma è un concetto esterno. Ma è ovvio che ad ogni predicato corrisponde una funzione e viceversa.
Dimostrazione. Consideriamo l’insieme . Grazie alle ipotesi del teorema possiamo applicare la terza proprietà dei numeri naturali per dedurre che . Dunque è soddisfatta per ogni . □
Tramite il principio di induzione è anche possibile definire funzioni (o operazioni) per induzione. Grazie al seguente teorema 1.50, se vogliamo definire una funzione basterà dichiarare il valore di e definire (cioè in funzione di . Questo metodo per definire una funzione si chiama definizione ricorsiva (o per ricorrenza) in quanto definisce il valore della funzione sul termine -esimo ricorrendo al valore assegnato sui termini precedenti.
Teorema 1.50 (definizione per induzione). Sia un insieme, sia e sia una funzione. Allora esiste una unica funzione tale che Si avrà dunque Più in generale se abbiamo e una funzione esisterà una unica funzione tale che
Dimostrazione. Dobbiamo ricordarci che le funzioni non sono altro che relazioni e cioè sottoinsiemi del prodotto . Le proprietà (1.19) si scrivono dunque nella forma e (se allora ). L’idea è quindi di prendere il più piccolo sottoinsieme di che possa rappresentare una funzione con le proprietà richieste. Consideriamo dunque la famiglia di insiemi: Chiaramente non è vuota in quanto . Possiamo dunque farne l’intersezione e definire un insieme : L’insieme che abbiamo definito rappresenta una relazione tra e . Visto che per ogni dovrà essere . Inoltre se allora per ogni e quindi per ogni da cui . Significa che .
Vogliamo ora dimostrare che è una funzione, cioè che è univocamente definita su tutto . Per prima cosa consideriamo l’insieme su cui è definita e cioè e dimostriamo, per induzione, che . In effetti quindi . E se sappiamo che esiste tale che e dunque, essendo , anche da cui . Abbiamo dimostrato che è definita su tutto .
Dimostriamo ora che è univoca. Consideriamo l’insieme su cui è univocamente definita: . Di nuovo vogliamo dimostrare per induzione che . Per dimostrare che , visto che già sappiamo che , dobbiamo dimostrare che se si ha . Sia dunque e consideriamo l’insieme . Chiaramente in quanto visto che e inoltre se allora e quindi . Ma certamente in quanto dunque . Visto che si deve avere e dunque . Dunque è univocamente definita in .
Dobbiamo ora mostrare che se anche . Se significa che c’è un unico tale che . Certamente anche . Prendiamo allora , vorremo dimostrare che . Consideriamo, similmente a prima, l’insieme e cerchiamo di dimostrare che . Chiaramente perché e non può essere in quanto . Se ora supponiamo che sia certamente sarà e dunque : dobbiamo mostrare che . D’altra parte se fosse dovrebbe essere in quanto è iniettiva. Ma visto che è univocamente definita su dovrà allora essere anche e quindi . Dunque e . Ma allora e quindi . Significa che è univocamente definita anche in . Per induzione ed è una funzione .
Ovviamente visto che sappiamo che soddisfa le proprietà richieste dal teorema.
Nella seconda parte del teorema, dove , possiamo considerare l’insieme e la funzione definita da . Allora applicando la prima parte possiamo trovare tale che e . Basterà prendere come la seconda componente di . □
Teorema 1.51 (addizione su ). addizioneSu è definita in modo unico una operazione di addizione che soddisfa le seguenti proprietà:
Questa operazione rende un monoide additivo commutativo con elemento neutro .
Dimostrazione. L’operazione di addizione è univocamente definita grazie al teorema 1.50.
Per dimostrare che è un monoide commutativo dobbiamo verificare che è elemento neutro e che valgono la proprietà associativa e commutativa.
Chiaramente per la definizione (1.21). Verifichiamo ora che anche e lo facciamo per induzione su . Se risulta vero per la definizione. Per quanto riguarda abbiamo per definizione: e per ipotesi induttiva . Dunque , che è quanto volevamo dimostrare.
Verifichiamo la proprietà associativa: , lo facciamo per induzione su . Se allora , per le proprietà precedenti. Per il passo induttivo valutiamo (usando sempre la definizione (1.21)): . L’ipotesi induttiva garantisce che e quindi: che è quanto volevamo dimostrare.
Verifichiamo infine la proprietà commutativa: . Lo facciamo per induzione su . Se è banale per le proprietà dell’elemento neutro. Il passo induttivo risulta immediatamente grazie alla definizione 1.21 e all’ipotesi induttiva: . □
Svolgimento. Ricordiamo che, per definizione (1.18), , , , e . Dobbiamo usare le proprietà e : □
Visto che , potremo in futuro evitare di utilizzare la funzione successore e scrivere direttamente per indicare il successore di .
Abbiamo definito l’addizione come l’iterazione della funzione successore. In generale è possibile definire la moltiplicazione per un numero naturale come una somma ripetuta, e l’elevamento a potenza (con esponente naturale) come una moltiplicazione ripetuta. Questo può essere fatto su come su ogni monoide.
Teorema 1.53 (operazioni iterate). Se è un monoide additivo (definizione 1.32) possiamo definire per induzione la moltiplicazione tra un numero naturale e un elemento del monoide:
Valgono inoltre le seguenti proprietà (valide per ogni e ogni ):
Lo stesso ovviamente si può fare nei monoidi moltiplicativi se definiamo la potenza come prodotto ripetuto: le proprietà sono analoghe:
Dimostrazione. Le proprietà andranno dimostrate per induzione. Facciamo il caso che sia un monoide additivo. La proprietà assorbente è data per definizione, mentre si dimostra immediatamente per induzione, infatti per si ha e il passo induttivo è .
Per la prima proprietà distributiva: è verificato il caso base: . Il passo induttivo diventa: . La seconda per è banale: . Il passo induttivo: .
La proprietà associativa: è ovvia per : . Per il passo induttivo usiamo anche la proprietà distributiva: .
Per quanto riguarda il monoide moltiplicativo le proprietà sono esattamente le stesse, cambia solamente la notazione con cui le scriviamo: al posto della somma su scriviamo un prodotto, e al posto del prodotto scriviamo una potenza. □
Definiamo l’ordinamento di con l’idea che un numero è più grande di se si ottiene aggiungendo qualcosa ad . ordinamento di
Teorema 1.55 (proprietà delle operazioni su ). Le operazioni di addizione, moltiplicazione, elevamento a potenza e l’ordinamento definiti su soddisfano le seguenti proprietà. Proprietà di addizione e moltiplicazione:
proprietà dell’elevamento a potenza:
proprietà di ordinamento:
Dimostrazione. Molte di queste proprietà sono valide in qualunque monoide, e sono già state dimostrate nel teorema 1.53: elemento neutro, elemento assorbente, proprietà associativa, distributiva e tutte le proprietà delle potenze. Che l’addizione sia commutativa e associativa è già stato dimostrato nel teorema 1.51. Dimostriamo le proprietà rimanenti.
Dimostrare la proprietà invariantiva per induzione su . Per la proprietà è banale. Per il passo induttivo osserviamo che se vale allora, grazie all’iniettività di , dovrà essere e per ipotesi induttiva concludiamo come dovevamo dimostrare.
La proprietà è conseguenza della definizione: . La proprietà si può dimostrare per induzione. Se è data per definizione. Per il passo induttivo abbiamo ed essendo per ipotesi induttiva si conclude , che è quanto dovevamo dimostrare.
La proprietà commutativa si può dimostrare facilmente per induzione su . Per è banale, grazie alla proprietà assorbente. Per il passo induttivo osserviamo che e suppendo per ipotesi induttiva che e usando la proprietà distributiva otteniamo: si ottiene che è quanto dovevamo dimostrare.
Per dimostrare l’annullamento del prodotto supponiamo per assurdo che il prodotto di due numeri diversi da possa essere nullo. Un numero naturale diverso da zero è il successore di un altro numero naturale, quindi potremmo scrivere . Ma è il successore di un numero naturale quindi non può essere zero.
vediamo infinite le proprietà dell’ordinamento. Il fatto che dimostra la proprietà riflessiva: .
Per la proprietà transitiva è sufficiente osservare che se e allora .
Per la proprietà antisimmetrica supponiamo di avere e . Deduciamo che da cui . Se fosse o il lato sinistro sarebbe il successore di un numero naturale, ma non è il successore di nessun numero naturale. Questo significa che e quindi , come volevamo dimostrare.
Per mostrare che l’ordinamento è totale dobbiamo invece procedere con una dimostrazione per induzione. Per induzione su vogliamo mostrare che per ogni si ha oppure . Se il fatto è ovvio in quanto e quindi per ogni . Fissati ed , supponiamo ora di sapere che oppure e dimostriamo che allora oppure . Se significa che per un qualche . Ma allora e quindi vale anche . Se invece significa che esiste per cui . Se allora con da cui e dunque anche . Se allora e dunque che ci porta alla disuguaglianza inversa . In ogni caso il passo induttivo è dimostrato.
Dimostriamo ora la monotonia della somma e del prodotto. Sia e sia qualunque. Visto che si ha . Dunque e
Per verificare la monotonia delle potenze procediamo per induzione. Basterà dimostrare che e . Lo facciamo, a loro volta, per induzione: e (supponendo ) □
La proprietà invariantiva ci dice che se esiste tale che allora tale è unico. differenza Dunque se si può definire la differenza come quell’unico tale che .
In maniera analoga se esiste tale che diremo che è un multiplo di multipli e divisoriovvero che divide (si può scrivere ). Diremo che è pari se è divisibile per due, altrimenti diremo che è dispari. Se e allora è unico (lo si verifichi utilizzando la proprietà di annullamento del prodotto) e si chiama quoziente di diviso , scriveremo: .
Si osservi che abbiamo definito per ogni , compreso . Dunque abbiamo consapevolmente definito : questa definizione (controversa) risulterà essere utile. Si noti invece che solo se . Infatti qualunque numero moltiplicato per dà zero, quindi una moltiplicazione ripetuta dà zero se c’è almeno un fattore nullo. Ma nel prodotto ci sono fattori quindi non c’è in effetti nessuna moltiplicazione per . E’ dunque naturale che il risultato sia , l’elemento neutro della moltiplicazione.
Abbiamo già visto che se è un insieme possiamo definire l’insieme delle coppie di elementi di con il prodotto cartesiano tra insiemi: . Cosa rappresenta un prodotto ripetuto? Gli insiemi e non sono uguali, in quanto il primo è un insieme di coppie il cui primo elemento è a sua volta una coppia, il secondo insieme invece è un insieme di coppie il cui secondo elemento è una coppia: Questi insiemi sono molto simili tra loro e potrebbero essere identificati. Un altro insieme molto simile è l’insieme . Usando la definizione di Von Neumann, , l’insieme rappresenta l’insieme di tutte le funzioni . La funzione è univocamente determinata dal suo valore nei tre punti del dominio: , , in quanto . Possiamo quindi identificare con la tripla (o vettore) di valori: I valori , e vengono anche chiamate coordinate o componenti del vettore . coordinate, componenti, vettoreIn effetti l’insieme può essere identificato con , l’insieme sarà l’insieme delle triple di elementi di e in generale se identifichiamo con l’insieme delle -uple (leggi: ennuple) di elementi di : Stiamo qui identificando con l’insieme .
Storicamente ci siamo abituati a contare partendo da invece che da . Per questo motivo è usuale numerare gli elementi di una -upla con gli indici che vanno da a invece che da a . Dunque se sarà usuale scrivere invece che .
Introduciamo ora su il concetto di somma (e prodotto) iterato. Andremo in genera a considerare un qualunque monoide , così le definizioni che daremo saranno utilizzabili su come monoide additivo (e quindi avremo le somme iterate) o come monoide moltiplicativo (così avremo i prodotti iterati). Inoltre la stessa definizione sarà utilizzabile sugli insiemi numerici che ancora non abbiamo definito, come , e .
In generale se è un monoide (definizione 1.32) additivo (o moltiplicativo) possiamo fare somme (o prodotti) di un numero arbitrario (ma finito) di addendi (o fattori) di . Più precisamente se è una -upla di elementi di , vogliamo definirne la somma e il prodotto: In questo ambito è usuale numerare gli elementi della -upla a partire dall’indice invece che dall’indice . Formalmente bisogna dare una definizione per induzione. Basterà dire che la somma (o il prodotto) di zero addendi (o fattori) vale l’elemento neutro dell’operazione cioè per la somma (e per il prodotto). La somma di addendi (o fattori) è la somma dei primi a cui aggiungiamo l’ultimo addendo (o moltiplichiamo per l’ultimo fattore). Formalmente: La variabile che si trova nelle formule (1.22) è muta: al suo posto si può utilizzare qualunque altra variabile che non compaia altrove. Le espressioni che abbiamo scritto dipendono da ma non da .
E’ naturalmente possibile anche fare una somma a partire da un indice diverso da : Dal punto di vista mnemonico abbiamo fatto un cambio di variabile : per si trova e per si trova .
Si osservi che risulta: in quanto la definizione ricorsiva di potenza coincide con la definizione ricorsiva del prodotto di fattori uguali a .
Teorema 1.59. In un monoide additivo commutativo, si ha:
Sia una funzione additiva cioè e . Allora
Infine risulta ovvero
Dimostrazione. Le dimostrazioni possono essere svolte per induzione. □
Il risultato della somma può essere ricordato nel modo seguente: la media di una progressione aritmetica è uguale alla media tra il primo e l’ultimo termine della progressione: .
Svolgimento. Lo dimostriamo per induzione. Per la somma è pari a per definizione. Se la formula è vera per un certo , si ha che è quanto volevamo dimostrare. □
Svolgimento. Vogliamo una formula simile a quelle dimostrate negli esercizi precedenti. Questa volta, però, la formula la dobbiamo trovare noi. Presentiamo un metodo che permette, in generale, di trovare la formula per calcolare se conosciamo la formula per .
Osserviamo che la differenza di due termini cubici consecutivi risulta essere quadratico: Sommando ambo i lati della precedente equazione si ottiene: Al lato destro compare la somma di cui vogliamo calcolare il valore (moltiplicata per ) insieme ad altre due somme di cui sappiamo già il valore. Basterà allora determinare il valore del lato sinistro dove osserviamo che i termini delle due somme si cancellano a vicenda, si chiama somma telescopica in quanto i termini delle due sommatorie si chiudono uno nell’altro come i tubi di un cannocchiale. tranne l’ultimo della prima somma e il primo della seconda: Moltiplichiamo per l’equazione (1.23), mettiamo in evidenza la somma dei quadrati e utilizzando la formula per ottenere:
Esercizio 1.62. Dimostrare che Si può utilizzare il metodo dell’esercizio precedente per trovare una formula esplicita oppure, banalmente, basta verificare per induzione che la formula è valida.
Esercizio 1.63. Si noti che se prendiamo una progressione geometrica (potenze successive con la stessa base) ad esempio: ogni addendo è uguale al precedente moltiplicato per . Dunque se moltiplichiamo per la base l’intera somma si ottiene la somma iniziale con un termine in più alla fine e un termine in meno all’inizio. Anche questa è una somma telescopica Facendo la differenza tutti i termini si cancellano tranne il primo e l’ultimo e possiamo ricavare .
Si formalizzi il ragionamento precedente per dimostrare che fissato si ha per ogni naturale :
Denotiamo con . Se è bigettiva (una tale funzione si chiama permutazionepermutazione) allora si può fare il cambio di variabile : Questa uguaglianza può essere dimostrata facilmente nel caso in cui scambi due soli indici lasciando fissi tutti gli altri (trasposizione) e poi può essere estesa a tutte le permutazioni osservando che ogni permutazione si può scrivere come composizione di trasposizioni.
Questa proprietà è sostanzialmente la proprietà commutativa della somma estesa ad un numero qualunque di addendi. Grazie a questa proprietà possiamo definire la somma di una funzione definita su qualunque insieme finito. Se dove è un monoide, e è una bigezione allora si può definire in quanto la somma sul lato destro non dipende dalla bigezione che abbiamo scelto.
Si faccia riferimento alle definizioni 1.17 per il concetto di minimo, maggiorante e minorante.
Dimostrazione. Osserviamo che se è un minorante di allora o e quindi è il minimo di oppure anche è un minorante di in quanto non ci sono numeri naturali strettamente compresi tra e . Se ci fosse un numero naturale tra e sottraendo avremmo un numero naturale tra e . Ma non esiste tale che . Infatti se , allora e quindi esiste tale che . Ma allora . Dunque se non avesse minimo, per il principio di induzione ogni sarebbe un minorante di . In tal caso dovrebbe essere vuoto perché se esistesse certamente non sarebbe un minorante di . □
Vogliamo ora dimostrare che l’insieme dei numeri naturali è sostanzialmente unico nel senso che se ci sono due insiemi che soddisfano gli assiomi di Peano allora è possibile mettere in corrispondenza gli elementi dei due insiemi in modo che lo zero vada in zero e numeri corrispondenti abbiano successori corrispondenti.
Teorema 1.65 (unicità dei numeri naturali). Se e sono due insiemi che soddisfano gli assiomi di Peano con zero e e funzioni successore su e su allora esiste una funzione bigettiva tale che e .
Dimostrazione. Possiamo definire per induzione: così rimane solo da dimostrare che è una bigezione.
Per dimostrare che è iniettiva consideriamo l’insieme Se tale insieme è vuoto allora è effettivamente iniettiva. Supponiamo allora per assurdo che non sia vuoto. In tal caso possiamo considerare il minimo (grazie al teorema 1.64). Dovrà quindi esistere tale che e . Ovviamente anche e quindi dovrà essere in quanto è il minimo. Dunque e . Se abbiamo e quindi da otteniamo che è nell’immagine di che è contrario agli assiomi di Peano. Se invece si avrà, come per , e dunque . Per l’iniettività di si deduce da cui . Ma questo è assurdo in quanto era il minimo di .
Per dimostrare che è surgettiva consideriamo l’immagine e usiamo il principio di induzione su per dimostrare che . Per prima cosa in quanto . Se poi allora esiste tale che . Ma allora e dunque anche . □
Per rappresentare in modo efficiente qualunque numero naturale utilizziamo la notazione posizionale decimalenotazione posizionale decimale. Ricordiamo che le cifre decimali sono state definite in (1.18) a pag 68. Il numero rappresentato da una sequenza finita di cifre decimali può essere definito ricorsivamente: una sequenza di una sola cifra rappresenta il numero corrispondente alla cifra stessa, una sequenza di cifre rappresenta il numero rappresentato dalle prime cifre, moltiplicato per (cioè dieci), e sommato alla ultima cifra. Ad esempio la sequenza di cifre (leggi: quattromilasettecentouno) è definita così: Osservando che si scriverà:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
| 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | |
| 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 | |
| 4 | 8 | 12 | 16 | 20 | 24 | 28 | 32 | 36 | |
| 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | |
| 6 | 12 | 18 | 24 | 30 | 36 | 42 | 48 | 54 | |
| 7 | 14 | 21 | 28 | 35 | 42 | 49 | 56 | 63 | |
| 8 | 16 | 24 | 32 | 40 | 48 | 56 | 64 | 72 | |
| 9 | 18 | 27 | 36 | 45 | 54 | 63 | 72 | 81 |
Procedendo come nell’esempio 1.52 si può costruire la tabellina della somma, dove sono riportate le somme di tutte le coppie di cifre decimali (tabella 1.4). Sfruttando la definizione e la proprietà distributiva del prodotto (teorema 1.55) non sarà difficile costruire anche la tabellina della moltiplicazione, dove sono riportati i prodotti delle coppie di cifre decimali. Ad esempio una volta dimostrato che si può procedere a dimostrare che come segue:
Una volta imparate a memoria le tabelline è possibile svolgere le operazioni di addizione e moltiplicazione su qualunque coppia di numeri naturali espressi in forma decimale. L’algoritmo è quello della somma e della moltiplicazione in colonna che abbiamo imparato alla scuola elementare. Si può capire la correttezza di questi algoritmi con un esempio. Proviamo a dimostrare che :
Definiamo il fattorialefattoriale di un numero naturale denotato con (leggi: fattoriale) come il prodotto di tutti i numeri naturali da a : La definizione ricorsiva del prodotto permette di definire il fattoriale come segue:
| 0 | 1 | 2 | 3 | 4 | |
| 5 | 6 | 7 | 8 | 9 | |
| 1 | 2 | 4 | 8 | 16 | |
| 32 | 64 | 128 | 256 | 512 | |
| 1024 | 2048 | 4096 | 8192 | 16384 | |
| 32768 | 65536 | 131072 | 262144 | 524288 | |
| 1048576 | 2097152 | 4194304 | 8388608 | 16777216 | |
| 1 | 3 | 9 | 27 | 81 | |
| 243 | 729 | 2187 | 6561 | 19683 | |
| 1 | 1 | 2 | 6 | 24 | |
| 120 | 720 | 5040 | 40320 | 362880 | |
| 3628800 | 39916800 | 479001600 | 6227020800 | 87178291200 | |
| K (chilo) | M (mega) | G (giga) | T (tera) | ||
| P (peta) | E (exa) | Z (zetta) | Y (yotta) | ||
| Ki (chibi) | Mi (mebi) | Gi (gibi) | Ti (tebi) | ||
| Pi (pebi) | Ei (exbi) | Zi (zebi) | Yi (yobi) |
A volte sarà utile considerare anche i prodotti di solamente i numeri pari o i numeri dispari fino ad un certo numero . Questo si chiama semi-fattorialesemi-fattoriale e si indica con Lo possiamo definire separatamente sui numeri pari (cioè i numeri che si possono scrivere nella forma con ) e i numeri dispari (che scriviamo nella forma ):
Osservazione 1.67. Si osservi che risulta mentre Queste formule permettono di esprimere il semi-fattoriale utilizzando il fattoriale intero e le potenze.
Esercizio 1.68. Si dia una definizione per induzione del semi-fattoriale (separatamente per i pari e per i dispari) e si dimostrino, per induzione, le formule nell’osservazione precedente.
Denotiamo con l’insieme dei primi numeri naturali. Si avrà . Si noti che se è l’insieme degli ordinali di Von Neumann (1.14) allora .
Definizione 1.69 (cardinalità finite). Se è un insieme e diremo che ha elementi (o ha cardinalità ) e scriveremo numero di elementi se esiste una funzione bigettiva .
Intuitivamente se è una qualunque funzione, posto , , …, avremo che l’immagine di è . Se è surgettiva e se è iniettiva tutti gli elementi , …, saranno distinti e quindi effettivamente l’insieme ha elementi.
Teorema 1.70 (cardinalità finite). Un insieme è finito (nel senso di Dedekind, definizione 1.46) se e solo se esiste tale che . Inoltre tale , se esiste, è unico.
Dimostrazione. Passo 1. Dimostriamo innanzitutto che è finito. Si tratta di dimostrare che se è iniettiva allora è anche surgettiva. Lo facciamo per induzione. Per notiamo che e c’è una unica funzione (la funzione vuota: ) che in effetti è bigettiva. Supponiamo ora che sia finito e che sia iniettiva. Possiamo allora definire ponendo: Con un poco di attenzione si verifica facilmente che se è iniettiva allora anche è iniettiva (l’idea è che utilizza gli stessi valori di scartando il valore , visto che , e utilizzando al suo posto il valore ). Ma allora, per ipotesi induttiva, è bigettiva. Dunque anche è bigettiva perché assume tutti i valori assunti da e, avendo un punto in più ed essendo iniettiva deve assumere un ulteriore valore che non può che essere .
Passo 2. Dimostriamo che se allora è finito. Data iniettiva dobbiamo dimostrare che è surgettiva. Per ipotesi dunque esiste una funzione bigettiva . La funzione è iniettiva, in quanto composizione di funzioni iniettiva. Dunque, essendo finito per il passo 1, la funzione è anche surgettiva. Ma allora anche è surgettiva in quanto .
Passo 3. Dimostriamo che se è iniettiva ed esiste iniettiva allora non può essere surgettiva. Infatti se fosse bigettiva allora la funzione definita da sarebbe iniettiva. Ma la sua restrizione sarebbe una funzione iniettiva che non assumerebbe mai il valore dunque non sarebbe suriettiva. Per definizione questo significa che è infinito, cosa che abbiamo già escluso al passo 1.
Passo 4. Dimostriamo che se è finito allora esiste tale che . Passiamo alla contronominale e supponiamo che non esista tale che : dobbiamo dimostrare che in tal caso è infinito. Per fare questo consideriamo le famiglie di funzioni:
Ovviamente se allora ristretta a è elemento di . Dunque se allora anche .
Se e allora possiamo affermare che perché presa una funzione iniettiva se questa non fosse surgettiva potremmo estenderla ad una funzione iniettiva .
Dunque dovrà essere per ogni .
Per il passo 3 sappiamo che ogni non è suriettiva dunque può essere estesa ad una funzione tale che coincide con su . qui si usa l’assioma della scelta Deve dunque esistere una successione di funzioni tali che coincide con su . I grafici di queste funzioni sono dunque una successione crescente di insiemi e la loro unione è il grafico di una funzione che anch’essa coincide con su . Dunque è iniettiva perché se fosse con si avrebbe anche che non può essere visto che ogni è iniettiva. Sull’immagine di ho quindi una struttura isomorfa a che posso sfruttare per costruire una funzione iniettiva ma non suriettiva su . Definisco ponendo: ovviamente è iniettiva (in quanto lo è) ma non è suriettiva (in quanto non è nell’immagine di ).
Abbiamo quindi mostrato che è infinito, come volevamo.
Passo 5. Dimostriamo che se , , allora . Se per assurdo fosse e con allora avremmo una contraddizione con quanto affermato al passo 3 in quanto dovrebbe esistere una funzione bigettiva (in quanto ) e dovrebbe esistere una funzione iniettiva in quanto essendo c’è una funzione iniettiva che posso restringere a . □
Dimostrazione. Per quanto riguarda l’unione disgiunta, se e sono bigettive, una funzione bigettiva si può definire così: Si verifica facilmente che è bigettiva. Per quanto riguarda la differenza basta osservare che se allora e dunque per il punto precedente.
Nei casi rimanenti, senza perdità di generalità, possiamo supporre che sia . E procediamo per induzione su .
Per il prodotto cartesiano il caso corrisponde a . Il passo induttivo si dimostra osservando che da cui, passando alle cardinalità diventa .
Gli elementi di sono le funzioni e si possono identificare univocamente prendendo una funzione e un valore da assegnare al punto . Dunque è in corrispondenza biunivoca con e passando alle cardinalità si ottiene appunto .
L’insieme è l’insieme delle funzioni bigettive . Visto che è finito l’insieme delle funzioni bigettive coincide con l’insieme delle funzioni iniettive. Supponiamo e procediamo per induzione su . Se si ha che, passando alle cardinalità, diventa . Per il passo induttivo osserviamo che una funzione iniettiva si identifica univocamente scegliendo il valore da assegnare al punto e poi prendendo una funzione iniettiva. Dunque si identifica con e, passando alle cardinalità, questo diventa la definizione ricorsiva del fattoriale: .
Per l’insieme delle parti osserviamo che è in corrispondenza biunivoca con l’insieme delle funzioni : basta associare ad ogni sottoinsieme di la funzione che vale su e altrimenti. Dunque .
Nell’ultimo punto dobbiamo contare i sottoinsiemi di con elementi. Posto possiamo procedere per induzione su . Se allora e l’unico sottoinsieme è l’insieme vuoto che ha elementi: dunque il risultato è vero perché effettivamente se e . Il numero di sottoinsiemi di con elementi può essere determinato come segue. Se fissa un elemento e si considera l’insieme . Ovviamente . Un sottoinsieme di con elementi può contenere oppure no. Il numero di sottoinsiemi di con elementi che contengono è uguale al numero di sottoinsiemi di con elementi mentre il numero di sottoinsiemi di con elementi che non contengono è uguale al numero di sottoinsiemi di con elementi. Dunque, per ipotesi induttiva, il numero di sottoinsiemi di con elementi è dove l’ultima uguaglianza è la relazione di ricorrenza per i coefficienti binomiali (vedi Teorema1.125) □
Teorema 1.72 (principio dei cassetti (o dei piccioni)). Se e sono insiemi finiti e allora per ogni esiste tale che
Dimostrazione. Dimostriamo l’implicazione contronominale: se per ogni si ha allora . Senza perdere di generalità supponiamo inoltre . Data la funzione possiamo definire una nuova funzione ponendo: Abbiamo in pratica appiccicato una diversa etichetta ad ogni valore di . In questo modo è facile convincersi che risulta essere iniettiva. Dunque che è la tesi contronominale. □
Esempio 1.73. In un gruppo di 1000 persone ci sono almeno tre persone che compiono gli anni lo stesso giorno. Si applica il principio dei cassetti con insieme delle persone, insieme dei giorni dell’anno che associa ad ogni persona il giorno del suo compleanno. Visto che il teorema si applica con .