Posts
Grice e Cellucci: la ragione
conversazionale e l’implicatura conversazionale del paradiso – aus dem Paradies,
das Cantor uns geschaffen, soll uns niemand vertreiben können – scuola di Santa
Maria Caputa Vetere – filosofia casertiana – filosofia campanese -- filosofia
italiana – Luigi Speranza, pel Gruppo di Gioco di H. P. Grice, The
Swimming-Pool Library (Santa Maria Caputa Vetere). Filosofo
campanese. Filosofo italiano. Santa Maria Caputa Vetera, Caserta, Campania. 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) C.; 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) 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. 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.
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. 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. (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
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. 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: 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 . .
. . . . 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. 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. 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 l’insieme dei numeri reali R
NON ha cardinalità numerabile! 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. 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 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. 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 −1 1 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 −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 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: 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. 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. ∅
{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|. 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) Se A,
B e C sono insiemi, |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öder-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