Logica: Il tremendo (per me) Paradosso di Skolem
Ciao a tutti, mi sento come un aristotelico che ha appena visto cadere simultaneamente due oggetti di diverso peso dalla Torre di Pisa (o come Frege che ha letto l'obiezione di Russell)...
In tutti i libri di Analisi che ho studiato all'Università:
1. Viene definito il campo dei numeri reali come campo ordinato e completo.
2. Viene dimostrato che due campi ordinati e completi sono isomorfi. Così ogni costruzione dei numeri reali porta allo stesso "unico" risultato (a meno di isomorfismi).
3. Viene dimostrato che l'insieme dei numeri reali non è numerabile.
Innanzitutto, queste definizioni e questi teoremi sotto quali ipotesi vengono dati? Nella teoria ZFC? La logica è quella del second'ordine? Esiste forse una teoria ZFC al prim'ordine e una teoria ZFC al second'ordine? Che cosa vuol dire che la teoria dei numeri reali al second'ordine è categorica mentre al prim'ordine no?
Faccio queste domande, perché capirete il mio sbigottimento di fronte al Paradosso di Skolem: esistono modelli numerabili di $\RR$.
Questa affermazione, infatti, sembra contraddire clamorosamente i punti 2 e 3 che ho appena presentato (e su cui tutti i testi concordano).
Nel suo libro "Il diavolo in cattedra", Odifreddi puntualizza che
Io non ci capisco niente. Anche quest'ultima affermazione mi resta del tutto oscura: un insieme con le stesse proprietà insiemistiche di $\RR$ non è forse $\RR$?.
Intuisco che la soluzione del paradosso possa risiedere nell'ambito dove vengono fatte le affermazioni matematiche. Per esempio l'affermazione "esistono triangoli la cui somma degli angoli interni è minore di due retti" potrà anche sorprendere e spiazzare uno studente che è abituato alla sola geometria euclidea (e risultare dunque "paradossale"), ma diventa del tutto accettabile in geometria iperbolica: è chiaro, cambiando gli assiomi non sorprende che cambino anche i teoremi!
Tuttavia vorrei davvero capirne di più.
I vostri interventi, e quelli del mitico Fields in particolare, sono benvenuti.
Grazie anticipate,
Lorenzo
In tutti i libri di Analisi che ho studiato all'Università:
1. Viene definito il campo dei numeri reali come campo ordinato e completo.
2. Viene dimostrato che due campi ordinati e completi sono isomorfi. Così ogni costruzione dei numeri reali porta allo stesso "unico" risultato (a meno di isomorfismi).
3. Viene dimostrato che l'insieme dei numeri reali non è numerabile.
Innanzitutto, queste definizioni e questi teoremi sotto quali ipotesi vengono dati? Nella teoria ZFC? La logica è quella del second'ordine? Esiste forse una teoria ZFC al prim'ordine e una teoria ZFC al second'ordine? Che cosa vuol dire che la teoria dei numeri reali al second'ordine è categorica mentre al prim'ordine no?
Faccio queste domande, perché capirete il mio sbigottimento di fronte al Paradosso di Skolem: esistono modelli numerabili di $\RR$.
Questa affermazione, infatti, sembra contraddire clamorosamente i punti 2 e 3 che ho appena presentato (e su cui tutti i testi concordano). Nel suo libro "Il diavolo in cattedra", Odifreddi puntualizza che
Skolem capì immediatamente che in realtà questi numeri reali non sono i "veri" numeri reali, ma soltanto un insieme con le stesse proprietà insiemistiche.
Io non ci capisco niente. Anche quest'ultima affermazione mi resta del tutto oscura: un insieme con le stesse proprietà insiemistiche di $\RR$ non è forse $\RR$?.
Intuisco che la soluzione del paradosso possa risiedere nell'ambito dove vengono fatte le affermazioni matematiche. Per esempio l'affermazione "esistono triangoli la cui somma degli angoli interni è minore di due retti" potrà anche sorprendere e spiazzare uno studente che è abituato alla sola geometria euclidea (e risultare dunque "paradossale"), ma diventa del tutto accettabile in geometria iperbolica: è chiaro, cambiando gli assiomi non sorprende che cambino anche i teoremi!
Tuttavia vorrei davvero capirne di più.
I vostri interventi, e quelli del mitico Fields in particolare, sono benvenuti.
Grazie anticipate,
Lorenzo
Risposte
"Lorenzo Pantieri":
Ciao a tutti, mi sento come un aristotelico che ha appena visto cadere simultaneamente due oggetti di diverso peso dalla Torre di Pisa (o come Frege che ha letto l'obiezione di Russell)...
In tutti i libri di Analisi che ho studiato all'Università:
1. Viene definito il campo dei numeri reali come campo ordinato e completo.
2. Viene dimostrato che due campi ordinati e completi sono isomorfi. Così ogni costruzione dei numeri reali porta allo stesso "unico" risultato (a meno di isomorfismi).
3. Viene dimostrato che l'insieme dei numeri reali non è numerabile.
Innanzitutto, queste definizioni e questi teoremi sotto quali ipotesi vengono dati? Nella teoria ZFC? La logica è quella del second'ordine? Esiste forse una teoria ZFC al prim'ordine e una teoria ZFC al second'ordine? Che cosa vuol dire che la teoria dei numeri reali al second'ordine è categorica mentre al prim'ordine no?
Faccio queste domande, perché capirete il mio sbigottimento di fronte al Paradosso di Skolem: esistono modelli numerabili di $\RR$.
Al primo ordine è impossibile identificare univocamente cosa si intende abitualmente per numeri reali (ci sono modelli numerabili, come ci sono gli iperreali, che sono "di più" dei reali). Grazie (o per causa) di teoremi come Lowenweim-Skolem (se una struttura ha un modello infinito, allora ha anche un modello numerabile) e LST (se una struttura ha un modello di cardinalità infinita $\kappa$, allora ha modelli per ogni cardinalità $\ge \kappa$) ci saranno sempre modelli non-standard per $NN$, $QQ$, $RR$ etc. Dunque il primo ordine non può descrivere la numerabilità.
L'approccio assiomatico di Dedekind che definisce l'ordinamento del campo reale completo, usa i quantificatori sui sottoinsiemi ("ogni sottoinsieme non vuoto di $RR$ etc"), dunque si passa al secondo ordine, che, aggiungendosi alle definizioni date dal primo ordine, definisce i reali.
Esattamente come dice TomSawyer... è molto difficile avere teorie categoriche al primo ordine (e tantomeno non lo è quella dei campi ordinati completi), solo che nel primo ordine valgono molti teoremi (compattezza su tutti) che non valgono al secondo ecco perché ci si "ostina" a formalizzare al primo ordine.
Innanzitutto grazie a tutti voi per le risposte. In particolare mi convince la posizione di TomSawyer.
Ho ben presente la discussione cui fa riferimento Zorn, tuttavia mi ha lasciato dei dubbi. In particolare:
1. Esiste una teoria ZFC al prim'ordine e una teoria ZFC al second'ordine?
2. E poi: che senso ha fare una teoria di $\RR$ al prim'ordine, visto che essa non è categorica, cioè visto che non si riesce a definire un oggetto "unico" e che esistono addirittura modelli che hanno cardinalità diverse (una cosa del tutto inaccettabile, secondo me, se si vuole definire $\RR$)?
3. A questo punto, dato quello che abbiamo visto, non dovrebbe essere completamente fuori luogo parlare di cardinalità all'interno di una logica del prim'ordine? Non se ne dovrebbe parlare solo al second'ordine?
Grazie ragazzi, siete mitici!
Ho ben presente la discussione cui fa riferimento Zorn, tuttavia mi ha lasciato dei dubbi. In particolare:
1. Esiste una teoria ZFC al prim'ordine e una teoria ZFC al second'ordine?
2. E poi: che senso ha fare una teoria di $\RR$ al prim'ordine, visto che essa non è categorica, cioè visto che non si riesce a definire un oggetto "unico" e che esistono addirittura modelli che hanno cardinalità diverse (una cosa del tutto inaccettabile, secondo me, se si vuole definire $\RR$)?
3. A questo punto, dato quello che abbiamo visto, non dovrebbe essere completamente fuori luogo parlare di cardinalità all'interno di una logica del prim'ordine? Non se ne dovrebbe parlare solo al second'ordine?
Grazie ragazzi, siete mitici!
Ciao.
Provo a risponderti, nel modo più semplice possibile. Prima un po' di "definzioni":
Supponiamo che tu abbia una concezione "intuitiva" di cosa è un modello per una teoria formale.
Una formula del primo ordine è una formula che quantifica sugli elementi del modello.
Una formula del secondo ordine è una formula che quantifica sui sottoinsiemi del modello.
Dire che una teoria (del primo o del secondo ordine) è categorica signfica semplicemente dire che tutti i suoi modelli sono isomorfi (come modelli, cioè non sono semplicemente in biezione ma per rispondere alla tua domanda ti basta sapere che esiste una biezione tra i due. Quali altre proprietà abbia questa biezione... direi che per ora te ne puoi fregare...)
Dare assiomaticamente una definizione dei reali significa scrivere un tot di assiomi (formule). Se vuoi una teoria dei reali "al primo ordine" devi stare attento che queste formule quantifichino solamente sugli elementi. Scriviamo brevemente l'assiomatizzazione che si impara di solito dei reali.
1) Sono un campo:
$\exists ! y \forall x \ x+y=x$ Chiamiamo $0$ tale elemento
$\forall x \exists ! y \ x+y=0$
$\forall x,y,z \ (x+y)+z=x+(y+z)$
$\forall x,y \ x+y=y+x$
$\exists ! y \forall x\ x\cdot y=x$ Chiamiamo $1$ tale elemento
$\forall x \exists ! y \ x\cdot y=1$
$\forall x,y,z\ (x\cdot y)\cdot z=x\cdot (y\cdot z)$
$\forall x,y\ x\cdot y=y\cdot x$
$\forall x,y,z \ x\cdot (y + z) = (x\cdot y) + (x\cdot z)$
2) Sono totalmente ordinati:
$\forall x \ x \leq x$
$\forall x,y \ x \leq y \wedge y \leq x -> x = y$
$\forall x,y,z \ x \leq y \wedge y \leq z -> x \leq z$
$\forall x,y \ x \leq y \vee y \leq x$
Fin qui, come vedi, è una teoria del primo ordine. Ma quello che abbiamo scritto sino ad ora va bene pure per i razionali (senza farsi costruzioni strane).
Adesso però tocca all'assioma di Dedekind... (prendo questo, tanto qualsiasi altro prenda risulta logicamente equivalente):
3) L'ordine è completo:
$\forall \emptyset \ne X \subseteq \RR \ (\exists s \in \RR \ \forall x \in X \ x \leq s ) -> \exists Sup X$
Ti prego non farmi scrivere la definizione di sup perchè già la formula è incasinata così (in pratica vuol dire che ogni sottoinsieme non vuoto che ha un maggiorante ha sup, cosa a esempio non vera nei razionali).
Ok. A questo punto avrai notato che il fatto di essere un ordine completo è una formula del secondo ordine (quantifica sui sottoinsiemi). Questa è la definizione assiomatica che di solito si usa (almeno da me).
Con questa caratterizzazione dei reali, tutti i modelli di queste formule sono isomorfi (come campi e come ordini completi).
Però noi adesso vogliamo scrivere le stesse cose al primo ordine e riscrivere Dedekind al primo ordine. Come facciamo? Dobbiamo sostituirlo con infiniti assiomi, uno per ogni sottoinsieme di $\RR$ esprimendo tale sotoinsieme come gli elementi che soddisfano una certa proprietà. E' possibile farlo per tutti i sottoinsiemi di $\RR$ (come lo pensiamo noi?). No! Perchè?
Semplice: le formule sono sequenze finite di simboli prese da un "alfabeto" finito. Con queste quante proprietà possiamo esprimere? Tutte quelle di lunghezza 1 sono finite, tutte quelle di lunghezza 2 idem... Unione numerabile di insiemi finiti. Anche ammesso che ogni formula sia valida e descriva un insieme diverso non potremo mai caratterizzare più di una quantità numerabile di insiemi. Ma i sottoinsiemi del "nostro" $\RR$ sono più che numerabili.
Quindi non c'è modo di esprimere i reali che hai tu in mente al primo ordine. Dovrai sempre togliere qualche proprietà. Quindi non puoi aspettarti che comunque tu ne scelga una rappresentazione al primo ordine questa ti assicuri che tutti i suoi modelli siano isomorfi, ne tantomeno + che numerabili.
Anzi, se ci pensi, la non numerabilità si ha solo dopo l'assioma di Dedekind che è appunto quello incriminato
Spero di essere stato comprensibile, cmq sono qua.
Provo a risponderti, nel modo più semplice possibile. Prima un po' di "definzioni":
Supponiamo che tu abbia una concezione "intuitiva" di cosa è un modello per una teoria formale.
Una formula del primo ordine è una formula che quantifica sugli elementi del modello.
Una formula del secondo ordine è una formula che quantifica sui sottoinsiemi del modello.
Dire che una teoria (del primo o del secondo ordine) è categorica signfica semplicemente dire che tutti i suoi modelli sono isomorfi (come modelli, cioè non sono semplicemente in biezione ma per rispondere alla tua domanda ti basta sapere che esiste una biezione tra i due. Quali altre proprietà abbia questa biezione... direi che per ora te ne puoi fregare...)
Dare assiomaticamente una definizione dei reali significa scrivere un tot di assiomi (formule). Se vuoi una teoria dei reali "al primo ordine" devi stare attento che queste formule quantifichino solamente sugli elementi. Scriviamo brevemente l'assiomatizzazione che si impara di solito dei reali.
1) Sono un campo:
$\exists ! y \forall x \ x+y=x$ Chiamiamo $0$ tale elemento
$\forall x \exists ! y \ x+y=0$
$\forall x,y,z \ (x+y)+z=x+(y+z)$
$\forall x,y \ x+y=y+x$
$\exists ! y \forall x\ x\cdot y=x$ Chiamiamo $1$ tale elemento
$\forall x \exists ! y \ x\cdot y=1$
$\forall x,y,z\ (x\cdot y)\cdot z=x\cdot (y\cdot z)$
$\forall x,y\ x\cdot y=y\cdot x$
$\forall x,y,z \ x\cdot (y + z) = (x\cdot y) + (x\cdot z)$
2) Sono totalmente ordinati:
$\forall x \ x \leq x$
$\forall x,y \ x \leq y \wedge y \leq x -> x = y$
$\forall x,y,z \ x \leq y \wedge y \leq z -> x \leq z$
$\forall x,y \ x \leq y \vee y \leq x$
Fin qui, come vedi, è una teoria del primo ordine. Ma quello che abbiamo scritto sino ad ora va bene pure per i razionali (senza farsi costruzioni strane).
Adesso però tocca all'assioma di Dedekind... (prendo questo, tanto qualsiasi altro prenda risulta logicamente equivalente):
3) L'ordine è completo:
$\forall \emptyset \ne X \subseteq \RR \ (\exists s \in \RR \ \forall x \in X \ x \leq s ) -> \exists Sup X$
Ti prego non farmi scrivere la definizione di sup perchè già la formula è incasinata così (in pratica vuol dire che ogni sottoinsieme non vuoto che ha un maggiorante ha sup, cosa a esempio non vera nei razionali).
Ok. A questo punto avrai notato che il fatto di essere un ordine completo è una formula del secondo ordine (quantifica sui sottoinsiemi). Questa è la definizione assiomatica che di solito si usa (almeno da me).
Con questa caratterizzazione dei reali, tutti i modelli di queste formule sono isomorfi (come campi e come ordini completi).
Però noi adesso vogliamo scrivere le stesse cose al primo ordine e riscrivere Dedekind al primo ordine. Come facciamo? Dobbiamo sostituirlo con infiniti assiomi, uno per ogni sottoinsieme di $\RR$ esprimendo tale sotoinsieme come gli elementi che soddisfano una certa proprietà. E' possibile farlo per tutti i sottoinsiemi di $\RR$ (come lo pensiamo noi?). No! Perchè?
Semplice: le formule sono sequenze finite di simboli prese da un "alfabeto" finito. Con queste quante proprietà possiamo esprimere? Tutte quelle di lunghezza 1 sono finite, tutte quelle di lunghezza 2 idem... Unione numerabile di insiemi finiti. Anche ammesso che ogni formula sia valida e descriva un insieme diverso non potremo mai caratterizzare più di una quantità numerabile di insiemi. Ma i sottoinsiemi del "nostro" $\RR$ sono più che numerabili.
Quindi non c'è modo di esprimere i reali che hai tu in mente al primo ordine. Dovrai sempre togliere qualche proprietà. Quindi non puoi aspettarti che comunque tu ne scelga una rappresentazione al primo ordine questa ti assicuri che tutti i suoi modelli siano isomorfi, ne tantomeno + che numerabili.
Anzi, se ci pensi, la non numerabilità si ha solo dopo l'assioma di Dedekind che è appunto quello incriminato
Spero di essere stato comprensibile, cmq sono qua.
"one.side.strip":
Avrai notato che il fatto di essere un ordine completo è una formula del secondo ordine ([l'assioma di Dedekind] quantifica sui sottoinsiemi). Questa è la definizione assiomatica che di solito si usa (almeno da me).
Con questa caratterizzazione dei reali, tutti i modelli di queste formule sono isomorfi.
Perfetto. D'accordo su tutto: sono sollevato!
"one.side.strip":
Però noi adesso vogliamo scrivere le stesse cose al primo ordine e riscrivere Dedekind al primo ordine.
Ecco, mi sfugge il perché di questa "volontà". Abbiamo una definizione di $\RR$ al second'ordine così ineccepibile e "naturale", abbiamo l'isomorfismo, perché passare al prim'ordine? Ma proseguiamo...
"one.side.strip":
Quindi non c'è modo di esprimere i reali che hai tu in mente al primo ordine. Dovrai sempre togliere qualche proprietà.
Certo. Non capisco però perché dici "i reali che ho in mente": io direi piuttosto "i reali" (e basta)!
"one.side.strip":
Quindi non puoi aspettarti che comunque tu ne scelga una rappresentazione al primo ordine questa ti assicuri che tutti i suoi modelli siano isomorfi, ne tantomeno + che numerabili.
Anzi, se ci pensi, la non numerabilità si ha solo dopo l'assioma di Dedekind che è appunto quello incriminato
Ecco, non capsico che cosa avrei definito in questo modo: non certo i numeri reali, ma semmai un'altra struttura (ma quale?) che potrà anche avere più modelli non isomorfi.
Insomma, in conclusione direi che per definire $\RR$ ci vuole la logica del second'ordine (occorrono quantificatori che agiscono su sottoinsiemi): in questo caso abbiamo definito un "unico" oggetto (a meno di isomorfismi), che è più che numerabile. Al prim'ordine invece $\RR$ non si può definire.
È giusta questa mia conclusione?
A questo punto, però, non capisco ancora la ragion d'essere del paradosso di Skolem: si parla di $\RR$ ed è relativo alla logica del prim'ordine, ma a quale titolo?
Grazie infinite per il tuo prezioissimo aiuto!
Penso che i termini giusti in cui mettere la cosa siano che al primo ordine riesci a costruire una teoria il cui modello è "anche" $\RR$. In questo senso puoi definire i reali, ma sicuramente non a meno di isomorfismo.
Però la logica del primo ordine è quella che permette di essere studiata in termini di deduzione puramente formale ed automatica... Un vantaggio non da poco!
Però la logica del primo ordine è quella che permette di essere studiata in termini di deduzione puramente formale ed automatica... Un vantaggio non da poco!
Appunto, Lorenzo Pantieri. E' quello che mostra il teorema di Skolem Lowehim.
"one.side.strip":
Penso che i termini giusti in cui mettere la cosa siano che al primo ordine riesci a costruire una teoria il cui modello è "anche" $\RR$.
Capisco.
"one.side.strip":
In questo senso puoi definire i reali, ma sicuramente non a meno di isomorfismo.
La parola "definire" in questo contesto mi piace poco: è un po' come dire che la teoria dei gruppi "definisce" gli interi (con la somma), perché gli interi sono un gruppo. Io direi che la struttura di gruppo è molto generale e gli interi sono un esempio di gruppo.
"one.side.strip":
Però la logica del primo ordine è quella che permette di essere studiata in termini di deduzione puramente formale ed automatica... Un vantaggio non da poco!
Capisco.
Grazie mille per il tuo aiuto, davvero prezioso!
Eh, eh, vedo che gli interventi non mancano, quindi mi limito ad approfondire alcune questioni.
La matematica, come sappiamo, si fonda sulla teoria degli insiemi. La teoria assiomatica ZFC al prim'ordine riesce ad esprimere perfettamente gli assiomi correnti della teoria degli insiemi. Bene! Questo vuol dire che tutti i concetti della matematica sono esprimibili nella logica del prim'ordine, attraverso l'uso di ZFC. Dal momento che la costruzione dei reali di Dedekind è una costruzione di teoria degli insiemi, anch'essa viene espressa in ZFC. Dunque possiamo definire $RR$ in ZFC, senza usare la logica del secondo ordine.
Il fatto che i reali siano definiti univocamente a meno di isomorfismi e il fatto che siano non numerabili lo puoi dimostrare anche in ZFC. Il paradosso di Skolem nasce appunto da questo e dal fatto che, come ha detto TomSaywer, ZFC ha un modello numerabile, e dunque $RR$ definito in ZFC potrà essere interpretato come insieme numerabile.
La contraddizione tuttavia non c'è perché dire che un insieme è non numerabile significa dire che non esiste una biettività di esso con $NN$. Quello che si è scoperto è che noi possiamo concepire il concetto di insieme, così come assiomatizzato dalla matematica e da ZFC, in modo tale che sia permesso a certe funzioni di non essere "considerate insiemi", e in particolare alla biettività "esterna" che noi vediamo esistere quando $RR$ viene interpretato come insieme numerabile. Dall'esterno dunque vediamo $RR$ numerabile, ma se vediamo con gli occhi del modello di ZFC, la biettività non esiste, e dunque in esso $RR$ non è numerabile. Il fatto è che la nostra assiomatizzazione della teoria degli insiemi non è sufficientemente precisa per far sì che il concetto di insieme sia univocamente determinato, e quindi a seconda del modo in cui concepiamo il concetto di insieme, avremo $RR$ numerabile, o non numerabile.
A questo punto rispondo ad un'altra delle domande di Lorenzo. Sì, esiste ZFC al secondo ordine. Essa è uguale a ZFC del prim'ordine, solo che viene sostituito l'assioma di rimpiazzamento:
$\forall A \forall x\in A \exists !y \phi(x,y)\rightarrow \exists Y\ forall x \in A \exists y\in Y \phi(x,y)$
($\exists !y$ significa esiste un solo $y$) con l'assioma
$\forall f \forall A \exists Y\ forall x \in A \exists y\in Y f(x)=y$
dove $f$ e' una funzione quantificata universalmente. Chiara la differenza, no? In ZFC al secondo ordine puoi quantificare i sottinsiemi di elementi, le funzioni etc., mentre in ZFC lo puoi fare solo indirettamente, quantificando gli insiemi e le funzioni presenti nel modello.
Il problema di ZFC al secondo ordine e' chiaro. Nel momento in cui definisci la teoria degli insiemi con la logica del secondo ordine, hai bisogno di concetti di teoria degli insiemi (quali il concetto di power set) per far funzionare la logica del secondo ordine! In effetti la logica del secondo ordine e' stata chiamata "set theory in disguise". Questo e' uno dei tanti motivi (oltre alla incompletezza) che ne ha bloccato la diffusione.
Inoltre, il poter espressivo della logica del secondo ordine aumenta, è "vero", ma tuttavia non aumentano di pari passo le sua capacità dimostrative, quindi è molto fumo e poco arrosto. In altri termini, ci ritroviamo a poter parlare dei massimi sistemi, senza poter decidere quale dei massimi sistemi è quello giusto
In effetti ad esempio CH è "decisa" da ZFC al secondo ordine (nel senso che o lei o la sua appropriata negazione sono verità logiche), tuttavia non è dimostrabile, né lei né la sua appropriata negazione.
La matematica, come sappiamo, si fonda sulla teoria degli insiemi. La teoria assiomatica ZFC al prim'ordine riesce ad esprimere perfettamente gli assiomi correnti della teoria degli insiemi. Bene! Questo vuol dire che tutti i concetti della matematica sono esprimibili nella logica del prim'ordine, attraverso l'uso di ZFC. Dal momento che la costruzione dei reali di Dedekind è una costruzione di teoria degli insiemi, anch'essa viene espressa in ZFC. Dunque possiamo definire $RR$ in ZFC, senza usare la logica del secondo ordine.
Il fatto che i reali siano definiti univocamente a meno di isomorfismi e il fatto che siano non numerabili lo puoi dimostrare anche in ZFC. Il paradosso di Skolem nasce appunto da questo e dal fatto che, come ha detto TomSaywer, ZFC ha un modello numerabile, e dunque $RR$ definito in ZFC potrà essere interpretato come insieme numerabile.
La contraddizione tuttavia non c'è perché dire che un insieme è non numerabile significa dire che non esiste una biettività di esso con $NN$. Quello che si è scoperto è che noi possiamo concepire il concetto di insieme, così come assiomatizzato dalla matematica e da ZFC, in modo tale che sia permesso a certe funzioni di non essere "considerate insiemi", e in particolare alla biettività "esterna" che noi vediamo esistere quando $RR$ viene interpretato come insieme numerabile. Dall'esterno dunque vediamo $RR$ numerabile, ma se vediamo con gli occhi del modello di ZFC, la biettività non esiste, e dunque in esso $RR$ non è numerabile. Il fatto è che la nostra assiomatizzazione della teoria degli insiemi non è sufficientemente precisa per far sì che il concetto di insieme sia univocamente determinato, e quindi a seconda del modo in cui concepiamo il concetto di insieme, avremo $RR$ numerabile, o non numerabile.
A questo punto rispondo ad un'altra delle domande di Lorenzo. Sì, esiste ZFC al secondo ordine. Essa è uguale a ZFC del prim'ordine, solo che viene sostituito l'assioma di rimpiazzamento:
$\forall A \forall x\in A \exists !y \phi(x,y)\rightarrow \exists Y\ forall x \in A \exists y\in Y \phi(x,y)$
($\exists !y$ significa esiste un solo $y$) con l'assioma
$\forall f \forall A \exists Y\ forall x \in A \exists y\in Y f(x)=y$
dove $f$ e' una funzione quantificata universalmente. Chiara la differenza, no? In ZFC al secondo ordine puoi quantificare i sottinsiemi di elementi, le funzioni etc., mentre in ZFC lo puoi fare solo indirettamente, quantificando gli insiemi e le funzioni presenti nel modello.
Il problema di ZFC al secondo ordine e' chiaro. Nel momento in cui definisci la teoria degli insiemi con la logica del secondo ordine, hai bisogno di concetti di teoria degli insiemi (quali il concetto di power set) per far funzionare la logica del secondo ordine! In effetti la logica del secondo ordine e' stata chiamata "set theory in disguise". Questo e' uno dei tanti motivi (oltre alla incompletezza) che ne ha bloccato la diffusione.
Inoltre, il poter espressivo della logica del secondo ordine aumenta, è "vero", ma tuttavia non aumentano di pari passo le sua capacità dimostrative, quindi è molto fumo e poco arrosto. In altri termini, ci ritroviamo a poter parlare dei massimi sistemi, senza poter decidere quale dei massimi sistemi è quello giusto
In effetti ad esempio CH è "decisa" da ZFC al secondo ordine (nel senso che o lei o la sua appropriata negazione sono verità logiche), tuttavia non è dimostrabile, né lei né la sua appropriata negazione.
Grazie a tutti! Credo di aver capito: è possibile che un insieme sia, allo stesso tempo, non numerabile relativamente a un modello, ma numerabile "dal di fuori". In altre parole, che esistano corrispondenze biunivoche coi numeri interi, ma che nessuna di queste stia nel modello. Come dice Odifredddi (C'era una volta un paradosso):
Quest'ultima affermazione mi lascia dubbioso. Io direi: CH è indecisa al prim'ordine (come Goedel e Cohen hanno provato). CH è però decisa al second'ordine, solo che, ancora, non sappiamo in quale direzione sia decisa, cioè se sia dimostrabile o refutabile.
Correggimi se sbaglio!
Grazie a tutti,
L.
i risultati di esistenza di infiniti sempre maggiori sono in realtà risultati di inesistenza di corrispondenze biunivoche. Essi mostrano, cioè, non tanto la ricchezza dell'universo matematico, quanto piuttosto l'intrinseca limitatezza della nostra possibilità di conoscerlo.
"fields":
Inoltre, il poter espressivo della logica del secondo ordine aumenta, è "vero", ma tuttavia non aumentano di pari passo le sua capacità dimostrative, quindi è molto fumo e poco arrosto. In altri termini, ci ritroviamo a poter parlare dei massimi sistemi, senza poter decidere quale dei massimi sistemi è quello giusto
Quest'ultima affermazione mi lascia dubbioso. Io direi: CH è indecisa al prim'ordine (come Goedel e Cohen hanno provato). CH è però decisa al second'ordine, solo che, ancora, non sappiamo in quale direzione sia decisa, cioè se sia dimostrabile o refutabile.
Correggimi se sbaglio!
Grazie a tutti,
L.
Nel sistema deduttivo di ZFC del secondo ordine, CH e NCH (l'opportuna negazione di CH) non sono dimostrabili, proprio come non lo sono nel sistema deduttivo di ZFC al prim'ordine.
"fields":
Nel sistema deduttivo di ZFC del secondo ordine, CH e NCH (l'opportuna negazione di CH) non sono dimostrabili, proprio come non lo sono nel sistema deduttivo di ZFC al prim'ordine.
Questa tua affermazione mi sembra (sbaglio?) in contrasto con quello che ho trovato scritto sul testo di Odifreddi (che tendo a conisderare un'auctoritas in queste cose):
L’ipotesi del continuo è decisa dalla teoria del second’ordine degli insiemi. Benché non sia indipendente, come nel caso della teoria del prim’ordine di ZF, nessuno sa però in che direzione essa sia decisa: in altre parole, se sia vera o falsa nel modello minimale.
Che ne pensi?
Attenzione, Odifreddi parla di verita' e falsita'. Io ho detto che non e' dimostrabile ne' CH ne' NCH in ZFC del secondo ordine.
"fields":
Attenzione, Odifreddi parla di verita' e falsita'. Io ho detto che non e' dimostrabile ne' CH ne' NCH in ZFC del secondo ordine.
Un momento: Odifreddi dice:
L’ipotesi del continuo è decisa dalla teoria del second’ordine degli insiemi.
"Decisa" non significa forse "dimostrabile o refutabile"?
Evidentemente è un improprietà linguistica di Odifreddi. Tranquillo, ho una fonte attendibile: "Foundations without foundationalism" di Shapiro (pag 105), il miglior libro di testo in circolazione sulla logica del secondo ordine.
Si può scrivere in ZFC2 una formula CH logicamente valida (i.e vera in ogni modello) sse l'ipotesi del continuo è vera nel modello minimale e si può scrivere una formula NCH logicamente valida (i.e vera in ogni modello) sse l'ipotesi del continuo è falsa nel modello minimale. Chaquai (1972) ha dimostrato che né CH né NCH sono dimostrabili nel sistema deduttivo della logica del secondo ordine.
Nota che al prim'ordine CH non e' logicamente valida, cosi' come non lo e' $\not$CH.
Si può scrivere in ZFC2 una formula CH logicamente valida (i.e vera in ogni modello) sse l'ipotesi del continuo è vera nel modello minimale e si può scrivere una formula NCH logicamente valida (i.e vera in ogni modello) sse l'ipotesi del continuo è falsa nel modello minimale. Chaquai (1972) ha dimostrato che né CH né NCH sono dimostrabili nel sistema deduttivo della logica del secondo ordine.
Nota che al prim'ordine CH non e' logicamente valida, cosi' come non lo e' $\not$CH.
"fields":
Evidentemente è un improprietà linguistica di Odifreddi.
Caro Fields, sei come sempre risolutivo!
Grazie mille,
L.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo