Nello scorso capitolo ci siamo soffermati sulla cardinalità ℵ0 dei numeri naturali e abbiamo mostrato alcune proprietà di tale cardinale. Adesso che abbiamo dato le definizioni delle operazioni tra cardinali possiamo esprimere i risultati del prece-dente capitolo in formula:
(1) κ < ℵ0 se e solo se κ ∈ N;
(2) n + ℵ0 = ℵ0+ ℵ0= ℵ0 per n ∈ N (questo esprime che l’unione di due insiemi numerabili è numerabile);
(3) n · ℵ0 = ℵ0· ℵ0 = ℵ0 per n ∈ N (questo invece è il fatto che il prodotto carte-siano di insiemi numerbaili è numerabile).
Nell’ultimo paragrafo dello scorso capitolo abbiamo poi mostrato che l’insieme R è equipotente a P(N), e che entrambi hanno cardinalità strettamente superiore ad ℵ0. Abbiamo mostrato che
|P(N)| = |2N|,
e adesso con la definizione di esponenziazione possiamo scrivere |P(N)| = 2|N| = 2ℵ0. Quindi possiamo scriovere adesso
c = 2ℵ0.
Ripetendo la stessa dimostrazione del teorema 5.4.3 con X al posto di N possiamo formulare il seguente teorema:
Teorema 6.2.1. Per ogni X insieme vale |P(X)| = 2|X|.
Il teorema di Cantor può essere dunque ora espresso in termine di cardinali come segue: per ogni κ cardinale
κ < 2κ.
Adesso invece vogliamo concentrarci sulla cardinalità del continuo c = 2ℵ0, la cardinalità dell’insieme dei numeri reali.
Teorema 6.2.2. Valgono le seguenti uguaglianze:
(1) n + 2ℵ0 = ℵ0+ 2ℵ0 = 2ℵ0+ 2ℵ0 = 2ℵ0 per n ∈ N;
(2) n · 2ℵ0 = ℵ0· 2ℵ0 = 2ℵ0 · 2ℵ0 = 2ℵ0 per n > 1;
(3) (2ℵ0)n= (2ℵ0)ℵ0 = nℵ0 = ℵℵ00 = 2ℵ0 per n > 1.
Dimostrazione. Per (1) e (2) si conclude per il teorema di Cantor–Bernstein da 2ℵ0 ≤ n + 2ℵ0 ≤ ℵ0+ 2ℵ0 ≤ 2ℵ0 + 2ℵ0 = 2 · 2ℵ0 = 21+ℵ0 = 2ℵ0.
La seconda parte è del tutto analoga.
(3) Per questa basta notare che valgono sia
2ℵ0 ≤ (2ℵ0)n≤ (2ℵ0)ℵ0 = 2ℵ0·ℵ0 = 2ℵ0 e anche
2ℵ0 ≤ nℵ0 ≤ ℵℵ00 ≤ (2ℵ0)ℵ0 = 2ℵ0. Il teorema è così provato.
Osserviamo che il teorema appena provato, benché sia un’immediata conseguen-za del teorema di Cantor–Bernstein, porta a delle conseguenze inaspettate. Per esempio 2ℵ0 · 2ℵ0 = 2ℵ0 significa che R × R è equipotente ad R. Cioè, esiste una mappa biunivoca dalla retta nel piano (!); ma di più anche lo spazio Rn, spazio n–dimensionale, è equipotente ad R. Questo risultato (dovuto a Cantor) stupì i contemporanei di Cantor tanto era controintuitivo: questo era quello che però la teoria, a partire da assiomi intuitivi, dimostrava.
Corollario 6.2.1. L’insieme dei numeri complessi, delle sequenze infinite di nu-meri naturali e delle sequenze infinite di nunu-meri reali hanno cardinalità 2ℵ0. Dimostrazione. Per i numeri complessi basta osservare che C è isomorfo a R2, quindi ha cardinalità del continuo. Poi, l’insieme delle sequenze infinite di numeri naturali altri non è che NN, quindi |NN| = ℵℵ00 = 2ℵ0. L’insieme delle sequenze infinite di numeri reali è RN, e vale |RN| = (2ℵ0)ℵ0 = 2ℵ0.
Adesso mostriamo un risultato che a prima vista sembra intuitivo, ma che necessita di una rigorosa dimostrazione:
Teorema 6.2.3. Sia A un insieme numerabile e B un insieme di cardinalità 2ℵ0. Allora B − A ha sempre cardialità 2ℵ0.
Dimostrazione. Assumiamo senza perdere di generalità che B = R × R e A ⊆ B.
Sia ora
P = {x ∈ R | ∃y tale che (x, y) ∈ A};
visto che |A| = ℵ0 allora |P | ≤ ℵ0. Così esiste x0 ∈ R tale che x0 ∈ P e dunque/ l’insieme X = {x0} × R è disgiunto da A, ossia X ⊆ (R × R) − A. Ovviamente X ha cardinalità 2ℵ0. e allora |(R × R) − A| ≥ 2ℵ0.
Corollario 6.2.2. L’insieme dei numeri irrazionali ha cardinalità 2ℵ0.
Dimostrazione. Segue dal teorema precedente essendo i numeri irrazionali l’insieme R − Q e Q è numerabile.
Adesso occupiamoci dei numeri algebrici e dei numeri trascendenti: essendo abi-tuati a lavorare più con numeri algebrici che con numeri trascendenti saremmo por-tati a dire che i primi sono di più dei secondi: in realtà è esattamente il contrario.
Intanto ricordiamo le loro definizioni:
Definizione 6.2.1. Un numero reale si dice algebrico se è radice di un polinomio non nullo a coefficienti interi. Un nero numero reale si dice trascendente se non è algebrico.
Teorema 6.2.4. I numeri algebrici sono una quantità numerabile, mentre i tra-scendenti hanno cardinalità 2ℵ0.
Dimostrazione. Mostrato che gli algebrici sono numerabili seguirà immediatamente che i trascendenti sono 2ℵ0 per il teorema precedente. Dapprima mostriamo che l’anello Z[x] ha una quantità numerabile di elementi. Possiamo identificare ogni polinomio di Z[x] con il vettore dei suoi coefficienti, di modo che
Z[x] è isomorfo a
∞
[
k=1
Zk.
Adesso l’unione a destra è l’unione numerabile di insiemi numerabili e dunque ha cardinalità ℵ0. Adesso mostrare che gli algebrici sono numerabili è molto semplice:
infatti ogni polinomio, per il teorema fondamentale dell’algebra, ha un numero finito di radici basterà unire tutte le radici reali di tutti tali polinomi. Queste saranno numerabili perché unione numerabile di insiemi finiti.
Infine vogliamo calcolare la cardinalità di alcuni insiemi significativi, come quello delle funzioni continue, delle funzioni in generale e degli aperti di R.
Teorema 6.2.5. L’insieme C0(R) delle funzioni continue su R e l’insieme degli aperti di R ha cardinalità 2ℵ0.
Dimostrazione. Dal corso di analisi è noto che ogni funzione continua è univoca-mente determinata dalle immagini di ogni punto di un insieme denso in R, per esempio sull’insieme Q dei razionali. Consideriamo allora la mappa da C0(R) in RQ che manda f in f |Q. Per quanto appena detto tale corrispondenza deve essere iniettiva e dunque
|C0(R)| ≤ |RQ| = (2ℵ0)ℵ0 = 2ℵ0.
Dall’altro lato è ovvio che |C0(R)| ≥ 2ℵ0, basta considerare le funzioni costanti.
Per la seconda parte invece usiamo un fatto noto dal corso di topologia: ogni aperto di R può essere scritto come unione di un sistema intervalli aperti con estremi razionali. Ci sono dunque ℵ0 intervalli siffatti e pertanto 2ℵ0 sistemi di intervalli. Questo mostra che ci sono al massimo 2ℵ0 aperti. Dall’altro lato però, per ogni a, b ∈ R distinti (a, ∞) 6= (b, ∞), e quindi ci sono almento 2ℵ0 aperti. In effetti se adesso consideriamo le funzioni da R in sé, queste superano la cardi-nalità del continuo. Infatti vale il seguente:
Lemma 6.2.1. L’insieme di tutte le funzioni da R in sé ha cardinalità strettamente superiore a 2ℵ0.
Dimostrazione. Si ha semplicemente
|RR| = (2ℵ0)2ℵ0 = 2ℵ0·2ℵ0 = 22ℵ0,
che supera certamente 2ℵ0 per il teorema sull’insieme delle parti.
Capitolo 7
Numeri ordinali
Quando abbiamo introdotto i numeri naturali, eravamo motivati dall’esigenza di formalizzare il processo di “contare”: i numeri naturali iniziano con 0 e sono gene-rati mediante successivi incrementi di una unità: 0, 1, 2, . . . , e così via. Abbiamo definito l’operatore di successore mediante S(x) = x ∪ {x}, e introdotto i numeri naturali come il più piccolo degli insiemi contenenti 0 e chiusi per successore.
Quello che vogliamo fare in questo capitolo è di continuare il processo di enume-razione altre oltre i numeri naturali. L’idea è che possiamo immaginare di definire un numero infinito ω che viene “dopo” tutti i numeri naturali e quindi continuare il processo di conta nel transfinito: ω, ω + 1, (ω + 1) + 1, e così via. In questo capitolo formalizzeremo questi concetti e introdurremo i numeri ordinali come una generalizzazione dei numeri naturali. Molto importante sarà che generalizze-remo i teoremi di induzione e di ricorsione numerabile che abbiamo enunciato (in questo capitolo dovremo anche dimostrare la ricorsione numerabile) ai teoremi di induzione e ricursione transfinita.