Congettura di Goldbach
In università mi è giunta una notizia inquietante e vorrei avere una risposta...
E' stata per caso dimostrata l'indimostrabilità della congettura di goldbach con gli assiomi correnti (se non sbaglio come cohen aveva fatto con l'ipotesi del continuo)?
Poi:
Quali sono i risultati più vicini alla congettura di goldbach? e dove (se possibile) trovare tali dimostrazioni?
Qualche titolo di un bel libro di divulgazione matematica sulla teoria dei numeri primi?
Grazie...
E' stata per caso dimostrata l'indimostrabilità della congettura di goldbach con gli assiomi correnti (se non sbaglio come cohen aveva fatto con l'ipotesi del continuo)?
Poi:
Quali sono i risultati più vicini alla congettura di goldbach? e dove (se possibile) trovare tali dimostrazioni?
Qualche titolo di un bel libro di divulgazione matematica sulla teoria dei numeri primi?
Grazie...
Risposte
Si gioca tutto, caro Luca, sul concetto di indecidibilità ?
Propongo allora questo ragionamento.
Chiamo "indecidibile" :
"una proposizione di cui non si può dimostrare la verità o la falsità all'interno del sistema assiomatico in cui la proposizione viene fatta".
Presa questa definizione per buona, costruisco una geometria basata sui primi quattro assiomi di Euclide e la chiamo "geometria pre-euclidea".
Introduco una proposizione che chiamo "congettura delle rette parallele" identica alla proposizione nota come V postulato di Euclide.
Dimostro che la congettura delle rette parallele è indecidibile all'interno della geometria pre-euclidea (come mi risulta sia stato effettivamente fatto).
1) Dichiaro che la congettura delle rette parallele è vera, la chiamo V postulato di Euclide e costruisco la geometria Euclidea.
Oppure.
2) Dichiaro che la congettura delle rette parallele è falsa, scelgo postulati alternativi e costruisco le varie geometrie non euclidee.
Oppure.
3) Mi fermo alla geometria pre-euclidea.
E' giusto fin qui questo "processo" ?
Introduco ora la "macchina di Riemann". Essa utilizza i soli primi quattro postulati di Euclide e quindi "lavora" all'interno della cosiddetta (da me ...) geometria pre-euclidea.
Se la congettura delle rette parallele, all'interno della geometria pre-euclidea, fosse "indecidibile + falsa", la macchina di Riemann mi fornirebbe un contro-esempio ovvero due rette parallele si incontrano.
Allora, la congettura delle rette parallele, all'interno della geometria pre-euclidea, deve essere "indecidibile + vera" ovvero due rette parallele non si incontrano.
Ma la macchina ha dimostrato che si incontrano ... e quindi l'evidente antinomia ...
Dove sbaglio ?
ps. scusate la stupidità di questo post, ma da alcuni giorni sono entrato in un loop mentale ... con buona pace di Turing ...
ps2. una soluzione del mio dilemma potrebbe essere che non può esistere una "macchina di Riemann". Ma perchè ? ...
Propongo allora questo ragionamento.
Chiamo "indecidibile" :
"una proposizione di cui non si può dimostrare la verità o la falsità all'interno del sistema assiomatico in cui la proposizione viene fatta".
Presa questa definizione per buona, costruisco una geometria basata sui primi quattro assiomi di Euclide e la chiamo "geometria pre-euclidea".
Introduco una proposizione che chiamo "congettura delle rette parallele" identica alla proposizione nota come V postulato di Euclide.
Dimostro che la congettura delle rette parallele è indecidibile all'interno della geometria pre-euclidea (come mi risulta sia stato effettivamente fatto).
1) Dichiaro che la congettura delle rette parallele è vera, la chiamo V postulato di Euclide e costruisco la geometria Euclidea.
Oppure.
2) Dichiaro che la congettura delle rette parallele è falsa, scelgo postulati alternativi e costruisco le varie geometrie non euclidee.
Oppure.
3) Mi fermo alla geometria pre-euclidea.
E' giusto fin qui questo "processo" ?
Introduco ora la "macchina di Riemann". Essa utilizza i soli primi quattro postulati di Euclide e quindi "lavora" all'interno della cosiddetta (da me ...) geometria pre-euclidea.
Se la congettura delle rette parallele, all'interno della geometria pre-euclidea, fosse "indecidibile + falsa", la macchina di Riemann mi fornirebbe un contro-esempio ovvero due rette parallele si incontrano.
Allora, la congettura delle rette parallele, all'interno della geometria pre-euclidea, deve essere "indecidibile + vera" ovvero due rette parallele non si incontrano.
Ma la macchina ha dimostrato che si incontrano ... e quindi l'evidente antinomia ...
Dove sbaglio ?
ps. scusate la stupidità di questo post, ma da alcuni giorni sono entrato in un loop mentale ... con buona pace di Turing ...
ps2. una soluzione del mio dilemma potrebbe essere che non può esistere una "macchina di Riemann". Ma perchè ? ...
Per filelds: Quindi stai dicendo che l'indecidibilità di una affermazione equivale a dire che posso trovare due modelli in cui in uno l'affermazione è vere e in un altro l'affermazione è falsa?
Ho postato senza leggere il tuo intervento, fields, perchè ero impegnato a scrivere la mia elucubrazione ... che mi sarei certamente risparmiato ... alla luce di ciò che scrivi e che devo però ancora capire ...
Dunuqe, provo a riassumere quello che ho capito io: in geometria il postulato delle parallele è indecidibile nel senso che la sua verità nè la sua falsità possono essere dimostrate a partire dai primi 4 assiomi. Dunque esistono due modelli in cui il postulato è rispettivamente vero o falso.
Nella teoria dei numeri interi supponiamo che la congettura di Glodbach sia indecidibile. Allora esistono due modelli degli assiomi di Peano nei quali rispettivamente la congettura è falsa o vera. $\NN$ è un modello degli assiomi di Peano in cui Goldbach sarebbe vera, perchè il controesempio lo potrei costruire con la Macchina di Turing. Ma quindi questa è una dimostrazione che Goldbach è vera? oppure Goldbach rimane vera ma non dimostrabile anche in $\NN$?
Nella teoria dei numeri interi supponiamo che la congettura di Glodbach sia indecidibile. Allora esistono due modelli degli assiomi di Peano nei quali rispettivamente la congettura è falsa o vera. $\NN$ è un modello degli assiomi di Peano in cui Goldbach sarebbe vera, perchè il controesempio lo potrei costruire con la Macchina di Turing. Ma quindi questa è una dimostrazione che Goldbach è vera? oppure Goldbach rimane vera ma non dimostrabile anche in $\NN$?
Rimane vera ma non dimostrabile in $NN$. Quella sarebbe una dimostrazione che Goldbach è vera, ma tale dimostrazione NON è fatta all'interno del modello $NN$ (cioè tramite l'utilizzo degli assiomi e delle regole di deduzione), ma "da fuori".
"Luca.Lussardi":
Per filelds: Quindi stai dicendo che l'indecidibilità di una affermazione equivale a dire che posso trovare due modelli in cui in uno l'affermazione è vere e in un altro l'affermazione è falsa?
Sì, Luca, nella logica del prim'ordine quello che dici è vero. Questo deriva dal fatto che la logica del prim'ordine è completa, ovvero dal fatto che se un insieme di assiomi A implica logicamente un formula F, allora da A è possibile dedurre F. Infatti supponiamo che F sia indecidibile da A. Se F fosse vera (risp. falsa) in tutti i modelli di A, allora A implicherebbe logicamente F (risp. non F), e per la completezza, da A si potrebbe dedurre F (risp. non F), assurdo. Dunque deve esistere un modello in cui F è vera e uno in cui è falsa.
L'altra direzione invece segue dal teorema di correttezza.
Quindi la cosa interessante potrebbe essere questa. Per dimostrare che Goldbach è indecidibile, si potrebbe costruire un nuovo tipo di numeri che falsificano Goldbach ma che soddisfano gli assiomi di PA e un altro tipo di numeri che verificano Goldbach e soddisfano PA. Se Goldabch è veramente indecidibile, una tale costruzione si può portare a termine.
Da notare che l'aritmetica del secondo ordine, che di fatto è quella usata dai matematici "reali", non gode di questa elasticità perché $(NN,+,*)$ è il suo unico modello.
"Luca.Lussardi":
Nella teoria dei numeri interi supponiamo che la congettura di Glodbach sia indecidibile. Allora esistono due modelli degli assiomi di Peano nei quali rispettivamente la congettura è falsa o vera. $NN$ è un modello degli assiomi di Peano in cui Goldbach sarebbe vera, perchè il controesempio lo potrei costruire con la Macchina di Turing. Ma quindi questa è una dimostrazione che Goldbach è vera? oppure Goldbach rimane vera ma non dimostrabile anche in $NN$?
Sì, è una dimostrazione valida al di fuori dell'aritmetica di Peano. Cioè Goldbach rimane indecidibile nel sistema formale, ma attraverso una meta-dimostrazione noi possiamo dire che è vera in $NN$. Comunque il controesempio non è che per forza tu lo debba costruire con una macchina di Turing: l'importante è che esso esista, perché questo è sufficiente per dire, anche se non sappiamo qual è, che esso può essere dimostrato in PA.
Notare che se Goldbach è indecidibile in PA del prim'ordine, essa potrebbe essere decidibile in PA del secondo ordine.
Eh sì, ora ho capito perchè i matematici chiamano la Teoria ZF come aritmetica del 2 ordine, perchè in ZF dimostri che c'è solo un insieme che verifica gli assiomi di Peano.
Grazie di tutto.
Grazie di tutto.
Posso chiedervi due cose...
1) cosa ha in più $(N,+,*)$ rispetto agli assiomi di Peano? quale è la differenza tra un set di assiomi ed un "modello"? forse che il modello è per forza decidibile?
2) cosa è la logica del primo (e del secondo) ordine?
1) cosa ha in più $(N,+,*)$ rispetto agli assiomi di Peano? quale è la differenza tra un set di assiomi ed un "modello"? forse che il modello è per forza decidibile?
2) cosa è la logica del primo (e del secondo) ordine?
grazie a fields per le spiegazioni...
mi pare che da ciò si possa rispondere al problema iniziale sulla differenza logica fra Goldbach e il V postulato:
se Goldbach è indecidibile allora è vera perchè esiste un unico modello per $NN$. Stessa cosa non si può
dire per il V postulato in quanto è possibile costruire altri modelli.
mi pare che da ciò si possa rispondere al problema iniziale sulla differenza logica fra Goldbach e il V postulato:
se Goldbach è indecidibile allora è vera perchè esiste un unico modello per $NN$. Stessa cosa non si può
dire per il V postulato in quanto è possibile costruire altri modelli.
@Thomas 1) La tua domanda non ha senso... Un modello è una struttura, ovvero un insieme con delle relazioni, mentre un insieme di assiomi è un'insieme di formule simboliche che vengono interpretate nel modello.
2) la logica del prim'ordine è la logica dei connettivi proposizionali, dei predicati e della quantificazione sugli individui. Es: Per ogni n in N, Pari(n) o Dispari(n).
La logica del secondo ordine comprende la logica del primo, più le quantificazioni su insiemi di individui. Es: Per ogni sottinsieme S di N, e per ogni s in S Pari(s) o Dispari(s).
@Ubermensch Non è proprio come dici. Se consideriamo l'aritmetica di peano PA essa non ha un unico modello. Se poi consideriamo l'aritmetica della teoria degli insiemi, la questione dei modelli è ancora più complicata.
2) la logica del prim'ordine è la logica dei connettivi proposizionali, dei predicati e della quantificazione sugli individui. Es: Per ogni n in N, Pari(n) o Dispari(n).
La logica del secondo ordine comprende la logica del primo, più le quantificazioni su insiemi di individui. Es: Per ogni sottinsieme S di N, e per ogni s in S Pari(s) o Dispari(s).
@Ubermensch Non è proprio come dici. Se consideriamo l'aritmetica di peano PA essa non ha un unico modello. Se poi consideriamo l'aritmetica della teoria degli insiemi, la questione dei modelli è ancora più complicata.
?? non c'è un teorema che dice che se esiste un insieme che verifica gli assiomi di Peano, questo è unico?
altra cosa... come possiamo dire, partendo dall'indecilibilità della congettura di Goldbach nella teoria assiomatica dei numeri interi, dimostrare la verità nel modello $(N,+,*)$. mi sfugge perchè dalla falsità nel sistema particolare potrei dedurre la decidibilità nella teoria assiomatica?...
Allora, l'aritmetica di peano PA è questa:
http://it.wikipedia.org/wiki/Aritmetica_di_Peano
Essa è formulata nella logica del prim'ordine, il principio di induzione viene preso come assioma e PA ha modelli fra loro non isomorfi.
L'aritmetica di peano del secondo ordine PA2 è questa:
http://it.wikipedia.org/wiki/Assiomi_di_Peano
Essa è formulata nella logica del secondo ordine, perché c'è una quantificazione universale sui insiemi di naturali, e il principio d'induzione è un teorema. Essa ammette un solo modello $(NN,+,*)$.
L'aritmetica di peano del secondo ordine si può riformulare nella teoria del prim'ordine degli insiemi ZF. Tuttavia i modelli sono molto difficili da descrivere.
Ma perché si usa spesso PA se i suoi modelli non sono tutti fra loro isomorfi? Perché la logica del prim'ordine gode di importanti proprietà, quali la completezza deduttiva: cioè, se un enunciato è conseguenza logica degli assiomi, esso è dimostrabile nel sistema formale.
Quando parliamo di aritmetica dobbiamo dunque precisare quale. Se consideriamo PA2 tutti i modelli sono isomorfi. In ogni caso, supponiamo che Goldbach sia indecidibile in PA2. Allora Goldbach è vera in $(NN,+,*)$ perché se fosse falsa esisterebbe un naturale N pari che non è somma di due primi. Ma allora potremmo scrivere nel sistema formale tutte le coppie di primi minori di N, far vedere che N non è somma di queste coppie di primi, e dedurre dunque la negazione della congettura di Goldbach nel sistema formale, e questo è assurdo.
In ogni caso se Goldbach è indecidibile in PA2, Goldbach è indecidibile in PA. Dunque possiamo trovare un modello che soddisfa PA e Goldbach e un modello che soddisfa PA e la negazione di Goldbach.
http://it.wikipedia.org/wiki/Aritmetica_di_Peano
Essa è formulata nella logica del prim'ordine, il principio di induzione viene preso come assioma e PA ha modelli fra loro non isomorfi.
L'aritmetica di peano del secondo ordine PA2 è questa:
http://it.wikipedia.org/wiki/Assiomi_di_Peano
Essa è formulata nella logica del secondo ordine, perché c'è una quantificazione universale sui insiemi di naturali, e il principio d'induzione è un teorema. Essa ammette un solo modello $(NN,+,*)$.
L'aritmetica di peano del secondo ordine si può riformulare nella teoria del prim'ordine degli insiemi ZF. Tuttavia i modelli sono molto difficili da descrivere.
Ma perché si usa spesso PA se i suoi modelli non sono tutti fra loro isomorfi? Perché la logica del prim'ordine gode di importanti proprietà, quali la completezza deduttiva: cioè, se un enunciato è conseguenza logica degli assiomi, esso è dimostrabile nel sistema formale.
Quando parliamo di aritmetica dobbiamo dunque precisare quale. Se consideriamo PA2 tutti i modelli sono isomorfi. In ogni caso, supponiamo che Goldbach sia indecidibile in PA2. Allora Goldbach è vera in $(NN,+,*)$ perché se fosse falsa esisterebbe un naturale N pari che non è somma di due primi. Ma allora potremmo scrivere nel sistema formale tutte le coppie di primi minori di N, far vedere che N non è somma di queste coppie di primi, e dedurre dunque la negazione della congettura di Goldbach nel sistema formale, e questo è assurdo.
In ogni caso se Goldbach è indecidibile in PA2, Goldbach è indecidibile in PA. Dunque possiamo trovare un modello che soddisfa PA e Goldbach e un modello che soddisfa PA e la negazione di Goldbach.
ah ma allora è l'indecibilità in PA2 unita al fatto che tutti i modelli sono isomorfi che potrebbe portare a dire che Goldbach è vera...
l'indecibilità in PA1 non porterebbe a nulla, giusto?
continuando con le domande (poi finisco) è vero che PA2 (e quindi PA) è indecidibile??? Si conoscono proposizioni indecidibili? Esiste un sistema assiomatico con tutte le proposizioni decidibili?
l'indecibilità in PA1 non porterebbe a nulla, giusto?
continuando con le domande (poi finisco) è vero che PA2 (e quindi PA) è indecidibile??? Si conoscono proposizioni indecidibili? Esiste un sistema assiomatico con tutte le proposizioni decidibili?
Allora, se Goldbach è indecidibile in un qualunque sistema fra PA, PA2, ZF, allora Goldbach è vera se interpretata in $(NN,+,*)$. Il ragionamento che ho fatto per PA2, vale anche per PA e ZF, e non dipende dall'unicità dei modelli, ma solo dal fatto che siamo certi che se Goldbach è falsa in $(NN,+,*)$, possiamo SCRIVERE la dimostrazione di questo fatto nel sistema formale, essendo tale dimostrazione il semplice calcolo di un controesempio.
Unendo i ragionamenti, si ottiene che le seguenti proposizioni sono EQUIVALENTI:
1) Goldbach è indecidibile in uno qualunque fra PA, PA2, ZF
2) Esiste un modello di PA che verifica Goldbach e un modello di PA che verifica la negazione di Goldbach
3) $(NN,+,*)$ verifica PA e Goldbach ed esiste un modello di PA che verifica la negazione di Goldbach.
Per quanto riguarda l'altra domanda, sì, PA e PA2 sono indecidibili. Il termine più preciso è sintatticamente incomplete: esiste un enunciato di PA e PA2, chiamiamolo G, tale che né G, né non G sono dimostrabili in PA e PA2. Questo significa che i nostri assiomi per i naturali non bastano a risolvere tutti i problemi di teoria dei numeri e inoltre è stato dimostrato che nessun sistema di assiomi ricorsivo che contenga PA può essere completo.
La geometria euclidea, come assiomatizzata da Hilbert, è invece completa: per ogni enunciato A della geometria eulidea, A oppure non A è dimostrabile. Questo deriva dal fatto che i modelli della geometria euclidea sono tutti fra loro isometrici e la geometria euclidea è una teoria del prim'ordine.
Unendo i ragionamenti, si ottiene che le seguenti proposizioni sono EQUIVALENTI:
1) Goldbach è indecidibile in uno qualunque fra PA, PA2, ZF
2) Esiste un modello di PA che verifica Goldbach e un modello di PA che verifica la negazione di Goldbach
3) $(NN,+,*)$ verifica PA e Goldbach ed esiste un modello di PA che verifica la negazione di Goldbach.
Per quanto riguarda l'altra domanda, sì, PA e PA2 sono indecidibili. Il termine più preciso è sintatticamente incomplete: esiste un enunciato di PA e PA2, chiamiamolo G, tale che né G, né non G sono dimostrabili in PA e PA2. Questo significa che i nostri assiomi per i naturali non bastano a risolvere tutti i problemi di teoria dei numeri e inoltre è stato dimostrato che nessun sistema di assiomi ricorsivo che contenga PA può essere completo.
La geometria euclidea, come assiomatizzata da Hilbert, è invece completa: per ogni enunciato A della geometria eulidea, A oppure non A è dimostrabile. Questo deriva dal fatto che i modelli della geometria euclidea sono tutti fra loro isometrici e la geometria euclidea è una teoria del prim'ordine.
Ho sempre pensato che ogni sistema assiomatico fosse incompleto ... e che il teorema di Goedel fosse applicabile ad ogni sistema assiomatico. Invece la geometria euclidea è completa !!!
Solo i sistemi che si basano sull'aritmetica lo sono !!!
Grazie fields !!!
Azzardo una domanda approfittando della tua gentilezza.
La teoria degli insiemi suppongo sia incompleta, quindi anche la topologia, giusto ?
E l'analisi è incompleta ? e la geometria differenziale ?
ps. quando si affrontano argomenti "difficili" senza i dovuti prerequisiti si prendono granchi enormi ...
Solo i sistemi che si basano sull'aritmetica lo sono !!!
Grazie fields !!!
Azzardo una domanda approfittando della tua gentilezza.
La teoria degli insiemi suppongo sia incompleta, quindi anche la topologia, giusto ?
E l'analisi è incompleta ? e la geometria differenziale ?
ps. quando si affrontano argomenti "difficili" senza i dovuti prerequisiti si prendono granchi enormi ...
"fields":
Allora, se Goldbach è indecidibile in un qualunque sistema fra PA, PA2, ZF, allora Goldbach è vera se interpretata in $(NN,+,*)$. Il ragionamento che ho fatto per PA2, vale anche per PA e ZF, e non dipende dall'unicità dei modelli, ma solo dal fatto che siamo certi che se Goldbach è falsa in $(NN,+,*)$, possiamo SCRIVERE la dimostrazione di questo fatto nel sistema formale, essendo tale dimostrazione il semplice calcolo di un controesempio.
ma allora non ci sono... abbi pazienza...
supponiamo che Goldbach sia falsa in $(NN,+,*)$. Se ho ben capito $(NN,+,*)$ è semplicemente un assieme nel quale si possono interpretare delle "regole" date dall'insieme assiomatico. Ma se dimostro che qui Goldbach è falsa, nulla impedisce che esistano altri modelli dell'insieme assiomatico in cui Goldbach è vera. Quindi non si può dire che "Goldbach falsa in $(NN,+,*)$" implica "Goldbach decidibile"...
e poi vorrei osservare anche un'altra cosa. Supponendo che io nel futuro capisca perchè invece "Goldbacg falsa in $(NN,+,*)$" implica "Goldabch decidibile", la dimostrazione andrebbe avanti dicendo: quindi Goldbach vera in $(NN,+,*)$. Quest'ultimo passaggio presuppone che in $(NN,+,*)$ Goldbach è o vera o falsa. Quindi si presuppone a priori che la proposizione abbia un valore in sè in $(NN,+,*)$... questo però con le rette parallele non funziona a meno di non caratterizzare bene in modo hilbertiano (se ho ben capito)... quindi rimane da vederee perchè ci sia questo "valore assoluto della proposizione di Goldbach" in $(NN,+,*)$... o sbaglio???
Se sono troppo insistente e avete voglia di dirmi "vai a leggerti un libro di logica" ditemelo, eh...
...
A proposito ... che libro di logica mi consigliereste ?
Grazie !!
Grazie !!
@arriama
Non preoccuparti per eventuali "granchi" in logica: senza averla studiata rigorosamente e approfonditamente è praticamente impossibile non prendere "granchi"! Guarda i paradossi che erano venuto fuori agli inizi del Novecento che casino hanno combinato...
Per quanto riguarda le domande sulla completezza dell'analisi, della geometria differenziale e della topologia, vanno oltre le mie conoscenze di logica. Non saprei nemmeno come definire una teoria e un linguaggio apposito ad esempio per la geometria differenziale e non so nemmeno se esista una tale teoria. Certo tutte queste teorie si codificano nella teoria degli insiemi del prim'ordine, ma è estremamente difficile studiare la completezza di frammenti della teoria degli insiemi (tra l'altro molto complessi).
Lo studio di geometria euclidea, aritmetica di peano, teoria dei numeri reali, teoria pura degli insiemi, è stato condotto con successo perché per queste teorie si può definire un apposito linguaggio logico del prim'ordine con cui esprimere assiomi e teoremi. Codificare teorie all'interno di altre teorie complica decisamente le cose e su questo argomento so poco. (Ormai la logica è talmente sviluppata, sopratutto nella teoria dei modelli e teoria della dimostrazione, che è impossibile esserne totalmente aggiornati senza essere specialisti o logici professionisti)
Libri di logica consigliati:
Lolli, Introduzione alla logica formale (rimane piuttosto elementare)
Mendelson, Logica Matematica (ottimo, anche se datato e anche se le notazioni sono fastidiosamente vecchie)
Per dispense ben fatte on line, quelle del mio maestro:
http://www.scienze.univr.it/fol/main?en ... erro&grp=2
(guardare su logica 2005/2006)
Hodges, A Shorter model theory (bellissimo, qui si incomincia a fare sul serio!, ma bisogna già conoscere la logica)
Non preoccuparti per eventuali "granchi" in logica: senza averla studiata rigorosamente e approfonditamente è praticamente impossibile non prendere "granchi"! Guarda i paradossi che erano venuto fuori agli inizi del Novecento che casino hanno combinato...
Per quanto riguarda le domande sulla completezza dell'analisi, della geometria differenziale e della topologia, vanno oltre le mie conoscenze di logica. Non saprei nemmeno come definire una teoria e un linguaggio apposito ad esempio per la geometria differenziale e non so nemmeno se esista una tale teoria. Certo tutte queste teorie si codificano nella teoria degli insiemi del prim'ordine, ma è estremamente difficile studiare la completezza di frammenti della teoria degli insiemi (tra l'altro molto complessi).
Lo studio di geometria euclidea, aritmetica di peano, teoria dei numeri reali, teoria pura degli insiemi, è stato condotto con successo perché per queste teorie si può definire un apposito linguaggio logico del prim'ordine con cui esprimere assiomi e teoremi. Codificare teorie all'interno di altre teorie complica decisamente le cose e su questo argomento so poco. (Ormai la logica è talmente sviluppata, sopratutto nella teoria dei modelli e teoria della dimostrazione, che è impossibile esserne totalmente aggiornati senza essere specialisti o logici professionisti)
Libri di logica consigliati:
Lolli, Introduzione alla logica formale (rimane piuttosto elementare)
Mendelson, Logica Matematica (ottimo, anche se datato e anche se le notazioni sono fastidiosamente vecchie)
Per dispense ben fatte on line, quelle del mio maestro:
http://www.scienze.univr.it/fol/main?en ... erro&grp=2
(guardare su logica 2005/2006)
Hodges, A Shorter model theory (bellissimo, qui si incomincia a fare sul serio!, ma bisogna già conoscere la logica)
@Thomas 
Secondo me la confusione che hai in testa deriva dal fatto che non conosci la distinzione tra verità di un enunciato in un modello e dimostrabilità dell'enunciato nel sistema assiomatico. Supponiamo di avere un enunciato A e un insieme di assiomi S. Noi ci possiamo chiedere due cose.
1) Esiste una dimostrazione di A da S?
2) Sia M un modello di S: A è vero in M?
Diciamo che A è dimostrabile a partire da S (e lo indichiamo con S |- A) , se esiste una sequenza di enunciati, scritti nel linguaggio di A e S, tale che ogni enunciato della sequenza o appartiene a S oppure deriva da enunciati che lo precedono nella sequenza tramite l'applicazione di una regola logica di inferenza (ad esempio da A->B e A possiamo ricavare B per modus ponens).
Il fatto che S |- A è un fatto assoluto, ovvero sintattico, non dipende dai modelli in cui interpretiamo gli enunciati, cioè prescinde dal significato che attribuiamo agli enunciati. E' possibile inoltre che non accada né che S |-A né che S |- non A. Diremo che S decide A se S |- A oppure S |- non A.
Se invece abbiamo un modello M che rende veri gli enunciati di S possiamo chiederci se M rende vero A o falso A: infatti ogni modello rende vero A oppure falso A. Abbiamo che S |-A e M rende vero S implica che A è vero in M.
Tuttavia il fatto che M renda vero S e A non implica affatto che S|-A.
Tornando a Goldbach, se essa è falsa in $(NN,+,*)$, possiamo dedurre che PA |- non A, e che dunque per definizione PA decide A.
Dunque se PA non decide Goldbach, Goldbach è vera in un particolare modello di PA, ovvero $(NN,+,*)$. Tuttavia ci sarà anche un altro modello M di PA che rende falsa Goldbach.
Se invece PA2 non decide Goldbach, Goldbach è vera in un particolare modello di PA2, ovvero $(NN,+,*)$. Non si possono trovare modelli di PA2 che rendono falsa Goldbach perché PA2 ha un solo modello.
Per la geometria euclidea GH4 (primi quattro postulati) vale lo stesso discorso di PA. Poiché GH non decide il V postulato, esiste un modello di GH4 che rende vero il postulato V e un modello di GH4 che rende falso il postulato V.
Tuttavia dal semplice fatto che il V postulato sia falso in $RR^2$, non potremmo dedurre che GH4 |- V postulato, perché nel linguaggio della geometria euclidea non è possibile esprimere il controesempio (non ci sono i numeri reali e tanto meno le equazioni $y=ax+b$).
Se non ti è chiaro anche questo discorso, allora "vai a leggerti un libro di logica"
Secondo me la confusione che hai in testa deriva dal fatto che non conosci la distinzione tra verità di un enunciato in un modello e dimostrabilità dell'enunciato nel sistema assiomatico. Supponiamo di avere un enunciato A e un insieme di assiomi S. Noi ci possiamo chiedere due cose.
1) Esiste una dimostrazione di A da S?
2) Sia M un modello di S: A è vero in M?
Diciamo che A è dimostrabile a partire da S (e lo indichiamo con S |- A) , se esiste una sequenza di enunciati, scritti nel linguaggio di A e S, tale che ogni enunciato della sequenza o appartiene a S oppure deriva da enunciati che lo precedono nella sequenza tramite l'applicazione di una regola logica di inferenza (ad esempio da A->B e A possiamo ricavare B per modus ponens).
Il fatto che S |- A è un fatto assoluto, ovvero sintattico, non dipende dai modelli in cui interpretiamo gli enunciati, cioè prescinde dal significato che attribuiamo agli enunciati. E' possibile inoltre che non accada né che S |-A né che S |- non A. Diremo che S decide A se S |- A oppure S |- non A.
Se invece abbiamo un modello M che rende veri gli enunciati di S possiamo chiederci se M rende vero A o falso A: infatti ogni modello rende vero A oppure falso A. Abbiamo che S |-A e M rende vero S implica che A è vero in M.
Tuttavia il fatto che M renda vero S e A non implica affatto che S|-A.
Tornando a Goldbach, se essa è falsa in $(NN,+,*)$, possiamo dedurre che PA |- non A, e che dunque per definizione PA decide A.
Dunque se PA non decide Goldbach, Goldbach è vera in un particolare modello di PA, ovvero $(NN,+,*)$. Tuttavia ci sarà anche un altro modello M di PA che rende falsa Goldbach.
Se invece PA2 non decide Goldbach, Goldbach è vera in un particolare modello di PA2, ovvero $(NN,+,*)$. Non si possono trovare modelli di PA2 che rendono falsa Goldbach perché PA2 ha un solo modello.
Per la geometria euclidea GH4 (primi quattro postulati) vale lo stesso discorso di PA. Poiché GH non decide il V postulato, esiste un modello di GH4 che rende vero il postulato V e un modello di GH4 che rende falso il postulato V.
Tuttavia dal semplice fatto che il V postulato sia falso in $RR^2$, non potremmo dedurre che GH4 |- V postulato, perché nel linguaggio della geometria euclidea non è possibile esprimere il controesempio (non ci sono i numeri reali e tanto meno le equazioni $y=ax+b$).
Se non ti è chiaro anche questo discorso, allora "vai a leggerti un libro di logica"
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo