Questa costruzione generale esula dalle finalità di questo corso, ci limiteremo a farla soltanto per una particolare classe di insiemi: gli insiemi finiti (cfr. 3.5 e 4.1
Dimostrazione.
L'identità è una bigezione; se f è una bigezione, allora f-1 è
una bigezione; composizione di bigezioni è una bigezione.
Ricordiamo gli assiomi (dovuti a Peano) che descrivono la struttura dei numeri naturali.
Dimostrazione.
Avendo l'esistenza, l'unicità segue immediatamente dall'iniettività di
.
Supponiamo per assurdo che esista un
tale che
per
ogni n, allora sia
.
Chiaramente
,
in quanto
.
Se
,
allora
e quindi
.
Ma allora
,
e questa è una contraddizione.
L'assioma di induzione fornisce una potente tecnica di dimostrazione di proposizioni indicizzate sui naturali.
Dimostrazione.
Sia
,
allora
e se
allora
vale P(n), quindi vale
ossia anche
,
quindi per l'assioma di induzione
.
Al momento i naturali sembrano essere una struttura molto povera, non vi è definita né la somma né il prodotto e nemmeno la relazione d'ordine (poter dire quando due numeri sono uno più grande dell'altro). Per poter dare queste definizioni è necessario dimostrare il seguente
Dimostrazione. Cominciamo con il provare l'unicità di una tale f. Supponiamo che f e gverifichino le due proprietà e proviamo per induzione che f(n)=g(n) per ogni n. Usiamo l'induzione. Per n=0 la proposizione è vera, infatti dato che sia f che g verificano 1, si ha che f(0)=c=g(0).
Supponiamo che f(n)=g(n). Dalla 2 per f si ha che
e la stessa applicata a g dà che
,
dato che f(n)=g(n), allora
Proviamo ora l'esistenza. Per definizione di funzione quello che si cerca è un insieme
tale che:
Sia
,
quello che dobbiamo trovare è un elemento di
che sia una funzione.
Sia
.
Dato che f è l'intersezione di tutti gli
elementi di
,
necessariamente
Provaiamo che
.
Infatti
per ogni
,
quindi
.
Se
allora
per ogni
,
ma
allora dato che ogni
verifica la (5),
per ogni
e quindi
.
Per concludere resta da provare che f verifica la (3). Procediamo
per induzione su n. Se n=0. Abbiamo già visto che
.
Supponiamo per assurdo che esista
con
,
e sia
.
Chiaramente
e se
allora
,
ma allora, per il terzo assioma di
Peano,
per ogni
e quindi
,
pertanto
.
Quindi
,
ma ciò contraddice la (6) perché
.
Supponiamo la tesi vera per n. Sia x l'unico elemento tale che
,
dato che f verifica la (5), allora
.
Supponiamo per assurdo che anche
e si ponga
.
Proviamo che anche in questo caso
e si
avrà, come prima, un assurdo. Dal terzo assioma di Peano segue che
.
Se
allora
.
Se
allora, per l'iniettività di
si ha che
e quindi
.
Se invece i=n allora
implica, per
l'unicità di x, che z=x e quindi, dato che
,
.
Questo conclude la dimostrazione.