Contare gli infiniti (Un infinito, due infiniti, tre infiniti. . . , infiniti infiniti,. . . e ancora di più)

(1)

Contare gli infiniti

(Un infinito, due infiniti, tre infiniti. . . , infiniti infiniti,. . . e ancora di pi`u)

Contare gli infiniti

(2)

L’infinito potenziale

L’esperienza comune ci fa intuire l’esistenza dell’infinito, almeno in forma potenziale:

non importa fino a quale numero contiamo, esistono sempre numeri pi`u grandi

in qualunque numero di pezzi dividiamo un segmento possiamo sempre fare una suddivisione in pi`u

dato un numero decimale qualunque N, a₀a₁a₂. . . a_n

possiamo costruire un numero decimale con una cifra in pi`u:

N, a0a1a2. . . anan+1

Ci sono parti della matematica per le quali questa nozione di infinito `e sufficiente, per esempio: l’aritmetica.

(3)

L’infinito in matematica

Ci sono per`o concetti matematici che richiedono, per essere definiti correttamente, l’esistenza di enti infiniti:

i numeri irrazionali (√

2, π, e, . . .) e la loro rappresentazione decimale le operazioni su tali numeri

i limiti

la possibilit`a di definire nozioni quali la velocit`a e l’accelerazione di un moto

. . .

(4)

Alcune opinioni sull’infinito

Il fatto di dover trattare con degli enti infiniti non `e stato privo di problemi tecnici e filosofici nella storia della matematica, e la sua accettazione e fondazione rigorosa `e frutto degli sviluppi della disciplina.

Le considerazioni sull’infinito hanno però una difficoltà, perché si presentano molte impossibilità, tanto se si immagina che esso esista, quanto se si immagina che esso non esista. Aristotele, 383 a.C. – 322 a.C.

(5)

Alcune opinioni sull’infinito

Queste son di quelle difficolt`a che derivano dal discorrer che noi facciamo col nostro intelletto finito intorno a gl’infiniti, dandogli quegli attributi che noi diamo alle cose finite e terminate; il che penso sia inconveniente. G. Galilei, 1564 – 1642

Protesto contro l’uso di grandezze infinite come di qualche cosa di completo, cosa che non `e mai permessa in matematica.

L’infinito `e solo un modo di dire. C.F. Gauss, 1777 – 1855.

(6)

Alcune opinioni sull’infinito

Nessun’altra questione ha scosso da tempi immemorabili la mente degli uomini quanto quella dell’infinito. L’infinito ha agito in modo cos`ı eccitante e ricco di frutti sull’intelligenza come poche altre idee.

Per`o l’infinito ha bisogno di spiegazioni pi`u di qualsiasi altro concetto. D. Hilbert, 1926.

Se si vuol trovare una breve massima che riguardi il centro vivo della matematica si pu`o dire certamente che la matematica `e la scienza dell’infinito. H. Weyl, 1927.

(7)

Enti infiniti in matematica

Esempi di oggetti infiniti necessari alla matematica moderna sono gli insiemi numerici quali:

N = {0, 1, 2, 3, 4, . . .}: insieme dei numeri naturali

Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}: insieme dei numeri interi Q =

np

q | p ∈ Z, q ∈ N, q 6= 0o

: insieme dei numeri razionali R: insieme dei numeri reali; sono i numeri usati per identificare i punti su una retta, una volta stabilite un’origine e un’unit`a di misura C: insieme dei numeri complessi

. . .

Cosa significa che questi insiemi sono infiniti?

(8)

Contare

Per riconoscere che un insieme `e infinito, bisognerebbe poter contare i suoi elementi.

Cosa significa contare?

Esempi:

(9)

Funzioni

Definizione

Siano X e Y due insiemi.

Una funzione f da X a Y , denotato f : X → Y , `e una relazione che a ogni elemento a dell’insieme X associa un elemento, denotato f (a) dell’insieme Y . L’elemento f (a) si dice immagine di a attraverso f . Si scrive anche a 7→ f (a).

Una funzione f : X → Y è suriettiva (una suriezione) se ogni elemento di Y è immagine attraverso f di qualche elemento di X . Una funzione f : X → Y è iniettiva (una iniezione) se elementi diversi di X hanno immagini diverse.

Una funzione `e bijettiva (una bijezione) se `e sia suriettiva sia iniettiva.

Nota: Se esiste una bijezione f : X → Y , allora esiste anche una bijezione g : Y → X : definita da

g (b) = a se e solo se f (a) = b Le funzione g si chiama inversa di f , e si denota f⁻¹.

(10)

Cardinalit` a

Definizione

Siano X e Y due insiemi.

X e Y hanno la stessa cardinalit`a, in simboli |X | = |Y |, se esiste una bijezione X → Y

X ha cardinalit`a minore o uguale della cardinalit`a di Y , in simboli

|X | ≤ |Y |, se esiste una funzione iniettiva X → Y

X ha cardinalit`a minore della cardinalit`a di Y , in simboli |X | < |Y |, se

|X | ≤ |Y | ma |X | 6= |Y | cio`e:

esiste una iniezione X → Y

ma non esiste alcuna bijezione X → Y

(11)

Esempi

L’insieme N dei numeri naturali ha la più piccola cardinalità infinita possibile. Cioè, se A è un insieme infinito, allora |N| ≤ |A|.

Un insieme A tale che |A| = |N| si dice numerabile.

Se dall’insieme dei numeri naturali si toglie un elemento, si ottiene un insieme che ha tanti elementi quanto quello di partenza:

N = {0, 1, 2, 3, 4, 5, . . .} N^∗= {1, 2, 3, 4, 5, . . .}

f : N → N^∗, f (n) = n + 1

Nota: Alcuni principi che valgono per gli insiemi finiti falliscono quando si ha a che fare con insiemi infiniti.

Per esempio: il tutto `e maggiore di ogni sua parte

I numeri naturali sono tanti quanti sono i numeri naturali pari:

N = {0, 1, 2, 3, 4, 5}, P = {0, 2, 4, 6, . . .}

f : N → P, f (n) = 2n

(12)

Esempi

I numeri interi sono tanti quanti sono i numeri naturali:

Z = {. . . , −3, −2, −1, 0, 1, 2, 3, 4, . . .} N = {0, 1, 2, 3, 4, 5, . . .}

f : Z → N, f (n) =

2n se n ≥ 0

−2n − 1 se n < 0 I numeri naturali sono tanti quanti i quadrati perfetti:

N = {0, 1, 2, 3, 4, 5, . . .} Q = {0, 1, 4, 9, 16, 25, . . .}

f : N → Q, f (n) = n²

Due segmenti di lunghezza diversa contengono lo stesso numero di punti:

I numeri in−^π₂,^π₂ sono tanti quanti tutti i numeri reali: x 7→ tgx.

(13)

Esercizi

Dimostrare che le coppie ordinate di numeri naturali (cio`e i punti del piano a coordinate naturali) sono tanti quanti i numeri naturali:

|N × N| = |N|

Più in generale, dimostrare che se A è un insieme numerabile, allora A × A è un insieme numerabile

(14)

Alcune propriet` a della cardinalit` a

Se |A| = |B| e |B| = |C |, allora |A| = |C | Se |A| ≤ |B| e |B| ≤ |C |, allora |A| ≤ |C |

(!) (Teorema di Schr¨oder-Bernstein)

Se |A| ≤ |B| e |B| ≤ |A|, allora |A| = |B|

(!!) Dati due insiemi qualunque X , Y si ha che almeno una tra le relazioni

|A| ≤ |B|, |B| ≤ |A|

vale (se valgono entrambe, da (!) segue allora che |A| = |B|) Se A ⊆ B allora |A| ≤ |B|

Queste propriet`a affermano che

la relazione ≤ `e un ordine totale tra i numeri cardinali (che estende l’usuale relazione d’ordine tra numeri cardinali finiti).

(15)

Ancora un esempio

I numeri interi sono tanti quanti i numeri razionali:

La funzione n 7→ n `e una iniezione Z → Q, quindi |Z| ≤ |Q|

Esiste una suriezione Z → Q:

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9 . . .

2 1

2 2

2 3

2 4

2 5

2 6

2 7

2 8

2 9 . . .

3 1

3 2

3 3

3 4

3 5

3 6

3 7

3 8

3 9 . . .

4 1

4 2

4 3

4 4

4 5

4 6

4 7

4 8

4 9 . . .

5 1

5 2

5 3

5 4

5 5

5 6

5 7

5 8

5 9 . . .

6 1

6 2

6 3

6 4

6 5

6 6

6 7

6 8

6 9 . . . . . . .

(16)

Riflessioni dopo le prime osservazioni sperimentali

I primi esperimenti fatti con le cardinalit`a infinite conducono ad alcune riflessioni:

il concetto di infinito porta a qualche paradosso: il tutto non `e sempre maggiore di ogni sua parte, p. es. |Q| = |Z|

tutte le coppie di insiemi infiniti testati finora hanno la medesima cardinalit`a

Domanda: `E vero che due qualunque insiemi infiniti hanno lo stesso numero di elementi?

Cio`e: Esiste quindi un’unica cardinalit`a infinita?

In tal caso, le possibili cardinalit`a di un insieme sarebbero:

0, 1, 2, 3, . . . , ∞

(Suggerimento: Se fosse cos`ı, questa conferenza non avrebbe molto senso...)

(17)

Infiniti diversi

|N| = |Z| = |Q| < |R|

|N| < |R| perch´e N ⊆ R

Si deve ancora dimostrare che |N| 6= |R|, cioè che non ci può essere alcuna bijezione N → R. Infatti, sia f : N → R una qualunque funzione, dimostriamo che non è suriettiva (e quindi non può essere bijettiva):

f (0) = N₀, a_0,0a_0,1a_0,2 a_0,3a_0,4 a_0,5a_0,6a_0,7 . . . f (1) = N1, a1,0a1,1a1,2 a1,3a1,4 a1,5a1,6a1,7 . . . f (2) = N2, a2,0a2,1a2,2 a2,3a2,4 a2,5a2,6a2,7 . . . f (3) = N3, a3,0a3,1a3,2 a3,3a3,4 a3,5a3,6a3,7 . . . f (4) = N4, a4,0a4,1a4,2 a4,3a4,4 a4,5a4,6a4,7 . . . . . . .

il numero reale x =

non appartiene all’immagine della funzione f : x = 0, b0b1b2b3. . ., dove bn=

(5 se a_n,n6= 5 6 altrimenti .

(18)

Infiniti sempre pi` u grandi

L’esempio precedente mostra che esistono almeno due infiniti. In realt`a:

esistono infiniti arbitrariamenti grandi

cioè: data una qualunque cardinalità, ce n’è una ancora più grande.

Definizione

Dato un qualunque insieme A, sia

P(A) = {C | C ⊆ A}

la collezione di tutti i sottoinsiemi di A.

Per esempio, se

A = {a, b, c}

allora

P(A) ={∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

(19)

Infiniti sempre pi` u grandi

Teorema di Cantor Qualunque sia l’insieme A:

|A| < |P(A)|

Dimostrazione.

La funzione f : A → P(A) tale che f (a) = {a} `e una iniezione e testimonia che |A| ≤ |P(A)|

Resta da dimostrare che |A| 6= |P(A)|, cio`e che non esiste alcuna bijezione g : A → P(A).

Data una qualunque funzione g : A → P(A), dimostriamo che g non può essere suriettiva, dimostrando che c’è un elemento Y ∈ P(A) che non è immagine di alcun x ∈ A.

(20)

Infiniti sempre pi` u grandi

Dimostrazione (cont.)

Y = {a ∈ A | a /∈ g (a)}

Se fosse Y = g (x ) per qualche x si avrebbe che:

se x ∈ g (x ), cio`e x ∈ Y , allora x /∈ g (x) se x /∈ g (x), cio`e x /∈ Y , allora x ∈ g (x)

Quindi non esiste alcun x tale che Y = g (x ): la funzione g non `e suriettiva.

Corollario: Esistono infiniti infiniti.

Partiamo da un insieme infinito A:

|A| < |P(A)| < |P(P(A))| < |P(P(P(A)))| < . . .

Questa lista non esaurisce tutte le cardinalit`a infinite: ci sono infiniti pi`u grandi di tutti questi.

(21)

Ancora pi` u infiniti

Data una qualunque sequenza di insiemi infiniti, c’`e un insieme infinito pi`u grande di tutti i termini della sequenza:

Dati

|A0| < |A1| < |A2| < |A3| < |A4| < . . . sia

A = A0∪ A1∪ A2∪ A3∪ A4∪ . . . allora |A| ≥ |A_n|, per ogni n.

Pi`u in generale, dato un qualunque insieme I di numeri cardinali, per ogni κ ∈ I sia Aκ tale che |Aκ| = κ. Allora l’insiemeS

κ∈IAκ ha cardinalit`a maggiore o uguale a quella di ogni Aκ.

(22)

La lista di tutti gli infiniti (e pi` u) infiniti

Propriet`a: i numeri cardinali sono bene ordinati

Data una qualunque collezione non vuota di numeri cardinali, esiste il minimo numero cardinale della collezione.

Questa propriet`a e le precedenti permettono di definire la lista di tutti i numeri cardinali infiniti:

ℵ0= il minimo cardinale infinito = |N| = cardinalit`a del numerabile ℵ₁= il minimo cardinale pi`u grande di ℵ₀

ℵ₂= il minimo cardinale pi`u grande di ℵ₁ . . .

ℵn+1= il minimo cardinale pi`u grande di ℵn

. . .

ℵω= il minimo cardinale pi`u grande di ℵ0, ℵ1, ℵ2, ℵ3, . . . ℵω+1= il minimo cardinale pi`u grande di ℵω

. . .

ℵω+ω= il minimo cardinale pi`u grande dei precedenti ℵω+ω+1= . . .

. . .

(23)

Esercizi

Quali dei seguenti insiemi possono essere pi`u che numerabili?

I: una collezione infinita di intervalli che non si intersecano in R D: una collezione infinita di dischi che non si intersecano in R² C: una collezione infinita di circonferenze che non si intersecano in R²

O: una collezione infinita di figure a forma di 8 che non si intersecano in R²

(24)

Il problema del continuo: quanti sono i numeri reali?

Domanda

Qual `e la posizione di |R| nella lista?

La cardinalit`a di R si chiama cardinalit`a del continuo e, talvolta, si indica con c.

Per quanto abbiamo gi`a dimostrato c ≥ ℵ1

Cantor, l’inventore della teoria degli insiemi, era convinto che valesse l’uguaglianza c = ℵ1e ha passato molti anni cercando, senza successo, di dimostrarla.

L’uguaglianza c = ℵ1si chiama ipotesi del continuo (CH).

(25)

Il problema del continuo: primo problema di Hilbert

Una riformulazione equivalente dell’ipotesi del continuo `e quindi:

CH

Dato un sottoinsieme infinito A ⊆ R, o |A| = |N| o |A| = |R|.

ovvero ancora:

CH

Non c’`e alcuna cardinalit`a intermedia tra il numerabile e il continuo.

Nel 1900 D. Hilbert, che era considerato il pi`u grande matematico dell’epoca, al Congresso matematico internazionale di Parigi ha

presentato una lista di 23 problemi, in quel momento ancora irrisolti, che secondo lui sarebbero stati centrali nella matematica del secolo che iniziava. Il primo dei problemi era appunto il problema del continuo.

(26)

Il problema del continuo: la soluzione

Nel 1940 K. Gödel dimostra che la negazione dell’ipotesi del continuo non si può dimostrare; cioè la disuguaglianza c 6= ℵ₁(che è equivalente a c > ℵ₁) è indimostrabile

Nel 1963 P. Cohen dimostra che l’ipotesi del continuo non si può dimostrare; cioè l’uguaglianza c = ℵ1è indimostrabile

L’ipotesi del continuo è un esempio di enunciato indipendente (o indecidibile): nè lui nè la sua negazione sono dimostrabili.

Ma cosa vuol dire?

(27)

Teorie, assiomi, dimostrazioni, teoremi

Una teoria matematica T `e caratterizzata da un insieme di enunciati, detti assiomi della teoria. Sono i principi fondamentali dai quali tutte le verit`a della teoria possono essere dedotte.

Esempi:

La geometria euclidea:

si basa sui cinque postulati (o assiomi) d’Euclide

L’aritmetica (PA, Peano arithmetic):

si basa su un insieme (infinito) di assiomi

(28)

Teorie, assiomi, dimostrazioni, teoremi

Si dice teorema della teoria T un qualunque enunciato che si possa dedurre a partire dagli assiomi di T utilizzando delle regole logiche. Una tale deduzione si dice dimostrazione del teorema.

Se l’enunciato ϕ `e un teorema della teoria T , si scrive T ` ϕ

Esempi:

I teoremi della geometria euclidea (che avete dedotto durante il primo biennio di liceo)

L’enunciato 2 + 2 = 4 `e un teorema dell’aritmetica:

PA ` 2 + 2 = 4

(29)

La teoria degli insiemi ZFC

Con queste definizioni, le teorie matematiche diventano degli oggetti matematici ben definiti, concreti, come i numeri, gli insiemi, le figure geometriche, le funzioni,. . .

Un altro esempio molto importante di teoria matematica `e . . . la matematica stessa!

A partire dall’inizio del XX secolo `e stato costruito un sistema (infinito) di assiomi nel quale si pu`o sviluppare tutta la matematica. Si chiama teoria degli insiemi. Si indica con l’acronimo ZFC :

Z : E. Zermelo (1871–1953)

F : A.A. Fraenkel (1891–1965)

C : assioma della scelta (axiom of choice)

(30)

Consistenza, completezza e incompletezza

Dato un enunciato matematico ϕ, indichiamo con ¬ϕ la sua negazione.

Esempio: se

ϕ : 2 + 2 = 5 allora

¬ϕ : 2 + 2 6= 5

Dato un enunciato ϕ potremmo aspettarci che o lui o la sua negazione siano dimostrabili.

Esempio: L’enunciato 2 + 2 = 5 non `e dimostrabile; in effetti `e dimostrabile la sua negazione 2 + 2 6= 5.

(31)

Consistenza, completezza e incompletezza

Definizione

Una teoria T si dice consistente se non `e contradditoria, cio`e se non esiste alcun enunciato ϕ tale che

T ` ϕ e T ` ¬ϕ

Una teoria T si dice completa se per ogni enunciato ϕ, si ha esattamente una delle due alternative seguenti:

T ` ϕ o T ` ¬ϕ

(32)

Il primo teorema di incompletezza di G¨ odel

Le teorie matematiche complete sono abbastanza rare:

Teorema (K. G¨odel) Sia T una teoria

consistente

ricorsivamente assiomatizzabile che interpreti l’aritmetica

Allora T è incompleta, cioè esiste un enunciato ϕ tale che né T ` ϕ né T ` ¬ϕ

La teoria ZFC è una teoria alla quale si applica il teorema di Gödel, quindi è una teoria incompleta. Un esempio di enunciato indipendente è l’ipotesi del continuo.