Matematica Discreta I
Lezione del giorno 22 ottobre 2007
Useremo i seguenti simboli per indicare gli insiemi numerici più comuni: N è l’insieme dei numeri interi >0, detti numeri naturali; Z è l’insieme dei numeri interi relativi (cioè positivi, negativi e lo zero); Q è l’insieme dei numeri razionali relativi; R è l’insieme dei numeri reali relativi.
Un asterisco sul simbolo indicherà che dall’insieme è escluso lo 0 (per es. Q* è l’insieme dei numeri razionali relativi non nulli); un segno + sul simbolo indicherà che dell’insieme sono considerati solo i positivi (per es. Q+ è l’insieme dei numeri razionali positivi)
Cardinalità degli insiemi infiniti: insiemi equipotenti
Per un insieme finito A (cioè che contiene un numero finito di elementi), abbiamo definito la cardinalità A di A coincidente appunto con il numero di elementi di A.
Se volessimo definire il concetto di cardinalità anche per un insieme infinito A, una soluzione (poco soddisfacente dal punto di vista matematico) potrebbe essere quella di dire semplicemente che la cardinalità di un insieme infinito è uguale a infinito: ciò porterebbe a non distinguere fra i vari “tipi” di cardinalità infinita.
Cantor propose invece di costruire una teoria per gli insiemi infiniti che fosse coerente con i risultati già dimostrati nel caso degli insiemi finiti. Ricordiamo un teorema già dimostrato: se A,B sono insiemi finiti e se esiste una funzione biunivoca f: A B, allora A e B hanno la stessa cardinalità.
L’esistenza o la non esistenza di una funzione biunivoca f: A B, con A,B insiemi infiniti, potrebbe allora essere presa come misura dell’eguaglianza o differenza della cardinalità.
Se A,B sono insiemi infiniti, diremo che A è equipotente a B (o anche che A,B hanno la stessa cardinalità) se esiste una funzione biunivoca f: A B.
Notiamo che:
- ogni insieme A è equipotente a sé stesso, in quanto la funzione identica iA : A A è biunivoca - se A,B sono insiemi e se A è equipotente a B allora anche B è equipotente a A, in quanto se esiste una funzione biunivoca f: A B, sappiamo che anche la funzione inversa f-1 : A B è biunivoca
- se A,B,C sono insiemi e se A è equipotente a B e B è equipotente a C, allora A è equipotente a C, in quanto se esistono due funzioni biunivoche f: A B, g: B C, sappiamo che anche la loro composizione gf: A C è biunivoca
Il modello più semplice di insieme infinito è l’insieme N dei numeri naturali: diremo che un insieme infinito A ha la cardinalità del numerabile se A è equipotente ad N, cioè se esiste una funzione biunivoca f: N A.
Cerchiamo esempi di insiemi numerici infiniti che abbiano la cardinalità del numerabile.
L’insieme Z dei numeri interi relativi ha la cardinalità del numerabile.
Esiste infatti una funzione biunivoca f: N Z, che si può descrivere graficamente (anche se in modo incompleto) nel modo seguente:
f
N Z
e che formalmente è definita ponendo f(x)=x/2 se x pari, ed f(x)=(1-x)/2 se x è dispari.
Dimostriamo che f è biunivoca.
Iniettività di f: per assurdo siano x,yN, con xy, e tali che f(x)=f(y). Distinguiamo i 3 casi possibili e in ognuno troviamo una contraddizione:
- x,y entrambi pari: si ha f(x)=x/2=f(y)=y/2, da cui x=y (contraddizione)
- x,y entrambi dispari: si ha f(x)=(1-x)/2=f(y)=(1-y)/2, da cui x=y (contraddizione)
- x,y uno pari (per es. x) ed uno dispari (per es. y): si ha f(x)=x/2=f(y)=(1-y)/2, da cui x=1-y (contraddizione perché x>0, 1-y≤0).
Surgettività di f: per ogni yZ cerchiamo un xN tale che f(x)=y; se y>0, l’equazione f(x)=x/2=y ha la soluzione x=2yN; se invece y≤0, l’equazione f(x)=(1-x)/2=y ha la soluzione x=1-2yN (perché 2y≤0, dunque x=1-2y>0).
L’insieme Q+ dei numeri razionali positivi ha la cardinalità del numerabile.
Si può infatti costruire una funzione biunivoca f: N Q+ :
disponiamo tutti i numeri razionali positivi, sotto forma di frazioni, in una tabella con infinite righe e colonne, con la regola che nella casella all’incrocio fra la riga numero n e la colonna numero m poniamo la frazione con numeratore n e denominatore m; costruendo per esempio solo le prime 5 righe e 5 colonne si ha
1/1 1/2 1/3 1/4 1/5 2/1 2/2 2/3 2/4 2/5 3/1 3/2 3/3 3/4 3/5 4/1 4/2 4/3 4/4 4/5 5/1 5/2 5/3 5/4 5/5
(Notiamo che nelle infinite caselle della tabella troviamo tutti i numeri razionali positivi, nessuno escluso, anche se alcune caselle contengono lo stesso valore)
Poi percorriamo in successione le caselle con il seguente procedimento a “zig-zag”:
Definiamo la funzione biunivoca f: N Q+ associando al numero naturale 1 il contenuto della prima casella del percorso (quindi f(1)=1/1) , al 2 quello della seconda casella (quindi f(2)=1/2), al
1 2 3 4 5 6 . . .
0 1 -1 2 -2 3 -3 . . .
3 quello della terza casella (quindi f(3)=2/1) e così via, con la regola (necessaria per l’iniettività di f) che se tocchiamo una casella il cui contenuto è già stato incontrato in precedenza, la saltiamo (quindi f(4)=3/1, ma f(5)=1/3 e non f(5)=2/2, perché 2/2=1/1=f(1)).
L’insieme Q dei numeri razionali relativi ha la cardinalità del numerabile.
Si dimostra con procedimenti simili.
Non è facile, invece, trovare un insieme numerico infinito che non abbia la cardinalità del numerabile. Fu lo stesso Cantor a dimostrare che:
L’insieme R dei numeri reali non ha la cardinalità del numerabile.
Per assurdo supponiamo che esista una funzione biunivoca f: N R .
Rappresentiamo ogni reale positivo in forma decimale, con una parte intera e delle cifre (scelte fra 0 e 9) dopo la virgola.
Per ogni numero naturale nN usiamo la seguente notazione per rappresentare l’immagine f(n)R+: f(n) = an , bn1 bn2 bn3 bn4 . . .
(dove an indica la parte intera, e bnj indica la cifra dopo la virgola che occupa il posto j).
Seguendo tale notazione si ha:
f(1) = a1 , b11 b12 b13 b14 . . . f(2) = a2 , b21 b22 b23 b24 . . . f(3) = a3 , b31 b32 b33 b34 . . . f(4) = a4 , b41 b42 b43 b44 . . . . . . .
. . . . . . . .
Per la surgettività di f, l’elenco dei numeri dopo i segni di eguaglianza dovrebbe esaurire tutti i numeri reali positivi.
Costruiamo allora (con il cosiddetto “procedimento diagonale di Cantor”) un numero reale x con parte intera a piacere e con le cifre dopo la virgola scelte con la seguente regola: la cifra al posto 1 è diversa dalla cifra b11 (cifra di posto 1 di f(1)); la cifra al posto 2 è diversa dalla cifra b22 (cifra di posto 2 di f(2)); etc…, quindi in generale la cifra di posto j è diversa dalla cifra bjj (cifra di posto j di f(j)).
Tale numero x dovrebbe essere uguale all’immagine f(n) di qualche numero naturale n: ma ciò è una contraddizione, perché f(n) ha almeno una cifra dopo la virgola diversa dalla cifra (dello stesso posto) del numero x (per costruzione esattamente la cifra bnn di posto n).
Definiremo cardinalità del continuo la cardinalità dell’insieme R dei numeri reali (e di tutti gli insiemi equipotenti ad R).
Il prossimo Teorema permette di costruire, a partire da un qualunque insieme infinito A, un insieme di cardinalità diversa:
Teorema. Sia A un insieme infinito e P(A) l’insieme delle parti di A. Allora la cardinalità di A è diversa da quella di P(A).
Dimostrazione:
Per assurdo supponiamo che esista una funzione biunivoca f: A P(A), che associa ad ogni elemento xA un elemento f(x)P(A) (quindi f(x) è un sottoinsieme di A).
Dato un elemento qualunque xA, può avvenire che x sia elemento del sottoinsieme f(x) oppure che non lo sia. Costruiamo allora il sottoinsieme B di A contenente tutti gli elementi xA che soddisfano la condizione xf(x):
B = { xA / xf(x) }
Essendo f surgettiva, ed essendo BP(A), esiste almeno un xA tale che f(x)=B.
Tale elemento xA può appartenere o no a B:
caso 1: xB; in questo caso xf(x), dunque (per costruzione di B) si ha xB (contraddizione) caso 2: xB; in questo caso xf(x), dunque (per costruzione di B) si ha xB (contraddizione) Poiché in ogni caso si ottiene una contraddizione, il teorema è dimostrato.
