Hinweis auf die DSGVO: Auf unserer Seite werden keine Dritt-Anbieter-Cookies verwendet und nur Daten erfasst, welche für das Minimum an Board-Funktionalität notwendig sind.
Bevor Sie sich registrieren oder das Board verwenden, lesen Sie bitte zusätzlich die DSGVO-Erklärung, welche in der Navigationsleiste verlinkt ist.

Kurzfassung der unserer Meinung nach wichtigsten DSGVO-Punkte:
Es kann vorkommen, dass Benutzer eigenverantwortlich Videos oder sonstige Medien in ihren Beiträgen verlinken, welche beim Aufruf der Forenseite als Teil der Seite samt zugehörigem Material mitgeladen werden. Sollten Sie dies nicht wünschen, verwenden Sie beim Benutzen des Forums einen Blocker wie z.B. uMatrix, welcher das Laden von Inhaltsblöcken von Fremd-URLs effektiv unterbinden kann.
Wir blenden keine Werbung ein und schränken die Inhalte in keinster Weise bei Benutzung von Addblockern ein. Dadurch ist die Grundfunktionalität des Forums auch bei vollständigem Blockieren von Drittanbieter-Inhalten stets gegeben.

Cookies werden unsererseits nur verwendet um das Einloggen des Benutzers für die Dauer der Forenbenutzung zu speichern. Es steht dem Benutzer frei die Option 'Angemeldet bleiben' zu verwenden, damit der Cookie dauerhaft gespeichert bleibt und beim nächsten Besuch kein erneutes Einloggen mehr notwendig ist.
EMail-Adressen werden für Kontakt bei wichtigen Mitteilungen und zur Widerherstellung des Passwortes verwendet. Die verwendeten IPs können von uns ohne externe Hilfsmittel mit keiner realen Person in Verbindung gebracht werden und werden nach spätestens 7 Tagen gelöscht. Diese IPs werden höchstens verwendet um Neuanmeldungen unerwünschter oder gesperrter Nutzer zu identfizieren und zu unterbinden. Wir behalten uns daher vor bei Verdacht, die Frist für die IP-Löschung auf maximal 14 Tage zu verlängern.
Unsere Webseite läuft auf einem virtuellen Linux-Server, welcher von einem externen Anbieter gehostet wird. Etwaige Verstöße der DSGVO-Auflagen seitens dieses deutschen Hosters können wir nicht feststellen und somit auch nicht verfolgen.
Wir halten Backups unserer Datenbanken, welche in regelmäßigen Abständen als Schutz vor Katastrophen, Hackerangriffen und sonstigen Ausfällen erstellt werden. Sollte ein Nutzer die Löschung seiner Daten wünschen, betrachten wir es als Unzumutbar die Backups auch von den Daten zu befreien, da es sich hierbei um eine mehrtägiges Unterfangen handelt - dies ist für eine Einzelperson beim Betrieb eines privaten Forums nicht zumutbar möglich ohne das Backup komplett zu löschen.
Sollten Sie etwas gegen die dauerhafte anonyme Speicherung ihrer EMail-Adresse, ihres Pseudonyms und ihrer Beiträge in einem Backup haben, sehen Sie von der Registrierung in diesem Forum ab. Für Mitglieder, welche vor dem 25.05.2018 registriert waren steht jedoch das Recht im Raum, eine Löschung der Datenbank-Backups zu beantragen.



Wenn dies Ihr erster Besuch hier ist, lesen Sie bitte zunächst die FAQs sowie die wesentlichen Regeln zur Benutzung des Forums.
Um an den Diskussionen teilnehmen zu können, müssen Sie sich zunächst registrieren.

Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Mathematische Fragestellungen
Antworten
Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 19. Apr 2016, 14:15

Mit dem Halteproblem von Turing kann man Gödel's ersten Unvollständigkeitssatz recht gut nachvollziehen (eine der besten Erklärungem, die sogar ich verstehe: https://www.youtube.com/watch?v=jDGKUYTBubQ).

Denn im Halteproblem konstruiert man eine Turingmaschine T, die anhalten soll, wenn ihr Inputprogramm nicht anhält und nicht anhalten soll, wenn das Inputprogramm anhält. T wird dann T selbst als Input gegeben. Hält T nicht, dann soll T halten und umgekehrt, beide Male ein Widerspruch, woraus folgt, dass keine Turingmaschine jeden Input entscheiden kann (oder nur eine widersprüchliche Turingmaschine das könnte, weil aus Widersprüchen alles folgt). Das ist ziemlich genau Gödel's erstes Unvollständigkeitstheorem, wonach nicht die Wahrheit jedes arithemtischen Satzes entschieden werden kann (oder nur, wenn das System widersprüchlich ist, weil dann alles beweisbar ist). Der Unterschied liegt eigentlich nur darin, dass Turing Programme und Gödel Aussagen als Bausteine verwendet, wobei die Konstruktion der problematischen Turingmaschine sehr viel leichter nachvollziehbar ist als die Konstruktion des Gödelsatzes (finde ich).

Nun ist der 2. Unvollständigkeitssatz für mich (als Skeptiker) viel interessanter, weil er besagt, dass jedes System widersprüchlich sein kann (und das System selbst das nicht widerlegen/beweisen kann). Gibt es dazu ein anschauliches Pendant bei Turing? Oder wie würdet ihr das sonst jemandem erklären wollen, der den 1. Unvollständigkeitssatz versteht, den 2. aber nicht.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 19. Apr 2016, 19:51

Zunächst mal eine sehr kurze Zusammenfassung (nach Wikipedia)

Der erste Gödelsche Unvollständigkeitssatz besagt, dass es in hinreichend mächtigen, widerspruchsfreien Systemen immer unbeweisbare, jedoch wahre Aussagen gibt: Jedes hinreichend mächtige, rekursiv aufzählbare formale System ist entweder widersprüchlich oder unvollständig.
Der zweite Gödelsche Unvollständigkeitssatz besagt, dass hinreichend mächtige, widerspruchsfreie Systeme ihre eigene Widerspruchsfreiheit nicht beweisen können: Jedes hinreichend mächtige, konsistente formale System kann die eigene Konsistenz nicht beweisen.

Nach den Erkenntnissen von Turing gilt: In jedem formalen System lassen sich Aussagen formulieren, die weder bewiesen noch widerlegt werden können. Das Halteproblem beschreibt explizit eine solche Aussage. Aus der Unlösbarkeit des Halteproblems folgt, dass es mathematische Funktionen gibt, die zwar wohldefiniert sind, deren Werte sich jedoch nicht für jeden Parameter berechnen lassen. Ein bekanntes Beispiel für eine solche Funktion ist die Radó-Funktion.

Damit ist zunächst mal richtig, dass dieser Satz von Turing dem ersten Gödelschen Unvollständigkeitssatz entspricht. Ich sehe jedoch nicht, wie es möglich sein soll, den zweiten Gödelschen Unvollständigkeitssatz auf Turingmaschinen abzubilden.

Das Problem ist doch folgendes:

Der erste Gödelschen Unvollständigkeitssatz besagt im wesentlichen, dass wenn ich ein Axiomensystem in einen "Beweisgenerator" füttere, der nach konsistenten Regeln Theoreme generiert, es immer Theoreme gibt, die dem formalen System nicht widersprechen, die der Generator jedoch nicht generiert. Kurz: es gibt mehr wahre als beweisbare bzw. generierbare Theoreme.

Das Ergebnis von Turing besagt im wesentlichen, dass wenn ich Input in einen "Zahlengenerator" füttere, der nach konsistenten Regeln Output generiert, es immer Zahlenfolgen gibt, die wohldefiniert sind, jedoch vom Generator nicht generiert werden. Kurz: es gibt mehr wohldefinierte als berechenbare bzw. generierbare Zahlenfolgen bzw. Funktionen.

Um nun den zweiten Gödelschen Unvollständigkeitssatz im Turingschen Sinne betrachten zu können, müsste man die Aussage, dass eine Turingmaschine bestimmte Zahlenfolgen nicht generieren kann, selbst als Turingmaschine formulieren.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 20. Apr 2016, 09:25

Weißt du mit welcher Idee, Gödel seinen 2. Unvollständigkeitsbeweis erbringt? Denn schon das verstehe ich nicht richtig.

Ich stelle mir das auf's Erste so vor: Gödel wußte durch sein erstes Theorem, dass es in einem hinreichend mächtigen System mind. einen Satz S gibt mit der Eigenschaft: Weder S noch ~S ist beweisbar. Innerhalb des Systems wäre damit völlig offen, ob dieser S wahr (dann Unvollständigkeit des Systems) oder S faslch (dann Inkonsistenz des Systems) wäre. Doch dann kann das System die Alternative der Falschheit des Satzes und damit der Inkonsistenz nicht ausschließen. Das wäre dann der 2. Unvollständigkeitssatz, der damit lediglich eine Fußnote des ersten wäre.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 21. Apr 2016, 07:03

Beim ersten Unvollständigkeitssatz liegst du falsch. Es handelt sich darum, dass weder S noch ~S beweisbar sind, deswegen darfst du einen von beiden als neues Axiom hinzunehmen. Dadurch wird dein Axiomensystem nicht inkonsistent (wenn es dies nicht schon vorher war, was ausgeschlossen ist, denn wenn ein Axiomensystem inkonsistent wäre, dann wären sowohl S als auch ~S beweisbar).

Ein Beispiel für S bzw. ~S ist die Kontinuumsypothese für ZFC.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 24. Apr 2016, 15:12

tomS hat geschrieben:Beim ersten Unvollständigkeitssatz liegst du falsch. Es handelt sich darum, dass weder S noch ~S beweisbar sind, deswegen darfst du einen von beiden als neues Axiom hinzunehmen.
Wir wissen durch den ersten U-Satz, dass weder S noch ~S beweisbar sind. Wir wissen aber auch, dass entweder S oder ~S falsch sein muss. Solange beide nicht beweisbar sind ist unser System widerspruchsfrei, denn wäre es widersprüchlich, so müssten beide beweisbar sein (ex falso quodlibet). Richtig?

Wenn du aber einen der beiden Sätze (S oder ~S) als Axiom hinzunimmst und es ist dies die falsche Aussage, dann wird das System auf einmal widersprüchlich. Woher weiß nun unser System, welcher der beiden Sätze wahr und damit als Axiom hinzu zu nehmen ist? Das weiß es aus seiner Innenarchitektur heraus nicht, denn sohwohl S als auch ~S sind ja beide gleich unbeweisbar. M.a.W.: Entweder unser System bescheidet sich mit seiner Unvollständigkeit oder es entscheidet sich für einen der beiden Sätze als Axiom und geht damit das Risiko ein, widersprüchlich zu werden. Ein angeblicher Beweis, dass dieses Risiko nicht besteht und das System sich sicher richtig entschieden hat, muss falsch sein und damit das System als Ganzes.

So reime ich mir das jedenfalls zusammen. Es ist auf jeden Fall bemerkenswert, dass in Vorlesungsvideos immer nur der erste U-Satz gezeigt wird, der zweite wird nur kurz erwähnt. Woran mag das liegen?

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 24. Apr 2016, 15:23

Es geht mir um Folgendes: Die Folge 1/n (n € IN) läuft doch zum Grenzwert Null, wenn n gegen unendlich geht. Wieso sagt der Mathematiker das Unterstrichene? Ergibt sich das nicht bereits daraus, dass n für beliebige natürliche Zahlen steht und es eben nicht endlich viele davon gibt?

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 24. Apr 2016, 16:38

Pippen hat geschrieben:
tomS hat geschrieben:Beim ersten Unvollständigkeitssatz liegst du falsch. Es handelt sich darum, dass weder S noch ~S beweisbar sind, deswegen darfst du einen von beiden als neues Axiom hinzunehmen.
Wir wissen durch den ersten U-Satz, dass weder S noch ~S beweisbar sind. Wir wissen aber auch, dass entweder S oder ~S falsch sein muss ... Richtig?
Nein, leider nicht richtig.

Wenn weder S noch ~S innerhalb eines gegebenen Axiomensystems beweisbar sind, dann ist weder S entweder wahr oder falsch, noch ist ~S entweder wahr oder falsch. Beide sind unbeweisbar. Punkt.
Pippen hat geschrieben:Wenn du aber einen der beiden Sätze (S oder ~S) als Axiom hinzunimmst und es ist dies die falsche Aussage ...
Aus dem oben gesagten folgt, dass das nicht zutrifft. Da sowohl S als auch ~S unbeweisbar sind, ist sowohl S als auch ~S mit dem Axiomensystem verträglich (natürlich immer nur einer von beiden, nie beide zusammen)
Pippen hat geschrieben:Woher weiß nun unser System, welcher der beiden Sätze wahr und damit als Axiom hinzu zu nehmen ist?
Das weiß das System gerade nicht; das ist die wesentliche Aussage von Gödels Satz.

Ich habe den Eindruck, du denkst, S und ~S seien unbeweisbar, allerdings sei einer von beiden wahr. Das ist nicht der Fall! Im Kontext eines Axiomensystems bedeutet beweisbar und wahr exakt das selbe! Wenn darüberhinaus meinst, einer der beiden Sätze sei "tatsächlich wahr", dann befindest du dich nicht mehr im Kontext des Axiomensystems.
Pippen hat geschrieben:Entweder unser System bescheidet sich mit seiner Unvollständigkeit oder es entscheidet sich für einen der beiden Sätze als Axiom und geht damit das Risiko ein, widersprüchlich zu werden.
Das System entscheidet sich überhaupt nicht. Aus dem System folgt die Unentscheidbarkeit, mehr nicht.

Was du damit anfängst, ist deine Entscheidung.
Pippen hat geschrieben:Ein angeblicher Beweis, dass dieses Risiko nicht besteht ...
Natürlich! Gödels Satz ist genau dieser Beweis.

Anmerkung: der aus Gödels Theorem folgende Satz S sowie andere unentscheidbar Sätze sind üblicherweise zu kompliziert, um als Axiome geeignet zu sein.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 24. Apr 2016, 16:55

Zu Erinnerung: Ein Beispiel für S bzw. ~S ist die Cantorsche Kontinuumsypothese CH für ZFC.

Deren Unentscheidbarkeit wurde von Gödel sowie Cohen gezeigt. Gödel zeigte die Verträglichkeit von CH mit ZFC, d.h.: wenn ZFC widerspruchsfrei ist, dann auch "ZFC + CH"; Cohen zeigte die Verträglichkeit von ~CH mit ZFC, d.h.: wenn ZFC widerspruchsfrei ist, dann auch "ZFC + ~CH";

Gemäß Gödel folgt also, dass die Kontinuumshypothese aus ZFC nicht widerlegt werden kann. Gemäß Cohen folgt, die Kontinuumshypothese aus ZFC nicht bewiesen werden kann. Damit ist die Kontinuumshypothese unabhängig von ZFC, d.h. weder beweisbar noch widerlegbar.

Das bedeutet u.a., dass es möglich ist, Mengenlehren durch Hinzunahme von Axiomen X, X', ... zu konstruieren, wobei je nach Wahl von X, X', ... entweder CH oder ~CH beweisbar wird. D.h. es kann eine Mengenlehre ZFCX geben, in der CH beweisbar (und ~CH widerlegbar) ist. Und es kann eine andere Mengenlehre ZFCX' geben, in der CH widerlegbar ist.

Die Axiome X, X', ... sind dabei nicht unbedingt CH oder ~CH selbst.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 25. Apr 2016, 00:23

tomS hat geschrieben:Ich habe den Eindruck, du denkst, S und ~S seien unbeweisbar, allerdings sei einer von beiden wahr.
Ja, das denke ich.
Das ist nicht der Fall! Im Kontext eines Axiomensystems bedeutet beweisbar und wahr exakt das selbe!
Nehmen wir an, das wäre so, d.h. "beweisbar" = "wahr". Dann gilt: "S und ~S sind nicht beweisbar" = "S und ~S sind nicht wahr". Doch "S und ~S sind nicht wahr" ist ganz offensichtlich ein Widerspruch, weil S und ~S den gleichen Wahrheitswert 'nicht-wahr' hätten. Damit wäre auch "S und ~S sind nicht beweisbar" widersprüchlich. Genau deshalb muss Gödel mit Beweisbarkeit etwas anderes als Wahrheit gemeint haben, übrigens auch deshalb, weil der Gödelsatz "Ich bin nicht beweisbar" nach deiner Lesart auch "Ich bin nicht wahr" lauten könnte und damit hätte Gödel in seinem System eine Antinomie abgeleitet, die das System natürlich ebenfalls widersprüchlich machen würde.

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 25. Apr 2016, 07:00

Pippen hat geschrieben:
tomS hat geschrieben:Ich habe den Eindruck, du denkst, S und ~S seien unbeweisbar, allerdings sei einer von beiden wahr.
Ja, das denke ich.
Das ist ein Denkfehler. Es gibt für mathenatische Sätze keine Wahrheit jenseits der Beweisbarkeit. Ein Satz S, der nicht beweisbar ist, ist nicht wahr. Ein Satz, der nicht widerlegbar ist, ist nicht falsch. Ein Satz, der weder beweisbar noch widerlegbar ist, ist weder wahr noch falsch. Woher soll die Wahrheit eines Satzes stammen, wenn nicht aus einem Beweis?

Es gilt ja:
Pippen hat geschrieben:
Im Kontext eines Axiomensystems bedeutet beweisbar und wahr exakt das selbe!
Nehmen wir an, das wäre so, d.h. "beweisbar" = "wahr". Dann gilt: "S und ~S sind nicht beweisbar" = "S und ~S sind nicht wahr". Doch "S und ~S sind nicht wahr" ist ganz offensichtlich ein Widerspruch, weil S und ~S den gleichen Wahrheitswert 'nicht-wahr' hätten. Damit wäre auch "S und ~S sind nicht beweisbar" widersprüchlich. .
Nein, das gilt nicht, wenn man in "S und ~S sind nicht wahr" das "nicht wahr" mit "falsch" übersetzt; das ist nicht zulässig, da auch die Falschheit nicht beweisbar ist. Es gibt hier offensichtlich drei Wahrheitswerte, nämlich "wahr", "falsch" und "weder beweisbar noch widerlegbar" = "weder wahr noch falsch".
Pippen hat geschrieben:Genau deshalb muss Gödel mit Beweisbarkeit etwas anderes als Wahrheit gemeint haben, übrigens auch deshalb, weil der Gödelsatz "Ich bin nicht beweisbar" nach deiner Lesart auch "Ich bin nicht wahr" lauten könnte und damit hätte Gödel in seinem System eine Antinomie abgeleitet, die das System natürlich ebenfalls widersprüchlich machen würde.
Vorsicht. Ich habe nicht behauptet, dass "nicht beweisbar" = "nicht wahr" bedeutet, sondern lediglich, dass "beweisbar" = wahr" bedeutet; das ist ein Unterschied.

Außerdem habe ich geschrieben "Im Kontext eines Axiomensystems" und das ist enorm wichtig. Der Gödelsatz "Dieser Satz ist nicht beweisbar" ist im Kontext des Axiomensystems formulierbar jedoch nicht beweisbar. Er ist erst auf einer Metaebene als <wahr> erkennbar; man muss dazu sozusagen "aus dem Axiomensystem heraustreten".

Gödels Wahrheitsbegriff im Kontext des Axiomensystems deckt sich mit Beweisbarkeit.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 25. Apr 2016, 12:25

Ok, dann war es ein Mißverständnis. Denn was du zuletzt schriebst, meine ich gerade: S und ~S sind in einem Metasystem zu unserem System entweder wahr oder falsch, im System selbst sind sie beide nicht beweisbar. Was folgt daraus?

Wenn wir mal davon ausgehen, beim Beweisen keine Fehler zu machen, dann folgt daraus zunächst, dass unser System nicht widersprüchlich sein kann, denn wäre es widersprüchlich, dann müssten S und ~S beweisbar sein. Weiterhin folgt, dass es unvollständig ist, denn es stünde ja fest, dass mind. ein wahrer Satz aus unserem System dort nicht beweisbar ist. Das ist die Quintessenz des ersten Unvollständigkeitssatzes.

Und genau hier verstehe ich nicht, wo da noch Raum für den zweiten Unvollständigkeitssatz sein soll, denn wir haben ja schon festgestellt, dass unser System konsistent sein muss, weil eben nicht alles beweisbar ist. Das kann das System "selbst" auch überprüfen, es muss nur schauen, ob mind. einer seiner Sätze nicht beweisbar ist und es wüßte: "Ich bin konsistent". Deshalb verstehe ich da Gödel nicht, wenn er glaubte, solche Konsistenzbeweise seien unmöglich - für mich sind sie möglich, sogar recht leicht. Wo liegt da mein falsches Verständnis?

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 25. Apr 2016, 13:18

Pippen hat geschrieben:Denn was du zuletzt schriebst, meine ich gerade: S und ~S sind in einem Metasystem zu unserem System entweder wahr oder falsch, im System selbst sind sie beide nicht beweisbar. Was folgt daraus?
Daraus folgt, dass du frei bist in der Wahl des Metasystems. Du kannst verschiedene Metasysteme betrachten, in manchen ist S beweisbar und damit wahr, in manchen ist ~S beweisbar und damit wahr, in wieder anderen bleiben beide unbeweisbar.
Pippen hat geschrieben:... dann folgt daraus zunächst, dass unser System nicht widersprüchlich sein kann, denn wäre es widersprüchlich, dann müssten S und ~S beweisbar sein.
Nein, das folgt daraus nicht, denn die exakte Formulierung der Gödelschen Sätze lautet (am Bsp. CH in ZFC) präzise ...
tomS hat geschrieben:... wenn ZFC widerspruchsfrei ist, dann auch "ZFC + CH"; wenn ZFC widerspruchsfrei ist, dann auch "ZFC + ~CH";
Gödels Satz besagt nicht einfach, dass S und ~S unbeweisbar sind, sondern dass sie unter der Voraussetzung der Widerspruchsfreiheit unbeweisbar sind.
Pippen hat geschrieben:Und genau hier verstehe ich nicht, wo da noch Raum für den zweiten Unvollständigkeitssatz sein soll, denn wir haben ja schon festgestellt, dass unser System konsistent sein muss, ...
Nochmal: Gödels erster Unvollständigkeitssatz wird unter der Voraussetzung der Widerspruchsfreiheit bewiesen.
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 25. Apr 2016, 14:21

Ach ja, das stimmt. S und ~S sind unbeweisbar unter der Voraussetzung der Widerspruchsfreiheit des Systems, aber ob diese Voraussetzung beim System tatsächlich vorliegt, ist eine andere Frage, die Gödel mit dem 2. U-Satz beantwortet: Das System selbst kann seine Widerspruchsfreiheit nicht beweisen. Hast du eine grobe Vorstellung, wie Gödel diesen 2. U-Satz beweist?

Benutzeravatar
tomS
Ehrenmitglied
Ehrenmitglied
Beiträge: 10670
Registriert: 19. Nov 2007, 20:29

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von tomS » 25. Apr 2016, 15:48

Pippen hat geschrieben:S und ~S sind unbeweisbar unter der Voraussetzung der Widerspruchsfreiheit des Systems, ...
ja
Pippen hat geschrieben:... aber ob diese Voraussetzung beim System tatsächlich vorliegt, ist eine andere Frage, die Gödel mit dem 2. U-Satz beantwortet: Das System selbst kann seine Widerspruchsfreiheit nicht beweisen.
ja
Pippen hat geschrieben:Hast du eine grobe Vorstellung, wie Gödel diesen 2. U-Satz beweist?
Ich kann dich zunächst mal auf die Wikipedia verweisen, aber das ist m.E. sehr fomal und wenig allgemeinverständlich
https://de.wikipedia.org/wiki/Beweise_d ... gkeitssatz
Gruß
Tom

Der Wert eines Dialogs hängt vor allem von der Vielfalt der konkurrierenden Meinungen ab.
Sir Karl R. Popper

Pippen
Ehrenmitglied
Ehrenmitglied
Beiträge: 2071
Registriert: 9. Jul 2010, 04:02

Re: Visualisierung des 2. gödelschen U-Theorem's mittels des Halteproblems?

Beitrag von Pippen » 8. Mai 2016, 18:22

Ok, ich versuche mich nochmal, die beiden Grundideen der Gödelschen Unvollständigkeitsbeweise möglichst einfach und doch präzise darzustellen, wobei wohl die eigentliche Leistung Gödel's darin zu liegen scheint, zu zeigen, dass unsere Arithmetik und alles ab PL, 2. Stufe, (leider) schon stark genug ist, Systeme herzustellen, die unvollständig oder inkonsistent sind und die ihre eigene Konsistenz nie beweisen können.

1. Unvollständigkeitssatz

Zur Erinnerung definieren wir die Vollständigkeit eines (S)ystems dadurch, dass es für eine Aussage entweder 0 (Widerlegbarkeit) oder 1 (Beweisbarkeit) ausgibt. Wir setzen außerdem voraus, dass S konsistent ist, d.h. 0 und 1 nicht gleichzeitig auftreten darf. Wir definieren nun eine (A)ussage wie folgt: Wenn S = 0, dann A = 1, wenn S = 1, dann A = 0. Wir geben A in S. Wegen der Konsistenzannahme kann S weder 0 noch 1 ausgeben, weil beides widersprüchlich wäre. Damit gäbe es mind. eine Aussage, die (ein konsistentes) S weder beweisen noch widerlegen kann.

2. Unvollständigkeitssatz

Sei S in der Lage, den 1. Unvollständigkeitssatz zu formulieren, das heißt: wenn S konsistent ist, dann ist A in S weder beweisbar noch widerlegbar (= unbeweisbar). Nehmen wir an, S könnte die eigene Konsistenz beweisen. Dann folgt mit modus ponens in S der Beweis dafür, dass A in S unbeweisbar ist, was ein Widerspruch wäre, so dass die Konsistenzannahme falsch sein muss.

Meinungen? Korrekturen?

Ein hochinteressantes Folgeproblem ist nun, dass die beiden o.g. Unvollständigkeitssätze selbst wieder in einem System konstruiert und bewiesen werden, welches - wenn die beiden Unvollständigkeitssätze wahr wären - selbst unvollständig oder inkonsistent sein könnte, was wiederum bedeuten würde, dass die beiden Unvollständigkeitssätze falsch sein könnten, wenn sie zB auf einem inkonsistenten System beruhten. MaW: Sind die Unvollständigkeitssätze wahr, dann besteht trotzdem und gerade die Möglichkeit, dass sie falsch sind. Wieso werden dann diese Sätze in der Mathematik als Beweise anerkannt? So darf das eigentlich in einer Wissenschaft nicht sein!

Antworten