GRICE E CELLUCCI: Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können

 Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können. Insiemi infiniti 1. Introduzione Finch ́e gli insiemi che si considerano sono finiti (cio`e si pu`o contare quanti sono i loro elementi mettendoli in corrispondenza biiettiva con i numeri che precedono un certo numero naturale) la nozione di insieme pu`o fornire un comodo modo di esprimersi, ma non `e indi- spensabile. Di fatto Cantor per primo elabor`o la nozione di insieme per risolvere problemi di quantita` di elementi in insiemi infiniti (cio`e non finiti). Definizione. Si dice che due classi hanno la stessa cardinalit`a quando c’`e una biiettivit`a tra le due classi. In tal caso si dir`a anche che le due classi sono equinumerose. Definizione. Si dice che un insieme A `e finito se esistono un numero naturale n e una biiettivit`a da A sull’insieme dei numeri naturali che precedono n; in questo caso diremo che A ha n elementi. Se ci`o non succede, si dice che l’insieme `e infinito. Se un insieme A `e finito e un altro insieme B `e contenuto propriamente (contenuto ma non uguale) in A allora A e B non sono equinumerosi, cio`e non c’`e alcuna biiettivit`a tra i due. Questo risultato dipende dal fatto che per nessun numero naturale ci pu`o essere una biiettivit`a tra l’insieme dei numeri che lo precedono e l’insieme di quelli che precedono un diverso numero naturale. L’ultima affermazione non si estende agli insiemi infiniti; lo giustifichiamo con un con- troesempio gi`a considerato da Galileo Galilei nel suo Dialogo sopra i due massimi sistemi del mondo. I numeri pari sono un sottinsieme proprio dei numeri naturali, ed entrambi gli insiemi non sono finiti; inoltre la funzione che a un numero naturale associa il suo doppio `e una biiettivit`a dai numeri naturali sui numeri pari. Cos`ı si deve dire che i numeri naturali sono tanti quanti i numeri pari pur costituendo questi un sottinsieme proprio dell’insieme dei naturali. Per gli insiemi finiti non solo si pu`o dire se hanno lo stesso numero di elementi, ma anche se uno ha piu` elementi di un altro o meno. Per fare ci`o ci si rif`a alla relazione d’ordine naturale tra i numeri naturali che contano gli elementi di ciascuno dei due insiemi. Per gli insiemi infiniti non si pu`o utilizzare lo stesso metodo. Come decidere allora quando un insieme ha piu` o meno elementi di un altro? Ci si potrebbe limitare a dire che un insieme `e finito o infinito. Tuttavia l’esperienza di vari insiemi infiniti porta naturalmente a domandarci se si pu`o stabilire una gerarchia simile a quella fra gli insiemi finiti. Prenderemo a modello le stesse propriet`a degli insiemi finiti. 2. Cardinalit`a Definizione 1. Siano A e B due insiemi. Diremo che la cardinalit`a dell’insieme A `e minore o uguale a quella dell’insieme B, e scriveremo |A| ≤ |B| quando esiste una funzione totale iniettiva di A in B. Questa relazione fra insiemi non `e un ordine, n ́e stretto n ́e largo. Non `e stretto perch ́e |A| ≤ |A|, per motivi ovvi (basta considerare la funzione identit`a). Non `e un ordine largo, perch ́e pu`o accadere che |A| ≤ |B| e anche |B| ≤ |A|, con A ̸= B. Un esempio `e proprio quello in cui A `e l’insieme dei numeri naturali e B quello dei numeri naturali pari. Scopo di queste note `e di studiare le propriet`a di questa relazione. Attraverso essa potremo arrivare al concetto di “uguale cardinalit`a”, che `e ci`o che ci interessa. 1  2 (2) (3) INSIEMI INFINITI Esempi. (1) Se A `e un insieme e B ⊆ A, allora |B| ≤ |A|. Se Z `e l’insieme dei numeri interi e N quello dei numeri naturali, allora |Z| ≤ |N|. Ci`o pu`o apparire paradossale, ma vedremo che non lo `e. Consideriamo infatti la seguente funzione: 􏰈2x se x ≥ 0, −2x−1 sex<0. Si pu`o facilmente verificare che f : Z → N `e non solo iniettiva, ma anche suriettiva. Se X `e un insieme finito e Y `e un insieme infinito, allora |X| ≤ |Y |. Supponiamo che X abbia n elementi. Faremo induzione su n. Se n = 0, la funzione vuota `e quella che cerchiamo. Supponiamo la tesi vera per insiemi con n elementi e supponiamo che X abbia n + 1 elementi: X = {x1, . . . , xn, xn+1}. Per ipotesi induttiva esiste una funzione totale iniettiva f: {x1,...,xn} → Y. Siccome Y `e infinito, esiste un elemento y ∈/ Im(f) (altrimenti Y avrebbe n elementi). Possiamo allora definire una funzione totale iniettiva g : X → Y che estende f ponendo g(xn+1) = y. Diamo subito la definizione che ci interessa maggiormente. Definizione 2. Siano A e B due insiemi. Diremo che A e B hanno la stessa cardinalit`a, f(x) = e scriveremo |A| = |B|, quando esiste una funzione biiettiva (totale) di A su B. Non daremo la definizione di cardinalit`a, per la quale occorrerebbe molta piu` teoria e che non ci servir`a. Sar`a piu` rilevante per noi scoprire le connessioni fra le due relazioni introdotte. 3. Propriet`a della cardinalit`a di insiemi infiniti (C1) Se A `e un insieme, allora |A| = |A|. (C2) Se A e B sono insiemi e |A| = |B|, allora |B| = |A|. (C3) SeA,BeCsonoinsiemi,|A|=|B|e|B|=|C|,allora|A|=|C|. Queste tre proprieta` sono quasi ovvie: basta, nel primo caso, considerare la funzione identit`a; nel secondo si prende la funzione inversa della biiettivit`a A → B; nel terzo si prende la composizione fra la biiettivit`a A → B e la biiettivit`a B → C. (M1) Se A `e un insieme, allora |A| ≤ |A|. (M2) SeA,BeCsonoinsiemi,|A|≤|B|e|B|≤|C|,allora|A|≤|C|. La dimostrazione di queste due `e facile (esercizio). C’`e un legame fra le due relazioni? La risposta `e s`ı e sta proprio nella “propriet`a antisimmetrica” che sappiamo non valere per ≤. Il risultato che enunceremo ora `e uno fra i piu` importanti della teoria degli insiemi e risale allo stesso Cantor, poi perfezionato da altri studiosi. Teorema 1 (Cantor, Schr ̈oder, Bernstein). Siano A e B insiemi tali che |A| ≤ |B| e |B| ≤ |A|, allora |A| = |B|. Dimostrazione. L’ipotesi dice che esistono una funzione f : A → B iniettiva totale e una funzione g : B → A iniettiva totale. Per completare la dimostrazione dobbiamo trovare una funzione biiettiva h: A → B. Un elemento a ∈ A ha un genitore se esiste un elemento b ∈ B tale che g(b) = a. Analogamente diremo che un elemento b ∈ B ha un genitore se esiste a ∈ A tale che f(a) = b. Siccome f e g sono iniettive, il genitore di un elemento, se esiste, `e unico. Dato un elemento a ∈ A oppure b ∈ B, possiamo avviare una procedura: (a) poniamo x0 = a o, rispettivamente x0 = b e i = 0; (b) se xi non ha genitore, ci fermiamo; (c) se xi ha genitore, lo chiamiamo xi+1, aumentiamo di uno il valore di i e torniamo al passo (b). Partendo da un elemento a ∈ A, possono accadere tre casi: • la procedura non termina; scriveremo che a ∈ A0;  3. PROPRIET`a DELLA CARDINALIT`a DI INSIEMI INFINITI 3 • la procedura termina in un elemento di A; scriveremo che a ∈ AA; • la procedura termina in un elemento di B; scriveremo che a ∈ AB. Analogamente, partendo da un elemento b ∈ B, possono accadere tre casi: • la procedura non termina; scriveremo che b ∈ B0; • la procedura termina in un elemento di A; scriveremo che b ∈ BA; • la procedura termina in un elemento di B; scriveremo che b ∈ BB. Abbiamo diviso ciascuno degli insiemi A e B in tre sottoinsiemi a due a due disgiunti: A = A0 ∪ AA ∪ AB , B = B0 ∪ BA ∪ BB . Se prendiamo un elemento a ∈ A0, `e evidente che f(a) ∈ B0, perch ́e, per definizione, a `e genitore di f(a). Dunque f induce una funzione h0 : A0 → B0, dove h0(a) = f(a). Questa funzione, essendo una restrizione di f, `e iniettiva e anche totale. E` suriettiva, perch ́e, se b ∈ B0, esso ha un genitore a che deve appartenere ad A0. Se prendiamo un elemento a ∈ AA, allora f(a) ∈ BA: infatti a `e genitore di f(a) e la procedura, a partire da b = f(a) termina in A. Dunque f induce una funzione hA : AA → BA che `e iniettiva e totale. Essa `e anche suriettiva, perch ́e ogni elemento di BA ha genitore che deve appartenere ad AA. Analogamente, se partiamo da un elemento b ∈ BB, allora g(b) ∈ AB e g induce una funzione iniettiva e totale hB : BB → AB che `e suriettiva, esattamente per lo stesso motivo di prima. Ci resta da porre h = h0 ∪hA ∪h−1. Allora h `e una funzione h: A → B che `e totale, B iniettiva e suriettiva (lo si verifichi). Esempio. Illustriamo la dimostrazione precedente con la seguente situazione: sia f : N → Z la funzione inclusione; consideriamo poi la funzione g : Z → N 􏰈4z se z ≥ 0, −4z−2 sez<0. Quali sono gli elementi di N che hanno un genitore? Esattamente quelli che appartengono all’immagine di g, cio`e i numeri pari. I numeri dispari, quindi, appartengono a NN, perch ́e la procedura si ferma a loro stessi. Consideriamo x0 = 2 ∈ N; siccome g(−1) = 2, abbiamo x1 = −1; poich ́e −1 ∈/ Im(f), la procedura si ferma e 2 ∈ NZ. Consideriamo invece x0 = 4 ∈ N; siccome g(1) = 4, abbiamo x1 = 1 e possiamo andare avanti, perch ́e 1 = f(1), dunque x2 = 1 ∈ N. Poich ́e 1 ∈/ Im(g), abbiamo che 4 ∈ NN. Studiamo ora x0 = 16 ∈ N; siccome g(4) = 16, abbiamo x1 = 4; siccome f(4) = 4, abbiamo x2 = 4 ∈ N; siccome 4 = g(1), abbiamo x3 = 1 ∈ Z; siccome 1 = f(1), abbiamo x4 = 1 ∈ N. La procedura si ferma qui, dunque 16 ∈ NN. Si lascia al lettore l’esame di altri elementi di N o di Z. La relazione ≤ si pu`o allora vedere non come una relazione d’ordine largo fra insiemi, ma piuttosto come un ordine largo fra le “cardinalit`a” degli insiemi. Non vogliamo per`o definire il concetto di cardinalit`a; ci limiteremo a confrontarle usando le relazioni introdotte. Il teorema seguente dice, in sostanza, che la cardinalit`a dell’insieme dei numeri naturali `e la piu` piccola cardinalit`a infinita. Teorema 2. Sia A un insieme infinito. Allora |N| ≤ |A|. Dimostrazione. Costruiremo un sottoinsieme di A per induzione. Siccome A `e infinito, esso non `e vuoto; sia x0 ∈ A. Evidentemente {x0} ̸= A, quindi esiste x1 ∈ A \ {x0}. Ancora {x0, x1} ≠ A, quindi esiste x2 ∈ A \ {x0, x1, x2}. Proseguiamo allo stesso modo: supponiamo di avere scelto gli elementi x0, x1, . . . , xn ∈ A, a due a due distinti. Siccome {x0, . . . , xn} ≠ A, esiste xn+1 ∈A\{x0,...,xn}. Dunque la procedura associa a ogni numero naturale un elemento di A e la funzione n 􏰀→ xn `e iniettiva. 􏰃 Questo risultato ha una conseguenza immediata. g(z) = 􏰃  4 INSIEMI INFINITI Corollario 3. Sia A ⊆ N. Allora A `e finito oppure |A| = |N|. Dimostrazione. Se A non `e finito, allora `e infinito. Per il teorema, |N| ≤ |A|. Ma |A| ≤ |N| perch ́e A ⊆ N. Per il teorema di Cantor-Schr ̈oder-Bernstein, |A| = |N|. 􏰃 Un altro corollario `e la caratterizzazione che Dedekind prese come definizione di insieme infinito. Corollario 4. Un insieme A `e infinito se e solo se esiste un sottoinsieme proprio B ⊂ A tale che |B| = |A|. Dimostrazione. Se A `e finito, `e evidente che un suo sottoinsieme proprio non pu`o avere tanti elementi quanti A. Supponiamo ora che A sia infinito. Per il corollario precedente, esiste una funzione iniettiva totale f : N → A. Definiamo ora una funzione g : A → A ponendo: 􏰈f(n+1) seesisten∈Ntalechex=f(n), x se x ∈/ Im(f). La condizione “esiste n ∈ N tale che x = f(n)” equivale alla condizione “x ∈ Im(f)”. La funzione g `e ben definita, perch ́e f `e iniettiva; dunque, se x = f(n) per qualche n, questo n `e unico. Osserviamo anche che x ∈ Im(f) se e solo se g(x) ∈ Im(f). Verifichiamo che g `e totale e iniettiva. Il fatto che sia totale `e ovvio. Supponiamo che g(x) = g(y). • Se x ∈/ Im(f), allora g(x) = x; dunque non pu`o essere y ∈ Im(f) e perci`o g(y) = y, da cui x = y. • Sex∈Im(f),`ex=f(n)perununicon∈N. Allorag(x)=f(n+1)∈Im(f). Perci`o g(y) = g(x) = f(n + 1) ∈ Im(f) e quindi, per quanto osservato prima, y ∈ Im(f). Ne segue che y = f(m) per un unico m ∈ N e g(y) = f(m + 1). Abbiamo allora f(n+1) = f(m+1) e, siccome f `e iniettiva, n+1 = m+1; perci`o n = m e x = f(n) = f(m) = y. Qual `e l’immagine di g? E` chiaro che f(0) ∈/ Im(g). Viceversa, ogni elemento di A\{f(0)} appartiene all’immagine di g, cio`e Im(g) = A \ {f(0)}. Se allora consideriamo la funzione g come una funzione g : A → A \ {f (0)}, questa `e una biiettivit`a. In definitiva |A| = |A \ {f(0)}|; se poniamo B = A \ {f(0)}, abbiamo il sottoinsieme cercato. 􏰃 Notiamo che, nella dimostrazione precedente, A \ B = {f (0)} `e finito. Come esercizio si trovi in modo analogo al precedente un sottoinsieme C ⊂ A tale che |C| = |A| e A \ C sia infinito. 4. Insiemi numerabili Il teorema secondo il quale per ogni insieme infinito A si ha |N| ≤ |A| ci porta ad attribuire un ruolo speciale a N (piu` precisamente alla sua cardinalit`a). Definizione 3. Un insieme A si dice numerabile se |A| = |N|. Un sottoinsieme di N `e allora finito o numerabile. Abbiamo gi`a visto in precedenza che anche Z (insieme dei numeri interi) `e numerabile. Piu` in generale possiamo enunciare alcune propriet`a degli insiemi numerabili. Teorema 5. Se A `e finito e B `e numerabile, allora A ∪ B `e numerabile. Dimostrazione. Se A ⊆ B, l’affermazione `e ovvia. Siccome A ∪ B = (A \ B) ∪ B possiamo supporre che A e B siano disgiunti, sostituendo A con A \ B che `e finito. Possiamo allora scrivere A = {a0,...,am−1} e considerare una biiettivit`a g: N → B. Definiamo una funzione f : N → A ∪ B ponendo 􏰈an se 0 ≤ n < m, g(n−m) sen≥m. g(x) = f(n) =  4. INSIEMI NUMERABILI 5 E` facile verificare che f `e una biiettivit`a. 􏰃 Teorema 6. Se A e B sono numerabili, allora A ∪ B `e numerabile. Se A1, A2,..., An sono insiemi numerabili, allora A1 ∪ A2 ∪ ··· ∪ An `e un insieme numerabile. Dimostrazione. La seconda affermazione segue dalla prima per induzione (esercizio). Vediamo la prima. Supponiamo dapprima che A ∩ B = ∅. Abbiamo due biiettivit`a f : N → A e g: N → B. Definiamo una funzione h: N → A ∪ B ponendo: f 􏰄n􏰅 2 h(n) = 􏰆 n − 1 􏰇 g 2 Si verifichi che h `e una biiettivit`a. In generale, possiamo porre A′ =A\(A∩B), e abbiamo A∪B = A′ ∪(A∩B)∪B′; questi tre insiemi sono a due a due disgiunti. I casi possibili sono i seguenti: (1) A′, A ∩ B e B′ sono infiniti; (2) A′ `e finito, A ∩ B `e infinito, B′ `e infinito; (3) A′ `e finito, A ∩ B `e infinito, B′ `e finito; (4) A′ `e infinito, A ∩ B `e infinito, B′ `e finito; (5) A′ `e infinito, A ∩ B `e finito, B′ `e infinito; (6) A′ `e infinito, A ∩ B `e finito, B′ `e finito. Ci basta applicare quanto appena dimostrato e il teorema precedente. Si concluda la dimostrazione per induzione della seconda affermazione. 􏰃 Il prossimo teorema pu`o essere sorprendente. Un modo breve per enunciarlo `e dire: L’unione di un insieme numerabile di insiemi numerabili `e numerabile. Teorema 7. Per ogni n ∈ N, sia An un insieme numerabile e supponiamo che, per m ̸= n, Am ∩ An = ∅. Allora A=􏰊{An :n∈N} `e numerabile. Dimostrazione. Per questa dimostrazione ci serve sapere che la successione dei numeri primi p0 = 2, p1 = 3, p2 = 5,..., `e infinita. Sia,perognin∈N,gn:An →Nunafunzionebiiettiva. Sex∈A,esisteununicon∈N tale che x ∈ An; poniamo j(x) = n. Definiamo allora f(x) = pgj(x)(x). j (x) Per esempio, se x ∈ A2, sar`a f(x) = 5g2(x). La funzione f : A → N `e iniettiva; quindi |A| ≤ |N|. MaA0 ⊆Aequindi |N| = |A0| ≤ |A| ≤ |N|. Per il teorema di Cantor-Schr ̈oder-Bernstein, |A| = |N|. 􏰃 Il teorema si pu`o estendere anche al caso in cui gli insiemi An non sono a due a due disgiunti; si provi a delinearne una dimostrazione. Questo teorema ha una conseguenza sorprendente. Teorema 8. L’insieme N × N `e numerabile. Dimostrazione. Poniamo An = { (m, n) : m ∈ N }. Gli insiemi An sono a due a due disgiunti e ciascuno `e numerabile. E` evidente che 􏰉n∈N An = N × N. 􏰃 Ancora piu` sorprendente `e forse quest’altro fatto. Teorema 9. L’insieme Q dei numeri razionali `e numerabile. se n `e pari, se n `e dispari.  B′ =B\(A∩B)  6 INSIEMI INFINITI Dimostrazione. Un numero razionale positivo si scrive in uno e un solo modo come m/n, con m, n ∈ N primi fra loro (cio`e aventi massimo comune divisore uguale a 1). Ne segue che l’insieme Q′ dei numeri razionali positivi `e numerabile, perch ́e a m/n (con m e n primi fra loro) possiamo associare la coppia (m, n) ∈ N × N e la funzione cos`ı ottenuta `e iniettiva. Dunque |N| ≤ |Q′| ≤ |N × N| = |N|. L’insieme Q′′ dei numeri razionali negativi `e numerabile, perch ́e la funzione f : Q′ → Q′′ definita da f(x) = −x `e chiaramente biiettiva. Per concludere, possiamo applicare altri teoremi precedenti, tenendo conto che Q = Q′ ∪ {0} ∪ Q′′. 􏰃 C’`e un altro modo per convincersi che Q′ `e numerabile, illustrato nella figura 1. Si   1/5 1/4 1/3 1/2 1/1 2/5 3/5 4/5 3/4 5/4 2/3 4/3 5/3 3/2 5/2 2/1 3/1 4/1 5/1  Figura 1. Enumerazione dei razionali positivi immagina una griglia dove segniamo tutte le coppie con coordinate intere positive. Possiamo percorrere tutta la griglia secondo il percorso indicato e associare in questo modo a ogni numero naturale un numero razionale, incontrandoli tutti. Trascuriamo naturalmente i punti in cui il quoziente fra ascissa e ordinata `e un numero razionale gi`a incontrato precedentemente (per esempio, nella prima diagonale si trascura il punto (2, 2) che corrisponderebbe al numero razionale 2/2 = 1, gi`a incontrato come 1/1; nella terza diagonale si trascurano (2, 4), (3, 3) e (4, 2)). 5. Esistenza di cardinalit`a A questo punto sorge naturale la domanda se ci sono insiemi infiniti di un’infinit`a diversa da quella dei numeri naturali. Non ci siamo riusciti nemmeno considerando l’insieme dei razionali che, intuitivamente, dovrebbe avere piu` elementi dei numeri naturali. C’`e una costruzione che produce cardinalit`a maggiori. Prima per`o definiamo con preci- sione ci`o che intendiamo. Definizione 4. Se A e B sono insiemi, diciamo che A ha cardinalit`a minore della cardinalit`a di B, e scriviamo |A| < |B|, se |A| ≤ |B|, ma non `e vero che |A| = |B|.  5. ESISTENZA DI CARDINALIT`a 7 Il modo corretto per verificare che |A| < |B| `e questo: • esiste una funzione totale iniettiva di A in B; • non esiste una biiettivit`a di A su B. Notiamo che non basta verificare che una funzione iniettiva totale di A in B non `e suriettiva. Per esempio, esiste certamente una funzione totale iniettiva di N in Q che non `e suriettiva; tuttavia, come abbiamo visto, |N| = |Q|. Un altro esempio: l’insieme N ∪ {−2} `e numerabile, anche se la funzione di inclusione N → N ∪ {−2} non `e suriettiva. Infatti la funzione f : N → N ∪ {−2} definita da f(0) = −2 e f(n) = n − 1 per n > 0 `e una biiettivit`a. L’idea per trovare un insieme di cardinalit`a maggiore partendo da un insieme X `e dovuta a Cantor. Teorema 10 (Cantor). Se X `e un insieme, allora |X| < |P (X)|. Dimostrazione. Dimostriamo che esiste una funzione totale iniettiva X → P(X); essa `e, per esempio, { (x, {x}) : x ∈ X } cio`e la funzione che all’elemento x ∈ X associa il sottoinsieme {x} ∈ P(X). Dobbiamo ora dimostrare che non esistono funzioni biiettive di X su P(X). Lo faremo per assurdo, supponendo che g: X → P(X) sia biiettiva. Consideriamo C ={x∈X :x∈/ g(x)}. La definizione di C ha senso, perch ́e g(x) `e un sottoinsieme di X, dunque si hanno sempre due casi: x ∈ g(x) oppure x ∈/ g(x). Siccome, per ipotesi, g `e suriettiva, deve esistere un elemento c ∈ X tale che C = g(c). Dunquesihac∈C oppurec∈/C. Supponiamo c ∈ C; allora c ∈ g(c) e quindi, per definizione di C, c ∈/ C: questo `e assurdo. Supponiamo c ∈/ C; allora c ∈/ g(c) e quindi, per definizione di C, c ∈ C: assurdo. Ne concludiamo che l’ipotesi che g sia suriettiva porta a una contraddizione. Perci`o nessuna funzione di X in P(X) `e suriettiva. 􏰃 L’insieme P(X) ha la stessa cardinalit`a di un altro importante insieme. Indichiamo con 2X l’insieme delle funzioni totali di X in {0, 1}. Definizione 5. Se A `e un sottoinsieme di X, la funzione caratteristica di A `e la funzione χA : X → {0, 1} definita da 􏰈1 sex∈A, χA(x)= 0 sex∈/A. Possiamodefinireduefunzioni,f:P(X)→2X eg:2X →P(X)nelmodoseguente: per A∈P(X)siponef(A)=χA;perφ∈2X sipone g(φ)={x∈X :φ(x)=1}. Teorema 11. Per ogni insieme X si ha |P(X)| = |2X|. Dimostrazione. Proveremo che g ◦ f e f ◦ g sono funzioni identit`a. Sia A ∈ P(X); dobbiamo calcolare g(f(A)) = g(χA): abbiamo g(χA)={x∈X :χA(x)=1}=A, per definizione di χA. Sia φ ∈ 2X; dobbiamo calcolare f(g(φ)). Poniamo B = g(φ) = {x ∈ X : φ(x) = 1}. Occorreverificarecheφ=χB. Siax∈X;seφ(x)=1,allorax∈BequindiχB(x)=1; se φ(x) = 0, allora x ∈/ B e quindi χB(x) = 0. Non essendoci altri casi, concludiamo che φ = χB. Ora, siccome per ogni A ∈ P(X) si ha A = g(f(A)), g `e suriettiva e f `e iniettiva. Analogamente, per φ ∈ 2X, φ = f(g(φ)) e dunque f `e suriettiva e g `e iniettiva. 􏰃  8 INSIEMI INFINITI 6. La cardinalit`a dell’insieme dei numeri reali Con il teorema di Cantor a disposizione, si pu`o affrontare il problema di determinare la cardinalit`a dei numeri reali. Intanto dimostriamo un risultato preliminare; consideriamo l’intervallo aperto I={x∈R:0<x<1} e dimostriamo che |I| = |R|. Consideriamo la funzione f : R → R, √ 2  1+x−1 f(x) = x 0 Un facile studio di funzione mostra che f `e iniettiva e che Im(f) = I. Allo stesso risultato si arriva considerando la funzione g(x) = π2 arctan x. La considerazione di I ci permetter`a di semplificare i ragionamenti. Sappiamo che ogni numero reale in I si pu`o scrivere come allineamento decimale: 21 = 0,500000000000 . . . 31 = 0,333333333333 . . . √71 = 0,142857142857 . . . 22 = 0,707106781187 . . . π4 =0,785398163397... dove i puntini indicano altre cifre decimali. Prevedibili in base a uno schema periodico nei primi tre casi, non prevedibili negli ultimi due che sono numeri irrazionali. Il numero dieci non ha nulla di particolare. Si pu`o allo stesso modo sviluppare un nu- mero reale come allineamento binario. Gli stessi numeri, scritti a destra dell’uguale come allineamenti binari, sono: 21 = 0,100000000000000000000000000 . . . 13 = 0,010101010101010101010101010 . . . 17 = 0,001001001001001001001001001 . . . √ 22 = 0,101101010000010011110011001 . . . π4 =0,110010010000111111011010101... e le cifre si ripetono ancora periodicamente nei primi tre casi. In generale un numero r ∈ I si scrive come r = 0,a0a1a2 ..., dove ai = 0 oppure ai = 1; in modo unico, se escludiamo tutte le successioni che, da un certo momento in poi, valgono 1. Questo `e analogo ai numeri di periodo 9 nel caso decimale. Dunque abbiamo in modo naturale una funzione f : I → 2N: f(r) `e la funzione φ: N → {0, 1} definita da φ(n) = an dove a0, a1, · · · sono le cifre di r nello sviluppo binario di r. La funzione f `e totale e iniettiva, quindi concludiamo che |I| ≤ |2N|. se x̸=0,  se x = 0.  7. IL PARADISO DI CANTOR 9 Vogliamo ora definire una funzione g: 2N → I. Prendiamo φ ∈ 2N; la tentazione sarebbe di definire g(φ) come quel numero reale il cui sviluppo binario `e 0,φ(0) φ(1) φ(2) . . . ma questo non funziona, perch ́e, se per esempio la funzione φ `e la costante 1, il numero 0,111111 . . . `e 1 ∈/ I. Se anche escludessimo questa funzione, avremmo il problema del “periodo 1”. Dunque agiamo in un altro modo. Alla funzione φ associamo il numero reale il cui sviluppo binario `e g(φ) = 0,0 φ(0) 0 φ(1) 0 φ(2) ... cio`e intercaliamo uno zero fra ogni termine. E` chiaro che, se φ ̸= ψ, allora g(φ) ̸= g(ψ), dunque g `e iniettiva e totale. Teorema 12 (Cantor). |R| = |P (N)|. Dimostrazione. Abbiamo gi`a a disposizione le funzioni f: I → 2N e g: 2N → I, entrambe iniettive. In particolare, |I| ≤ |2N e |2N| ≤ |I|; per il teorema di Cantor-Schr ̈oder-Bernstein, |I| = |2N|. Sappiamo poi che |I| = |R| e che |2N| = |P(N)|. Dunque |R| = |I| = |2N| = |P(N)|, come voluto. Occorre commentare questo risultato. Per dimostrarlo abbiamo usato il teorema di Cantor-Schr ̈oder-Bernstein, quindi non abbiamo potuto scrivere esplicitamente una biietti- vit`a di R su P (N). Ma non `e questo il punto piu` importante. La conseguenza piu` rilevante del teorema `e che non `e possibile descrivere ogni numero reale, perch ́e, come vedremo in seguito, i numeri reali che possono essere espressi con una formula sono un insieme numerabile. 7. Il paradiso di Cantor Un’altra applicazione del teorema di Cantor porta alla costruzione del cosiddetto “paradi- so di Cantor”. Questa espressione vuole indicare l’esistenza di una successione di cardinalit`a infinite ciascuna strettamente maggiore della precedente. Allo scopo basta iterare il passaggio all’insieme dei sottinsiemi, per esempio a partire dall’insieme dei numeri naturali, per ottene- re una successione di insiemi la cui cardinalit`a, per il teorema di Cantor, continua a crescere strettamente: |N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < ··· < |P(...P(P(P(N))))...)| < ··· Si potrebbe ancora andare avanti; definiamo, per induzione, P0(X) = X, Pn+1(X) = P(Pn(X)). Allora possiamo considerare l’insieme Y1 = 􏰊 Pn(N), n∈N e si pu`o dimostrare che |Pn(N)| < |Y1|, per ogni n ∈ N. Dunque abbiamo trovato una cardinalit`a ancora maggiore di tutte quelle trovate in precedenza e il gioco pu`o continuare: consideriamo Y2 = 􏰊 Pn(Y1) n∈N e ancora |Pn(Y1)| < |Y2|. E cos`ı via, costruendo una gerarchia infinita di cardinalit`a sempre maggiori. Oltre a interrogarci sul prolungarsi della successione delle cardinalit`a infinite sempre mag- giori, `e del tutto naturale domandarsi se tra |N| e |P (N)| c’`e o no una cardinalit`a strettamente compresa tra le due. Piu` in generale, ci si pu`o chiedere se, dato un insieme infinito X, esiste un insieme Y tale che |X| < |Y | < |P(X)|. 􏰃  10 INSIEMI INFINITI Cantor ipotizz`o che non ci siano insiemi Z tali che |N| < |Z| < |P(N)|, e questa ipotesi ha preso il nome di ipotesi del continuo. Non `e questo il luogo dove discutere questa questione, risolta brillantemente da P. J. Cohen nel 1963: l’ipotesi del continuo `e indecidibile rispetto agli assiomi della teoria degli insiemi, nel senso che `e altrettanto coerente prenderla come vera che prenderla come falsa. Non si tratta di argomenti semplici, tanto che per i suoi studi Cohen fu insignito della Fields Medal che, per i matematici, `e l’analogo del Premio Nobel. Esercizi Si ricordi che kN indica l’insieme dei numeri naturali multipli di k, N≥k l’insieme dei numeri naturali maggiori o uguali a k, e N>k l’insieme dei numeri naturali strettamente maggiori di k. Esercizio 1. Si dica, motivando la risposta, se gli insiemi 3N ∪ {2, 5} e 2N \ {10, 8} hanno la stessa cardinalit`a. Esercizio 2. Si costruisca una funzione biiettiva tra gli insiemi 4N ∪ { 32 , 7, √2} e N>9 . Esercizio 3. Si dimostri che per ogni insieme finito X, se f : X → X `e totale e iniettiva, allora `e biiettiva. Si dia un esempio di un insieme infinito in cui l’analoga propriet`a non sussiste. Esercizio 4. Si dimostri che per ogni insieme finito X, se f : X → X `e totale e suriettiva, allora `e biiettiva. Si dia un esempio di un insieme infinito in cui l’analoga propriet`a non sussiste. Esercizio 5. Si costruisca una funzione biiettiva tra gli insiemi Z ∪ { 32 , √3 2} e 3N. Esercizio 6. Si dica, motivando la risposta, se gli insiemi (5N \ {5, 15}) ∪ {√3, 25 } e 2N ∪ {11, 17} hanno la stessa cardinalit`a. Esercizio 7. Si dica, motivando la risposta, se gli insiemi N≥50 ∪ 5N e 3N ∩ 2N hanno la stessa cardinalit`a. Esercizio 8. Sia A un insieme numerabile e sia a ∈/ A. Si costruisca una biiezione tra gli insiemi A e A ∪ {a}. Esercizio 9. Sia A un insieme numerabile e sia a ∈ A. Si costruisca una biiezione tra gli insiemi A e A \ {a}. Esercizio 10. Sia Π l’insieme dei numeri reali irrazionali. L’insieme Π `e numerabile? Esercizio 11. L’insieme di tutte le funzioni da Q all’insieme {0, 1, 2, 3} `e numerabile? Esercizio 12. Sia P = {I | I ⊆ N e I `e un insieme finito} l’insieme delle parti finite di N. Qual `e la cardinalit`a di P ? Esercizio 13. Si dica, motivando la risposta, se l’insieme P(3N) `e numerabile.