Unvollständigkeitssätze

27.03.2020, 20:52

Pippen

Unvollständigkeitssätze

1. ME setzen die o.g. Sätze von Gödel voraus, dass das betreffende formale System imstande ist, unendlich viele Formeln zu bilden. Meine Überlegung: Könnte man in dem System nur endlich viele Formeln bilden, dann könnte man zu jeder ein positives oder negatives Axiom bilden (je nachdem, ob sie wahr sein soll) und damit wäre jede Formel des System beweisbar oder widerlegbar, keine weder noch. Denke ich da richtig?

2. Gödel's erster U-Satz hängt ja sehr vom sog. Diagonalisierungslemma (Fixpunktsatz) ab. Ich lese da oft, dass die Idee von Cantor's Diagonalargumenten stammt, habe aber bei Beweisen des Diagonalisierungslemmas noch nie sowas wie die dortige Tabellenform mit der Diagonalen gesehen. Kann man das Diagonalisierungslemma so ähnlich erklären, wie damals Cantor die Überabzählbarkeit von IR - eben mit einer Liste und der dortigen Diagonalen?

29.03.2020, 10:09

Elvis

Auf diesen Beitrag antworten »

1. Es gibt kein endliches formales System, das alle Aussagen über die natürlichen Zahlen enthält.
2. Siehe die schwer verständliche Originalarbeit von Kurt Gödel (Seite 175) oder das leicht verständliche Buch von Dirk W. Hoffmann (Seite 133).

31.03.2020, 04:42

Pippen

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
1. Es gibt kein endliches formales System, das alle Aussagen über die natürlichen Zahlen enthält.

Ja, aber mein Punkt ist ein Anderer: ich glaube, jedes endliche formale System (zB ein System wo es nur 100 Mrd. natürliche Zahlen gibt, also 100.000.000.000 die größte natürliche Zahl wäre) ist vollständig und kann seine eigene Konsistenz beweisen, weil man - platt gesagt - einfach eine Liste mit allen (endlich vielen) Formeln aufstellen und als Axiome verwenden könnte und anschließend auf die Liste sehen und ihre Konsistenz prüfen könnte. Gödel's Theoreme würden dann notwendig unendliche Mengen voraussetzen. Ist das so oder denke ich (mal wieder) falsch?

Zitat:

2. Siehe die schwer verständliche Originalarbeit von Kurt Gödel (Seite 175) oder das leicht verständliche Buch von Dirk W. Hoffmann (Seite 133).

Auch Hoffmann erklärt nicht, warum es Diagonal-Lemma heißt und angeblich von Cantor inspiriert ist. Meine bisherige Spekulation geht so:

Die Peano-Arithmetik hat abzählbar viele Formeln mit freien Variablen, d.h. man könnte jede Formel in unendlich vielen Zeilen auflisten. In die Spalten trägt man die natürlichen Zahlen ein. Anschließend trägt man für jede Zeilen-Spalten-Kombination ein, ob für die betreffende natürliche Zahl in die freie Variable eingesetzt, ein Beweis existiert. Das sähe dann etwa so aus:

..............1.....2....3...
Formel1...|-...~|-...|-...
Formel2...|-.....|-...|-...
Formel3.. |-...~|-...|-...
Formel4...|-...~|-...|-...

Jetzt konstruieren wir eine Formel, welche über die Diagonale spricht und festlegt, dass dort jeweils genau das Gegenteil gelten soll. Diese Formel wäre damit nicht in der Liste und damit außerhalb jeder Beweisbarkeit (die ja durch die o.g. Matrix vorgegeben wird). In diesem Fall würde ich kapieren, warum man vom Diagonalisiierungslemma spricht, aber ich weiß nicht, ob das überhaupt so gemeint wird.

31.03.2020, 07:16

Elvis

Auf diesen Beitrag antworten »

1. Ich verstehe nicht, warum man über endlich viele natürliche Zahlen nur endlich viele Aussagen machen sollte. Philosophen und Theologen brauchen auch nur endlich viele Gegenstände um endlos lange zu reden und dicke Bücher zu schreiben.
2. Auf Seite 133 oben steht die Tabelle bei Hoffmann, die den entsprechenden Beweisteil von Gödel illustriert. Es ist nicht nötig, das zu zerreden, wenn du es nicht kennst.

31.03.2020, 08:04

G310320

Auf diesen Beitrag antworten »

Zitat:

Ich verstehe nicht, warum man über endlich viele natürliche Zahlen nur endlich viele Aussagen machen sollte.

Was meint hier "Aussagen"? Was fällt alles darunter? verwirrt

31.03.2020, 08:50

Elvis

Auf diesen Beitrag antworten »

Eine Aussage im Sinne der Aussagenlogik ist ein wahrer oder falscher Satz der zugrunde liegenden formalen Sprache.
Aussagen: "1+1=2" ist wahr, "1+1=3" ist falsch.

Nennen wir die endlich vielen Zahlen $\begin{eqnarray*} P-Zahlen \end{eqnarray*}$ . Dann definiere ich die $\begin{eqnarray*} E-Zahlen \end{eqnarray*}$ als $\begin{eqnarray*} \{n+m:n\in P-Zahlen, m\in P-Zahlen \vee m\in E-Zahlen\} \end{eqnarray*}$ , so ist $\begin{eqnarray*} \mathbb N=E-Zahlen \end{eqnarray*}$ , und schon haben wir die gesamte Arithmetik neu erfunden. Wie es möglich sein soll, darüber nur endlich viele Aussagen zu machen, kann ich nicht verstehen.

31.03.2020, 12:11

Pippen

Auf diesen Beitrag antworten »

@ elvis:

1. Es geht um die Frage, ob ein formales System, in dem sich nur endlich viele Formeln bilden lassen, unvollständig sein kann. Als Beispiel habe ich dir eine Arithmetik gegeben, die nur auf x natürliche Zahlen zugeschnitten ist, meinetwegen steill dir eine Arithemtik vor, die per Axiom nur 0 und 1 kennt und sonst keine andere Zahl und dann halt die üblichen Rechenregeln. Das 'Warum' ist hier völlig egal. Mich interessiert, ob Gödel's Theoreme Unendlichkeiten brauchen. Das ist der Hintergrund meiner Frage.

2. Hoffmann's Diagramm verwirrt mehr als es zeigt. Dort läßt sich gerade kein Diagonalargument erkennen, wie wir es von Cantor kennen und wie ich es versuche zu interpretieren. Bei meiner Interpretation erkennt man die Analogie zu Cantor, aber die Frage ist eben, ob die was taugt.

3. Vielleicht auch gleich noch der Beweis des Diagonallemmas, so wie ich es verstehe:

Wir nehmen ein formales System an, in dem eine Funktion gebaut werden kann, F: x -> y und B(y). Die Funktion nimmt eine Formel x und weist ihr die Gödelnummer y zu, um sie anschließend auch dem Prädikat B zuzuordnen. F hat nun auch eine Gödelnummer, sagen wir G, wozu wir kommen, in dem wir einfach F in sich selbst einsetzen, also F: F -> G und B(G). Nehmen wir jetzt an, eine Theorie kann G ableiten, also T |- G, dann gilt wg. F trivial auch T |- B(G). Nehmen wir an, T |- B(G), dann kann man mit F zurückrechnen auf G, also T |- G, also insgesamt T |- G <-> B(G) und B kann eben letztlich auch ein Nichtbeweisbarkeitsprädikat sein, wodurch letztlich der Gödelsatz gebildet werden kann.

31.03.2020, 13:47

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von Pippen
1. Es geht um die Frage, ob ein formales System, in dem sich nur endlich viele Formeln bilden lassen, unvollständig sein kann.

Ja, warum nicht. Vollständigkeit ist eine spezielle Eigenschaft. 1=1 ist in natürlichen Zahlen wahr, aber im formalen System 0=0 nicht ableitbar.

Zitat:

Original von Pippen
2. Hoffmann's Diagramm verwirrt mehr als es zeigt.

Dein Problem verstehe ich nicht. Ich halte Gödels Argument für erheblich komplizierter als Hoffmanns Erläuterung.

Zitat:

Original von Pippen
2. Dort läßt sich gerade kein Diagonalargument erkennen, wie wir es von Cantor kennen und wie ich es versuche zu interpretieren.

Ganz offensichtlich doch.

Zitat:

Original von Pippen
2. Bei meiner Interpretation erkennt man die Analogie zu Cantor, aber die Frage ist eben, ob die was taugt.

Darin erkenne ich gar nichts, also taugt es wohl nichts.

Zitat:

Original von Pippen
3. Vielleicht auch gleich noch der Beweis des Diagonallemmas, so wie ich es verstehe:

Wir nehmen ein formales System an, in dem eine Funktion gebaut werden kann, F: x -> y und B(y). Die Funktion nimmt eine Formel x und weist ihr die Gödelnummer y zu, um sie anschließend auch dem Prädikat B zuzuordnen. F hat nun auch eine Gödelnummer, sagen wir G, wozu wir kommen, in dem wir einfach F in sich selbst einsetzen, also F: F -> G und B(G). Nehmen wir jetzt an, eine Theorie kann G ableiten, also T |- G, dann gilt wg. F trivial auch T |- B(G). Nehmen wir an, T |- B(G), dann kann man mit F zurückrechnen auf G, also T |- G, also insgesamt T |- G <-> B(G) und B kann eben letztlich auch ein Nichtbeweisbarkeitsprädikat sein, wodurch letztlich der Gödelsatz gebildet werden kann.

Das lässt an Unverständlichkeit nichts zu wünschen übrig.

Neue Frage »

Antworten »

Unvollständigkeitssätze

Verwandte Themen