Infiniti 14/3/18 9 / 75 LM Prima di addentrarci nelle questioni concernenti gli insiemi qualsiasi, facciamo una breve rilettura di quello che sappiamo sugli insiemi finiti. Lo studio degli insiemi infiniti è iniziato nel decennio 1874-1884 ad opera del matematico tedesco GEORG CANTOR Annalisa Malusa Infiniti 14/3/18 10 / 75 Cardinalità di insiemi finiti LM Cosa vuol dire che in una palazzina ci sono 10 appartamenti? Annalisa Malusa Infiniti 14/3/18 11 / 75 Cardinalità di insiemi finiti LM Per contare gli appartamenti abbiamo associato univocamente a ciascuno di essi un numero (naturale) tra 1 e 10. In termini matematici, abbiamo determinato una corrispondenza biunivoca tra l’insieme degli appartamenti e l’insieme ω10 = {1,2,3,4,5,6,7,8,9,10} Annalisa Malusa Infiniti 14/3/18 12 / 75 LM f è un’iniezione di A in B se è una corrispondenza biunivoca tra A e un sottoinsieme di B Siano A e B due insiemi qualsiasi e f : A → B una funzione, ossia una legge tale per cui per ogni a ∈ A esiste uno e un solo b ∈ B tale che f (a) = b. Definizione 1 (Corrispondenza biunivoca) f è una corrispondenza biunivoca tra A e B se per ogni b ∈ B esiste uno e un solo a ∈ A tale che f (a) = b. Definizione 2 (Iniezione) Annalisa Malusa Infiniti 14/3/18 13 / 75 LM Esercizio 1 Dire quali di queste funzioni sono iniezioni e quali sono corrispondenze biunivoche, giustificando la risposta. (a) f:N→{numeripari},n→2n (b) f : {esseri umani} → {donne}, figlio → mamma (c) f : quadrati → R, quadrato → area del quadrato (d) f : {quadrati centrati in O} → R+, quadrato → area del quadrato (e) f : {quadrati centrati in O} → R, quadrato → area del quadrato Annalisa Malusa Infiniti 14/3/18 14 / 75 LM Esercizio 1 Dire quali di queste funzioni sono iniezioni e quali sono corrispondenze biunivoche, giustificando la risposta. (a) f:N→{numeripari},n→2n (b) f : {esseri umani} → {donne}, figlio → mamma (c) f : quadrati → R, quadrato → area del quadrato (d) f : {quadrati centrati in O} → R+, quadrato → area del quadrato (e) f : {quadrati centrati in O} → R, quadrato → area del quadrato Soluzione dell’Esercizio 1 (c) niente (d) corrispondenza biunivoca (e) iniezione (a) corrispondenza biunivoca (b) niente Annalisa Malusa Infiniti 14/3/18 14 / 75 questo caso scriveremo |A| = n; LM Cardinalità degli insiemi finiti In conclusione, per contare gli elementi di un insieme finito ci servono l’insieme dei numeri naturali N = {0, 1, 2, 3, 4, 5, 6 . . .}; i sottoinsiemi di N della forma ωn = {1,2,3,...,n}; la nozione di corrispondenza biunivoca. Definizione 3 (Cardinalità degli insiemi finiti) Sia A un insieme e n un numero naturale. Diremo che A ha n elementi (o anche che ha cardinalità uguale ad n) se esiste una corrispondenza biunivoca tra A e l’insieme {1, 2, 3, 4, . . . , n}. In Diremo che A è un insieme finito se esiste n ∈ N tale che |A| = n; Diremo che A è un insieme infinito se non è finito. Annalisa Malusa Infiniti 14/3/18 15 / 75 Proprietà della cardinalità di insiemi finiti LM La cardinalità degli insiemi finiti gode di proprietà che ci sono ben note: (1) due insiemi finiti hanno la stessa cardinalità se e solo se sono in corrispondenza biunivoca tra loro. Annalisa Malusa Infiniti 14/3/18 16 / 75 Proprietà della cardinalità di insiemi finiti LM La cardinalità degli insiemi finiti gode di proprietà che ci sono ben note: (1) due insiemi finiti hanno la stessa cardinalità se e solo se sono in corrispondenza biunivoca tra loro. (2) un sottoinsieme A ⊆ B di un insieme finito è un insieme finito. Annalisa Malusa Infiniti 14/3/18 16 / 75 Proprietà della cardinalità di insiemi finiti LM La cardinalità degli insiemi finiti gode di proprietà che ci sono ben note: (1) due insiemi finiti hanno la stessa cardinalità se e solo se sono in corrispondenza biunivoca tra loro. (2) un sottoinsieme A ⊆ B di un insieme finito è un insieme finito. (3) se A è un sottoinsieme proprio di un insieme finito B, allora |A| < |B|. Riflettiamo un po’ su queste proprietà... Annalisa Malusa Infiniti 14/3/18 16 / 75 LM Due insiemi finiti hanno la stessa cardinalità se e solo se sono in corrispondenza biunivoca tra loro. Ci sta semplicemende dicendo che le corrispondenzee biunivoche A a b c d e f g h B 1 2 3 4 equivalgono a A a b c d e f g h B Annalisa Malusa Infiniti 14/3/18 17 / 75 LM La nozione di corrispondenza biunivoca vale anche tra insiemi infiniti (ad esempio, i punti di una semicirconferenza sono in corrispondenza biunivoca con i punti di una retta). Annalisa Malusa Infiniti 14/3/18 18 / 75 LM La nozione di corrispondenza biunivoca vale anche tra insiemi infiniti (ad esempio, i punti di una semicirconferenza sono in corrispondenza biunivoca con i punti di una retta). Questo ci permette di estendere il concetto di "equinumerosità": Diremo che due insiemi A e B (qualsiasi) hanno la stessa cardinalità (o sono equinumerosi) se esiste una corrispondenza biunivoca tra loro. In questo caso scriveremo |A| = |B|. Ovviamente, se gli insiemi sono infiniti la cardinalità NON è un numero. Annalisa Malusa Infiniti 14/3/18 18 / 75 LM Nota: nel caso di insiemi finiti "<" è l’usuale simbolo per l’ordinamento tra numeri. Nel caso di insiemi infiniti denota una nozione astratta nuova, introdotta per analogia. Sempre "imparando" dagli insiemi finiti e utilizzando le funzioni, possiamo introdurre una nozione di "maggiore numerosità". se A è un sottoinsieme proprio di un insieme finito B, allora |A| < |B|. Inoltre, |A| < |B| se e solo se esiste un’iniezione di A in B B a b c d g h A Diremo che la cardinalità di un insieme A è minore o uguale di quella di un insieme B se esiste una iniezione di A in B. In questo caso scriveremo |A| ≤ |B|. Annalisa Malusa Infiniti 14/3/18 19 / 75 La stravaganza dell’infinito naturali N. LM Abbiamo ora a disposizione gli strumenti per confrontare la cardinalità di insiemi qualsiasi. Prima di procedere oltre, entriamo nello spirito giusto per studiare gli insiemi infiniti con una storia stravagante: l’albergo di Hilbert (immagini tratte da "A. Catalioto, Seminario TFA 2015") L’insieme infinito protagonista di questa storia è l’insieme dei numeri Annalisa Malusa Infiniti 14/3/18 20 / 75 LM Annalisa Malusa Infiniti 14/3/18 21 / 75 IonilTraLnquillocercava M una camera.... Pensò di trovarla all’Hotel Infinito, noto per avere infinite stanze. Ion non ebbe fortuna perché l’hotel ospitava i delegati del congresso di zoologia cosmica. Siccome gli zoologi cosmici venivano da alassie, e di galassie ne esiste un numero infinito, tutte le stanze erano occupate. tutte le g Annalisa Malusa Infiniti 14/3/18 22 / 75 LM ...Soluzione del problema... Il direttore dec ide di spostare lo zoologo della stanza 1 nella 2, quello della 2 nella 3 e così via... così può mettere Ion nella stanza 1! In generale, viene spostato lo zoologo della stanza «n» nella stanza «n+1» Annalisa Malusa Infiniti 14/3/18 23 / 75 LM Il problema si complicò perché arrivò un rappresentante dei filatelici per ogni galassia per partecipare al congresso interstellare dei filatelici Annalisa Malusa Infiniti 14/3/18 24 / 75 LM Il direttore, come soluzione al problema, decise di spostare l’ospite della 1 nella 2, quello della 2 nella 4, quello della 3 nella 6 e così via... In generale mettere l’ospite della stanza «n» nella stanza «2n» Così, gli zoologi occuparono l’insieme delle stanze dei numeri pari e i filatelici occuparono l’insieme delle stanze dei numeri dispari, visto che il filatelico n-esimo nella coda ottenne il numero di stanza «2n-1» Annalisa Malusa Infiniti 14/3/18 25 / 75 LM rimettere tutto in ordine e a chiudere tutti gli hotel, eccetto l’Hotel Cosmos I costruttori dell’Hotel Cosmos avevano smantellato tantissime galassie per costruire infiniti hotel con infinite stanze. Furono costretti, però, a Annalisa Malusa Infiniti 14/3/18 26 / 75 LM Quindi venne chiesto al direttore di mettere le infinite persone di infiniti hotel nel suo hotel, già pieno. COME FARE ? Annalisa Malusa Infiniti 14/3/18 27 / 75 LM Ion propose di usare solo le progressioni dei numeri primi poiché se si prendono due numeri primi, nessuna delle potenze intere positive di uno può equivalere a quelle dell’altro. Annalisa Malusa Infiniti 14/3/18 28 / 75 LM In questo modo nessuna stanza avrebbe avuto due occupanti! Annalisa Malusa Infiniti 14/3/18 29 / 75 Esercizio 2 LM Vediamo cosa ci ha insegnato questa storia. Mostrare che N ha la stessa cardinalità dei suoi seguenti sottoinsiemi propri (1) A={n∈N, n≥7} (2) A={2n+1, ninN} Annalisa Malusa Infiniti 14/3/18 30 / 75 VediamLo cosa ci ha insegnato quMesta storia. Esercizio 2 Mostrare che N ha la stessa cardinalità dei suoi seguenti sottoinsiemi propri (1) A={n∈N, n≥7} (2) A={2n+1, ninN} Soluzione dell’Esercizio 2 01234 n 7 8 9 1011 7+n 01234 n 1 3 5 7 9 2n+1 L’ultimo partecipanti, che sostanzialmente ci racconta che l’insieme prodotto N × N ha la stessa cardinalità di N) è più complicato e ci torneremo più tardi. I risultati dell’Esercizio 2 sono una vera e propria rivoluzione del pensiero. caso descritto nella sto ria(quello degli infiniti convegni con infiniti Annalisa Malusa Infiniti 14/3/18 30 / 75 Povero Euclide! LM Abbiamo imparato che se togliamo all’insieme N i primi n0 termini (pensate n0 grande quanto volete!), quello che resta ha esattamente la stessa cardinalità di tutto l’insieme. Crolla così il principio fissato da Euclide: "il tutto è maggiore di una sua qualsiasi parte" (Elementi,300 a.C.) Ricordiamo che Euclide è probabilmente il più grande matematico dell’antichità e i suoi Elementi (opera in 13 libri) sono stati la principale opera di riferimento per la geometria fino al XIX secolo. Quello citato è uno degli 8 enunciati di "nozioni comuni" contenuti nel Libro I, quello in cui vengono fissati tutti i fondamenti per la trattazione di tutta la geometria nota all’epoca. Annalisa Malusa Infiniti 14/3/18 31 / 75 Povero Galileo! D’altra Lparte, di questo problemMa si era accorto anche Galileo, senza trovarne soluzione: "queste son di quelle difficoltà che derivano dal discorrere che noi facciamo col nostro intelletto finito intorno agli infiniti, dandogli quegli attributi che noi diamo alle cose finite e terminate; il che penso che sia inconveniente, perché stimo che questi attributi di maggioranza, minorità ed ugualità non convenghino agli infiniti, dei quali non si può dire uno essere maggiore o minore o uguale all’altro" (Nuove Scienze, 1638) Parafrasando Galileo, possiamo dire che la teoria della cardinalità di Cantor è esatta il giusto attributo di maggioranza, minorità ed ugualità che convenga agli infiniti mente Annalisa Malusa Infiniti 14/3/18 32 / 75 LM Riepilogo e domande Finora sono stati solo definiti solo dei metodi di confronto tra cardinalità infinite. Diremo che due insiemi A e B (qualsiasi) hanno la stessa cardinalità (o sono equinumerosi) se esiste una corrispondenza biunivoca tra loro. In questo caso scriveremo |A| = |B|. Diremo che la cardinalità di un insieme A è minore o uguale di quella di un insieme B se esiste una iniezione di A in B. In questo caso scriveremo |A| ≤ |B|. Annalisa Malusa Infiniti 14/3/18 33 / 75 LM Riepilogo e domande Finora sono stati solo definiti solo dei metodi di confronto tra cardinalità infinite. Diremo che due insiemi A e B (qualsiasi) hanno la stessa cardinalità (o sono equinumerosi) se esiste una corrispondenza biunivoca tra loro. In questo caso scriveremo |A| = |B|. Diremo che la cardinalità di un insieme A è minore o uguale di quella di un insieme B se esiste una iniezione di A in B. In questo caso scriveremo |A| ≤ |B|. Ora è arrivato il momento di porsi qualche domanda: ci sono insiemi infiniti con cardinalità diverse? Annalisa Malusa Infiniti 14/3/18 33 / 75 LM Riepilogo e domande Finora sono stati solo definiti solo dei metodi di confronto tra cardinalità infinite. Diremo che due insiemi A e B (qualsiasi) hanno la stessa cardinalità (o sono equinumerosi) se esiste una corrispondenza biunivoca tra loro. In questo caso scriveremo |A| = |B|. Diremo che la cardinalità di un insieme A è minore o uguale di quella di un insieme B se esiste una iniezione di A in B. In questo caso scriveremo |A| ≤ |B|. Ora è arrivato il momento di porsi qualche domanda: ci sono insiemi infiniti con cardinalità diverse? c’è una "cardinalità infinita" più piccola di tutte le altre? Annalisa Malusa Infiniti 14/3/18 33 / 75 LM Riepilogo e domande Finora sono stati solo definiti solo dei metodi di confronto tra cardinalità infinite. Diremo che due insiemi A e B (qualsiasi) hanno la stessa cardinalità (o sono equinumerosi) se esiste una corrispondenza biunivoca tra loro. In questo caso scriveremo |A| = |B|. Diremo che la cardinalità di un insieme A è minore o uguale di quella di un insieme B se esiste una iniezione di A in B. In questo caso scriveremo |A| ≤ |B|. Ora è arrivato il momento di porsi qualche domanda: ci sono insiemi infiniti con cardinalità diverse? c’è una "cardinalità infinita" più piccola di tutte le altre? c’è una "cardinalità infinita" più grande di tutte le altre? Annalisa Malusa Infiniti 14/3/18 33 / 75 LM Riepilogo e domande Finora sono stati solo definiti solo dei metodi di confronto tra cardinalità infinite. Diremo che due insiemi A e B (qualsiasi) hanno la stessa cardinalità (o sono equinumerosi) se esiste una corrispondenza biunivoca tra loro. In questo caso scriveremo |A| = |B|. Diremo che la cardinalità di un insieme A è minore o uguale di quella di un insieme B se esiste una iniezione di A in B. In questo caso scriveremo |A| ≤ |B|. Ora è arrivato il momento di porsi qualche domanda: ci sono insiemi infiniti con cardinalità diverse? c’è una "cardinalità infinita" più piccola di tutte le altre? c’è una "cardinalità infinita" più grande di tutte le altre? Annalisa Malusa Infiniti 14/3/18 33 / 75 LM Ripartiamo dal caso dell’albergo di Hilbert che non abbiamo ancora discusso. La storia ci racconta che la funzione (m,n) → 2m3n mette in corrispondenza biunivoca il prodotto cartesiano N × N con un sottoinsieme proprio di N e sembra complicato esibire una corrispondenza biunivoca tra questo e N. Facciamoci aiutare dalla teoria... Annalisa Malusa Infiniti 14/3/18 34 / 75 Se A ⊆ B, allora |A| ≤ |B|. LM Ripartiamo dal caso dell’albergo di Hilbert che non abbiamo ancora discusso. La storia ci racconta che la funzione (m,n) → 2m3n mette in corrispondenza biunivoca il prodotto cartesiano N × N con un sottoinsieme proprio di N e sembra complicato esibire una corrispondenza biunivoca tra questo e N. Facciamoci aiutare dalla teoria... Esercizio 3 Annalisa Malusa Infiniti 14/3/18 34 / 75 LM La funzione f : A → B, a → a è un’iniezione di A in B. Annalisa Malusa Infiniti 14/3/18 Ripartiamo dal caso dell’albergo di Hilbert che non abbiamo ancora discusso. La storia ci racconta che la funzione (m,n) → 2m3n mette in corrispondenza biunivoca il prodotto cartesiano N × N con un sottoinsieme proprio di N e sembra complicato esibire una corrispondenza biunivoca tra questo e N. Facciamoci aiutare dalla teoria... Esercizio 3 Se A ⊆ B, allora |A| ≤ |B|. Soluzione dell’Esercizio 3 34 / 75 Teorema LM Sia A un insieme infinito. Allora |N| ≤ |A|. Annalisa Malusa Infiniti 14/3/18 35 / 75 LM Teorema Sia A un insieme infinito. Allora |N| ≤ |A|. Dim: Dobbiamo costruire un’iniezione di N in A, ossia associare ad ogni n ∈ N un unico elemento an di A. Lo faremo in maniera ricorsiva. Annalisa Malusa Infiniti 14/3/18 35 / 75 LM Teorema Sia A un insieme infinito. Allora |N| ≤ |A|. Dim: Dobbiamo costruire un’iniezione di N in A, ossia associare ad ogni n ∈ N un unico elemento an di A. Lo faremo in maniera ricorsiva. Passo base: associamo a n = 0 un qualsiasi elemento a0 ∈ A. Siccome A è un insieme infinito, A ̸= {a0}, quindi siamo in grado di associarean=1unelementoa1 ∈A,a1 ̸=a0. Annalisa Malusa Infiniti 14/3/18 35 / 75 Teorema LM Sia A un insieme infinito. Allora |N| ≤ |A|. Dim: Dobbiamo costruire un’iniezione di N in A, ossia associare ad ogni n ∈ N un unico elemento an di A. Lo faremo in maniera ricorsiva. Passo base: associamo a n = 0 un qualsiasi elemento a0 ∈ A. Siccome A è un insieme infinito, A ̸= {a0}, quindi siamo in grado di associarean=1unelementoa1 ∈A,a1 ̸=a0. Meccanismo ricorsivo: supponiamo di aver associato ai numeri 0, 1, . . . , n gli elementi distinti a0, a1, . . . , an di A. Siccome A è un insieme infinito, A ̸= {a0,a1,...,an}, quindi siamo in grado di associare al numero n+1 un elemento an+1 ∈ A distinto da tutti i precedenti. Conseguenza immediata del Teorema e dell’Esercizio 3: Ogni sottoinsieme infinito di N ha la stessa cardinalità di N. Annalisa Malusa Infiniti 14/3/18 35 / 75 Teorema LM Sia A un insieme infinito. Allora |N| ≤ |A|. Dim: Dobbiamo costruire un’iniezione di N in A, ossia associare ad ogni n ∈ N un unico elemento an di A. Lo faremo in maniera ricorsiva. Passo base: associamo a n = 0 un qualsiasi elemento a0 ∈ A. Siccome A è un insieme infinito, A ̸= {a0}, quindi siamo in grado di associarean=1unelementoa1 ∈A,a1 ̸=a0. Meccanismo ricorsivo: supponiamo di aver associato ai numeri 0, 1, . . . , n gli elementi distinti a0, a1, . . . , an di A. Siccome A è un insieme infinito, A ̸= {a0,a1,...,an}, quindi siamo in grado di associare al numero n+1 un elemento an+1 ∈ A distinto da tutti i precedenti. Conseguenza immediata del Teorema e dell’Esercizio 3: Ogni sottoinsieme infinito di N ha la stessa cardinalità di N. In particolare, {p ∈ N della forma p = 2m3n, n, m ∈ N}, ha la stessa cardinalità di N. Quindi N × N ha la stessa cardinalità di N. Annalisa Malusa Infiniti 14/3/18 35 / 75 LM Cardinalità numerabile Quindi la cardinalità dell’insieme numerico N è "la più piccola cardinalità infinita". Per questo si è meritata un "nome proprio" e un simbolo speciale א0 = |N| prende il nome di CARDINALITA’ NUMERABILE. Il simbolo "א” è l’aleph, prima lettera dell’alfabeto ebraico. Diremo che un insieme A è numerabile se |A| = א0, cioè se A può essere messo in corrispondenza biunivoca con N. Annalisa Malusa Infiniti 14/3/18 36 / 75 LM N⊂Z⊂Q⊂R Ricordiamo brevemente cosa sono per poi confrontare le loro cardinalità. Esistono insiemi infiniti con cardinalità diversa (maggiore) da quella numerabile? Per rispondere a questa domanda usiamo gli insiemi numerici come prototipo. N = {0,1,2,3,4,5,6...} Z = {...,,−3,−2,−1,0,1,2,3,...} numeri NATURALI numeri INTERI p Q = q , p intero, q ̸= 0 naturale numeri RAZIONALI R numeri REALI Valgono le inclusioni strette: Annalisa Malusa Infiniti 14/3/18 37 / 75 LM I numeri interi Z = {...,,−3,−2,−1,0,1,2,3,...} I numeri interi sono un’estensione dei numeri naturali, nata dall’esigenza di poter fare liberamente la sottrazione. Si ottengono considerando tutti i numeri naturali e tutti i loro opposti. Possiamo rappresentare l’insieme dei numeri interi tramite punti di una retta ordinata. Basta fissare un punto che determina lo zero fissare un’unità di misura disegnare tutti punti equidistanti dal successivo. -6-5-4-3-2-10 1 2 3 4 5 6 In un certo senso, i numeri interi sono "il doppio" dei numeri naturali, quindi è ragionevole pensare che siano un insieme numerabile. Annalisa Malusa Infiniti 14/3/18 38 / 75 Corrispondenza biunivoca tra N e Z LM an = n 2 sen=0oppuresenèpari −n+1 senèdispari 2 Annalisa Malusa Infiniti 14/3/18 39 / 75 Corrispondenza biunivoca tra N e Z LM -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 39 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 40 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 41 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 42 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 43 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 44 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 45 / 75 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 -4 −3 −2 −1 0 1 2 3 4 Annalisa Malusa Infiniti 14/3/18 46 / 75 -4 −3 −2 −1 0 1 2 3 4 LM n 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari 012345678 Abbiamo così ottenuto che Z è numerabile. Annalisa Malusa Infiniti 14/3/18 47 / 75 LM I numeri razionali Q = qp , p intero, q ̸= 0 naturale I numeri razionali sono un’estensione dei numeri interi, nata dall’esigenza di poter fare liberamente la divisione. Si ottengono considerando tutte le possibili frazioni con a numeratore un numero intero (che quindi determina il segno della frazione); a denominatore un naturale non nullo. Cerchiamo di farci un’idea di "quanti siano" i numeri razionali. Annalisa Malusa Infiniti 14/3/18 48 / 75 (i numeri interi sono discreti). LM I numeri razionali Q = qp , p intero, q ̸= 0 naturale I numeri razionali sono un’estensione dei numeri interi, nata dall’esigenza di poter fare liberamente la divisione. Si ottengono considerando tutte le possibili frazioni con a numeratore un numero intero (che quindi determina il segno della frazione); a denominatore un naturale non nullo. Cerchiamo di farci un’idea di "quanti siano" i numeri razionali. Tra un numero intero e il suo successivo non c’è nessun altro numero intero 01 Annalisa Malusa Infiniti 14/3/18 48 / 75 Densità dei numeri razionali Invece tLra due numeri razionali dMistinti c’è sicuramente un altro numero razionale (ad esempio la loro media). 0 12 1 In realtà ce ne sono infiniti (tutte le possibili medie delle medie). 01131 424 113 084828481 Si intuisce che i numeri razionali coprono abbastanza bene la retta. 1537 Annalisa Malusa Infiniti 14/3/18 49 / 75 LM Da quanto abbiamo detto sembrerebbe che i numeri razionali siano molti di più dei numeri interi (sono densi sulla retta reale), ma anche in questo caso gli insiemi infiniti tornano a stupirci: Annalisa Malusa Infiniti 14/3/18 50 / 75 LM Da quanto abbiamo detto sembrerebbe che i numeri razionali siano molti di più dei numeri interi (sono densi sulla retta reale), ma anche in questo caso gli insiemi infiniti tornano a stupirci: Q ha cardinalità numerabile. Per dimostrarlo, basta esibire una corrispondenza biunivoca tra Z e Q, che possiamo pensare come un modo di "etichettare" con numeri interi gli elementi di Q. Per fare questo utilizzeremo il cosiddetto (primo) metodo diagonale di Cantor. Annalisa Malusa Infiniti 14/3/18 50 / 75 Esercizio: trovare un percorso che passa una sola volta per ogni stellina e numerare le stelline man mano che si incontrano (nota: verso il basso e verso destra ci sono infinite stelline!) ⋆⋆⋆⋆⋆⋆⋆··· LM ⋆⋆⋆⋆⋆⋆⋆··· ⋆⋆⋆⋆⋆⋆⋆··· ⋆⋆⋆⋆⋆⋆⋆··· ⋆⋆⋆⋆⋆⋆⋆··· . . . . . . . Annalisa Malusa Infiniti 14/3/18 51 / 75 Soluzione 11 20 ⋆ ⋆ ⋆ ⋆ ⋆ LM . . . . . . . Annalisa Malusa Infiniti 14/3/18 1 → 2 6 → 7 15 → 16 ⋆ ··· ↙↗↙↗↙ 3 5 8 14 17 ⋆ ⋆ ↓↗↙↗↙ 4 9 13 18 ⋆ ⋆ ⋆ ··· ··· ··· ··· ↙↗↙ 10 12 19 ⋆ ⋆ ⋆ ⋆ ↓↗↙ 52 / 75 Primo metodo diagonale di Cantor: costruire la tabella... LM 1234567 1111111 ··· ··· ··· ··· ··· 1234567 2222222 1234567 3333333 1234567 4444444 1234567 5555555 . . . . . . . Annalisa Malusa Infiniti 14/3/18 53 / 75 ... e percorrerla con il metodo che abbiamo determinato LM 1→23→4567··· 1111111 ↙↗↙ 1234567 ··· ··· ··· ··· 2222222 ↓↗↙ 1234567 3333333 ↙ 1234567 4444444 1234567 5555555 . . . . . . . Annalisa Malusa Infiniti 14/3/18 54 / 75 LM Abbiamo così mostrato come mettere in corrispondenza biunivoca tutti i numeri razionali positivi con i numeri naturali. In definitiva, abbiamo dimostrato che i numeri razionali positivi hanno cardinalità numerabile. Con lo stesso metodo si dimostra che tutti i numeri razionali negativi hanno cardinalità numerabile. Annalisa Malusa Infiniti 14/3/18 55 / 75 LM Abbiamo così mostrato come mettere in corrispondenza biunivoca tutti i numeri razionali positivi con i numeri naturali. In definitiva, abbiamo dimostrato che i numeri razionali positivi hanno cardinalità numerabile. Con lo stesso metodo si dimostra che tutti i numeri razionali negativi hanno cardinalità numerabile. Resta da dimostrare che se A e B sono due insiemi numerabili, allora A ∪ B è numerabile Annalisa Malusa Infiniti 14/3/18 55 / 75 Questo produce una corrispondenza biunivoca tra A ∪ B e N. LM Abbiamo così mostrato come mettere in corrispondenza biunivoca tutti i numeri razionali positivi con i numeri naturali. In definitiva, abbiamo dimostrato che i numeri razionali positivi hanno cardinalità numerabile. Con lo stesso metodo si dimostra che tutti i numeri razionali negativi hanno cardinalità numerabile. Resta da dimostrare che se A e B sono due insiemi numerabili, allora A ∪ B è numerabile Dimostrazione. visto che A e B sono due insiemi numerabili, allora esiste una corrispondenza biunivoca tra A e l’insieme dei numeri pari e una corrispondenza biunivoca tra B e l’insieme dei numeri dispari. A ←→ {pari} B ←→ {dispari} =⇒ A ∪ B ←→ N. Annalisa Malusa Infiniti 14/3/18 55 / 75 Voglia di misurare... LM 0? LA DIAGONALE DEL QUADRATO DI LATO UNITARIO NON HA LUNGHEZZA RAZIONALE! Abbiamo visto che i numeri razionali coprono abbastanza bene la retta. I Pitagorici pensavano che tutte le lunghezze fossero razionali (ossia che i punti corrispondenti ai razionali coprissero tutta la retta) e invece scoprirono presto che manca qualcosa... 1 ? Annalisa Malusa Infiniti 14/3/18 56 / 75 LM Quali numeri mancano? Per capire come estendere i numeri razionali in modo da ottenere tutte le possibili lunghezze, ricordiamo che ogni numero razionale si può scrivere come allineamento decimale finito o periodico (con periodo diverso da 9). Facciamo l’estensione di Q più ragionevole che ci viene in mente R = {allineamenti decimali con un numero arbitrario di cifre} ed è quella giusta, nel senso che i numeri reali sono in corrispondenza biunivoca con i punti della retta (difficile da dimostrare). Annalisa Malusa Infiniti 14/3/18 57 / 75 LM Quali numeri mancano? Per capire come estendere i numeri razionali in modo da ottenere tutte le possibili lunghezze, ricordiamo che ogni numero razionale si può scrivere come allineamento decimale finito o periodico (con periodo diverso da 9). Facciamo l’estensione di Q più ragionevole che ci viene in mente R = {allineamenti decimali con un numero arbitrario di cifre} ed è quella giusta, nel senso che i numeri reali sono in corrispondenza biunivoca con i punti della retta (difficile da dimostrare). −π −2−√2−101 √22 π 22 Quindi, geometricamente, possiamo pensare di aver "tappato i buchi" sulla retta lasciati dai punti corrispondenti ai numeri razionali (abbiamo aggiunto tutti i numeri irrazionali). Non sembra che siano stati aggiunti tanti elementi... invece... Annalisa Malusa Infiniti 14/3/18 57 / 75 LM l’insieme dei numeri reali R NON ha cardinalità numerabile! Annalisa Malusa Infiniti 14/3/18 58 / 75 LM R NON ha cardinalità numerabile!! Dimostreremo questa sorprendente proprietà in tre passi: l’intervallo (0, 1) non è numerabile; due intervalli distinti (a, b) e (c, d) hanno la stessa cardinalità; ogni intervallo (a, b) ha la stessa cardinalità di R (Ricordiamoci che R è in corrispondenza biunivoca con i punti della retta, quindi i due insiemi hanno la stessa cardinalità) Annalisa Malusa Infiniti 14/3/18 59 / 75 Secondo metodo diagonale di Cantor LM Dimostriamo, per assurdo, che l’intervallo (0, 1) non ha cardinalità numerabile. Ipotesi per assurdo: supponiamo che (0, 1) abbia una quantità numerabile di elementi ed enumeriamoli nel modo seguente: . Il numero reale x = 0,β1 β2 β3 ... con r1 = 0,a11 a12 a13 a14 ... r2 = 0,a21 a22 a23 a24 ... r3 = 0,a31 a32 a33 a34 ... βj ̸=ajj, βj ̸=0, βj ̸=9, ∀j appartiene all’intervallo (0, 1) (è positivo e ha parte intera uguale a zero), ma è diverso da tutti i numeri reali rj , in contraddizione col fatto di aver enumerato tutti i valori nell’intervallo. Annalisa Malusa Infiniti 14/3/18 60 / 75 LM Quindi sicuramente la cardinalità dell’intervallo (0, 1) è diversa da quella del numerabile. Passiamo a dimostrare che tutti gli intervalli della retta reale hanno la stessa cardinalità, dando solo un’idea grafica della dimostrazione. Esercizio 4 Determinare (geometricamente) una corrispondenza biunivoca tra due intervalli aperti (a, b) e (c, d) della retta reale. Suggerimento: allineare i due segmenti e considerare un punto P come in figura: a c b d P Annalisa Malusa Infiniti 14/3/18 61 / 75 LM Soluzione dell’Esercizio 4 P a c b d si proietta ogni punto di (a,b) in un unico punto di (c,d) dal punto P esterno ai due segmenti. Ovviamente questa operazione geometrica si può scrivere in formule utilizzando la geometria analitica e si trova la corrispondenza biunivoca cercata. Annalisa Malusa Infiniti 14/3/18 62 / 75 LM Infine, per mettere in corrispondenza biunivoca un intervallo limitato, diciamo (−1, 1), con tutta la retta reale, serve una sorta di “meccanismo di amplificazione” (proiezione stereografica). Diamo un’idea geometrica della corrispondenza biunivoca: disegnamo la retta reale; dalla retta reale “stacchiamo l’intervallo (−1, 1)” e disegnamone una copia; −1 1 R Annalisa Malusa Infiniti 14/3/18 63 / 75 LM Proiezione stereografica disegnamo la semicirconferenza di raggio 1 tangente alla retta reale in 0; indichiamo con P il centro di tale circonferenza; P −1 1 R Annalisa Malusa Infiniti 14/3/18 64 / 75 −1 1 LM Annalisa Malusa Infiniti 14/3/18 Proiezione stereografica fissiamo un qualsiasi punto dell’intervallo (−1, 1); P R 65 / 75 LM Proiezione stereografica fissiamo un qualsiasi punto dell’intervallo (−1, 1); proiettiamolo verticalmente sulla circonferenza; P −1 1 R Annalisa Malusa Infiniti 14/3/18 66 / 75 LM −1 1 Proiezione stereografica tracciamo la retta per P e il punto della circonferenza; associamo al punto di partenza in (−1, 1) i punto intersezione tra la retta considerata e la retta reale; P R Annalisa Malusa Infiniti 14/3/18 67 / 75 Se facciLamo questa operazione per ogni punto dell’intervallo (−1, 1) costruiamo una corrispondenza biunivoca tra questo intervallo e tutta la retta reale. −1 1 Il meccanismo di amplificazione funziona perchè proiettiamo tramite una semicirconferenza che ha tangente verticale agli estremi: i punti molto vicini a −1 o a 1 si proiettano sempre più lontano. P Annalisa Malusa Infiniti 14/3/18 68 / 75 M LM Cardinalità del continuo La cardinalità della retta reale prende il nome di cardinalità del continuo. Possiamo dividere i numeri reali in tre gruppi: razionali irrazionali algebrici: le soluzioni di equazioni algebriche a coefficienti interi (ad es. tutte le radici quadrate, cubiche, ecc...) irrazionali trascendenti: tutti gli altri irrazionali (ad es. π) Conosciamo esplicitamente tantissimi irrazionali algebrici e abbastanza pochi trascendenti. Abbiamo visto che i numeri reali sono molti di più dei numeri razionali (ma ricordiamoci anche che i numeri razionali sono densi in R). Si può essere più precisi sulle informazioni riguardanti la cardinalità dei numeri irrazionali. Precisamente, si può dimostrare che i numeri irrazionali algebrici sono una quantità numerabile; quindi i numeri irrazionali trascendenti sono veramente tanti! Annalisa Malusa Infiniti 14/3/18 69 / 75 QuantLe e quali altre cardiMnalità ci sono? Studiando gli insiemi numerici abbiamo trovato due cardinalità distinte, quella del numerabile e quella del continuo. E’ del tutto naturale porsi due domande: ci sono cardinalità intermedie tra queste due? ci sono cardinalità superiori a quella del continuo? La prima apre una questione particolarmente affascinante (o frustrante, dipende dai punti di vista) che prende il nome di Ipotesi del continuo nda ha una risposta stup ci sono infinite cardinalità (infinite) distinte! La seco efacente: Annalisa Malusa Infiniti 14/3/18 70 / 75 LM CH “Continuum Hypothesis” non c’è nessuna cardinalità strettamente compresa tra quella dei naturali e quella dei reali. Cantor era fermamente convinto del fatto che CH fosse vera. Annalisa Malusa Infiniti 14/3/18 71 / 75 LM CH “Continuum Hypothesis” non c’è nessuna cardinalità strettamente compresa tra quella dei naturali e quella dei reali. Cantor era fermamente convinto del fatto che CH fosse vera. nel 1940 Kurt Gödel dimostrò che nell’ambito della usuale teoria degli insiemi non si poteva dimostrare che CH fosse falsa. Annalisa Malusa Infiniti 14/3/18 71 / 75 LM CH “Continuum Hypothesis” non c’è nessuna cardinalità strettamente compresa tra quella dei naturali e quella dei reali. Cantor era fermamente convinto del fatto che CH fosse vera. nel 1940 Kurt Gödel dimostrò che nell’ambito della usuale teoria degli insiemi non si poteva dimostrare che CH fosse falsa. nel 1963 Paul Cohen dimostrò che nell’ambito della usuale teoria degli insiemi non si può nemmeno dimostrare che CH sia vera. Annalisa Malusa Infiniti 14/3/18 71 / 75 LM Per fortuna i modelli della matematica applicata non dipendono dalla validità o meno di CH, quindi la sua indecidibiltà non incide sui risultati che vengono utilizzati nella vita reale (fisica, ingegneria, informatica...) CH “Continuum Hypothesis” non c’è nessuna cardinalità strettamente compresa tra quella dei naturali e quella dei reali. Cantor era fermamente convinto del fatto che CH fosse vera. nel 1940 Kurt Gödel dimostrò che nell’ambito della usuale teoria degli insiemi non si poteva dimostrare che CH fosse falsa. nel 1963 Paul Cohen dimostrò che nell’ambito della usuale teoria degli insiemi non si può nemmeno dimostrare che CH sia vera. Quindi, la CH è indecidibile nell’ambito della usuale teoria degli insiemi, nel senso che è altrettanto coerente prenderla come vera che prenderla come falsa. Annalisa Malusa Infiniti 14/3/18 71 / 75 ∅ {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c} LM L’insieme delle parti Per rispondere alla seconda domanda introduciamo una nuova nozione. Insieme delle parti Dato un insieme X, il suo insieme delle parti P(X) è dato da P(X) = {A sottoinsieme di X}. Esempio. Se X = {a,b,c}, allora P(X) è l’insieme formato dai seguenti 8 insiemi: Si può dimostrare che se |X| = n allora |P(X)| = 2n > |X|. Annalisa Malusa Infiniti 14/3/18 72 / 75 LM Esistono infinite cardinalità infinite Teorema di Cantor Sia X un insieme. Allora |P(X)| > |X|. Come conseguenza del Teorema di Cantor, otteniamo che esiste una sequenza di cardinalità infinite, ciascuna strettamente maggiore della precedente. Partendo da |N|, che sappiamo essere la cardinalità infinita minima, basta iterare il passaggio all’insieme delle parti: |N| < |P(N)| < |P(P(N))| < |P(P(P(N)))| < |P(P(P(P(N)))))| < · · · Annalisa Malusa Infiniti 14/3/18 73 / 75 LM Dimostriamo il teorema di Cantor. L’applicazione ”x → {x}” è un’iniezione di X in P(X). Quindi |P(X)| ≥ |X|. Dimostriamo ora che non esiste un’applicazione biunivoca tra X e P(X). Supponiamo, per assurdo, che esista e indichiamola con ”x ↔ A(x)”. Consideriamo l’insieme C ∈ P(X) C = {x ∈ X tali che x ̸∈ A(x)}. L’ipotesi per assurdo garantisce che esiste un’unico x0 ∈ X tale che C = A(x0). Si ha che se x0 ∈ C = A(x0), allora, per come sono definiti gli elementi di C, deve essere x0 ̸∈ C = A(x0) se x0 ̸∈ C = A(x0), allora, per come sono definiti gli elementi di C, deve essere x0 ∈ C = A(x0) Le contraddizioni trovate dipendono dal fatto che abbiamo supposto che ”x ↔ A(x)” sia biunivoca. Se ne conclude che non può esistere nessuna corrispondenza biunivoca tra X e l’insieme delle sue parti. Annalisa Malusa Infiniti 14/3/18 74 / 75
Subscribe to:
Post Comments (Atom)
Posts
No comments:
Post a Comment