Appendici

Funzioni e operazioni

In teoria degli insiemi di definisce come relazione un insieme i cui elementisono tutti coppie ordinate 〈x, y〉. A sua volta la coppia ordinata e statadefinita nel 1922, dopo che da tempo era usata tacitamente come una nozioneprimitiva, da Casimir Kuratowski (1896-1980) come

〈x, y〉 = {{x}, {x, y}},

dove x e y si chiamano rispettivamente prima e seconda componente (nonelementi) della coppia. Per individuare la prima componente bisogna direche e l’elemento della coppia (non ordinata) che e un singoletto, mentre laseconda componente e l’altro elemento dell’altro termine della coppia.1

La definizione permette di dimostrare

〈x, y〉 = 〈u, v〉 ↔ x = u ∧ y = v

che e tutto quello che serve, perche permette di definire le proiezioni in modounivoco come operazioni: (〈x, y〉)1 = x e (〈x, y〉)2 = y.2

Il prodotto cartesiano X × Y di due insiemi X e Y e l’insieme

{〈x, y〉 | x ∈ X, y ∈ Y }.1Questo se x 6= y; 〈x, x〉 sembrerebbe porre qualche problema, ma siccome e uguale a

{{x}, {x, x}} = {{x}, {x}} = {{x}} basta dire che le coppie ordinate sono gli insiemi odella forma generale indicata sopra, con due componenti diverse, oppure del tipo {{x}},indicato allora con 〈x, x〉.

2Sono state proposte altre definizioni, altrettanto utilizzabili anche se piu scomode;ad esempio {{∅, {x}}, {{y}}} da Norbert Wiener (1894-1964), o {{x, a}, {y, b}} con dueoggetti a e b estranei al dominio del discorso. Invece si puo verificare che {x, {x, y}} nonfunziona.

1

Se R e una relazione, si definisce il dominio di R come

dom(R) = {x | ∃y(〈x, y〉 ∈ R)}

e l’immagine di R come

im(R) = {y | ∃x(〈x, y〉 ∈ R)}.

Se R ⊆ X × Y si dice anche che R e una relazione tra X e Y .Se dom(R) ⊆ X e im(R) ⊆ Y allora R e una relazione tra X e Y .Con R‘x si indica l’insieme {y | 〈x, y〉 ∈ R}, o insieme delle immagini di

x rispetto a R.Con R“x si indica l’insieme {y | ∃u ∈ x(〈u, y〉 ∈ R)}.Con R � Y si indica la relazione {〈x, y〉 ∈ R | x ∈ Y ∩ dom(R)}, la

restrizione su R a Y .Se R e una relazione, la relazione inversa R e la relazione {〈x, y〉 | 〈y, x〉 ∈

R}.R‘y e l’insieme delle controimmagini di y rispetto a R.Una relazione R si dice univoca se per ogni x esiste al piu un y tale che

〈x, y〉 ∈ R.Una relazione univoca si chiama anche funzione. Se f e una funzione tra

X e Y e dom(f) = X si dice anche che f e una funzione da X in Y e si scrive

f : X −→ Y.

Se f e una funzione, per ogni x ∈ dom(f) si indica con f(x) l’unico elementodell’insieme f ‘x, cioe l’unica immagine di x mediante f , cioe l’unico y taleche 〈x, y〉 ∈ f .

Per quel che riguarda f“X, si usa talvolta anche la notazione f(X), masolo quando non vi sia assolutamente pericolo di ambiguita, in particolarequando gli insiemi sono denotati da lettere maiuscole per distinguerli dailoro elementi: f(X) = {f(x) | x ∈ X}.

Per descrivere una corrispondenza si usa anche la notazione x 7→ f(x).Se f : X −→ Y e im(f) = Y , si dice che f e suriettiva, o sopra Y .Una funzione f si dice iniettiva, o 1-1 se per ogni x e y in dom(f),

x 6= y → f(x) 6= f(y).

In tale caso la relazione inversa f e anch’essa una funzione, che si indicapreferibilmente con f−1.

2

Una funzione iniettiva e suriettiva da X in Y si dice biiezione o corri-spondenza biunivoca tra X e Y .

Sinonimi di “funzione” sono “applicazione”, “mappa”, “corrispondenza”.Date due funzioni f : X −→ Y e g : Y −→ Z, si chiama composizione di

f e g, e si indica con g ◦ f : X −→ Z la funzione {〈x, z〉 | ∃y ∈ Y (f(x) =y ∧ g(y) = z)}, che a ogni x ∈ X fa corrispondere g(f(x)).3

La composizione di due funzioni iniettive e iniettiva, di due suriettive esuriettiva.

Le funzioni sono insiemi. Si parla di “operazione” quando si fa corrispon-dere a ogni oggetto un (unico) oggetto, con una definizione che non permettetuttavia di riconoscere come insieme la totalita delle coppie cosı individuate;un esempio e la corrispondenza x 7→ ∪x. In questi casi si utilizza tuttaviala notazione funzionale, e si trasporta gran parte della terminologia dellefunzioni. Le operazioni sono funzioni “viste dal di fuori dei modelli”.

Le operazioni sono indicate da nuovi simboli, non presenti nell’alfabetoiniziale. La giustificazione dell’introduzione di un nuovo simbolo funzionalee la seguente, valida per ogni linguaggio L e teoria T .

Se per una formula A(x, y) si dimostra in T che

∀x∃1yA(x, y),

dove ∃1 significa “esiste esattamente un”, allora si puo aggiungere al linguag-gio L un nuovo simbolo funzionale f e alla teoria T un nuovo assioma

∀x∀y(y = f(x)↔ A(x, y)).

Con “si puo” si intende che l’arricchimento del linguaggio e della teoriaha solo un obiettivo di comodita, ma non modifica la teoria stessa: si dicein logica che si ottiene una estensione conservativa, cioe che ogni enunciatodimostrato nella teoria arricchita e che non contenga il simbolo f e dimo-strabile (di solito in modo piu lungo) gia in T . Si dice anche che il nuovosimbolo e eliminabile (sostituendo ogni occorrenza di f(x) = y con A(x, y)).

Vale naturalmente lo stesso per formule A(x1, . . . , xn, y) con un maggiornumero di parametri e simboli funzionali f(x1, . . . , xn).

In logica l’espressione di ∃1yP (y) si realizza per mezzo dell’usuale quan-tificatore ∃ (esiste almeno un) e dell’uguaglianza, con il costrutto

3La composizione si definisce anche per relazioni, ma consideriamo solo il caso dellefunzioni, piu frequente.

3

∃y(P (y) ∧ ∀u(P (u) ↔ u = y)). (1)

L’espressione “esiste al massimo un y tale che P (y)” si realizza con

∀u∀v(P (u) ∧ P (v) ↔ u = v). (2)

Per quel che riguarda il singoletto si verifica che

∀x∃1y∀z(z ∈ y ↔ z = x),

il che permette di introdurre, prendendo ∀z(z ∈ y ↔ z = x) per A(x, y),

∀x∀y(y = {x} ↔ ∀z(z ∈ y ↔ z = x)).

Per la dimostrazione di ∀x∃1y∀z(z ∈ y ↔ z = x) si deve considerare chenella (1) P (y) sia ∀z(z ∈ y ↔ z = x). Ora dall’Assioma II di Zermelo (esisteun insieme che ha come elementi x e solo x) segue che esiste un y per cuiP (y), mentre

∀u(∀z(z ∈ u↔ z = x)↔ u = y)

e conseguenza dell’assioma di estensionalita (applicato a y e u).4

L’introduzione di un nuovo simbolo relazionale non richiede neanche lacondizione di unicita: per ogni formula A(x, y) si puo introdurre un nuovosimbolo R con il nuovo assioma

∀x∀y(R(x, y)↔ A(x, y))

e si ottiene una estensione conservativa.Un esempio e dato da X ⊆ Y ↔ ∀x(x ∈ X → x ∈ Y ).

4Stesso discorso vale per la coppia, l’unione, l’intersezione, il complemento, l’insiemepotenza e le proiezioni delle coppie ordinate.

4

Insiemi numerabili

Due insiemiA eB hanno la stessa cardinalita, o potenza, e si scrive card(A) =card(B), se esiste una biiezione f : A −→ B.

Si dice che A ha cardinalita minore o uguale a quella di B, card(A) ≤card(B), se esiste una iniezione f : A −→ B di A in B.

Si dice che A ha cardinalita minore di quella di B, card(A) < card(B),se card(A) ≤ card(B) ma non esiste una biiezione tra A e B.

Un insieme A e numerabile se esiste una biiezione a : N −→ A. Dataa, A si dice enumerato da a, a una enumerazione di A, e A si rappresentacome una successione {a0, . . . , an, . . .}, che si indica anche con {an}n∈N (sidice anche che {an}n∈N e indiciato da N).

Se un insieme e in corrispondenza biunivoca con un insieme numerabilee numerabile, perche la composizione di due biiezioni e una biiezione.

Se A e numerabile5 e B e finito, A ∪B e A \B sono numerabili:Infatti se B ha n elementi, la successione che ha gli elementi di B come

primi n termini e bn+i = ai per i ∈ N e una enumerazione di A ∪B.D’altra parte, se B ha n elementi, esistera un k tale che (B ∩ A) ⊆

{a0, . . . , ak}. L’insieme {ak+1, . . .} e numerabile, e A \B si ottiene da questoaggiungendo un numero finito di elementi. 2

Un sottoinsieme infinito B di un insieme numerabile A e numerabile: Bnon e vuoto ed ha un primo elemento b0, nella enumerazione di A. Ammessodi aver definito bn ∈ B diverso dai precedenti bi, con i < n, sia bn+1 il primoelemento di B \{b0, . . . , bn}, che esiste altrimenti B sarebbe finito. Si ha cosıuna enumerazione di B. 2

L’unione di due insiemi numerabili e numerabile: supponendo che gliinsiemi {a0, . . . , an, . . .} e {b0, . . . , bn, . . .} siano disgiunti, la successione

cn =

{an/2 se n parib(n−1)/2 se n dispari

enumera A ∪B come a0, b0, a1, b1, a2, . . .Se A e B non sono disgiunti si considera A e B \ A; se questo e finito si

ricade in un caso precedente; se e infinito e disgiunto da A e A ∪ (B \ A) =A ∪B. 2

5Supporremo implicito che A si rappresenti allora come {a0, . . . , an, . . .}, o {an}n∈N,avendo scelto una particolare enumerazione.

5

Un insieme infinito contiene sempre un sottoinsieme numerabile. Se A einfinito, non e vuoto, e sia a0 un suo elemento. Ammesso di aver definitoelementi distinti {a0, . . . , an}, siccome questi non esauriscono A esistera unelemento di A distinto da questi, e sceltone uno lo si ponga uguale a an+1.L’immagine della funzione a e un sottoinsieme numerabile di A.6 2

Per ogni insieme infinito A esiste un sottoinsieme numerabile B ⊆ Atale che A \ B ha la stessa cardinalita di A. Possiamo supporre che A sianumerabile, altrimenti lavoriamo su un suo sottoinsieme numerabile. Presauna successione strettamente crescente di numeri 0 = k0 < k1 < k2 < . . ., siprenda in ogni insieme {a2ki

, . . . , a2ki+1} un aj ∈ A come bi. Si individua cosı

un sottoinsieme numerabile B; in A \B ci sono elementi di A tratti ciascunoda un {a2ki

, . . . , a2ki+1}, e quindi A \B e infinito.

Per vedere che ha la stessa cardinalita di A si osservi che A e decompostoin un insieme numerabile B e in un insieme A \ B = A′ infinito. Quindi A′

si puo a sua volta decomporre in un insieme numerabile C e in un insiemeinfinito A′′:

A = B ∪ A′A′ = C ∪ A′′

Ma siccome B ∪ C = D e numerabile

A = B ∪ A′ = D ∪ A′′A′ = C ∪ A′′

e quindi A e A′ si ottengono aggiungendo allo stesso A′′ due insiemi della stes-sa cardinalita numerabile; si vede facilmente che hanno la stessa cardinalita.2

Se un insieme A ha cardinalita maggiore del numerabile e se B ⊆ A eun sottoinsieme qualunque numerabile, A \ B ha la stessa cardinalita di A.Infatti e infinito, e per quando visto prima si puo togliere un sottoinsieme Cnumerabile in modo che (A \B) \C abbia la stessa cardinalita di A \B; maB ∪ C e numerabile, quindi

A = ((A \B) \ C) ∪ (B ∪ C)A \B = ((A \B) \ C) ∪ C

6Occorre per un tale argomento una forma dell’assioma di scelta, di cui diremo inseguito. Ma la proprieta si dimostra anche senza assioma di scelta, si veda nel testonell’esposizione di Dedekind.

6

quindi sia A sia A \B si ottengono dall’insieme (A \B) \C, che ha la stessacardinalita di A \B aggiungendo un insieme numerabile. 2

L’unione di un insieme numerabile di insiemi finiti e finito o numerabile:se gli insiemi finiti Bi, per i ∈ N, hanno cardinalita ki, basta far corrisponderegli elementi di B0 ai numeri del segmento {0, k0−1}, quelli di B2 al segmento{k0, . . . , k0 +k1−1)}, quelli di B2 al segmento {k0 +k1, . . . , k0 +k1 +k2−1)},e cosı via. Se gli insiemi Bi non sono disgiunti, possono esserci ripetizioni, equindi si ha in realta una relazione tra

⋃{Bi}i∈N e N che non e una funzione:

a un elemento di⋃{Bi}i∈N possono corrispondere piu numeri, se l’elemento

appartiene a piu di un Bi. Basta allora a ciascun elemento far corrispondereil primo numero di quelli che gli sono associati, e si ottiene una funzioneiniettiva di

⋃{Bi}i∈N in N. Se l’immagine e un sottoinsieme finito di N, anche

l’unione e finita; se l’immagine e un sottoinsieme infinito, quindi numerabile,l’unione e in corrispondenza biunivoca con un insieme numerabile e quindinumerabile. 2

L’unione di un insieme numerabile di insiemi numerabili e numerabile:visualizziamo gli insiemi (supposti enumerati) con la matrice infinita

u00 u01 u02 u03 u04 . . .

u10 u11 u12 u13 u14 . . .

u20 u21 u22 u23 u24 . . .

u30

Procedendo per diagonali come e ovvio dal disegno

7

u00

��

u01 // u02

||yyyy

yyyy

u03 // u04

||yyyy

yyyy

. . .

u10

<<yyyyyyyyu11

||yyyy

yyyy

u12

<<yyyyyyyyu13

||yyyy

yyyy

u14 . . .

u20

��

u21

<<yyyyyyyyu22

||yy

yy

yu23 u24 . . .

u30

<<yyyyyyyy

l’insieme unione viene enumerato, se gli insiemi non hanno elementi comuni.Altrimenti come sopra occorre eliminare le ripetizioni. 2

Anche il prodotto cartesiano X ×Y e numerabile se X e Y sono numera-bili. Basta far vedere che N×N e numerabile. Si consideri la matrice infinitacostituita da tutte le coppie 〈m,n〉:

〈0, 0〉 〈0, 1〉 〈0, 2〉 〈0, 3〉 〈0, 4〉 . . .

〈1, 0〉 〈1, 1〉 〈1, 2〉 〈1, 3〉 〈1, 4〉 . . .

〈2, 0〉 〈2, 1〉 〈2, 2〉 〈2, 3〉 〈2, 4〉 . . .

〈3, 0〉

Procedendo di nuovo per diagonali come e ovvio dal disegno

8

〈0, 0〉

��

〈0, 1〉 // 〈0, 2〉

{{wwwww

wwww

〈0, 3〉 // 〈0, 4〉

{{wwwww

wwww

. . .

〈1, 0〉

;;wwwwwwwww〈1, 1〉

{{wwwww

wwww

〈1, 2〉

;;wwwwwwwww〈1, 3〉

{{wwwww

wwww

〈1, 4〉 . . .

〈2, 0〉

��

〈2, 1〉

;;wwwwwwwww〈2, 2〉

{{ww

ww

ww

〈2, 3〉 〈2, 4〉 . . .

〈3, 0〉

;;wwwwwwwww

l’insieme N×N viene enumerato (non ci sono elementi comuni a due righe).La funzione f che stabilisce una corrispondenza biunivoca tra N×N e N

e

f(m,n) =1

2(m+ n)(m+ n+ 1) +

{m se m+ n parin se m+ n dispari

Si puo verificare con i calcoli che tale f e una biiezione. 2

L’insieme dei numeri interi relativi e numerabile come unione di due insie-mi numerabili. L’insieme dei numeri razionali e numerabile come sottinsiemeinfinito dell’insieme N×N; oppure come unione, per ogni m > 0 fissato comedenominatore, dell’insieme infinito, quindi numerabile, dei numeri che sonoprimi con m, come numeratore. 2

L’insieme dei numeri algebrici e numerabile, come unione numerabile diinsiemi finiti. Per ogni k fissato, si considerino tutte le scomposizioni

k = n+ | a0 | + . . . | an |,

dove gli ai sono numeri interi, che sono in numero finito; ciascuna dellesequenze n, a0, . . . an associate in numero finito a k rappresenta l’equazione

a0xn + a1x

n−1 + . . .+ an = 0,

9

che ha al piu un numero finito di soluzioni. L’unione d questi insiemi finiti,al variare di k, e l’insieme dei numeri algebrici.7 2

L’insieme dei numeri reali non e numerabile; si dice anche piu che nume-rabile, perche card(N) < card(R) in quanto ovviamente N ⊂ R e quindi Ne iniettabile in R con la funzione identita. Possiamo anche considerare solol’intervallo (0, 1), che ha la stessa cardinalita di R.

Facciamo vedere che dato un insieme numerabile {an}n∈N di elementi di(0, 1) esiste un elemento di (0, 1) non appartenente all’insieme: quindi (0, 1)non puo essere numerabile, non essendo uguale a nessun {an}n∈N.

Consideriamo i primi due indici i e j tali che ai < aj e supponiamo chesiano 0 e 1: a0 < a1, che non e un’ipotesi restrittiva (altrimenti eliminiamoquelli di indice minore ripartendo da i, e abbiamo cosı escluso solo un numerofinito di punti, che non incide sulla cardinalita).

Sia ora b0 il primo (nel senso di quello con indice minimo) elemento dellasuccessione {an} che cade nell’intervallo (a0, a1) e c0 il primo che cade nel-l’intervallo (b0, a1). Questi, e i successivi numeri che considereremo, esistonoperche altrimenti si sarebbe gia trovato tutto un intervallo contenuto in (0, 1)dentro al quale non cadono elementi della successione.

Una volta definito l’intervallo (b0, c0), si itera. Si ottiene una successionedi intervalli (bn, cn) con (bn+1, cn+1) ⊂ (bn, cn), tutti con gli estremi apparte-nenti ad {an}, cioe bn = akn e cn = akn+1 , e tutti con la seguente proprieta:che tutti gli ai che cadono nell’intervallo (bn, cn) hanno un indice superioreal kn tale che bn = akn . Altrimenti quando abbiamo scelto bn lo avremmoscelto in modo diverso.

Questo comporta che all’esterno di ogni (bn, cn) cade soltanto un numerofinito di {ai}, i restanti tutti interni a (bn, cn). Inoltre kn+1 > kn, e sesupponiamo che il procedimento vada avanti all’infinito la successione dei knsupera con i suoi termini qualsiasi h ∈ N dato.

La successione bn e crescente, e limitata superiormente, quindi per laproprieta di continuita tende a un limite, o estremo superiore8 b: b /∈ {an}altrimenti se fosse b = ah, preso kn > h avremmo che ah e compreso in(bn, cn), mentre h < kn.

7I numeri trascendenti sono i numeri reali che non sono algebrici, ovvero il loro insiemee il complemento, rispetto a R, dell’insieme degli algebrici.

8L’estremo superiore di un insieme A e il minimo dei confini superiori, o maggioranti,cioe di quegli r tali che x ≤ r per ogni x ∈ A.

Nel caso di una successione crescente e limitata superiormente l’estremo superiorecoincide con il limite.

10

Questa dimostrazione non dipende da come sono definiti i numeri reali,ma solo dal fatto che e soddisfatta la continuita. 2

11

I reali come sezioni di Dedekind

Sia Q il campo ordinato dei numeri razionali.

Definizione Una sezione, o taglio di Dedekind e un sottinsieme R ⊂ Q taleche

(i) ∅ 6= R 6= Q(ii) R e chiuso verso il basso, nel senso che q ∈ R ∧ r < q → r ∈ R(iii) R non ha massimo.

Le sezioni di Dedekind saranno anche detti numeri reali; R e l’insiemedelle sezioni di Dedekind.

Lemma 1 La relazione di inclusione tra le sezioni e una relazione d’ordinetotale.

Dimostrazione La relazione di inclusione e chiaramente transitiva, e l’u-nica condizione da verificare e la connessione: supponiamo che X non siaincluso in Y ne uguale; allora esiste r ∈ X \ Y ; preso q ∈ Y qualsiasi, ser ≤ q allora r sarebbe in Y , quindi q < r, e q ∈ X, cioe Y ⊂ X. 2

Poniamo X <R Y se e solo se X ⊂ Y . La proprieta di completezza eespressa dal seguente

Lemma 2 Se A e un insieme ⊂ R non vuoto limitato superiormente, A haun estremo superiore

Dimostrazione Rispetto alla inclusione,⋃A e l’estremo superiore di A;

quello che bisogna far vedere e che⋃A ∈ R.

Ovviamente⋃A 6= ∅, e

⋃A 6= R perche esiste un maggiorante; se q ∈⋃

A e r < q, allora q ∈ X per qualche X ∈ A, e r ∈ X, e quindi r ∈⋃A.⋃

A non ha massimo, perche questo sarebbe un massimo di un suo elemento.2

Questo lemma, dalla semplicissima dimostrazione, e quello che serve aderivare piu il teorema 5.IV di Dedekind, e tutte le conseguenze per l’analisi.

Osserviamo che se ripetiamo la costruzione a partire da R, cioe se defi-niamo le sezioni di R invece che di Q, non otteniamo nulla di nuovo. Infattia ogni X ⊂ R, X 6= ∅ e soddisfacente alle (ii) e (iii), si puo far corrisponderel’insieme dei razionali che e l’unione di tutte le sezioni di razionali in X e cherisulta ancora una sezione dei razionali.

12

Definiamo ora le operazioni, incominciando dalla addizione; posto

X +R Y = {q + r | q ∈ X, r ∈ Y }

si deve dimostrare

Lemma 3 X +R Y ∈ R se X, Y ∈ R.

Dimostrazione X +R Y non e vuoto, se X e Y non sono vuoti; e 6= Qperche se q′ ∈ Q \X, r′ ∈ Q \ Y , allora per ogni q ∈ X ed r ∈ Y si ha q < q′

e r < r′, quindi q + r < q′ + r′, e questo vuol dire che q′ + r′ /∈ X +R Y .Se p < q + r ∈ X +R Y allora p − q < r, p − q ∈ Y , e p si puo’ scrivere

p = q+ (p− q), il primo addendo in X e il secondo in Y , quindi p ∈ X +R Y .Non c’e un massimo, perche se q+ r ∈ X +R Y e q < q′ ∈ X e r < r′ ∈ Y

allora q + r < q′ + r′ ∈ X +R Y . 2

Che l’addizione sia associativa e commutativa e facile da dimostrare. Sipone poi

0R = {r ∈ Q | r < 0}

e si ha

Lemma 4 Per ogni X ∈ R, X +R 0R = X.

Dimostrazione Si deve dimostrare che

X = {r + s | r ∈ X, s < 0}.

L’inclusione da destra a sinistra e ovvia. Se p ∈ X, esiste un r tale chep < r ∈ X, perche X non ha massimo; s = p− r < 0, e p = r + s. 2

L’unica definizione un po’ complicata e quella dell’opposto,

−X = {r ∈ Q | ∃s > r(−s /∈ X)}.

Si dimostra innanzi tutto che

Lemma 5 −X ∈ R.

Dimostrazione(i) −X non e vuoto, perche preso t /∈ X, se r = −t−1, allora r = −t−1 ∈

−X.

13

(ii) −X non e uguale a Q, perche se p ∈ X allora −p /∈ −X; infatti ses > −p allora −s < p ∈ X, quindi −s ∈ X e quindi −p non appartiene a−X.

(iii) Se q < r ∈ −X, allora ∃s > r(−s /∈ X) quindi ∃s > q(−s /∈ X) eq ∈ −X.

(iv) Se r ∈ −X, allora ∃s > r(−s /∈ X) ma per la densita di Q, ∃p(s >p > r ∧ −s /∈ X), quindi p > r appartiene a −X. 2

Quindi si dimostra che

Lemma 6 Per ogni X ∈ R, X +R (−X) = 0R.

Dimostrazione Se p ∈ X e q ∈ −X, esiste r > q tale che −r /∈ X; quindip < −r e p < −q, da cui p+R q < 0R.

Viceversa, sia dato p < 0R, cioe −p > 0R. Consideriamo un razionale qtale che q ∈ X e q +R (−p/2) /∈ X. Lo possiamo trovare partendo da unelemento di −X e uno di X e suddividendo ripetutamente l’intervallo fino ache e minore di −p/2.

Si noti che (p/2)− q > p− q, quindi p− q ∈ −X; allora p = q +R (p− q)appartiene a X +R (−X). 2

Le ulteriori definizioni sono: | X |= X ∪ (−X), per cui si dimostra che| X |≤ X e

X · Y = 0R ∪ {rs | 0 ≤ r ∈ X, 0 ≤ s ∈ Y }per X e Y positivi; per gli altri casi, si estende la definizione mettendo ilsegno positivo o negativo secondo la regola dei segni.

Quindi si dimostrano le proprieta della moltiplicazione e R risulta uncorpo commutativo ordinato e completo, che e il modo come si presentaassiomaticamente l’insieme dei numeri reali.

La teoria dei campi (che sono i corpi commutativi)9 e la teoria determinatadai seguenti assiomi:

0 6= 1∀x, y (x+ y = y + x)∀x, y (x · y = y · x)∀x, y, z (x+ (y + z) = (x+ y) + z)∀x, y, z (x · (y · z) = (x · y) · z)∀x (x+ 0 = x)

9Un corpo e commutativo se la moltiplicazione e commutativa; l’addizione si assumecommutativa anche nei corpi.

14

∀x (x · 1 = x)∀x, y, z (x · (y + z) = x · y + x · z)∀x, y ∃z(x+ z = y)∀x, y (x · y = 0→ x = 0 ∨ y = 0)∀x, y (y 6= 0→ ∃z(y · z = x))

Per ottenere gli assiomi dei campi ordinati occorre aggiungere

∀x(x 6< x)∀x, y, z(x < y ∧ y < z → x < z)∀x, y(x < y ∨ x = y ∨ y < x)

∀x, y, z(x < y → x+ z < y + z)∀x, y, z(x < y ∧ 0 < z → x · z < y · z)

L’assioma di completezza10 si puo formulare nel seguente modo, che affermache ogni sottoinsieme non vuoto e limitato superiormente ha un estremosuperiore:

∀X 6= ∅(∃a∀x ∈ X(x ≤ a)→ ∃l(∀x ∈ X(x ≤ l)∧∀r < l∃x ∈ X(r < x ≤ l))).

A differenza degli altri, questo richiede un quantificatore su sottoinsiemi diR, cioe e una formula del secondo ordine.

Grazie a questo assioma nella logica del secondo ordine piena si dimostrache due campi ordinati completi sono isomorfi, entrambi il completamento diQ.

10O continuita. Naturalmente in un’impostazione assiomatica la continuita deve esserepostulata anche per i numeri, non solo per la retta.

15

Il principio di induzione

Il linguaggio del primo ordine per l’aritmetica ha come alfabeto propriouna costante 0 e un simbolo di funzione s, l’uguaglianza =, quindi variabilix, y, . . . per individui, i connettivi e i quantificatori.

s(t) si scrive anche t′; i termini

0, 0′, 0′′, 0′′′, . . .

sono i numerali, e si pensa che i numeri di N siano in corrispondenza biunivocacon i numerali.11 In effetti, tra i vari modelli della teoria che presenteremoper l’aritmetica, per individuare quello che si indica con N e che si chiamastandard non si puo dire altro che esso e in corrispondenza biunivoca con inumerali.

Alcune proprieta evidenti della successione numerica sono immediate dascrivere:

∀x(0 6= x′)

∀x∀y(x 6= y → x′ 6= y′)

e costituiscono i primi due assiomi dei numeri naturali. L’idea di Dedekindche N sia la catena di 0, ovvero l’intersezione (o il piu piccolo, rispetto a ⊆)di tutti i sottoinsiemi di N che contengono 0 e sono chiusi rispetto a s, siesprime con l’affermazione

0 ∈ X ∧ ∀x(x ∈ X → x′ ∈ X)→ N ⊆ X,

che si chiama principio di induzione. Esso tuttavia non appartiene al lin-guaggio del primo ordine dell’aritmetica, ma a un linguaggio con variabiliX, Y, . . . per insiemi oltre alle variabili per individui.12

Da questa condizione, applicata a un X ⊆ N, pensando a X come definitoda una formula A(x), X = {x ∈ N | A(x)}, si ricava l’assioma di induzione

11Per distinguere i numeri e i numerali esistono diverse soluzioni grafiche: o i numeralisi scrivono in grassetto, o sottolineati 0, 0′, . . ., oppure per i numeri si mette un indicerelativo alla struttura 0N, 0′N, . . . Quando sia remoto il pericolo di confusione non useremoalcuno di questi artifici.

12Se questi sono gli unici due tipi di variabili, si parla di un linguaggio del secondoordine, se invece le formule si pensano come frammenti di un discorso insiemistico, siamoall’interno della teoria degli insiemi.

16

A(0) ∧ ∀x(A(x)→ A(x′))→ ∀xA(x),

dove A e una formula qualsiasi del linguaggio aritmetico.I primi due assiomi e lo schema di induzione formano la teoria PA, acro-

nimo di “aritmetica di Peano”.Dall’assioma di induzione deriva una forma particolare di dimostrazione,

la cosiddetta dimostrazione per induzione:

A(0) Base∀x(A(x)→ A(x+ 1)) Passo induttivo

∀xA(x).

Per dimostrare ∀xA(x) sono sufficienti due mosse: la prima consiste neldimostrare A(0), e la seconda nel dimostrare ∀x(A(x)→ A(x+ 1)).

Si dice allora che ∀xA(x) e stata dimostrata per induzione su x, e A(x)si chiama la formula d’induzione, e x la variabile d’induzione (potrebberoessercene altre nella formula). Nella dimostrazione del passo induttivo, A(x)si chiama ipotesi induttiva.

Come esempio, dimostriamo

∀x(x 6= 0→ ∃y(x = y′)).

La base 0 6= 0 → ∃y(0 = y′) e un teorema logico, perche lo e 0 = 0; per ilpasso induttivo, ammesso x 6= 0→ ∃y(x = y′), consideriamo x′ e supponiamox′ 6= 0. Due casi: se x = 0, allora x′ = 0′ e quindi ∃y(x′ = y′); se x 6= 0, peripotesi induttiva ∃y(x = y′), quindi x′ = y′′ e ∃z(x′ = z′). 2

Come applicazione, dimostriamo l’unicita di una funzione definita per ri-corsione:13 date due funzioni: g(x1, . . . , xr) a r argomenti e h(x1, . . . , xr, x, y)a r + 2 argomenti,14 dove r puo essere 0, esiste una e una sola funzionef(x1, . . . , xr, x) che soddisfa per tutti gli argomenti la coppia di equazioni{

f(x1, . . . , xr, 0) = g(x1, . . . , xr)f(x1, . . . , xr, x

′) = h(x1, . . . , xr, x, f(x1, . . . , xr, x))

e f(x1, . . . , xr, x) si dice definita ricorsivamente a partire da g e h.

13Questa forma di ricorsione si chiama “ricorsione primitiva”, ma non avremo occasionedi considerare altri casi.

14Casi particolari, dove g ed h non hanno necessariamente lo stesso numero di parametri,o h puo non dipendere da x, sono riconducibili a questo mediante funzioni proiezione.

17

Supponiamo che due funzioni f1 ed f2 soddisfino entrambe le equazioni.Dimostriamo per induzione su x che f1 e f2 hanno sempre lo stesso valore:

Base: f1(x1, . . . , xr, 0) = g(x1, . . . , xr) = f2(x1, . . . , xr, 0).

Passo induttivo: Se f1(x1, . . . , xr, x) = f2(x1, . . . , xr, x), allora

f1(x1, . . . , xr, x′) = h((x1, . . . , xr, x, f1(x1, . . . , xr, x))

= h((x1, . . . , xr, x, f2(x1, . . . , xr, x))= f2((x1, . . . , xr, x

′).2

L’esistenza si dimostra nel modo seguente, supponendo per semplicita discrittura che non ci siano parametri, cioe che si consideri{

f(0) = x0

f(x′) = h(x, f(x))

dove x0 ∈ X e h : N×X −→ X.Sia Nm = {0, 1, . . . ,m − 1}, e N0 = ∅. Si dimostra prima per induzione

che per ogni n esiste una e una sola funzione ϕn : Nn −→ X che soddisfa ledue equazioni per ogni elemento del suo dominio.

Per n = 0 si considera la funzione vuota. Ammesso che esista ϕn conle proprieta richieste (che con un argomento uguale al precedente implical’unicita), si definisca ϕn+1 ponendo

ϕn+1(i) =

{ϕn(i) i ≤ nh(n, ϕn(n)) i = n+ 1,

o in termini insiemistici ϕn+1 = ϕn ∪ {〈n+ 1, h(n, ϕn(n))〉}.Infine la f e definita ponendo f(n) = ϕn(n). In termini insiemistici piu

espliciti, f e l’unione, per n ∈ N, delle ϕn, intese come insieme di coppieordinate. 2

Si definiscono anche relazioni per ricorsione (riconducendosi al caso dellefunzioni con la loro funzione caratteristica), sostituendo bicondizionali alleuguaglianze, ad esempio tra le prime{

y < 0 ↔ y 6= yy < x′ ↔ y < x ∨ y = x,

che e di immediata utilita.

18

Dal principio di induzione segue che la relazione d’ordine < e un buonordine, cioe un ordine totale in cui ogni sottoinsieme non vuoto ha unminimo.15

La proprieta di buon ordine per N si esprime con il principio del minimo:

∅ 6= X ⊆ N→ ∃x(x ∈ X ∧ ∀y ∈ X(x ≤ y))

o equivalentemente:

∅ 6= X ⊆ N→ ∃x(x ∈ X ∧ ∀y < x(y 6∈ X)).

Assumendo l’induzione, se ∅ 6= X ⊆ N, si hanno due casi: o 0 ∈ X, eallora X ha un minimo, oppure no, e si consideri l’insieme

Y = {x ∈ N | ∀y ≤ x(y 6∈ X}.

Y deve essere diverso da N altrimenti X sarebbe vuoto; ma 0 ∈ Y e alloraesiste un c tale che c ∈ Y ma c′ 6∈ Y . Si vede subito che c′ e il minimo di X.2

Non si puo dimostrare che il principio del minimo implica l’induzione,perche esistono altre strutture infinite che sono bene ordinate e diverse daN, ad esempio una della forma

t t t tttt s s s s r q q q t s s r qω ω′0

Per escluderle occorre che siano vietati elementi come ω che non sono ilsuccessore di nessun numero. Che ogni numero diverso da 0 sia un succes-sore lo abbiamo dimostrato per induzione; in assenza dell’induzione occorrepostularlo, aggiungendo ai primi due assiomi

∀x(x 6= 0→ ∃y(x = y′)).

Il principio del minimo insieme a questa assunzione giustifica l’induzione:supponiamo infatti che 0 ∈ X e che ∀x(x ∈ X → x′ ∈ X) ma che ∃x ∈N(x 6∈ X).

Allora N \X 6= ∅, e sia c un suo elemento; c 6= 0 e quindi ha un predeces-sore c1 tale che c′1 = c (oltre a un successore c′). Deve essere c1 6∈ X perche

15Che < sia una relazione d’ordine totale stretto, cioe antiriflessiva, transitiva e connessa(∀x, y(x < y ∨ y < x ∨ x = y)), si dimostra per induzione. x ≤ y e una abbreviazione perx < y ∨ x = y.

19

c1 ∈ X → c ∈ X. A sua volta c1 6= 0 deve avere un predecessore c2 taleche c′2 = c1 e per cui c2 6∈ X, perche c2 ∈ X → c1 ∈ X, e cosı via. Alloral’insieme {. . . , c2, c1, c}

t t t tttt s s s s r q q qq q q r r s s r q0 c c′

non avrebbe un minimo. 2

Col principio del minimo si giustifica anche un’altra forma di dimostrazio-ne per induzione. Se A(x) e una qualunque formula aritmetica, considerandoX = {x ∈ N | A(x)} come l’insieme definito da A(x), si deduce che

∃xA(x)→ ∃x(A(x) ∧ ∀y < x¬A(y)).

Poiche questo vale per ogni formula, possiamo considerare una formula cheinizi con una negazione, che scriveremo ¬A, e abbiamo

∃x¬A(x)→ ∃x(¬A(x) ∧ ∀y < xA(y)).

Di qui, contrapponendo

¬∃x(¬A(x) ∧ ∀y < xA(y))→ ¬∃x¬A(x),

ovvero

∀x¬(¬A(x) ∧ ∀y < xA(y))→ ∀xA(x),

e infine

∀x((∀y < xA(y))→ A(x))→ ∀xA(x).

Questo schema si chiama induzione sul decorso dei valori . Per dimostrare∀xA(x) e sufficiente dimostrare che ∀x(∀y < xA(y)→ A(x)):

∀x(∀y < xA(y)→ A(x))∀xA(x)

ovvero, a parole, che per ogni x la validita di A(x) segue dal fatto che Avalga per tutti gli y < x.16

L’induzione semplice e quella sul decorso dei valori si possono dimostrareequivalenti direttamente nel seguente modo.

La conclusione ∀xA(x) a partire da ∀x(∀y<xA(y) → A(x)) si giustificaper induzione semplice. Si considera la formula

16Sembra che non ci sia piu la base, ma se si dimostra ∀x((∀y < xA(y))→ A(x)) alloranel caso che x valga 0 segue A(0), perche ∀y < 0A(y) e banalmente vero.

20

B(x)↔ ∀y <xA(y)

e si dimostra ∀xB(x) (da cui segue ovviamente ∀xA(x)) per induzione su x,utilizzando anche ∀x(∀y < xA(y)→ A(x)) nel corso della dimostrazione:

Base: B(0) e immediato perche y < 0 e falso.

Passo induttivo: Ammesso B(x), cioe ∀y <xA(y), da questa segue A(x), equindi ∀y < x′A(y) che e B(x′). 2

Viceversa l’induzione si giustifica in base a quella sul decorso dei valo-ri. Supponiamo A(0) ∧ ∀x(A(x) → A(x′)); per ottenere ∀xA(x), in baseall’induzione forte e sufficiente dimostrare ∀x(∀y < xA(y)→ A(x)).

Distinguiamo due casi, assumendo di nuovo che sia stato aggiunto l’as-sioma ∀x(x 6= 0 → ∃y(x = y′)); un numero o e 0, e allora abbiamo A(0)e quindi ∀y < 0A(y) → A(0), oppure se e diverso da 0 e un successore epossiamo indicarlo x′, e dobbiamo dimostrare ∀y < x′A(y)→ A(x′).

Ma ∀y <x′A(y) implica A(x), e con ∀x(A(x)→ A(x′)) anche A(x′). 2

Il principio del minimo e anche equivalente all’affermazione che non esi-stono catene discendenti infinite; se una successione {an} fosse tale che. . . < an+1 < an < . . . < a0, l’insieme {an | n ∈ N } non avrebbe mini-mo. Viceversa, dato un insieme non vuoto X, preso un suo elemento a0, senon e il minimo di X si puo trovare un altro suo elemento a1 < a0, e seneanche a1 e il minimo si continua, ma siccome la successione cosı generatanon puo essere infinita, si trova un ak che e il minimo di X. 2

Al principio del minimo si da ancora un’altra formulazione nota comeprincipio della discesa finita. Esso afferma che se una proprieta P vale perun k > 0, e quando vale per un n > 0 qualunque allora vale anche per unnumero minore di n, allora P vale per 0.

Infatti in queste ipotesi, in cui l’insieme degli n che soddisfa P non evuoto, il minimo deve essere 0, perche un n > 0, non sarebbe il minimo, inquanto anche qualche numero minore soddisferebbe P .

Viceversa, ammesso il principio della discesa finita, e dato un insieme Xnon vuoto, consideriamo la proprieta P di appartenere a X. O la proprietaP vale per 0, e 0 e allora ovviamente il minimo di X, oppure 0 non ha laproprieta P . In questo caso, non e vero per P che per ogni n che ha laproprieta P anche uno minore ha la proprieta P . Quindi esiste un n chesoddisfa P ma tale che nessun suo predecessore soddisfa P , ed n e il minimodi X. 2

21

L’induzione al secondo ordine, ma non quella al primo ordine, permettedi dimostrare che due qualunque modelli dell’aritmetica sono isomorfi.

Siano 〈N1, 01, s1〉 e 〈N2, 02, s2〉 due strutture che soddisfano gli assiomidell’aritmetica.

Poiche per N1 vale il teorema di ricorsione, possiamo definire θ : N1 −→N2 ponendo {

θ(01) = 02

θ(s1(x)) = s2(θ(x))

ed e facile dimostrare che θ e iniettiva. Che la struttura sia conservata sivede dalla prima equazione per 0 e dalla seconda per la funzione successore.Per vedere che θ e suriettiva, si consideri Y = {y ∈ N2 | y /∈ im(θ)} ⊆ N2. SeY 6= ∅, siccome N2 soddisfa il principio del minimo esiste un primo elementodi Y , che non e 02 ed e quindi della forma s2(c). Ma allora c /∈ Y , cioe c = θ(x)per qualche x, e allora s2(c) = θ(s1(x)), s2(c) ∈ im(θ), contraddizione. 2

Non c’e modo tuttavia di definire Y con il linguaggio aritmetico in N2, dalmomento che la sua definizione fa riferimento a enti esterni a N2, come θ e N1.Infatti le proprieta della logica del primo ordine permettono di dimostrareche esiste una struttura soddisfacente gli assiomi di Peano e nella quale esisteun c diverso da tutti gli n′.

Nel commentare il principio della non esistenza di catene discendenti in-finite abbiamo usato il fatto che se un processo non e infinito allora essotermina a uno stadio k.

Questa osservazione dipende dalla equivalenza tra la definizione di “infi-nito” come “riflessivo” (X e riflessivo se esiste una iniezione di X su un suosottoinsieme proprio) e quella di “infinito” come non equivalente a nessunNn. Quest’ultima definizione di “infinito” e logicamente la stessa cosa chedire che un insieme e “finito” se e solo se e equipotente a un Nn.

Se un insieme X e equipotente a un Nn, allora X e non riflessivo, perchenon esiste una iniezione propria di Nn in se.

Infatti

Teorema 1 Se m > n, non esiste una iniezione di Nm in Nn.17

17La proprieta e detta anche Principio dei cassetti (in inglese Pigeonhole Principle):se si distribuiscono m oggetti in n cassetti, con m > n, in almeno un cassetto c’e piu diun oggetto. In altre parole, non esiste una iniezione di un insieme con m elementi in uninsieme con n < m elementi, o ancora: ogni funzione da un insieme con m elementi in uninsieme con n < m elementi non e iniettiva.

22

Dimostrazione La dimostrazione e per induzione su n.

Base: N0 e ∅ e non esiste nessuna funzione da un insieme non vuotonell’insieme vuoto.18

Passo induttivo: Supponiamo vero per n che per ogni m > n non esistaun’iniezione di Nm in Nn; supponiamo per assurdo che esista invece unm > n+ 1 con un’iniezione di Nm in Nn+1, chiamiamola g.

Siccome Nn+1 = Nn ∪ {n}, deve essere n = g(i) per qualche i < m,altrimenti g sarebbe una iniezione di Nm in Nn.

Se i = m−1 eliminiamo la coppia 〈m−1, n〉; altrimenti prima scambia-mo tra di loro i valori attribuiti da g a i e am−1, ed eliminiamom−1 colsuo nuovo valore n; consideriamo cioe g1 cosı definita: g1(i) = g(m−1),e g1(j) = g(j) per ogni altro j < m − 1, j 6= i. g1 risulta un’iniezionedi Nm−1 in Nn, con m− 1 > n, contro l’ipotesi induttiva. 2

Corollario 1 Per ogni m, non esiste una iniezione propria di Nm in se.

Dimostrazione Se i fosse una iniezione propria di Nm in se, due casi. Sem − 1 /∈ im(i), allora i sarebbe una iniezione di Nm in un Nn con n < m,contro il teorema. Se m − 1 ∈ im(i), m − 1 = i(h), c’e qualche altro j <m − 1 /∈ im(i), e di nuovo cambiando il valore per h a j si ottiene unacontraddizione con il teorema. 2

Viceversa si deve dimostrare

Teorema 2 Se X non e equipotente a nessun Nm allora X e riflessivo.

Dimostrazione Precisando la condizione che X non sia equipotente a nessunNm, possiamo intendere che ogni Nm con m > 0 sia iniettabile in X, senzache nessuno sia ad esso equipotente, perche questa precisazione si puo fareper induzione: ∅ e una iniezione di N0 in X non suriettiva; ammesso cheesiste una iniezione f : Nm −→ X non suriettiva, se c ∈ X \ im(f) si pongag(i) = f(i) per i < m e g(m) = c e si conclude che esiste una iniezione diNm+1 in X.

18Poiche X × ∅ = ∅ esiste solo una relazione tra X e ∅, la relazione vuota – ∅ e uninsieme di coppie ordinate (e di ogni altra cosa) perche e vero che per ogni x, se x ∈ ∅ x euna coppia, e per lo stesso motivo ∅ e una funzione – ma il dominio di ∅ e ∅, non X.

23

Si deve far vedere allora che N e iniettabile in X, con una iniezione idefinita per ricorsione, da cui segue che X e riflessivo.

Siccome N1 e iniettabile in X se X non e vuoto, e non lo e se no sarebbeequipotente a N0, basta far corrispondere a 0 un qualsiasi elemento di X eporre i(0) uguale a questo elemento.

Ammesso di aver definito i su Nm, in modo che ogni i(r) sia diverso datutti gli i(s) con s < r, consideriamo una iniezione f di Nm+1 in X. I suoivalori non possono coincidere con quelli di i, altrimenti componendo f coni−1 si avrebbe una iniezione di Nm+1 in Nm; ne esiste allora almeno uno chee diverso da i(0), . . . i(m − 1), e si prenda per definitezza quello che e f(h)per il primo h, e lo si ponga come valore per i(m). 2

Nella dimostrazione si usa l’assioma di scelta dove si considera una inie-zione f di Nm+1 in X. In alternativa, ammesso di aver definito i su Nm, inmodo che ogni i(r) sia diverso da tutti gli i(s) con s < r, si puo osservareche {i(j) | j < m} non puo essere X, altrimenti X sarebbe in biiezione conNm, per cui se c e una funzione di scelta per sottoinsiemi di X si puo porrei(m) = c(X \ {i(j) | j < m}).

24

Lettera di Dedekind a H. Keferstein del 27 febbraio 1890

Caro dottore,vorrei esprimerle i miei sinceri ringraziamenti per la sua gentile lettera

del 14 u.s. e per la sua disponibilita a pubblicare la mia risposta. Mavorrei chiederle di non essere impulsivo su questo argomento e di venire auna decisione solo dopo aver letto ancora una volta accuratamente e averconsiderato a fondo le definizioni e le dimostrazioni piu importanti contenutenel mio saggio sui numeri, se ne ha il tempo. Sono convinto infatti checon tutta probabilita lei allora verra ad accettare tutti i punti della miaconcezione e della mia trattazione dell’argomento; e questo e cio che mi premedi piu, dal momento che sono convinto che lei abbia un profondo interesse alriguardo.

Per facilitare per quanto possibile questo avvicinamento, vorrei chiederledi prestare attenzione al seguente corso di pensieri, che costituisce la genesidel mio saggio. Come e avvenuta la stesura del mio saggio? Certo non inun giorno; si tratta piuttosto di una sintesi costruita dopo una prolunga-ta gestazione, basata su una precedente analisi della successione dei numerinaturali proprio come si presenta nell’esperienza, per cosı dire, alla nostraconsiderazione. Quali sono le proprieta fondamentali mutuamente indipen-denti della successione N , vale a dire quelle proprieta che non sono derivabilil’una dall’altra, ma da cui tutte le altre seguono? E come fare per spoglia-re queste proprieta del loro carattere specificamente aritmetico in modo cheesse vengano sussunte sotto concetti piu generali e attivita di comprensionesenza le quali nessun pensiero e possibile ma grazie alle quali viene fornitoun fondamento per l’affidabilita e la completezza delle dimostrazioni e per lacostruzione di nozioni e definizioni coerenti?

Posto il problema in questo modo, si e forzati, credo, ad accettare iseguenti fatti.

(1) la successione numerica N e un sistema di individui, o elementi, chia-mati numeri. Questo porta alla considerazione generale dei sistemi in se (§1del mio saggio).

(2) Gli elementi del sistema N stanno tra loro in una certa relazione;sussiste un certo ordine, che consiste, per cominciare, nel fatto che a ciascunnumero definito n corrisponde un definito numero n′, il successore, o il primonumero piu grande. Questo porta alla considerazione del concetto generale diapplicazione ϕ di un sistema (§2) e siccome l’immagine ϕ(n) di ogni numeron e ancora un numero, n′, e quindi ϕ(N) e una parte di N , abiamo a che

25

fare con una applicazione ϕ di un sistema N in se, su cui dobbiamo dunquesviluppare una indagine generale (§4).

(3) Numeri distinti a e b hanno come successori numeri distinti a′ e b′;l’applicazione ϕ dunque ha la proprieta di distinzione, o similarita (§3).

(4) Non ogni numero e un successore n′; in altre parole, ϕ(N) e unaparte propria di N . Questo, insieme a quanto precede, e cio che rende lasuccessione numerica N infinita (§5).

(5) In particolare, il numero 1 e il solo numero che non appartiene a ϕ(N).Abbiamo cosı elencato i fatti che lei considera [. . . ] la caratterizzazionecompleta di un sistema N semplicemente infinito e ordinato.

(6) Ho mostrato tuttavia nella mia risposta [. . . ] che questi fatti sono an-cora lungi dall’essere adeguati per la caratterizzazione completa della naturadella successione numerica N . Tutti questi fatti varrebbero anche per ognisistema S che, oltre alla successione numerica N , contenesse un sistema Tdi elementi aggiuntivi arbitrari t, al quale l’applicazione ϕ potrebbe sempreessere estesa rimanendo simile e soddisfacendo ϕ(T ) = T . Un sistema S delgenere e ovviamente qualcosa di totalmente differente dalla nostra successio-ne numerica N , e io potrei sceglierlo in modo tale che neanche un singoloteorema dell’aritmetica sarebbe conservato in esso. Cosa dobbiamo aggiun-gere allora ai fatti sopra elencati in modo da ripulire S di tutti gli intrusialieni t che disturbano ogni traccia di ordine, e restringerlo a N? Questo fuuno dei momenti piu difficili della mia analisi e il suo superamento richieseuna lunga riflessione. Se uno presuppone la conoscenza della successione Ndei numeri naturali, e di conseguenza si concede l’uso del linguaggio aritme-tico, allora naturalmente se la cava con facilita. Basta che dica: un elementon appartiene alla successione N se e solo se cominciando con l’elemento 1 econtinuando a contare sistematicamente, cioe passando attraverso un numerofinito di iterazioni dell’applicazione ϕ (si veda la fine del paragrafo 131 delmio saggio), prima o poi raggiungo l’elemento n; procedendo in questo modoinvece, non raggiungero mai un elemento t al di fuori della successione N .Ma questo modo di caratterizzare la distinzione tra gli elementi t che devonoessere espunti da S e gli elementi n che soli devono rimanere e certamentedel tutto inutile al nostro scopo; esso conterrebbe, in sostanza, il piu ovvio epericoloso tipo di circolo vizioso. Neanche le semplici parole “prima o poi loraggiungo” naturalmente rappresentano una soluzione; non avrebbero altroeffetto che, ad esempio, le parole “karam sipo tatura”, che invento in questoistante senza dare ad esse alcun senso chiaramente definito. Allora, comeposso, senza presupporre alcuna conoscenza aritmetica, dare una fondazione

26

concettuale non ambigua alla distinzione tra gli elementi n e gli elementi t?Semplicemente attraverso la considerazione delle catene (paragrafi 37 e 44del mio saggio), e tuttavia grazie ad esse in modo completo! Se io volessievitare la mia espressione tecnica “catena” potrei dire: un elemento n di Sappartiene alla successione N se e solo se n e un elemento di ogni parte Kdi S che possiede le seguenti due proprieta: (i) l’elemento 1 appartiene a Ke (ii) l’immagine ϕ(K) e una parte di K. Nel mio linguaggio tecnico: Ne l’intersezione 10, o ϕ0(1), di tutte le catene K (in S) a cui 1 appartiene.Solo ora la successione N e caratterizzata in modo completo. Di passaggio,vorrei fare la seguente osservazione a questo proposito. I lavori Begriffschrifte Grundlagen der Aritmetik di Frege vennero in mio possesso per la primavolta la scorsa estate (1889), per un breve periodo, e ho notato con piace-re che il suo modo di definire la successione non immediata di un elementorispetto a un altro in una successione concorda essenzialmente con il mioconcetto di catena (paragrafi 37 e 44); bisogna soltanto non essere fuorviatidalla sua terminologia poco agevole.

(7) Dopo che nella mia analisi era stata riconosciuta la natura essenzialedel sistema semplicemente infinito (paragrafi 71 e 73), il cui tipo astrattoe la successione numerica N , si pose la questione: esiste un tale sistemanel dominio delle nostre idee? Senza una dimostrazione logica di esistenzaresterebbe sempre il dubbio che l’idea di un tale sistema non possa per casocontenere contraddizioni interne. Di qui la necessita di tali dimostrazioni(paragrafi 66 e 72 del mio saggio).

(8) Risolto anche questo problema, restava la domanda: tutto quantofatto finora, contiene anche un metodo di dimostrazione sufficiente a stabilire,in piena generalita, le proposizioni che si suppongono valere per tutti i numerin? Sı! Il famoso metodo per induzione si appoggia sulla sicura fondazionedel concetto di catena (paragrafi 59, 60 e 80 del mio saggio).

(9) Infine, e possibile anche presentare le definizioni di operazioni nume-riche coerentemente per ogni n? Sı! Questo e realizzato dal teorema nelparagrafo 126 del mio saggio.

Cosı l’analisi era terminata e poteva incominciare la sintesi; che mi ha cau-sato ancora non poca pena! Certo il lettore del mio saggio non ha neanche egliun compito facile; a parte una valida sensibilita, occorre una determinazionemolto forte per seguire e comprendere tutto a fondo e in dettaglio.

Vengo ora ad alcuni passi del suo scritto . . .

[Dedekind risponde ad alcune obiezioni e incomprensioni di Keferstein,

27

che non sono particolarmente interessanti, salvo forse la seguente, che ripor-tiamo per compeltezza.]

(e) [. . . ] Il significato di queste [sue] righe19 non mi e chiaro. Esprimo-no forse il desiderio che la mia definizione della successione numerica N edel modo in cui l’elemento n′ segue l’elemento n siano sostenuti, se possi-bile, da una successione intuitiva? Se e cosı, mi opporrei con la massimadeterminazione, perche si presenterebbe immediatamente il pericolo che dauna tale intuizione noi potremmo forse inconsciamente anche accettare comeevidenti teoremi che devono invece essere derivati del tutto astrattamentedalla definizione logica di N . Se io chiamo (paragrafo 73) n′ l’elemento chesegue n, si tratta solo di una nuova espressione tecnica per mezzo della qualesemplicemente porto un po’ di varieta nel mio linguaggio; questo linguaggiosuonerebbe ancora piu monotono e repellente se dovessi negarmi questa va-rieta e dovessi sempre chiamare n′ solo l’applicazione ϕ(n) di n. Ma l’unaespressione significa esattamente lo stesso dell’altra.

. . .

Ripetendo il desiderio espresso all’inizio e pregandola di scusarmi per lalunghezza della discussione, le porgo i piu cordiali ossequi.

SuoRichard Dedekind

27 febbraio 1890Petrithorpromenade 24

19[“Siccome Dedekind non sottolinea il fatto che N puo essere considerata una succes-sione in cui ϕ(n) = n′ segue immediatamente n, le nozioni di successione e di successorein una successione fanno una brusca comparsa quando si viene alla definizione dei numeriordinali”.]

28

Gottlob Frege

Gottlob Frege pubblico la Begriffschrift come prima opera,20 nel 1879, dopoessersi laureato in matematica a Gottingen ed essersi trasferitosi a Jena.Quest’opera e le successive di Frege sono fondamentali per la storia dellalogica contemporanea, mentre sono marginali per la storia della teoria degliinsiemi. La consideriamo solo per vedere il parallelo con Dedekind, e perchestoricamente ha la priorita. Nella Begriffschrift Frege presento, come diceil titolo, un linguaggio in formule per il pensiero puro (una ideografia, o unformalismo) allo scopo di indagare i principi della matematica:

Essendomi posto la questione a quale di questi due tipi apparte-nessero i giudizi aritmetici [quelli la cui dimostrazione puo esserecondotta in modo puramente logico e quelli la cui dimostrazionedeve appoggiarsi a fatti empirici], dovetti innanzi tutto indagarefino a che punto si possa procedere nell’aritmetica in modo pura-mente deduttivo, basandosi solo sulle leggi del pensiero, che sonoal di sopra di tutte le particolarita.

La via da seguire in tale indagine era questa: che dapprima iocercassi di ricondurre alla consequenzialita logica il concetto del-l’essere ordinato in una successione, per poi proseguire, partendoda cio, fino al concetto di numero. Per evitare che in questotentativo si introducesse inavvertitamente alcunche di intuitivo,tutto doveva svolgersi senza la minima lacuna entro la catenadeduttiva. Cercando di soddisfare nel modo piu rigoroso a que-sta esigenza, incontrai un ostacolo nell’inadeguatezza della lingua[. . . ]21

La costruzione della lingua simbolica nella Begriffschrift , insieme alla espli-citazione delle regole logiche, segnano la comparsa dei linguaggi logici e dellalogica contemporanea.

La terza parte dell’opera e dedicata alle successioni, presentate come“esempio del modo di adoperare il [mio] linguaggio”;22 in essa e definito il

20G. Frege, Begriffscrhrift. Eine der arithmetischen nachgebildete Formelsprache desreinen Denkens, Nebert, Halle, 1879.

21G. Frege, Logica e aritmetica (a cura di C. Mangione), Boringhieri, Torino, 1965, p.103.

22Il titolo e: “Elementi di una teoria generale delle successioni”.

29

concetto di “iterazione finita” per mezzo di quello di “proprieta ereditaria”;il concetto e strettamente analogo alle catene di Dedekind.

La trattazione fa vedere

come il pensiero puro, mentre astrae da ogni contenuto dato daisensi o addirittura da una intuizione a priori, sia in grado di pro-durre dal solo contenuto, che trae origine dalla sua propria natura,giudizi che a prima vista non sembrano possibili, se non in basea una qualche intuizione. [. . . ] Le proposizioni sulle successio-ni sviluppate qui di seguito, superano di gran lunga, per quantoriguarda la generalita, tutte le proposizioni simili che possanovenire derivate da una qualsiasi intuizione di successioni.23

Per esporre il lavoro di Frege in modo comprensibile senza dover imparareil suo formalismo, utilizziamo una traduzione nei linguaggi della logica con-temporanea.24 Per restare fedeli alla generalita dei suoi risultati dovremmoconsiderare soltanto una relazione binaria S, in un dominio senza elementiprivilegiati come lo zero. Tuttavia per ridurre la complessita della trattazio-ne, consideriamo una relazione funzionale e la rappresentiamo con il simbolodi funzione S.

A differenza di quanto si assume nei linguaggi logici attuali, la funzionedenotata dal simbolo S deve pero essere parziale.

I simboli funzionali dei linguaggi predicativi denotano funzioni totalinon tanto per comodita quanto come conseguenza della validita generaledell’assioma di generalizzazione esistenziale del primo ordine

A[t/y]→ ∃yA,

dove A[t/y] e il risultato della sostituzione di t a qualche occorrenza liberadi y in A.25 Esso infatti giustifica la derivazione

∀x(Sx = Sx)∀x∃y(Sx = y)

che stabilisce il carattere totale della funzione.

23Logica e aritmetica, cit. p. 169.24La traduzione e dovuta a F. Previale in Due crediti di logica, prossima pubblicazione.25t deve soddisfare una condizione (di essere libero per y in A) sulla quale possiamo

sorvolare.

30

Per evitare tale conseguenza, restringiamo l’assioma di generalizzazioneesistenziale al caso che t sia una variabile o una costante.

Se introduciamo l’abbreviazione

t↓ ↔ ∃y(t = y)

per affermare che t e definito (ha un valore), abbiamo comunque a disposi-zione l’assioma di generalizzazione esistenziale nella forma

A[t/y] ∧ (t)↓→ ∃yA.

Infatti se A[t/y] ∧ ∃z(t = z) si ha A[t/y] ∧ t = z da cui A[z/y] e ∃yA.

Tale restrizione si estende alla particolarizzazione universale

∀yA→ ((t)↓→ A[t/y]).

Ne segue che e richiesta la condizione di esistenza per i termini che si sosti-tuiscono negli assiomi dell’uguaglianza, che sono:

∀x(x = x)∀x, z(x = z → A[x/y]→ A[z/y]).

Nella deduzione di A[t/y] ∧ (t)↓→ ∃yA di sopra l’applicazione degli assiomidell’uguaglianza e permessa dall’ipotesi (t)↓.

A parte queste varianti, adottiamo per il linguaggio con il solo S la logicadel secondo ordine.26

Diamo ora la

Definizione x ≤ y ↔ ∀Z(Zx ∧Her(Z)→ Zy)

doveHer(Z)↔ ∀v(Zv ∧ (Sv)↓→ ZSv).

Her(Z) e una abbreviazione per la condizione che se v ha la proprieta Ze se esiste Sv, anche Sv ha la proprieta Z, e costituisce la definizione di“ereditaria”.

La relazione x ≤ y vuole esprimere il fatto che o y coincide con x o siottiene da x con una sequenza finita di applicazioni di S.

Si dimostrano le seguenti proprieta:

26Per non appesantire le formule, non usiamo le parentesi nelle parole come i terminifunzionali St o le formule atomiche Zt.

31

1. x ≤ x

Segue dalla definizione di ≤, per la tautologia A ∧B → A.

In realta si ha t ≤ t per ogni t, per lo stesso motivo.

2. (Sx)↓→ x ≤ Sx

Per avere x ≤ Sx occorre derivare ZSx da Zx e da ∀v(Zv ∧ (Sv)↓→ZSv), per una Z qualunque. Particolarizzando in quest’ultima v conx e usando Zx e (Sx)↓, si ha ZSx.

3. x ≤ y ∧ y ≤ z → x ≤ z

Supponiamo che aver dimostrato che Pv ↔ x ≤ v e ereditaria. Allorasiccome da y ≤ z segue Py ∧Her(P )→ Pz, si ha y ≤ z → (x ≤ y →x ≤ z) e usando anche x ≤ y si ha la conclusione.

Per dimostrare che P e ereditaria bisogna dedurre PSv da Pv e (Sv)↓,cioe x ≤ Sv da x ≤ v e (Sv)↓.x ≤ Sv, che dobbiamo dedurre, esplicitata e

∀Z(Zx ∧ ∀w(Zw ∧ (Sw)↓→ ZSw)→ ZSv).

Per una Z fissata assumiamo

Zx ∧ ∀w(Zw ∧ (Sw)↓→ ZSw)

per dedurre ZSv. Assumiamo cioe Zx e che Z sia ereditaria; allora dax ≤ v segue Zv. Se ora in ∀w(Zw ∧ (Sw)↓→ ZSw) particolarizziamow a v, e usiamo anche (Sv)↓, abbiamo ZSv.

4. x ≤ y ↔ x = y ∨ ((Sx)↓ ∧Sx ≤ y)

← Per casi. Se x = y allora x ≤ y da 1. e assiomi dell’uguaglianza.Se (Sx) ↓ e Sx ≤ y, da 2. segue x ≤ Sx e per la transitivita laconclusione voluta.

→ Dimostriamo che Pv ↔ x = v∨((Sx)↓ ∧Sx ≤ v) e ereditaria, dalche segue che siccome vale per x e x ≤ y, allora Py, che e la conclusionevoluta.

Per dimostrare che P e ereditaria, da Pv e (Sv)↓ occorre dedurre PSv.Assunto Pv, si hanno due casi: se x = v, allora da (Sv)↓ segue (Sx)↓e anche Sx ≤ Sv, cioe la conclusione voluta PSv. Se invece Pv vale

32

perche (Sx)↓ ∧Sx ≤ v, da (Sv)↓ segue v ≤ Sv quindi Sx ≤ Sv; questacongiunta con (Sx)↓ da PSv.

Definizione x < y ↔ (Sx)↓ ∧Sx ≤ y

Con questa definizione, la 4. diventa

4’. x ≤ y ↔ x = y ∨ x < y

5. (Sx)↓→ x < Sx

Da (Sx)↓ segue (Sx)↓ ∧Sx ≤ Sx (quest’ultima dalla 1., dove si puosostituire Sx a x perche (Sx)↓).

6. x < y ∧ y < z → x < z

In verita basta y ≤ z. Infatti x < y e (Sx)↓ ∧Sx ≤ y e quindi cony ≤ z implica (Sx)↓ ∧Sx ≤ z quindi x < z.

Le relazioni ≤ e < non sono relazioni d’ordine, non si riesce a dimo-strare antiriflessivita per < e l’antisimmetria. Vale invece una forma diconfrontabilita, tra elementi che abbiano un comune minorante.

7. z ≤ x ∧ z ≤ y → x < y ∨ y ≤ x

Supponiamo che Pv ↔ x < v ∨ v ≤ x sia ereditaria; allora dall’antece-dente, siccome P vale per z e z ≤ y, P vale per y.

Per dimostrare che P e ereditaria, assumiamo Pv e (Sv)↓ per dedurrePSv. Pv e una disgiunzione; se x < v, da (Sv)↓ segue v < Sv e quindix < Sv, cioe PSv. Se v ≤ x, per 4. o v = x o Sv ≤ x. Se v = x si hax < Sv da v < Sv, quindi PSv. Se Sv ≤ x si ha PSv.

Segnaliamo anche la forma che potrebbe assumere il principio di induzio-ne, che non e tuttavia mai usato da Frege, che risale sempre alla dimostrazioneche certe proprieta sono ereditarie:

8 ∀Z(Her(Z) ∧ Zx→ ∀y(x ≤ y → Zy))

che segue dalla definizione di ≤ con manipolazioni elementari.

33

Per rimediare al silenzio nel quale era caduta la sua opera, Frege pubbliconel 1884 Die Grundlagen der Arithmetik ,27 dove un’esposizione informale,senza uso dell’ideografia, presenta la definizione dei numeri naturali, basatasui risultati relativi alle successioni esposti nella Begriffschrift , oltre a unaampia discussione delle motivazioni e a una critica delle concezioni alternativeche erano diffuse nell’Ottocento, e anche prima.

Il seguito formale della trattazione della Begriffschrift si trova nel primovolume delle Grundgesetze del 1893.28 Essa e rivolta non solo a definire unarelazione ≤ come iterazione di una S, ma a definire i numeri naturali e larelazione S, funzionale e iniettiva, che li genera.

Per semplicita, discostandoci dal procedimento di Frege, introduciamo iseguenti assiomi,29 dopo aver aggiunto al linguaggio la costante individuale0,

α1 ∀x, y((Sx)↓ ∧(Sy)↓ ∧Sx = Sy → x = y)

α2 ∀x¬(Sx = 0).

L’interpretazione del linguaggio e ora costituita da strutture 〈M, 0, S〉 (iden-tificando i simboli e la loro denotazione), dove S e una funzione parzialeiniettiva sul suo dominio, e 0 non appartiene all’immagine di S.

Senza ancora fare appello agli assiomi, stabiliamo

9. x ≤ y ↔ x = y ∨ ∃z(Sz = y ∧ x ≤ z)

← Da x = y segue ovviamente x ≤ y; da ∃z(Sz = y ∧ x ≤ z) segueche (Sz)↓, quindi z ≤ Sz e per la transitivita x ≤ y.

→ Si dimostra che Pv ↔ x = v ∨ ∃z(Sz = v ∧ x ≤ z) e ereditaria(esercizio) da cui segue la conclusione.

Introduciamo ora la

Definizione x <∗ y ↔ ∃z(Sz = y ∧ x ≤ z)

dove invece di chiedere, come per x < y, che Sx ≤ y, si chiede che x siaminore o ugale del “predecessore” di y.

Con questa definizione la 9. diventa

27G. Frege, Die Grundlagen der Arithmetik , Koebner, Breslau.28G. Frege, Grundgesetze der Arithmetik , vol. I, Pohle, Jena.29Frege non assume alcun assioma, coerente con la sua volonta di dare una definizione

logica dei numeri naturali. Dimostrera, come vedremo, queste due proprieta, quando avradefinito la relazione S.

34

9’. x ≤ y ↔ x = y ∨ x <∗ y

Non e difficile dimostrare

10. x <∗ Sx

11. x <∗ y ∧ y <∗ z → x <∗ z

e dalla 4’. e 9’.

12. x 6= y → (x <∗ y ↔ x < y)

La relazione <∗ viene introdotta solo come artificio tecnico per la dimo-strazione piu agevole delle successive proprieta, finalizzate a dimostrare che≤ e < sono ordini, rispettivamente non stretto e stretto. Elenchiamo i passiche portano alle conclusioni volute, senza dare le dimostrazioni, e limitandocia segnalare dove si incominciano a usare gli assiomi.

13. (Sx)↓→ (x <∗ Sy ↔ x ≤ y)

x <∗ Sy equivale a ∃z(Sz = Sy ∧ x ≤ z); per α1 questa equivale a∃z(z = y ∧ x ≤ z), quindi a x ≤ y.

14. ¬(x <∗ 0)

x <∗ 0 implica che, per qualche z, Sz = 0, contro α2.

15. 0 ≤ y → (x <∗ y ↔ x < y)

16. 0 ≤ y ∧ (Sy)↓→ (x < Sy ↔ x ≤ y)

17. 0 ≤ x→ ¬(x < 0)

18. 0 ≤ y ∧ (Sy)↓→ (x < y ↔ Sx < Sy)

19. 0 ≤ x→ ¬(x < x)

20. 0 ≤ x→ ¬(x < y ∧ y < x)

21. 0 ≤ x→ (x ≤ y ∧ y ≤ x→ x = y)

22. 0 ≤ x ∧ 0 ≤ y → x < y ∨ y ≤ x

35

Con questo le proprieta delle relazioni d’ordine < e ≤ sono stabilite, sullabase di α1 e α2. Se ora assumiamo che S sia ovunque definita, ∀x(Sx)↓,abbiamo anche

23. 0 ≤ x→ ∃y∀z(z ≤ x→ z 6= y)

Da 4’., 5. e 6., assumendo (Sx)↓, segue ∀z(z ≤ x→ z < Sx); da 19.,assumento 0 ≤ x, segue percio ∀z(z ≤ x→ z 6= Sx), e Sx e l’y cercato.

Si puo ora porre Nx ↔ 0 ≤ x. Resta pero da dimostrare l’esistenzadi un sistema con una S totale soddisfacente gli assiomi. Abbiamo visto lasoluzione di Dedekind.

La via seguita da Frege e la seguente, che esponiamo in una terminologiainsiemistica, alla Russell in effetti, per facilitare la comprensione e il confrontocon le altre soluzioni.

Scriviamo x ∼ y per dire che esiste una corrispondenza biunivoca tra xe y. Per ogni x, il numero cardinale (o la cardinalita, o la potenza) di x el’insieme

x = {y | y ∼ x}.

La relazione ∼ e una relazione di equivalenza e le {y | y ∼ x} sono le classidi equivalenza (a parte il problema non da poco che non sono insiemi).

Segue ovviamentex = y ↔ x ∼ y.

Cantor invece fara appello a una capacita di astrazione che da un insiemeproduce un oggetto, il numero:

Chiameremo “potenza” o “numero cardinale” di M il concettogenerale che, per mezzo della nostra facolta di pensiero, sorgedall’aggregato M quando noi facciamo astrazione dalla naturadei suoi vari elementi m e dall’ordine in cui essi sono dati.

Le due diverse impostazioni non influiscono sulla definizione dei numerinaturali e della funzione successore.

Usiamo lettere in grassetto per denotare cardinali (costanti o variabili).Allora per Frege

0 = y↔ ∃y(y = y ∧ ∀z(z /∈ y))1 = y↔ ∃y(y = y ∧ ∃u∀z(z ∈ y ↔ z = u))

36

ma piu in generale

Sx = y↔ ∃x, y, z(x = x ∧ y = y ∧ z /∈ x ∧ y = x ∪ {z}).Si dimostra che S e funzionale (derivandolo dal fatto che se y1 = x∪{z1}

e y2 = x ∪ {z2} allora y1 ∼ y2, se z1 /∈ x e z2 /∈ x), che S e iniettiva e che0 non e Sx per nessun x. Non si puo dimostrare in generale che Sx 6= x(perche infatti non e vero per gli x infiniti).

Se si definisce ≤ come l’iterazione finita di questa S, o come dira Russell,la posterita di 0 rispetto a S, e si pone

N = {x | 0 ≤ x},

si ha che 〈N,0, S〉 soddisfa α1 e α2 ed S e ovunque definita in questastruttura. Quest’ultima affermazione segue da

24. ∀x,y(x = {z | z < y} ∧ 0 ≤ y→ x = y)

Facciamo che vedere che Pv ↔ ∀x(x = {z | z < v} → x = v) eereditaria. Dopo di che, dalla 8., se P0 allora per ogni y tale che0 ≤ y, cioe per tutti gli elementi di N, si ha Py. P0 vale perche

qualunque x soddisfacente l’antecedente e vuoto, e ∅ = 0.

Ammesso Py e supponendo Sy definito dimostriamo PSy. Sia x ={z | z < Sy}; dobbiamo dimostrare x = Sy. Ma x = {z | z ≤ y} ={z | z < y} ∪ {y}, e per Py se u = {z | z < y} allora u = y. Oray /∈ u, perche ¬(y < y), quindi x = Su, x = Sy.

In particolare, dalla dimostrazione risulta che per ogni y ∈ N si ha Sy = xdove x = {z | z ≤ y}, e S e definita.

37

Assioma di scelta30

L’enunciato dell’assioma di scelta AC e uno dei seguenti, o ancora altri chesono tutti equivalenti tra loro nella teoria di Zermelo:

1. Se a 6= ∅ e x ⊆P(a) \ {∅} e x 6= ∅ esiste c : x −→ a tale che per ogniy ∈ x c(y) ∈ y.

c si dice funzione di scelta per x, o anche per i sottoinsiemi di a sex = P(a) \ {∅}.

2. Se x 6= ∅ e per ogni y ∈ x y 6= ∅ allora esiste una funzione c : x −→ ∪xtale c(y) ∈ y per ogni y ∈ x (c funzione di scelta per x).

3. Se x 6= ∅ e per ogni y ∈ x y 6= ∅ e gli elementi di x sono a due a duedisgiunti allora esiste un insieme c tale che per ogni y ∈ x ∃u(c ∩ y ={u}).c si dice insieme di scelta per x.

4. Se x 6= ∅ e per ogni y ∈ x y 6= ∅ allora Πx 6= ∅, dove il prodotto di x,Πx, e l’insieme delle funzioni f : x −→ ∪x tali che f(y) ∈ y per ogniy ∈ x (assioma moltiplicativo).

5. Per ogni r che sia una relazione, esiste una funzione f ⊆ r con dom(f) =dom(r):

∀r(Rel(r)→ ∃f(Fn(f) ∧ f ⊆ r ∧ dom(f) = dom(r))).

L’assioma delle scelte numerabili e l’assioma di scelta con la restrizione, adesempio in 1 o in 3, che x sia numerabile (ma non i suoi elementi; questo e unaltro tipo di distinzione che da origine ad altri casi particolari). In generalese k e un numero cardinale infinito, con k-AC si indica l’assioma di sceltacon la restrizione che x abbia cardinalita k.

L’assioma delle scelte dipendenti e la seguente assunzione

30Per altri risultati, si veda [?], Jech e Rudin e Rudin.

38

DC Se r e una relazione in x tale che per ogni u ∈ x esiste v ∈ x taleche 〈u, v〉 ∈ r, allora esiste una successione {an}n∈N tale che 〈an, an+1〉 ∈ rper ogni n ∈ N.

DC e conseguenza di AC ma piu debole ed e stato formulato da PaulBernays nel 1942. A sua volta DC implica ℵ0-AC.

Il principio di partizione (Burali-Forti, Levi) e l’affermazione, conseguen-za di AC,

Se un insieme x e ripartito in un insieme s di sottoinsiemi disgiunti31, sha cardinalita minore o uguale a quella di x.

A meno di risultati recenti, fino a poco tempo fa non si sapeva se ilprincipio di partizione e equivalente ad AC.

Conseguenze dell’assioma di scelta

1. Ogni insieme infinito e l’unione di un insieme di sottoinsiemi numerabilidisgiunti.

2. Se k e infinito, k = 2k.

3. Se k e infinito, k = ℵ0 · k.

4. Se k e infinito e h ≤ k allora k + h = k.

5. Se Ai e equipotente a Bi e Ai ∩ Ai = Bi ∩ Bj = ∅ per ogni i, j ∈ C,allora

⋃i∈C Ai e equipotente a

⋃i∈C Bi.

6.∑

a∈AB = A ·B.

7. ℵα+1 e regolare, per ogni α.

8. Il principio di partizione.

Conseguenze del principio di partizione

1. Per ogni A e funzione f , f“A ≤ A.

31Cio significa che s ⊆P(x), e per u, v ∈ S, se u 6= v allora u ∩ v = ∅, e x = ∪s.

39

2. Se R e scomposto in due insiemi disgiunti, uno almeno ha cardinalita2ℵ0 .

3. L’insieme dei sottoinsiemi numerabili di R ha cardinalita 2ℵ0 .

4. Esiste un sottoinsieme non misurabile secondo Lebesgue di R.

5. Assioma delle scelte dipendenti.

Conseguenze dell’assioma delle scelte dipendenti

1. Se 〈M,<〉 non ha catene discendenti infinite, e un buon ordine.

2. Se 〈M,<〉 non ha un ultimo elemento, contiene un sottoinsieme di tipoω.

3. Lemma di Konig.

4. In R ci sono esattamente 2ℵ0 insiemi di Borel.

5. Esiste in R un insieme misurabile secondo Lebesgue non misurabilesecondo Borel.

6. Teorema di Lowenhein-Skolem.

7. Assioma delle scelte numerabili.

Conseguenze dell’assioma delle scelte numerabili

1. Ogni insieme non riflessivo e finito (equivalente a un n).

2. Se a e un insieme infinito di insiemi disgiunti, ∪a e infinito.

3. L’unione di un insieme numerabile di insiemi finiti e numerabile.

4. L’unione di un insieme numerabile di insiemi numerabili e numerabile.

5. Il limite di una successione crescente numerabile di ordinali numerabilee numerabile.

6. L’unione di un insieme numerabile di insiemi ciascuno di cardinalita ℵαha cardinalita ℵα, per ogni α.

40

7. La misura di Lebesgue e numerabilmente additiva.

8. Se una funzione di variabile reale e sequenzialmente continua in unpunto, e ivi continua.

9. Un sottospazio di uno spazio metrico separabile e separabile.

Equivalenti dell’assioma di scelta

1. Principio del buon ordinamento Ogni insieme e bene ordinabile.

2. Teorema degli aleph.

3. Tricotomia Per ogni a e b, o card(a) < card(b) o card(a) = card(b) ocard(b) < card(a).

4. Se k e infinito e h ≤ k, allora h · k = k.

5. h · k = h+ k per ogni h e k infiniti.

6. Assioma moltiplicativo: Se {Xi}i∈I e una famiglia disgiunta di insieminon vuoti, Πi∈IXi non e vuoto.

7. Teorema di Zermelo-Konig: Se per ogni i ∈ I hi < ki,∑i∈I

hi < Πi∈Iki.

8. Lemma di Zorn Se 〈a,≤〉 e un insieme parzialmente ordinato in cui ognicatena ha un maggiorante, allora esiste in a un elemento ≤-massimale.

9. Principio di Kuratowski Se a e un insieme di insiemi parzialmenteordinato da ⊆, esiste in a un elemento ⊆-massimale.

10. Principio di Hausdorff Se r e una relazione transitiva, esiste una r-catena massimale.

11. Lemma di Teichmuller-Tuckey Ogni in insieme a carattere finito32 con-tiene un elemento ⊆-massimale.

32Un insieme a ⊆ P(x) ha carattere finito se per ogni y ⊆ x, y ∈ a se e solo se ognisottoinsieme finito di t appartiene ad a.

41

12. Teorema dell’ideale massimale per reticoli. Ogni reticolo con > e alme-no un altro elemento, ha un ideale massimale, e ogni ideale puo essereesteso a un ideale massimale.

Conseguenze matematiche dell’assioma di scelta

1. Ogni spazio vettoriale ammette una base.

2. Ogni campo ammette una chiusura algebrica, unica a meno di isomor-fismi.

3. Teorema dell’ideale primo per algebre di Boole In ogni algebra di Booleogni ideale si puo estendere a un ideale primo.

4. Teorema di rappresentazione di Stone Ogni algebra di Boole e isomorfaa un’algebra di insiemi.

5. Teorema di compattezza Ogni insieme di proposizioni ammette unainterpretazione se e solo se ogni sottooinsieme finito ne ammette una.

6. Teorema di Hahn-Banach Se p e un funzionale sublineare su uno spaziovettoriale reale E e φ e un funzionale lineare su un sottospazio V ⊆ E,e φ(x) ≤ p(x) su V , esiste ψ lineare su E che estende φ e per cui ancoraψ(x) ≤ p(x) su E.

7. Teorema di Vitali Se µ e una misura a valori positivi o nulli definita susottoinsiemi di R, invariante per traslazioni, numerabilmente additivae tale che la misura degli intervalli e la differenza degli estremi, alloraesiste un sottoinsieme di R su cui µ non e definita.

8. Paradosso di Banach-Tarski Se U e una sfera chiusa, esistono due sferechiuse U1 e U2, disgiunte, entrambe equivalenti a U per decomposizionefinita33.

33A e B si dicono equivalenti per decomposizione finita se esistono due partizioni A =A1 ∪ . . .∪An e B = B1 ∪ . . .∪Bn tale che ogni Ai = f(Bi) dove f e un movimento rigido.

42

Gli assiomi di Z

Gli assiomi della teoria Z di Zermelo sono oggi presentati nel seguente modo,in un linguaggio del primo ordine con il solo simbolo relazionale binario ∈.

Secondo l’uso, sono via via introdotti simboli definiti per operazioni ecostanti, verificando facilmente che sono soddisfatte, grazie al primo assioma,la condizione logica dell’unicita della loro definizione34:

Assioma di estensionalita:

∀x∀y(x = y ↔ ∀z(z ∈ x↔ z ∈ y)),

due insiemi sono uguali se e solo se hanno gli stessi elementi.

Assioma dell’insieme vuoto:

∃x∀y(y 6∈ x)

indicato con ∅.L’insieme vuoto non ha alcun elemento.

Assioma della coppia:

∀x∀y∃z∀u(u ∈ z ↔ u = x ∨ u = y)

indicata con {x, y}.La coppia di x e y ha come elementi solo x e y.

Assioma dell’unione:

∀x∃z∀u(u ∈ z ↔ ∃y ∈ x(u ∈ y))

indicata con ∪x.L’unione di x ha come elementi gli elementi degli elementi di x.

Assioma della potenza:

∀x∃z∀u(u ∈ z ↔ u ⊆ x)35

34Si veda l’Appendice 2 per un ripasso delle condizioni per l’introduzione di nuovi simbolidefiniti.

35u ⊆ x e un’abbreviazione per ∀v(v ∈ u→ v ∈ x).

43

indicata con P(x).La potenza di x ha come elementi i sottoinsiemi di x.

Assioma dell’infinito:

∃x(∅ ∈ x ∧ ∀y(y ∈ x→ {y} ∈ x)),

ovvero: esiste un insieme che non e vuoto, in quanto contiene ∅, e per ognisuo elemento ne contiene uno diverso.

Assioma di separazione36:

(Schema di assiomi) Per ogni formula ϕ(u, . . .) non contenente x libera

∀ . . . ∀x∃z∀u(u ∈ z ↔ u ∈ x ∧ ϕ(u, . . .))

ovvero: esiste il sottoinsieme di x formato dagli elementi di x che soddisfanoϕ, indicato con z = {u ∈ x : ϕ(u, . . .)}.Assioma di fondazione37:

∀x∃y ∈ x∀u(u ∈ y → u 6∈ x)

ovvero: l’appartenenza e ben fondata, non ci sono catene discendenti rispettoa ∈ (e in particolare {u} 6= u).

Assioma di scelta:

∀x(∀y ∈ x(y 6= ∅) ∧ ∀y, z ∈ x(y ∩ z = ∅)→ ∃z∀y ∈ x∃u(z ∩ y = {u}))38.

ovvero: per ogni insieme non vuoto di insiemi non vuoti e a due a duedisgiunti x esiste un insieme che contiene un solo elemento di ogni elementodi x. Si puo precisare che tale insieme (z nella formula) e contenuto in ∪x.

Gli assiomi non sono indipendenti tra loro; ad esempio l’esistenza del-l’insieme vuoto si puo ottenere dalla separazione applicata con una condi-zione contraddittoria a un insieme qualsiasi (che esiste, perche ∃x(x = x) elogicamente vero).

36Oppure “di isolamento”, o “dei sottoinsiemi”.37L’assioma di fondazione non era tra quelli indicati da Zermelo, ma per il confronto

con ZF che lo contiene si preferisce aggiungerlo anche a Z.38L’intersezione di due insiemi si definisce con l’assioma di separazione come sottoinsieme

di uno qualunque dei due insiemi.

44

Gli assiomi di ZF

L’assioma di rimpiazzamento nelle formulazioni attuali recita:

Assioma di rimpiazzamento (Schema) Per ogni formula ϕ(u, v, . . .) dellinguaggio con il solo simbolo relazionale ∈, non contenente x libera

∀ . . . (∀x∃1yϕ(x, y, . . .)→ ∀u∃v∀y(y ∈ v ↔ ∃x ∈ uϕ(x, y, . . .)))

ovvero: per ogni operazione funzionale definibile, quando essa e ristretta aun insieme esiste l’insieme delle immagini39.

In alternativa, si puo chiedere nell’antecedente dell’assioma che per ognix esista al massimo un y, come in Skolem; le due versioni sono equivalenti.

Dall’assioma di rimpiazzamento si ricava quello di separazione, che diven-ta superfluo; la derivazione richiede tuttavia l’assioma dell’insieme vuoto, chenon si puo quindi derivare in un secondo momento dalla separazione, comee possibile in Z.

Se si vuole applicare la separazione a un insieme x con una formulaϕ(z, . . .),

∃y∀z(z ∈ y ↔ z ∈ x ∧ ϕ(z, . . .)),

si distinguano due casi: se non esistono z in x tali che ϕ(z, . . .), si pon-ga y = ∅; se ne esistono, sia z0 uno di questi e si consideri (ϕ(z, . . .) ∧u = z) ∨ (¬ϕ(z, . . .) ∧ u = z0), indicata con ψ(z, u, . . .). Si verifica che∀z∃1uψ(z, u, . . .). Per il rimpiazzamento, dato x esiste un v tale che i suoielementi sono esattamente gli u per cui ∃z ∈ xψ(z, u, . . .) cioe gli u per cui∃z(z ∈ x ∧ ϕ(z, . . .) ∧ u = z), piu z0, cioe gli u per cui u ∈ x ∧ ϕ(u, . . .).

Una volta che si abbia la separazione, con il rimpiazzamento si puo evitarel’assioma della coppia. Si noti che i singoletti {x} esistono come sottoinsiemidi P(x) per separazione. Si ha cosı l’esistenza di {∅, {∅}} = P(∅); conl’insieme di questi due elementi, come fossero 0 e 1, con il rimpiazzamento sipossono formare insiemi che contengono esattamente x e y, per ogni x e y.

Una formulazione suggestiva dell’assioma di rimpiazzamento e quella che,dalla stessa premessa, conclude

∀a∃f(fun(f) ∧ ∀z(z ∈ f ↔ (z)1 ∈ a ∧ ϕ((z)1, (z)2, . . .))),

39Il ∀ . . . iniziale si riferisce alla quantificazione universale dei parametri contenuti inϕ(u, v, . . .).

45

dove (z)1 e (z)2 sono le due proiezioni di z. Da questa forma non si potrebbetuttavia derivare la separazione, a meno di un ulteriore assioma che affermiche per ogni insieme che sia una funzione esiste l’insieme immagine.

L’assioma di rimpiazzamento permette di estendere il teorema di ricor-sione, che afferma esistenza e unicita della funzione f definita su un buonordine 〈a,≺〉 da

f(x) = g({f(y) | y ≺ x}),ai casi in cui {f(y) | y ≺ x} non e un sottoinsieme di un insieme gia dato.

Il risultato principale da cui seguono le altre applicazioni e il teorema cheogni buon ordine e isomorfo a un ordinale40.

L’altro assioma che manca per completare ZF e

Assioma di fondazione:

∀x∃y ∈ x∀u(u ∈ y → u 6∈ x).

L’assioma rende superflui gli assiomi di regolarita che escludono gli ∈-cicli.Il concetto che e alla base di questo assioma era stato anticipato da Mi-

rimanoff nel 191741, che aveva considerato gli insiemi che chiamava ordinari,cioe gli insiemi a per i quali tutte le catene discendenti, rispetto a ∈, chepartono da elementi di a sono finite. Tali insiemi saranno poi detti benfondati.

L’assioma e dovuto a John von Neumann (1903-1957)42. Esso permettedi semplificare la trattazione degli ordinali, che possono essere definiti comeinsiemi transitivi e connessi dalla relazione ∈ ristretta ai loro elementi, il buonordine essendo assicurato dalla proprieta di buona fondatezza di ∈ garantitadall’assioma.

Un interesse metamatematico degli insiemi ben fondati e che essi costi-tuiscono un modello degli assiomi di ZF, in un senso che evita la circola-rita di considerare un insieme come modello della teoria degli insiemi; essirappresentano il primo e piu semplice esempio di tale concetto.

Si definisca la relativizzazione di una formula ϕ a un insieme x comesegue:

40Si veda G. Lolli, Dagli insiemi ai numeri , Boringhieri, Torino, 1994, cap. 8.41D. Mirimanoff, “Les antinomies de Russell et de Burali-Forti et le probleme fon-

damentale de la theorie des ensembles”, L’enseignement mathematique, 19 (1917), pp.37-52.

42J. von Neumann, “Uber die Definition durch transfinite Induktion und verwandteFragen der allgemeinen Mengenlehre”, Mathematische Annalen, 99 (1928), pp. 373-91.

46

ϕ(x)(u, . . .) = ϕ ∧ u, . . . ∈ x(¬ϕ)(x) = ¬(ϕ(x))(ϕ • ψ)(x) = ϕ(x) • ψ(x)

(∀uϕ)(x) = ∀u ∈ xϕ(x).

Si chiami ora “classe” una formula con una variabile libera ϕ(x); incorrispondenza ad essa si puo introdurre un nuovo simbolo predicativo Φcon la convenzione di scrivere x ∈ Φ invece di Φ(x) e con la definizionex ∈ Φ↔ ϕ(x).

La classe V e il simbolo di classe associato a x = x, o universo. La classeOn e il simbolo associato a “x e un ordinale”.

La relativizzazione di una formula ϕ a una classe X e definita esattamentecome la relativizzazione a un insieme.

Una classe X si dice un modello interno della teoria degli insiemi T se

T ` ϕ(X)

per ogni assioma ϕ di T .Piu in generale, la teoria T dimostra che X e un modello interno della

teoria S seT ` ϕ(X)

per ogni assioma ϕ di S.Sia ZF− la teoria ZF meno l’assioma di fondazione. Il teorema di ricorsio-

ne e tutto quanto riguarda gli ordinali si dimostra ugualmente, modificandola definizione degli ordinali con l’aggiunta della condizione del buon ordi-ne. Si puo allora definire una gerarchia, detta di von Neumann, iterandol’operazione di insieme potenza su tutti gli ordinali:

V0 = ∅Vα+1 = Vα ∪P(Vα)Vλ =

⋃α∈λ Vα

e ponendo uguale a N la classe⋃α∈On Vα. La formula che la definisce e

∃α(On(α) ∧ x ∈ Vα).43

La gerarchia si suole rappresentatare, graficamente e intuitivamente, con

43Che x ∈ Vα sia una formula deriva dal teorema di ricorsione.

47

��������������������

AAAAAAAAAAAAAAAAAAAA

∅

Vω

Vα

ω

α

Si dimostra:

Teorema 3 N e un modello interno di ZF−,

e anche, se ϕ e l’assioma di fondazione,

Teorema 4 ZF− ` ϕ(N).

Il teorema si interpreta dicendo che la gerarchia di von Neumann e la ge-rarchia degli insiemi ben fondati. Se ora si potesse dimostrare una contrad-dizione in ZF, siccome in ZF− si dimostrano tutte le relativizzazioni a Ndegli assiomi coinvolti nella dimostrazione della contraddizione, si potrebbederivare la contraddizione stessa44 in ZF−.

Questa situazione si esprime dicendo che la teoria ZF e non contradditto-ria relativamente alla teoria ZF−, o anche che l’assioma di fondazione e noncontraddittorio con i restanti assiomi di ZF.

Se si assume l’assioma di fondazione, si ha V = N , o

V =⋃α∈On

Vα.

Questo mostra che la teoria degli insiemi, una volta completata con gliassiomi di rimpiazzamento e fondazione, non e troppo diversa dalla strutturadella teoria dei tipi, che vedremo nel prossimo capitolo. Anche gli insiemidi ZF sono stratificati in livelli, sia pure cumulativi (se x ∈ Vα ∈ Vβ, allorax ∈ Vβ).

44Si puo assumere che sia una formula senza quantificatori e senza variabili libere.

48

La teoria dei tipi

La teoria dei tipi e un sistema di logica, piu che di teoria degli insiemi.45

la teoria predicativa dei tipi PT

Definizione induttiva di simbolo di tipo:

(i) o e un simbolo di tipo;(ii) se t1, . . . , tn sono tutti simboli di tipo, (t1, . . . , tn) e un simbolo di tipo;(iii) null’altro e un simbolo di tipo.

Intuitivamente: gli individui sono le cose di tipo o; un insieme di individuiha tipo (o); una relazione binaria tra individui ha tipo (o, o); una relazionebinaria tra individui e relazioni binarie tra individui ha tipo (o, (o, o)), e cosıvia.

Una gerarchia di tipi basata sull’insieme non vuoto D e la collezione ditutte le relazioni tipate su D. Le relazioni tipate su D sono individuate dallaseguente definizione induttiva:

(i) un elemento di D e una relazione di tipo o;(ii) un insieme di n-uple di elementi diD e una relazione di tipo (o, o, . . . , o︸ ︷︷ ︸

n

);

(iii) una relazione di tipo t = (t1, . . . , tn) e un insieme di n-uple 〈r1, . . . , rn〉,dove ogni ri e di tipo ti, per 1 ≤ i ≤ n.

Se D e D′ sono due insiemi non vuoti della stessa cardinalita, le gerarchiedi tipi basate su D e rispettivamente D′ sono isomorfe.

Nella teoria dei tipi si tiene presente il rapporto tra il modello intuitivo diuna gerarchia di tipi e il linguaggio formale: si parla di tipo di una relazionenella gerarchia di tipi e di tipo di un termine nel linguaggio formale.

Alfabeto di PT, la teoria predicativa dei tipi:

per ogni tipo t, una lista infinita di variabili {xtn}1≤n di tipo t;per ogni tipo t, una lista infinita di costanti {atn}1≤n di tipo t;

45Da W. S. Hatcher, Foundations of Mathematics, W. B. Saunders, Philadelphia, 1968;trad. it. Fondamenti della matematica, Boringhieri, Torino, 1973, cap. 4. I sistemipresentati in questa appendice sono quelli classici che risalgono al lavoro di Russell; unanuova teoria, che ha influenzato la costruzione di linguaggi di programmazione tipati, estata elaborata negli ultimi anni da Martin-Lof: si veda Per Martin-Lof, IntuitionisticType Theory , Bibliopolis, Napoli, 1984.

49

parentesi, virgola, negazione, disgiunzione, accento circonflesso, ∀, ∃.Definizione induttiva simultanea dei termini e delle formule:

(i) una variabile o una costante di un dato tipo sono termini di quel tipo;(ii) Se A e un termine di tipo (t1, . . . , tn) e se y1, . . . , yn sono termini

rispettivamente di tipo t1, . . . , tn, allora A(y1, . . . , yn) e una formula;46

(iii) se A e B sono formule, anche (¬A) e (A ∨B) sono formule;47

(iv) se A e una formula e y una variabile, anche (∀y)A e (∃y)A sonoformule;

(v) se A e una formula e y1, . . . , yn (n > 0) sono variabili libere distintenell’ordine della loro prima occorrenza in A da sinistra a destra, e sono ri-spettivamente di tipo t1, . . . , tn, l’espressione che si ottiene da A mettendoun accento circonflesso su tutte le occorrenze delle variabili libere della listay1, . . . , yn e chiudendo il risultato in parentesi e un termine di tipo (t1, . . . , tn),che si chiama astratto. Le variabili y1, . . . , yn sono vincolate nel termine cosıformato.48

Se in A ci sono due o piu variabili dello stesso tipo, almeno una dellequali viene a essere vincolata nella formazione dell’astratto, allora le varia-bili di quel tipo che vengono circonflesse devono essere scritte a pedice deltermine, nell’ordine della prima occorrenza da sinistra a destra. Altrimentise si circonflettono due variabili dello stesso tipo in due stadi differenti del-la costruzione dell’astratto, sorgono ambiguita relativamente a quale e statocirconflesso per primo, e il risultato in genere e diverso.

46Le variabili metalinguistiche per i termini sono x, y, . . ., perche i ti sono riservati ai tipi.Per evitare confusione si potrebbe scrivere sempre anche l’indice n alle variabili, ma perevitare una scrittura troppo pesante qualche volta l’indice sara omesso, anche perche gliindici sono usati anche per numerare una successione di termini, e occorre fare attenzionealle precisazioni verbali.

47Scriviamo (A .B) per (¬((¬A) ∨ (¬B))).48Siccome le variabili di un astratto sono vincolate, la definizione di variabile libera e

vincolata di una formula deve tener conto della presenza di astratti nella formula stessa;occorre percio dall’inizio della definizione induttiva precisare la natura libera o vincolatadelle variabili che occorrono nei termini e nelle formule: rispetto a (i), in xtn, questa el’unica variabile libera e non occorrono variabili vincolate, in atn non occorrono variabililibere ne vincolate; rispetto a (ii), le variabili vincolate in A(y1, . . . , yn) quelle di A e deiy1, . . . , yn, e le variabili libere analogamente; la composizione con connettivi non modificale variabili libere e vincolate; rispetto a (iv) le variabili libere di sono quelle di (∀y)A (risp.di (∃y)A) meno y, e le vincolate quelle di A piu y.

50

Una notazione piu usuale per gli astratti, per chi e abituato alla teoriadegli insiemi, e quella di {y | A(y)} per A(y), per y libera in A.

Ovviamente anche l’interpretazione insiemistica di x(t)(xt) e (xt ∈ x(t)).

Definizione di ordine di un simbolo di tipo:

(i) l’ordine del simbolo di tipo o e 0;(ii) un simbolo di tipo della forma (t1, . . . , tn) e di ordine m + 1 se il

massimo ordine dei simboli di tipo ti e m.

In particolare un simbolo di tipo della forma (o, . . . , o) ha ordine 1.

Definizione di ordine di un termine:

(i) l’ordine di una variabile o di una costante e l’ordine del simbolo ditipo che occorre come indice nella variabile;

(ii) se A e un astratto, sia n il massimo ordine di tutte le sue variabili(vincolate e libere) e delle costanti. Se esiste una variabile vincolata y diordine n in A, A e di ordine n+ 1; se no, A e di ordine n.

Esempi Il termine (a(o)1 (xo1)) e un termine di tipo (o); l’ordine di questo

tipo e 1, e il termine stesso ha ordine 1.Il termine

((∀x(o)1 )x

(o)1 (xo1))

e un termine di tipo (o). Questo simbolo di tipo ha ordine 1, ma il termineha ordine 2 perche contiene una variabile quantificata di ordine 1.

Il termine((∃x((o))

2 )(∀x(o)1 )(x

((o))2 (x

(o)1 ) . x

(o)1 (xo1)))

ha tipo (o), di ordine 1, e ha ordine 3. E’ facile costruire esempi in cui l’ordinedi un termine e ancora maggiore dell’ordine del suo tipo.

L’ordine di un astratto e sempre maggiore o uguale dell’ordine del suotipo.

Definizione Un astratto e predicativo se e solo se l’astratto ha lo stessoordine come l’ordine del suo tipo. Altrimenti e detto impredicativo.

La spiegazione intuitiva delle precedenti definizioni e la seguente: nellateoria dei tipi le variabili di un dato tipo prendono come valori le relazionidi quel tipo in ogni gerarchia di tipi. Un astratto chiuso definisce o nominauna entita del suo tipo. Nella teoria predicativa, le relazioni e gli insiemi diuna gerarchia di tipi sono pensati come costruiti dal basso, in modo che una

51

relazione il cui tipo e di un dato ordine n > 0 e formata solo da relazioni ilcui tipo e di ordine minore di n. Gli individui, il cui tipo ha ordine 0, sonoalla base. Se un astratto chiuso A di tipo t non ha l’ordine del suo tipo, devecontenere variabili vincolate il cui tipo ha ordine maggiore o uguale a quellodel tipo di A, oppure costanti il cui tipo ha ordine maggiore del tipo di A.In ogni caso, l’astratto definisce una entita facendo riferimento a entita lacui esistenza dipende dalla esistenza di entita del tipo di quella che stiamodefinendo o superiore; questo collega il termine “predicativo” alla nozioneoriginaria del circolo vizioso.

Si puo definire un algoritmo per decidere se un astratto e predicativo ono.

Esempio di una costruzione di un termine non predicativo nella dimostra-zione che ogni insieme di numeri reali limitato superiormente ha un estremosuperiore.

Sia z un tale insieme e consideriamo l’insieme dei razionali, di tipo t, chesono elementi di elementi di z, formalmente

((∃x)(z(x). x(y)).

Sia y di tipo t ed n l’ordine di t. Allora perche l’astratto sia ben formato,deve essere x di tipo (t) e z di tipo ((t)). L’astratto ha tipo (t) e quindidovrebbe avere ordine n+ 1 per essere predicativo. Ma l’astratto contiene lavariabile libera z di ordine n+2 ed e di ordine n+2, quindi non e predicativo.

L’ordine di una formula che abbia almeno una variabile libera e definitacome l’ordine dell’astratto che si ottiene circonflettendo tutte le variabililibere della formula, e si dice predicativa se il suo ordine e uguale all’ordinedel tipo dell’astratto cosı ottenuto.

Non c’e bisogno di definire l’ordine di una formula chiusa (anche se sipotrebbe, ponendolo uguale a n+1 se nella formula il termine che ha massimoordine e una variabile, vincolata, di ordine n o una costante di ordine n+ 1).

Le variabili hanno ordine uguale all’ordine del loro tipo, per cui in realtanon stanno per entita arbitrarie del loro tipo ma solo per entita definite pre-dicativamente. Questo si realizza con una restrizione sulle regole dei quan-tificatori. Ad esempio nella particolarizzazione del quantificatore universaleil termine sostituito alla variabile deve essere dello stesso tipo e ordine della

52

variabile a cui e sostituito, e questo fa sı che debba essere predicativo: in

(∀xtn)A(xtn) . ⊃ A(y)

y deve avere tipo t e l’ordine di xtn; ma siccome l’ordine di xtn e l’ordine di t,l’ordine di y e l’ordine di t, cioe l’ordine del suo tipo, e quindi y e predicativo.

Si assume un sistema di logica, come la deduzione naturale, con le ovvierestrizioni sulle sostituzioni, oltre al rispetto di tipi e ordini.

Definizione dell’uguaglianza.

x = y. ≡ .(∀z(t))(z(t)(x) ≡ z(t)(y)),

dove x e y sono due termini di tipo t in cui z(t) non occorre.

Assiomi di PT.

PT.1(A(y1, . . . , yn))(z1, . . . , zn) ≡ A(z1, . . . , zn),

dove le yi sono variabili libere distinte della formula A(y1, . . . , yn) nell’ordinedella prima occorrenza da sinistra a destra, e l’astratto e predicativo e perogni i zi ha lo stesso tipo di yi ed e libera per yi in A(y1, . . . , yn).

PT.2

(∀z1) . . . (∀zn)(x(t1,...,tn)(z1, . . . , zn) ≡ y(t1,...,tn)(z1, . . . , zn)) ⊃ x(t1,...,tn) = y(t1,...,tn),

dove le zi sono di tipo ti e sono tutte variabili distinte che non occorrono neitermini x(t1,...,tn) e y(t1,...,tn).

Teorema Per ogni formula A(xt) predicativa rispetto a xt,49

` (∃x(t))(∀xt)(x(t)(xt) ≡ A(xt)).

Dimostrazione Si parte dalla tautologia (x(t)(xt) ≡ x(t)(xt)) quindi si passaa (∀xt)(x(t)(xt) ≡ x(t)(xt)), a (∃y(t))(∀xt)(y(t)(xt) ≡ x(t)(xt)), e infine a

(∀x(t))(∃y(t))(∀xt)(y(t)(xt) ≡ x(t)(xt)).

Si applica quindi la particolarizzazione con il termine (A(xt)), che e predica-tivo perche A(xt) lo e, e si usa PT.1. 2

49A(xt) si dice predicativa rispetto a xt se l’astratto A(xt) ottenuto circonflettendo soloxt e predicativo.

53

Da PT.1 si ha come caso particolare

` (∀xt)((A(yt))(xt) ≡ A(xt)),

con le dovute restrizioni sintattiche: A(yt) contiene yt libera ed e predicativarispetto a yt, xt e libera per yt in A(yt), e A(xt) risulta dalla sostituzione dixt a tutte le occorrenze libere di yt.

In notazione piu usuale,

(∀xt)(xt ∈ {yt | A(yy)} ≡ A(xt)),

che e il principio di comprensione; non si puo tuttavia derivare la contraddi-zione di Russell perche (¬y(y)), che dovrebbe essere messa al posto di (A(yt)),non puo essere espressa in PT. Tuttavia e solo la restrizione sui tipi, e nonquella predicativa, che evita la contraddizione di Russell.

PT.2 e l’assioma di estensionalita, che insieme alla definizione di ugua-glianza permette di dimostrare

Teorema ` x(t) = y(t) ≡ (∀zt)(x(t)(zt) ≡ y(t)(zt)),

ma solo per i termini di tipo diverso da o.

Dimostrazione Da destra a sinistra si applica PT.2. Viceversa,x(t) = y(t)

(∀w((t)))(w((t))(x(t)) ≡ w((t))(y(t)) per definizione di =

((x(t))(zt))(x(t)) ≡ ((x(t))(zt))(y(t)) particolarizzando w((t))

con l’astratto ((x(t))(zt)) di tipo ((t)), predicativo (zt e una

variabile che resta libera)

x(t)(zt) ≡ y(t)(zt) per PT.1, ((x(t))(zt))(x(t)) ≡ x(t)(zt)

(∀zt)(x(t)(zt) ≡ y(t)(zt)). 2

La formula equivalente a x(t) = y(t) e predicativa rispetto a x(t), mentrela definizione di uguaglianza non lo e.

Si definisce V ((o)) per (x(o)1 = x

(o)1 ), come classe universale per il tipo (0),

e analogamente V (t) come (xt1 = xt1) per tipi superiori, purche t non sia o.50

50Per V (o) volendo si puo usare una formula logicamente valida che dia luogo a unastratto predicativo, per esempio (x(o)(y0) ≡ x(o)(y0). Tuttavia in questo modo V (o) nonrisulta un termine chiuso e non e formalmente utilizzabile in modo agevole.

54

Si dimostra` (∀x(o)

1 )V ((o))(x(o)1 ),

e piu in generale` (∀x(t)

1 )V ((t))(x(t)1 ).

Si definisce Λ(t) per (xt1 6= xt1), come classe vuota per il tipo t diverso dao, e si dimostra

` (∀xt1)((¬Λ(t)(xt1))),

ma anche` (∀x(t)

2 )((∀xt1)((¬x(t)2 (xt1)) ≡ (x

(t)2 = Λ(t))),

e analogamente

` (∀x(t)2 )((∀xt1)(x

(t)2 (xt1) ≡ (x

(t)2 = V (t))).

Questo significa che per ogni tipo t diverso da o esiste un solo insiemevuoto di tipo t, e un’unica classe universale di tipo t; gli insiemi vuoti e leclassi universali di tipi diversi invece non sono uguali, perche l’uguaglianza edefinita solo per termini dello stesso tipo.

Si possono quindi dare le definizioni predicative di singoletto, complemen-to, intersezione e unione ponendo

{x(t)}((t)) per (y(t) = x(t)),con y(t) non occorrente in x(t),51

x(t)(t)

per (¬x(t)(xt)),(x(t) ∩ y(t))(t) per (x(t)(zt) . y(t)(zt)),(x(t) ∪ y(t))(t) per (x(t)(zt) ∨ y(t)(zt)).

La definizione dello zero, per il tipo minimo per cui ha senso la classevuota, e

0(((o))) =def {Λ((o))}(((o))),e piu in generale

0((t)) =def {Λ(t)}((t)).La definizione di successore e

S(x((t)))((t)) =def (∃zt)(y(t)(zt) . x((t))(y(t) ∩ {zt}(t)(t)

)).

La definizione naturale dei numeri, N (((t))) e impredicativa:

((∀x(((t)))1 )(x

(((t)))1 (0((t))) . (∀x((t))

2 )(x(((t)))1 (x

((t))2 ) ⊃ x

(((t)))1 (S(x

((t))2 )((t)))) ⊃

51Questa precisazione sara omessa nei casi successivi.

55

⊃ x(((t)))1 (x

((t))3 ))).

Non si puo quindi usare PT.1 per ottenere un astratto e relativamente adesso dimostrare gli assiomi di Peano.

Come assioma dell’infinito si puo assumere

PT.3 (∃x(o,o)1 )((∀xo1)((¬x

(o,o)1 (xo1, x

o1))) . (∀xo1)(∃xo2)(x

(o,o)1 (xo1, x

o2)) .

. (∀xo1)(∀xo2)(∀xo3)(x(o,o)1 (xo1, x

o2) . x

(o.o)1 (xo2, x

o3) ⊃ x

(o,o)1 (xo1, x

o3))).

la teoria dei tipi TT

La teoria dei tipi TT ha lo stesso linguaggio e assiomi e regole di inferenzacome PT ma senza la restrizione predicativa. Il sistema si chiama ancheteoria semplice dei tipi, a meno di non riservare questo nome a una ulterioresemplificazione che vedremo in seguito.

Ogni formula e ogni teorema di PT sono formule e teoremi di TT, ma nonviceversa. Nella teoria dei tipi, si dimostra che ogni insieme superiormentelimitato di reali ha un estremo superiore, e si dimostra anche il teorema diCantor.

Caduta la restrizione di predicativita, nella teoria dei tipi l’assioma del-l’infinito si puo formulare per mezzo degli assiomi di Peano, in particolareponendo, invece di TT.3

TT.3* (∀x(((o)))1 )(∀x(((o)))

2 )

(N ((((o))))(x(((o)))1 ) . N ((((o))))(x

(((o)))2 ) . S(x

(((o)))1 ) = S(x

(((o)))2 ) ⊃ x

(((o)))1 =

x(((o)))2 )

ovvero l’iniettivita della funzione successore.52

la teoria ramificata dei tipi RT

Nei Principia mathematica Russell ha usato una diversa presentazione for-male. Le variabili erano differenziate non solo per tipo ma anche per ordine,sı che si dovrebbe scrivere per esempio

x((o),(o,o))/5/(3,2)1

52Gli altri assiomi sono dimostrabili, in TT. Questo comunque no. Esistono modelli digerarchie di tipi con base D finita.

56

per indicare una variabile di tipo ((o), (o, o)) e ordine 5, il cui primo argo-mento e di tipo (o) e ordine 3 e il secondo di tipo (o, o) e ordine 2.

Il sistema RT della teoria ramificata dei tipi ha infatti come variabili ecostanti lettere con pedice un numero naturale > 0 e apice espressioni dellaforma “o/0” o “(t1, . . . , tn)/k/(y1, . . . , yn)” dove i ti sono simboli di tipo, ke gli yi sono numeri naturali con la restrizione che per ogni i il numero yie maggiore o uguale dell’ordine del corrispondente tipo ti, e k e maggioredel massimo dei valori degli yi; e se ti e o, allora yi deve essere 0 (i numeriche seguono immediatamente il simbolo di tipo sono l’ordine; l’espressionecompleta e il tipo-ordine).

Definizione delle formule:(i) variabili e costanti sono termini con il tipo-ordine indicato;(ii) se x e un termine di tipo-ordine (t1, . . . , tn)/k/(y1, . . . , yn), e z1, . . . , zn

sono termini di tipo rispettivamente ti, e di ordine minore o uguale agli yi,allora x(z1, . . . , zn) e una formula;

(iii) espressioni ottenute combinando formule con connettivi e quantifica-tori sono formule;

(iv) se A(z1, . . . , zn) e una formula nella quale le variabili libere zi oc-corrono nell’ordine della prima occorrenza, sono di tipo ti e di ordine yi, ek e il massimo ordine di tutte le variabili e le costanti nella formula, allora(A(z1, . . . , zn)) e un termine di tipo-ordine (t1, . . . , tn)/r/(y1, . . . , yn), dove re k se la formula non ha variabili vincolate di ordine k, e k + 1 altrimenti.

Esempio L’espressione

(∀x((o))/5/31 )x

((o))/5/31 (x

(o)/3/01 )

e una formula. Da questa si ottiene per particolarizzazione

x((o))/4/31 (x

(o)/3/01 )

che e una formula; non cosı

x((o))/4/21 (x

(o)/3/01 ).

Dalla formula (∀x((o))/5/31 )x

((o))/5/31 (x

(o)/2/01 ) si ottiene invece per particolariz-

zazione la formula x((o))/4/21 (x

(o)/2/01 ).

Gli assiomi RT.1, RT.2 e RT.3 di RT sono gli stessi che per PT, dove ladefinizione di predicativita ora diventa:

57

Un termine di tipo-ordine (t1, . . . , tn)/k/(y1, . . . , yn) e predicativo se esolo se k e y + 1, dove y e il massimo degli ordini y1, . . . , yn. Le variabili e lecostanti di tipo-ordine o/0 sono predicative.

Se si escludono dal linguaggio di RT tutti i termini eccetto quelli di tipo-ordine o/0 e (t1, . . . , tn)/k/(y1, . . . , yn), dove gli yi sono gli ordini di ti e k el’ordine di (t1, . . . , tn), allora le formule di RT corrispondono in modo naturalea quelle di PT, e gli assiomi e le regole ristrette a queste formule costituisconoun sistema equivalente a PT.

Scriviamo le formule indicando a latere il tipo-ordine delle variabili, invecedi scriverlo come apice.

Come nella teoria predicativa, l’estremo superiore di un insieme limitatodi numeri reali e dato dal termine ((∃x)(z(x). x(y)). Se t e il tipo di y ed nil suo ordine, il tipo-ordine di ((∃x)(z(x). x(y)), supponendo x al minimo diordine n+ 1, e (t)/n+ 2/n e quindi non predicativo.

Il sistema PM si ottiene da RT aggiungendo

Assioma di riducibilita

(∀x)(∃w)(∀z1) . . . (∀zn)(w(z1, . . . , zn) ≡ x(z1, . . . , zn)),

dove x e di tipo-ordine (t1, . . . , tn)/k/(y1, . . . , yn) e w e predicativa di tipo-ordine (t1, . . . , tn)/r/(y1, . . . , yn), r ≤ k.

Nella notazione di Russell:

(∃y)(∀x)(y!(x) ≡ A(x)).

la teoria dei tipi semplici ST

Il sistema ST dei tipi semplici, o semplificati, si ottiene riducendo le relazionia insiemi, con la definizione insiemistica della coppia ordinata.

Formalmente i tipi sono ora “o” e “(. . . (o) . . .)” con n coppie di parentesi,o piu semplicemente 0 e n.

Le gerarchie di tipi sopra un insieme D dato sono gli insiemi della gerar-chia {

T0 = DTn+1 = P(Tn).

58

Una relazione tra termini di tipo n ed m diventa, con la definizione disotto, un insieme di tipo max(n,m) + 3.

Si assume la definizione usuale di coppia ordinata 〈x, y〉 = {{x}, {x, y}}per x e y dello stesso tipo; se sono di tipo diverso, rispettivamente n ed m,e sia n il massimo, si considera {. . . {y} . . .} che abbia tipo n e si forma lacoppia ordinata di x e {. . . {y} . . .}, che ha tipo n+ 2.

Gli assiomi sono gli stessi di TT, numerati nello stesso modo, salvo leovvie modifiche di scrittura.

Assiomi di SP

SP.1(A(y))(x) ≡ A(x),

con x libera per y in A(y).

SP.2(∀zn)(xn+1(zn) ≡ yn+1(zn)) ⊃ xn+1 = yn+1,

dove x = y e definita da (∀z)(z(x) ≡ z(y)) per x e y di tipo n e z di tipon+ 1.

ST.3 (∃x31)((∀x0

1)(¬x31(〈x0

1, x01〉)) . (∀x0

1)(∃x02)(x

31(〈x0

1, x02〉) .

∧(∀x01)(∀x0

2)(∀x03)(x

31(〈x0

1, x02〉) . x3

1(〈x02, x

03〉) ⊃ x3

1(〈x01, x

03〉))).

59