2. Gödelsche Unvollständigkeit < axiomatisch < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:50 So 09.12.2012 | | Autor: | tobit09 |
Hallo zusammen,
der zweite Gödelsche Unvollständigkeitssatz, nach dem grob gesagt ZF im Falle seiner Konsistenz nicht die eigene Konsistenz beweist, bereitet mir Kopfzerbrechen. Ich meine nämlich (offensichtlich fälschlicherweise), dass damit die Konsistenz von ZF ausgeschlossen sei. Wo liegt mein Fehler in folgender Argumentation?
Angenommen ZF ist konsistent.
Da ZF nicht die eigene Konsistenz beweist, gibt es dann ein Modell M von ZF, das glaubt, das ZF inkonsistent sei.
Also glaubt $M$, es gäbe eine eine Herleitung des Satzes [mm] $\varphi:=(\exists x\colon \neg [/mm] (x=x))$ aus ZF.
Sei $H$ eine solche Herleitung, von der $M$ glaubt, sie beweise [mm] $\varphi$ [/mm] aus ZF.
Dann ist $H$ eine Herleitung von [mm] $\varphi$ [/mm] aus ZF. (*)
Also ist ZF inkonsistent, Widerspruch.
Meine Vermutung ist, dass die Schlussfolgerung (*) falsch ist. Das leuchtet mir aber noch nicht so recht ein. Wie kann M bei der Beurteilung, ob H eine korrekte Herleitung von [mm] $\varphi$ [/mm] aus ZF ist, falsch liegen? Glaubt nicht jedes Modell von ZF genau dann, eine Herleitung sei korrekt, wenn sie dies ist? Modelle von ZF verhalten sich doch "ganz natürlich" wie man es von Modellen der Mengenlehre erwartet...
Würde mich riesig freuen, wenn jemand den Knoten in meinem Kopf lösen würde!
Viele Grüße
Tobias
|
|
| |
|
Hallo Tobias!
> Hallo zusammen,
>
>
> der zweite Gödelsche Unvollständigkeitssatz, nach dem
> grob gesagt ZF im Falle seiner Konsistenz nicht die eigene
> Konsistenz beweist, bereitet mir Kopfzerbrechen. Ich meine
> nämlich (offensichtlich fälschlicherweise), dass damit
> die Konsistenz von ZF ausgeschlossen sei. Wo liegt mein
> Fehler in folgender Argumentation?
>
>
> Angenommen ZF ist konsistent.
>
> Da ZF nicht die eigene Konsistenz beweist, gibt es dann ein
> Modell M von ZF, das glaubt, das ZF inkonsistent sei.
Du meinst wohl eher Folgendes, oder?
Da [mm] $\omega$ [/mm] in ZF nicht ableitbar ist, gibt es ein Modell von ZF, das nicht Modell von [mm] $\omega$ [/mm] ist.
(Dabei ist [mm] $\omega$ [/mm] der ZF-Satz, der die Widerspruchsfreiheit von ZF ausdrückt.)
Ist das der Knackpunkt?
>
> Also glaubt [mm]M[/mm], es gäbe eine eine Herleitung des Satzes
> [mm]\varphi:=(\exists x\colon \neg (x=x))[/mm] aus ZF.
>
> Sei [mm]H[/mm] eine solche Herleitung, von der [mm]M[/mm] glaubt, sie beweise
> [mm]\varphi[/mm] aus ZF.
>
> Dann ist [mm]H[/mm] eine Herleitung von [mm]\varphi[/mm] aus ZF. (*)
>
> Also ist ZF inkonsistent, Widerspruch.
>
>
> Meine Vermutung ist, dass die Schlussfolgerung (*) falsch
> ist. Das leuchtet mir aber noch nicht so recht ein. Wie
> kann M bei der Beurteilung, ob H eine korrekte Herleitung
> von [mm]\varphi[/mm] aus ZF ist, falsch liegen? Glaubt nicht jedes
> Modell von ZF genau dann, eine Herleitung sei korrekt, wenn
> sie dies ist? Modelle von ZF verhalten sich doch "ganz
> natürlich" wie man es von Modellen der Mengenlehre
> erwartet...
>
>
> Würde mich riesig freuen, wenn jemand den Knoten in meinem
> Kopf lösen würde!
>
>
> Viele Grüße
> Tobias
LG mathfunnel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:35 Mi 26.12.2012 | | Autor: | tobit09 |
Hallo mathfunnel,
danke für deine Antwort! Freut mich, dass ich nun (quasi als Weihnachtsgeschenk  ) Antworten erhalten habe! 
> > Angenommen ZF ist konsistent.
> >
> > Da ZF nicht die eigene Konsistenz beweist, gibt es dann ein
> > Modell M von ZF, das glaubt, dass ZF inkonsistent sei.
>
> Du meinst wohl eher Folgendes, oder?
>
> Da [mm]\omega[/mm] in ZF nicht ableitbar ist, gibt es ein Modell von
> ZF, das nicht Modell von [mm]\omega[/mm] ist.
> (Dabei ist [mm]\omega[/mm] der ZF-Satz, der die
> Widerspruchsfreiheit von ZF ausdrückt.)
Ja, genau das meinte ich.
[mm] ($\omega$ [/mm] ist also ein Satz, der ausdrückt, dass [mm] $\varphi:=(\exists x\colon \neg(x=x))$ [/mm] nicht aus ZF ableitbar sei.)
> Ist das der Knackpunkt?
Leider fällt bei mir der Groschen noch nicht. Wo liegt nun mein Fehler?
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias!
Wir betrachten deine Aussage:
> Also glaubt $M$, es gäbe eine Herleitung des Satzes
> $ [mm] \varphi:=(\exists x\colon \neg [/mm] (x=x)) $ aus ZF.
In welchem Verhältnis stehen folgende Aussagen A) und B) zueinander und
zu deiner Formulierung?
A) $M$ ist ein Modell von [mm] $\neg \omega$.
[/mm]
B) [mm] $\neg \omega$ [/mm] folgt aus ZF.
Falls du weder A) noch B) meinst, dann habe ich dich immer noch nicht verstanden. Ich vermute aber, dass du jetzt klar siehst, oder?
LG mathfunnel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:51 Mi 02.01.2013 | | Autor: | tobit09 |
Hallo mathfunnel,
etwas verspätet herzlichen Dank für deine weiteren Antworten!
> Wir betrachten deine Aussage:
>
> > Also glaubt [mm]M[/mm], es gäbe eine Herleitung des Satzes
> > [mm]\varphi:=(\exists x\colon \neg (x=x))[/mm] aus ZF.
>
> In welchem Verhältnis stehen folgende Aussagen A) und B)
> zueinander und
> zu deiner Formulierung?
>
> A) [mm]M[/mm] ist ein Modell von [mm]\neg \omega[/mm].
>
> B) [mm]\neg \omega[/mm] folgt aus ZF.
Meine Aussage sollte die Bedeutung von Aussage A) ausdrücken, also äquivalent zu dieser sein.
Viele Grüße
Tobias
|
|
|
| |
|
Hallo Tobias!
Ich glaube jetzt zu wissen, wo der Hund begraben liegt.
Ich vermute, du glaubst, dass Folgendes aus ZF ableitbar ist:
[mm] $\neg\omega \leftrightarrow \varphi$
Das musst du nur noch beweisen. ;-)
LG mathfunnel
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:55 Mi 02.01.2013 | | Autor: | tobit09 |
> Ich vermute, du glaubst, dass Folgendes aus ZF ableitbar
> ist:
>
> [mm]\neg\omega \leftrightarrow \varphi[/mm]
>
> Das musst du nur noch beweisen.
Ich sehe nicht, an welcher Stelle ich das benötige...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 07:11 Do 03.01.2013 | | Autor: | mathfunnel |
Hallo Tobias!
> > Ich vermute, du glaubst, dass Folgendes aus ZF ableitbar
> > ist:
> >
> > [mm]\neg\omega \leftrightarrow \varphi[/mm]
> >
> > Das musst du nur noch beweisen.
> Ich sehe nicht, an welcher Stelle ich das benötige...
Du argumentierst so:
> Also glaubt $ M $, es gäbe eine Herleitung des Satzes $ [mm] \varphi:=(\exists x\colon \neg [/mm] (x=x)) $ > aus ZF.
Nach deiner Mitteilung soll das Folgendes heißen:
$ M $ ist ein Modell von $ [mm] \neg \omega [/mm] $.
Jetzt folgt:
> Sei $ H $ eine solche Herleitung, von der $ M $ glaubt, sie beweise [mm] $\varphi$ [/mm] aus ZF.
Dieser Satz ist nach deiner Übersetzung von 'glauben' wie folgt zu lesen:
$M$ ist ein Modell von 'H beweist [mm] $\varphi$'.
[/mm]
Das scheint mir nur sinnvoll, wenn man 'H beweist [mm] $\varphi$' [/mm] als [mm] $\neg \omega$ [/mm] interpretiert, da
es sich um einen ZF Ausdruck handeln muss!
Du drehst dich also im Kreis!
Dennoch glaubst du (jaja, ich weiß, dass du es nicht wirklich glaubst ) Folgendes bewiesen zu haben:
$ZF [mm] \vdash \varphi$.
[/mm]
An einer anderen Stelle sagst du selbst:
> Und dass $ [mm] \omega [/mm] $ in einem Modell nicht erfüllt ist, bedeutet nach meiner obigen Interpretation von $ [mm] \omega [/mm] $ ja gerade, dass es eine Herleitung von $ [mm] \varphi [/mm] $ aus ZF gibt.
Für mich sieht es also durchaus so aus, als ob du die von mir vermutete oder eine ähnliche Annahme triffst.
LG mathfunnel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:59 Do 03.01.2013 | | Autor: | tobit09 |
> > Und dass [mm]\omega[/mm] in einem Modell nicht erfüllt ist,
> bedeutet nach meiner obigen Interpretation von [mm]\omega[/mm] ja
> gerade, dass es eine Herleitung von [mm]\varphi[/mm] aus ZF gibt.
>
> Für mich sieht es also durchaus so aus, als ob du die von
> mir vermutete oder eine ähnliche Annahme triffst.
In der Tat hatte ich fälschlicherweise eine ähnliche Annahme:
> > In JEDEM ZF-Modell ist [mm] $\omega$ [/mm] genau dann erfüllt, wenn [mm] $\varphi$ [/mm] nicht aus ZF ableitbar ist.
Tatsächlich leistet [mm] $\omega$ [/mm] dies nur sicher für ZF-Modelle mit "gewöhnlichen natürlichen Zahlen".
|
|
|
| |
|
> Hallo zusammen,
>
> der zweite Gödelsche Unvollständigkeitssatz, nach dem
> grob gesagt ZF im Falle seiner Konsistenz nicht die eigene
> Konsistenz beweist, bereitet mir Kopfzerbrechen. Ich meine
> nämlich (offensichtlich fälschlicherweise), dass damit
> die Konsistenz von ZF ausgeschlossen sei. Wo liegt mein
> Fehler in folgender Argumentation?
>
> Angenommen ZF ist konsistent.
>
> Da ZF nicht die eigene Konsistenz beweist, gibt es dann ein
> Modell M von ZF, das glaubt, das ZF inkonsistent sei.
>
> Also glaubt [mm]M[/mm], es gäbe eine eine Herleitung des Satzes
> [mm]\varphi:=(\exists x\colon \neg (x=x))[/mm] aus ZF.
>
> Sei [mm]H[/mm] eine solche Herleitung, von der [mm]M[/mm] glaubt, sie beweise
> [mm]\varphi[/mm] aus ZF.
>
> Dann ist [mm]H[/mm] eine Herleitung von [mm]\varphi[/mm] aus ZF. (*)
>
> Also ist ZF inkonsistent, Widerspruch.
>
>
> Meine Vermutung ist, dass die Schlussfolgerung (*) falsch
> ist. Das leuchtet mir aber noch nicht so recht ein. Wie
> kann M bei der Beurteilung, ob H eine korrekte Herleitung
> von [mm]\varphi[/mm] aus ZF ist, falsch liegen? Glaubt nicht jedes
> Modell von ZF genau dann, eine Herleitung sei korrekt, wenn
> sie dies ist? Modelle von ZF verhalten sich doch "ganz
> natürlich" wie man es von Modellen der Mengenlehre
> erwartet...
>
> Würde mich riesig freuen, wenn jemand den Knoten in meinem
> Kopf lösen würde!
>
>
> Viele Grüße
> Tobias
Hallo Tobias,
ich bin erst jetzt auf deine Frage gestoßen, nachdem mathfunnel
nach 15 Tagen seit deiner Fragestellung eine erste Antwort gegeben hat.
Ich möchte zuerst darauf hinweisen, dass in deiner Argumentation
an keiner Stelle auf die Eigenschaften von ZF Bezug genommen
wird. Das bedeutet, dass du an die Stelle von "ZF" irgendein
beliebiges, ev. auch ganz rudimentäres logisches System "XY"
setzen könntest. Das stimmt schon mal ziemlich nachdenklich ...
Ein zweiter Punkt (nur als Bemerkung gemeint) : Du sprichst
von einem Modell, das "glaube" , dass ZF inkonsistent sei.
Dies ist wohl kaum eine angemessene Sprechweise in diesem
Zusammenhang.
Ich denke aber, dass der zentrale Punkt, um den es geht, der
Unterschied zwischen "Herleitbarkeit innerhalb eines definierten
logischen Systems" und "Wahrheit (bzw. Konsistenz) an sich" ist.
Du nimmst an, dass aus der Nicht-Beweisbarkeit von ZF innerhalb
von ZF selbst folgen müsse, dass es ein Modell (innerhalb ZF !)
geben müsse, in welchem ein Widerspruch in ZF mit ZF-Methoden
hergeleitet werden kann. Du forderst hier also das Prinzip des
"tertium non datur" auf einer Ebene heraus, welche innerhalb ZF
eben keine Grundlage hat ...
LG
Al-Chwarizmi
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:27 Mi 26.12.2012 | | Autor: | tobit09 |
Hallo Al-Chwarizmi,
auch dir vielen Dank für deine Antwort!
> Ich möchte zuerst darauf hinweisen, dass in deiner
> Argumentation
> an keiner Stelle auf die Eigenschaften von ZF Bezug
> genommen
> wird. Das bedeutet, dass du an die Stelle von "ZF"
> irgendein
> beliebiges, ev. auch ganz rudimentäres logisches System
> "XY"
> setzen könntest. Das stimmt schon mal ziemlich
> nachdenklich ...
Zum Beispiel für die ![[]](/images/popup.gif) Peano-Arithmetik ist meine Argumentation nicht anwendbar. An der Stelle, die ich mit (*) bezeichnet habe, geht es schief: Es gibt Nicht-Standard-Modelle der Peano-Arithmetik. Und [mm] $\omega_{PA}$ [/mm] (ein Satz, der die Konsistenz von PA codiert) drückt eben nur im Standard-Modell aus, dass [mm] $\varphi:=(\exists x\colon\neg(x=x))$ [/mm] nicht aus PA (Axiomensystem der Peano-Arithmetik) ableitbar ist.
Dagegen gibt es für ZF keine Unterscheidung in Standard- bzw. Nicht-Standard-Modelle. Die einzig sinnvolle mir einfallende Interpretation, in welchem Sinne [mm] $\omega$ [/mm] (s. mathfunnels Antwort) die Konsistenz von ZF ausdrückt, lautet: In JEDEM ZF-Modell ist [mm] $\omega$ [/mm] genau dann erfüllt, wenn [mm] $\varphi$ [/mm] nicht aus ZF ableitbar ist.
Falls ich mit dieser Interpretation falsch liegen sollte: In welchem Sinne drückt dann [mm] $\omega$ [/mm] die Konsistenz von ZF aus?
> Ein zweiter Punkt (nur als Bemerkung gemeint) : Du sprichst
> von einem Modell, das "glaube" , dass ZF inkonsistent sei.
> Dies ist wohl kaum eine angemessene Sprechweise in diesem
> Zusammenhang.
Damit meinte ich schlichtweg: ZF glaubt nicht an [mm] $\omega$. "$\mathfrak{M}$ [/mm] glaubt an [mm] $\psi$" [/mm] ist nur eine andere Sprechweise für "in [mm] $\mathfrak{M}$ [/mm] ist [mm] $\psi$ [/mm] erfüllt".
> Ich denke aber, dass der zentrale Punkt, um den es geht,
> der
> Unterschied zwischen "Herleitbarkeit innerhalb eines
> definierten
> logischen Systems" und "Wahrheit (bzw. Konsistenz) an
> sich" ist.
(Was verstehst du unter "Wahrheit an sich"?)
Nach dem Gödelschen Vollständigkeitssatz sind ja alle logischen Folgerungen aus ZF (d.h. alle in allen ZF-Modellen erfüllten Sätze) auch herleitbar.
> Du nimmst an, dass aus der Nicht-Beweisbarkeit von ZF
(Hier meinst du die Konsistenz von ZF, nicht ZF selbst, oder?)
> innerhalb
> von ZF selbst folgen müsse, dass es ein Modell (innerhalb
> ZF !)
(Was meinst du mit einem Modell innerhalb von ZF?)
> geben müsse, in welchem ein Widerspruch in ZF mit
> ZF-Methoden
> hergeleitet werden kann.
Ja. Denn Nicht-Beweisbarkeit von [mm] $\omega$ [/mm] aus ZF ist ja nach dem Gödelschen Vollständigkeitssatz gleichbedeutend damit, dass [mm] $\omega$ [/mm] nicht in allen Modellen von ZF erfüllt ist. Und dass [mm] $\omega$ [/mm] in einem Modell nicht erfüllt ist, bedeutet nach meiner obigen Interpretation von [mm] $\omega$ [/mm] ja gerade, dass es eine Herleitung von [mm] $\varphi$ [/mm] aus ZF gibt.
> Du forderst hier also das Prinzip
> des
> "tertium non datur" auf einer Ebene heraus, welche
> innerhalb ZF
> eben keine Grundlage hat ...
![[verwirrt]](/images/smileys/verwirrt.gif "[verwirrt]") Selbstverständlich sind in jedem vollständigen Kalkül der klassischen Prädikatenlogik erster Stufe Aussagen des Prinzips "tertium non datur" herleitbar.
Das Licht ist mir also leider noch nicht aufgegangen... Kannst du mir noch einmal weiterhelfen?
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:07 Mi 02.01.2013 | | Autor: | tobit09 |
Hallo Interessierte,
das Problem hat sich für mich nach Studium eines Skriptes zum Gödelschen Unvollständigkeitssatz geklärt:
[mm] $\omega$ [/mm] drückt nur in solchen Modellen von ZF die Konsistenz von ZF aus, deren natürliche Zahlen "unseren gewöhnlichen" natürlichen Zahlen entsprechen. Ich hatte angenommen, dass dies auf ALLE Modelle von ZF zutreffe.
Tatsächlich kann ein Modell von ZF zu meiner Überraschung sehr wohl mehr "natürliche Zahlen" enthalten als unsere gewöhnlichen natürlichen Zahlen!
Damit müssen auch Objekte, die ein ZF-Modell für eine Formel oder eine Herleitung hält, gar keiner wirklichen Formel oder Herleitung in unserem Sinne entsprechen.
Danke den beiden Antwortgebern für Ihre Impulse, die mich letztendlich auf die richtige Spur gebracht haben!
Viele Grüße
Tobias
|
|
|
|
