Matematica Discreta
Lezione del giorno 8 marzo 2012 Dimostreremo ora il seguente risultato:
L’insieme Q+ dei numeri razionali positivi ha la cardinalità del numerabile.
Si può infatti, come vedremo, 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 semplicità 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 percorso a “zig-zag”:
Definiamo la funzione 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 3 quello della terza casella (quindi f(3)=2/1) e così via, con la regola 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)). Tale regola ci garantisce che f è iniettiva (perché numeri naturali diversi saranno associati a razionali diversi); inoltre il fatto che la tabella contiene tutti i razionali positivi garantisce che f è surgettiva (ogni razionale positivo si trova in qualche casella della tabella, dunque è il corrispondente di qualche numero naturale).
Vale anche il seguente risultato:
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 positivi 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 (che è la cifra di posto 1 di f(1)); la cifra al posto 2 è diversa dalla cifra b22
(che è la cifra di posto 2 di f(2)); etc…, quindi in generale la cifra di posto j è diversa dalla cifra bjj
(che è la 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 quindi di tutti gli insiemi equipotenti ad R).
La funzione di Eulero.
Dati 2 numeri naturali a,b, diremo che a,b sono numeri coprimi se mcd(a,b)=1.
Poiché il massimo comune divisore di a,b è il più grande dei divisori comuni di a,b, in pratica affermare che a,b sono coprimi equivale ad affermare che l’unico divisore comune di a,b è 1.
Fissato un numero naturale n, si chiama funzione di Eulero la funzione φ: N N che associa ad ogni numero naturale nN il numero φ(n) di tutti i numeri naturali x tali che 1xn ed x,n sono coprimi.
E’ ovvio che φ(1)=1, dunque studieremo solo il caso n>1.
Esempio: se n=15, i numeri naturali x tali che 1x15 ed x,15 sono coprimi sono 1,2,4,7,8,11,13,14 quindi φ(15)=8 .
Cercheremo una formula che permetta di calcolare φ(n) conoscendo la fattorizzazione di n in prodotto di numeri primi. Premettiamo 2 risultati preliminari:
1) Siano p1, p2,….., pr dei numeri primi distinti e supponiamo che ognuno di essi sia divisore del numero naturale c. Allora anche il prodotto (p1p2…..pr) è divisore di c.
Dimostrazione: per ipotesi esiste un naturale b tale che p1b=c; se fattorizziamo sia c che b in prodotto di numeri primi:
b=q1q2…..qs , c=t1t2…..tm
si ha l’eguaglianza:
p1q1q2…..qs = t1t2…..tm
e per l’unicità della fattorizzazione segue che p1 coincide con uno dei fattori t1, t2, …., tm e (riordinando opportunamente i fattori) possiamo fare in modo che p1=t1.
Analogamente, ragionando su p2, si ottiene che p2 coincide con uno dei fattori t1, t2, …., tm (ma non con t1 perché p1p2) e (riordinando opportunamente i fattori) possiamo fare in modo che p2=t2. Procediamo fino ad ottenere pr=tr da cui c = t1t2…..tm = (p1p2…..pr)tr+1…..tm e si ha la tesi.
2) Siano x1, x2,…,xr delle variabili (che possono assumere come valori numerici arbitrari) e calcoliamo il valore dell’espressione algebrica seguente:
(1-x1)(1-x2)……(1-xr)
Per r=2 si ha, utilizzando la proprietà distributiva e sviluppando i calcoli : (1-x1)(1-x2)=1-(x1+x2)+x1x2
Per r=3 con calcoli analoghi si ha:
(1-x1)(1-x2)(1-x3)=1-(x1+x2+x3)+(x1x2+x1x3+x2x3)-x1x2x3
Si può in generale dimostrare (con una dimostrazione per induzione che omettiamo) che per qualunque numero r di variabili vale la seguente formula:
(1-x1)(1-x2)……(1-xr)=1-α1+α2-α3+α4+…….±αr
dove α1 è la somma delle singole variabili ; α2 è la somma dei prodotti delle variabili prese a 2 a 2;
α3 è la somma dei prodotti delle variabili prese a 3 a 3; …….. ……; r è il prodotto delle r variabili, preceduto da un segno + se r è pari, da un segno – se r è dispari.
