Posts
Grice e Cellucci: l’implicatura
conversazionale del paradiso – aus dem Paradies, das Cantor uns geschaffen, soll uns niemand
vertreiben können -- filosofia italiana – Luigi Speranza (Santa
Maria Caputa Vetere). Filosofo. Grice: “I love Cellucci; for one, he wrote on
Cantor’s paradise, which is an extremely interesting tract and figure! There’s
earthly paradise and heavenly paradise and Cellucci knows it!” – Grice:
“Cellucci, like me, also philosophised on ‘logic,’ in my case because of
Strawson; in his, because of me!” Si laurea a Milano. Insegna a Siena, Calabria,
e Roma. Si occupa soprattutto di logica e teoria della dimostrazione, filosofia
della matematica, filosofia della logica, ed epistemologia. Altre opere: “Breve
storia della logica italiana: dall'Umanesimo al primo Novecento” (Lulu,
Morrisville); “Perché ancora la filosofia” (Laterza, Roma) – perche no? “La
filosofia italiana della matematica del Novecento” (Laterza, Roma); “Filosofia
e matematica” (Laterza, Roma); “Le ragioni della logica, Laterza, Roma); “Teoria
della dimostrazione” (Boringhieri, Torino); “Alcuni momenti salienti della
storia del metodo” La Cultura; “I limiti dello scetticismo, Syzetesis); “La
logica della scoperta, Scienza & Società, Creatività; Conoscenza
scientifica e senso comune. In La guerra dei mondi. Scienza e senso comune, ed.
A. Lavazza & M. Marraffa. Codice Edizioni, Torino); Razionalità scientifica
e plausibilità. In I modi della razionalità, eds. M. Dell'Utri & A. Rainone.
Mimesis, Milano); Filosofia della matematica, Paradigmi, Il paradiso di Cantor, Bibliopolis, Napoli La
filosofia della matematica, Laterza, Roma); Breve storia della logica: Dall'Umanesimo al pr imo
Novecento [Lulu Press, Morrisville; Perché ancora la filosofia Laterza,
Rome, La filosofia della matematica del Novecento, Laterza, Rome, Filosofia e
matematica, Laterza, Rome, Le ragioni della logica, Laterza, Roma; Teoria della
dimostrazione, Boringhieri, Turin, “La rinascita della logica in Italia”, in “Momenti
di filosofia italiana, ed. F.Pezzelli & F. Verde. Efesto, Rome – quando e
morta? -- Alcuni momenti salienti della storia del metodo, La Cultura. La
logica della scoperta, Scienza e Societa. Creatività. “Aristotele e il ruolo
del nous nella conoscenza scientifica”, In Il Nous di Aristotele,
ed. G.Sillitti, F. Stella & F. Fronterotta. Academia Verlag, Sankt
Augustin; Conoscenza scientifica e senso comune. In La guerra dei mondi.
Scienzae senso comune, ed. A. Lavazza & M. Marraffa. Codice Edizioni,
Torino, Razionalità scientifica e plausibilità, In I modi della
razionalità, ed. M. Dell'Utri & A. Rainone.Mimesis, Milano; “La preistoria
della logica polivalente nell'antichità o la storia antica, Bollettino
della Società Filosofica Italiana. Gli approcci di Turing alla computabilità e
all'intelligenza. In Per ilcentenario di Alan Turing fondatore dell'informatica,
Accademia Nazionale dei Lincei, Scienze e Lettere, Roma; Intervista di Antonio
Gnoli, La Repubblica; Breve storia della logica antica; Ripensare la filosofia.
Un colloquio con (e su) Carlo Cellucci; La spiegazione in matematica. Periodicodi
Matematiche (For Grice, unlike Kantotle, mathematics “7 + 5 = 12” has
zero-explanatory value; Dialogando con Platone, in Il Platonismo e le scienze,
Carocci, Roma); Logica dell'argomentazione e logica della scoperta”, in Logica
ediritto: argomentazione e scoperta, Lateran University Press, Vaticano); Ragione,
mente e conoscenza, in Fenomenologia della scoperta, Bruno Mondadori, Milano); Filosofia
della matematica top-down e bottom-up. Paradigmi. L’ideale della purezza dei metodi,
I fondamenti della matematica e connessi sviluppi interdisciplinari Pisa-Tirrenia, Mathesis, Rome); Per
l'insegnamento della logica. Nuova Secondaria. La logica della macchina,
in Le macchine per pensare,La Nuova Italia, Firenze); Logica e filosofia della
matematica nella seconda metà del secolo, in La filosofia della scienza in
Italia nel ‘900, Angeli, Milano; Bolzano, Del metodo matematico, Boringhieri,
Torino; Il ruolo delle definizioni esplicite in matematica; in C. Mangione
(Ed.), Scienza e filosofia,Garzanti, Milano; Storia della logica, Laterza,
Bari, Il fondazionalismo: una filosofia regressiva, Teoria. La complessità
delle dimostrazioni nella logica dei predicati del primo ordine, Logica
Matematica, Siena. Il ruolo del principio di non contraddizione di Parmenide nelle
teorie scientifiche. Verifiche. “È adeguata la teoria dell’ adaequatio?” Scienza
e storia, Il Laboratorio, Napoli. Il paradiso di Cantor. Il dibattito sui
fondamenti della teoria degli insiemi. Bibliopolis, Napoli. Proprietà di
coerenza e completezza in L-omega1-omega. Le Matematiche. Proprietà di
uniformità e 1-coerenza dell’aritmetica del primo ordine, Le Matematiche. La
logica come teoria della dimostrazione, in Introduzione alla logica, Editori Riuniti,
Roma. La qualità nella dimostrazione matematica, in La qualità, Bologna (il
Mulino). Teoremi di normalizzazione per alcuni sistemi funzionali, Le Matematiche.
Logica matematica. EditoriRiuniti, Roma. Il problema del significato. Il
Veltro. Una dimostrazione del teorema di uniformità. Le Matematiche. Un
connettivo per la logica intuizionista. Le Matematiche. I limiti del programma
hilbertiano, Società Filosofica Italiana, Roma. L’evoluzione della ricerca sui
fondamenti, Terzo programma. Operazioni di Brouwer e realizzabilità
formalizzata, Pisa, Classe di Scienze. Concezioni di insiemi, Rivista di filosofia.
Qualche problema di filosofia della matematica. Rivista di filosofia. Un’osservazione
sul teorema di Minc-Orevkov, Unione Matematica Italiana. La filosofia della
matematica, Laterza, Bari). La teoria del ragionamento matematico: meccanico o
non meccanico? In L’uomo e la macchina, Edizioni di Filosofia, Torino. Categorie
ricorsive, Bollettino dell’Unione Matematica Italiana. Filosofia della
matematica. Paradigmi. La ricerca logica in Italia. Acme, Cisalpino, Milano. Prospettive
della logica e della filosofia della scienza, ETS, Pisa, Logica e filosofia
della scienza: problemi e prospettive, ETS, Pisa); Temi e prospettive della
logica e della filosofia della scienza contemporanee, CLUEB, Bologna, Logiche
moderne, Istituto dellaEnciclopedia Italiana, Rome, Il paradiso di Cantor. Il
dibattito sui fondamenti della teoria degli insiemi, Bibliopolis, Napoli, La
filosofia della matematica. Laterza, Roma. C. Cellucci ha illustrato gli
scopi della logica matematica di Peano. Anche se con motivazioni diverse, tali
scopi sono pressoché analoghi in Peano e Frege, e consistono principalmente
nell ' ottenere. Infiniti 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 ad
opera del matematico tedesco CANTOR Infiniti Cardinalità di
insiemi finiti LM Cosa vuol dire che in una palazzina ci sono 10
appartamenti? Infiniti
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} Infiniti 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 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. 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. 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à. 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 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). 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. 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|. 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 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 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» Il problema si
complica perché arrivò un rappresentante dei filatelici per ogni galassia per
partecipare al congresso interstellare dei filatelici 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» 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
Quindi venne chiesto al direttore di mettere le infinite persone di
infiniti hotel nel suo hotel, già pieno. COME FARE ?
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. In questo modo nessuna stanza avrebbe
avuto due occupanti! 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} VediamLo cosa ci ha insegnato
quMesta storia. Mostrare che N ha la stessa cardinalità dei suoi
seguenti sottoinsiemi propri (1) A={n∈N, n≥7} (2) A={2n+1, ninN} Soluzione 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. 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 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|. 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? 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? 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? 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? 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|.
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. 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. Se A ⊆ B, allora |A| ≤ |B|.
Soluzione. Sia A un insieme infinito. Allora |N| ≤ |A|. 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. 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. 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. 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: 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 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 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 Ann 2 sen=0oppuresenèpari an = 2 −n+1 senèdispari
012345678 -4 −3 −2 −1 0 1 2 3 4 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. 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 ⋆⋆⋆⋆⋆⋆⋆··· ⋆⋆⋆⋆⋆⋆⋆··· ⋆⋆⋆⋆⋆⋆⋆··· ⋆⋆⋆⋆⋆⋆⋆··· . . . . . . . 11 20 ⋆ ⋆ ⋆ ⋆ ⋆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 . . . . . . . ... 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. 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 ? 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). 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 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 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. 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. 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)))))| < · · ·
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 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) INSIEMI INFINITI. 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. Possiamo definire due funzioni,
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. Carlo
Cellucci. Keywords: il paradiso, Peano, logico filosofico, philosophical logic,
logica filosofica, il paradiso di Peano, la rinascita della logica in italia,
storia della logica in italia, formalismo, platonismo, teoria dell’adequazione,
calcolo di predicato di primo ordine, regole d’inferenza, spiegazione
matematica, logica antica, la logica nella storia antica, connetivo, connetivo
russelliano, connetivo intuizionista, prova, dimostrazione, Aristotele e la
mente, il nous, l’anima. Concetto di nomero, definizione splicita, implicita,
gradual del numero, peano, frege, logica della scoperta, revivirla? il paradiso
di Rota, il paradiso di Cantor, parmenide, non-contradizzione, il significato,
il problema de significato, il problema del significato in Hintikka, Grice divergenza
connetivo logico e connetivo nella lingua volgare (‘non,’ ‘e,’ ‘o,’ ‘si,’
‘ogni’, ‘alcuno (al meno uno)’, ‘il,’. Refs.:
Luigi Speranza, “Grice e Cellucci” – The Swimming-Pool Library. Cellucci
No comments:
Post a Comment