Frage von Tybald89, 73

Die Bedeutung des Gödelschen Unvollständigkeitssatzes?

Hallo liebe Mathematen,

der Wortlaut lautet ja: "Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig."

Okay, aber bedeutet das nun, dass es innerhalb der Mathematik als formales System stets nicht-beweisbare oder nicht-entscheidbare Probleme geben wird? Muss man ein System, dass zwar großflächig extrem gut funktioniert, aber an expliziten Stellen unweigerlich Sackgassen impliziert, einfach hinnehmen oder gibt es da einen Weg drumherum?

Ist das nicht eigentlich der Albtraum eines jeden Mathematikers? 

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von kreisfoermig, 31

Der Satz berührt auf zwei Konzepten von Komplexität. Einmal die von Formeln in der formalen Sprache und einmal die der quasi „materiellen“ Komplexität. Ich erkläre:

Eine Formel φ in der Sprache der Arithmetik heißt ∆₀⁰-komplex gdw. φ aufgebaut werden kann mittels Relationen, Funktionen, propositionaler Konnektiven und sog. „beschränkter“ Quantoren, d. h. derjenigen der Form ∀x<n und ∃x<n. Ab da wird die Arithmetische Hierarchie gebaut: man setzt ∑⁰₀ := ∆⁰₀ und ∏⁰₀:= ∆⁰₀ und dann ∑⁰_(n+1) besteht aus Formeln die durch (unbeschränkte) ∃-Quantoren präfigierte ∏⁰_(n) Formeln sind; und ∏⁰_(n+1) besteht aus Formeln die durch (unbeschränkte) ∀-Quantoren präfigierte ∏⁰_(n) Formeln sind. Und ∆⁰_(n) ist ∏⁰_(n) ∩ ∑⁰_(n). Kürzer ausgedrückt gilt:

∑⁰₀ und ∏⁰₀ := ∆⁰₀ und 
∑⁰_(n+1) = ∑∏⁰_(n)
∏⁰_(n+1) = ∏∑⁰_(n)
∆⁰_(n) = ∏⁰_(n) ∩ ∑⁰_(n) für alle n≥0

Bei Formel ist somit die Rede von syntaktischer Komplexität, weil dieses Konzept rein die Sprache betrifft. Wie sieht es bei OBJEKTEN (wie Mengen, Relationen, Funktionen) aus? Da könnten wir von materieller Komplexität sprechen, da die Rede von DINGEN ist. 

Definition. Sei Menge M ⊆ ℕⁿ eine Menge (eine Relation). Sei Γ irgendeine Komplexitätsklasse (bspw. aus der arithmetischen Hierarchie). Dann heißt M von materieller Komplexität Γ gdw. es eine Formel φ(x⁽¹⁾,x⁽²⁾,…,x⁽ⁿ⁾) aus der Klasse Γ gibt, so dass M = {(k⁽¹⁾,k⁽²⁾,…,k⁽ⁿ⁾)∈ℕⁿ | φ[k⁽¹⁾,k⁽²⁾,…,k⁽ⁿ⁾] gilt}.

Theorem. Eine n-stellige Relation R⊆ℕⁿ ist rekursiv (Turing) gdw. R der Komplexität ∆⁰₁ ist. Eine n-stellige Funktion ƒ : ℕⁿ→ℕ ist rekursiv gdw. R:=Gph(ƒ)⊆ℕⁿ⁺¹ rekursiv ist.

Frage. Wie kann eine arithmetische Sprache, welche sich nur auf Objekte bezieht, sich auf sich selbst (etwas Sprachliches) beziehen? Die gängige Antwort lautet „mittels Gödel-Codes“. Formeln, Logiken, Theorien usw. werden durch Zahlen kodiert. Jeder Formel φ∈FOR (in irgendwelcher fixierten formalen Sprache—nicht nur der der Arithmetik) wird (auf eine sinnvolle „rekursive“ Weise) ein Code [φ] ∈ ℕ zugeordnet. Einer Theorie T ⊆ FOR wird eine Menge von Codes zurgeordnet: [T] := {[φ] | φ∈T} ⊆ ℕ.

Hier die Schlüsselstelle. Man wende die Definitionen oben an. Eine Theorie T⊆FOR heißt dann von materieller Komplexität Γ, wenn die Menge der Gödel-Codes [T]⊆ℕ von materieller Komplexität Γ ist. Insbesondere ist eine Theorie T, eine Menge von Formeln, rekursiv gdw. [T] als Menge von Zahlen ist.

Beachte den Unterschied: Formel haben Komplexität bzgl. deren syntaktischen Struktur, Mengen von Formel müssen erst als Menge von Zahlen kodiert werden und dann wird ein beschreibendes Prädikat für die Menge der Zahlen nach Komplexität geprüft. Unsere Gödel-Codes sind so gebaut, dass man aus einem Code als Mensch eine Formel auf algorithmische Weise wiederherstellen kann. Daher ist eine Theorie materiell gesehen rekursiv gdw. es einen Algorithmus gibt, nach dem die Inhalte der Theorie erzeugt werden kann.

Definition. Eine Axiomatisierung von einer Struktur S ist Theorie, also eine Menge von Formeln, T⊆FOR in der Sprache der Struktur, so dass gilt Th(T) = Th(S), das heißt, für alle Formeln φ∈FOR gilt: φ ist beweisbar in der Logik ausgehend von den Annahmen in T ⟺ φ ist wahr, wenn in der Struktur S interpretiert. (Kürzer: T⊢φ ⟺ S⊨φ.)

Theorem (Unvollständigkeitssatz). Sei S eine Struktur, die die Struktur der natürlichen Zahlen enthält. Dann gibt es keine materiell rekursive Axiomatisierung von S. Genauer genommen: sei Γ:=∆⁰₁, dann gibt es zu jeder konsistenten Theorie T⊆FOR der materiellen Komplexität Γ, eine Formel (in der Tat einen Satz) GOED∈FOR, so dass gilt GOED ist der Komplexität ∑Γ und S⊨GOED und T⊬GOED.

ACHTUNG: Dies ist nicht die Formulierung von Gödel. Seine ist sehr verzwickt. Ich versuche hier dem Resultat einen (hoffentlich) zugänglichen Sinn zu verleihen. Mit anderen Worten lehrt uns der Unvollständigkeitssatz, keine (konsistente) Theorie kann mit niedrigem materiellem Preis (bzgl. materieller Komplexität) alle teureren Formeln (bzgl. syntaktischer Komplexität) entscheiden. Salopp gesagt, die Leistungsfähigkeit deines Fundaments hängt von den quasi materiellen Eigenschaften ab.

ACHTUNG: die Verwendung des Begriffs materiell ist von mir aus dem Grund, zwischen zwei Konzepten zu unterscheiden. Das wirst du nicht in der Literatur finden, den Unterschied aber schon.

Gödels Formulierung war etwa wie folgt (ich hab sie trotzdem modernisiert):

Theorem (Gödel). Betrachte eine Theorie T. Entweder

  • ist die Theorie nicht rekursiv präsentierbar (das heißt du hast irgendeine Menge von Formeln, kannst sie aber nie mit endlichen algorithmischen Mitteln beschreiben!); oder
  • sie ist nicht in der Lage, auf rekursive Weise die Axiome von Peano-Arithmetik zu reden; oder
  • sie ist inkonsistent;
  • oder sie ist rekursiv präsentierbar, konsistent, erfasst Peano-Arithmetik… und aber ist unvollständig.

Genauer genommen, benutzte Gödel den Begriff ∏⁰₁- oder ω-Konsistenz/Vollständigkeit, denn er misste die genaue Komplexität der entscheidenden Formeln.

Bedeutung für Mathematik. Für „normale“ Bereiche der Mathematik taucht Unvollständigkeit eher am Rande, aber stellt ein echtes Problem da. In dem Bereich ‘Foundation of Mathematics’ erscheint dieses Problem um praktisch jede Ecke und dafür gibt es Mittel (namentlich Forcing). Unvollständigkeit schien anfangs pathologisch zu sein und daher für die normale Mathematik irrelevant. Man entdeckte jedoch echte Beispiele (z. B. in der Arithmetik—Paris, Harrington; in AnaIysis—siehe Farah). Es gibt Sorgen bei dem P≠NP Problem, ob da das Problem nicht erscheint. Es mag ein Alptraum scheinen, macht aber die Mathematik viel spannender!! Vor allem gilt:

  • es gibt keine (rekursiv beschreibbare) 2-stufige Logik, das heißt keine Logik, die über Teilmengen reden kann außer auf versteckte Weise mittels FOL-Theorien von Mengenlehre; 
  • dies führt zum Problem: wie die Welt der mathematischen Objekte aussieht… hat einen Einfluss auf die Logik! Wir müssen quasi eine Physik des mathematischen Universums betreiben, um immer mehr über es herauszufinden. Daher
  • darfst du die Mathematik nicht auf bloßen Formalismus reduzieren—mindestens ist diese Position nicht rechtfertigt.
  • U. a. bedeutet dies, kein klassischer Rechner kann jemals einen Mathematiker ersetzen, um neue Mathematik zu entdecken.

Der Gödel'sche Unvollständigkeitssatz bedeutet u. a. die Unentscheidbarkeit von FOL (first oder Logic / 1. stufiger Prädikaten Logik). Kein Rechner lässt sich bauen, der alle Theoreme erzeugen kann. Faustregel: jedes wesentlich neue Theorem bedarf eines neuen Ansatzes. Der Mathematiker hat es als gut.

Was die Künstliche Intelligenz leisten könnte? Das ist eine andere Geschichte…

Kommentar von Physikus137 ,

Na, das nenne ich aber mal Butter bei die Fische! 

Kommentar von Astroknoedel2 ,

Wow, das nenne ich mal eine Antwort.

Kommentar von Tybald89 ,

Okay, obwohl ich ein Semester 'Diskrete und computerorientierte Mathematik' hatte kann ich nicht behaupten alles bis ins Letzte zu verstehen. Dennoch: Wenn diese Antwort keine Hilfreichste wäre, würde hier einiges falsch laufen. Daher: Danke (!)

Kommentar von kreisfoermig ,

Bitte!

Anmerkung. Es wird etwas schwierig/verzwickt sein, sobald man über „Theorien die über PA sprechen“ spricht, da man dann ein Übersetzungsschema braucht:

Z. B. ist ZFC in der Sprache LST={∈}; man findet in ZFC, dass eine durch die Sprache {∈} beschreibbare Klasse N existiert, die mittels eines Übersetzungsschemas PA erfüllt (in der Sprache LA={S;0;+;·} der Arithmetik). Formuliert GOED in LA… dann übersetzt dies in LST mittels des Übersetzungsschemas. Dann gilt 𝕍  ⊨ GOED aber ZFC ⊬ GOED, wobei 𝕍 ein „das“ Mengeuniversum ist (das wir mittels ZFC beschreiben wollten). Es gilt aus sematischer Sicht: man gehe davon aus, dass es dieses Mengenuniversum, 𝕍, gibt… und dass wir dies halt beschreiben wollen, und dann besagt dem Mathematik der Unvollständigkeitssatz: egal, was du für eine Theorie nimmst, ob ZF, ZFC, ZFC+CH, usw., solange diese Theorie rekursiv präsentierbar ist,  konsistent ist und PA erfüllt (und insbesondere in dem Universum 𝕍 erfüllt ist) so deine Theorie unvollständig.

So ist es halt für den Mathematiker, der von einem Mengenuniversum ausgeht: er weiß, ich werde dies nie vollständig erfassen können mittels einer rekursiv präsentierbaren Theorie.

Für den Logiker ist es noch abstrakter: er geht nicht von der Existenz von irgendeinem Rahmen aus. Er kann an den Unvollständigkeitssatz rein syntaktisch herangehen. Die Formulierung ist dann bei ihm super trocken aber schon konservativ.

Den Informatiker interessiert (z. T.) meistens nur die Arithmetik. Also bedarf es keines Übersetzungsschemas zwischen Sprachen. Wenn man nur die Struktur der natürlichen Zahlen betrachtet, kann man den Argument und seine Bedeutung leichter verfolgen und erkennen. Was auch immer ich für ein System (einen Kalkül) benutze, um Arithmetik zu beschreiben, ist dies rekursiv und damit kann sich das System auf sich selbst beziehen (auf kodierte Weise), da das System über alle rekursiven Sachen reden kann. Und das Gödel'sche Argument reduziert sich auf das übliche Diagonalargument und liefert ein Fakt… das nicht im Kalkül ableitbar ist. Dies zeigt uns, dass es Fakten über die natürlichen Zahlen gibt, die nicht rekursiv sind. Besser erfasst (angesichts des ersten Theorems): die Arithmetische Hierarchie fällt nicht zusammen zwischen dem 0.ten und 1.ten Level.

(Wie wir Menschen auf dieses nicht ableitbare Fakt kommen, obwohl wir selber einem Kalkül auf der Metaebene unterliegen… das ist ne spannende Frage. Hier muss man aber schon die Sichtweise des Mathematikers übernehmen und nicht mehr über bloße Arithmetik sondern über Theorien für die Grundlage aller Mathematik reden.)

Antwort
von Hamburger02, 23

Gödel hat die theroetische Grenze der Erkenntnisfähigkeit herausgefunden und damit ist der Unvollständigkeitssatz einer der wichtigsten der gesamtem Mathematikgeschichte.

Das bedeutet letzlich, dass ein komplexes System, wie z.B,. unser Universum, niemals von innen heraus vollständig erklärt und verstanden werden kann.

Kommentar von kreisfoermig ,

Nein, der Satz bedeutet dies nicht. Das sagt z. B. Hawking, aber sein Schluss ist voreilig und weist Missverständnisse auf. Wenn überhaupt, wurde die Unvollständigkeit der Naturwissenschaft schon seit John Locke (wir können nur das an der Natur erkennen, was man vorher in sie hineindenkt) und die der menschlichen Erkenntnisse dank I. Kant demonstriert. Apropos Missverständnisse, kann ich das Buch von Törkel Franzen empfehlen.

Kommentar von Hamburger02 ,

Du denkst in eine andere Richtung. Auch wenn ich von Hawking nicht sooo viel halte, denke ich, dass er in dem Punkt Recht hat.

Das geht mehr in die Richtung einer Alltagserfahrung:

Leute, die selber Teil des Problems sind, finden meistens keine gute Lösung, da sie das Problem nicht vollständig und objektiv überblicken können. Außenstehende haben es da einfacher, weil sie die gesamte Lage incl. der Problemperson objektiv betrachten können und daher leichter Lösungen finden.

Antwort
von FataMorgana2010, 32

Ja. Sobald das System mächtig genug ist, kann man etwas formulieren, das man dann nicht mehr entscheiden kann. 

Aber wie das so ist mit den wirklich großen Problemen: Man nimmt sie als gegeben hin, kümmert sich aber nicht weiter drum. Das ist wie in anderen Bereichen auch: Jeder Mathematiker weiß, dass er mit der naiven Sicht der Mengenlehre ins Paradoxon stolpern kann, aber im "normalen" Gebrauch macht das nix, also - so what?

Letztlich läuft es darauf hinaus, dass die Mathematik eben nicht die vollkommene Welt ist, die man sich erhofft. Aber auch in unvollkommenen Welten kann man arbeiten und leben. Der Unvollständigkeitssatz stellt ja die bisher gewonnenen Erkenntnisse nicht in Frage, die Geometrie, die Algebra, die (äh, wie heißt noch die Fachrichtung mit den Grenzwerten, die gutefrage.de als unanständig betrachtet? :-), ach ja: AnaIysis... - alle können daneben weiterexistieren und müssen nicht grundsätzlich neu gedacht werden. 

Kommentar von Schachpapa ,

Darf man dieses Wort neuerdings unbeanstandet schreiben???

Kommentar von kreisfoermig ,

Es geht nur mit einem großen i: AnaIysis oder einem Zeichen: Anaℓysis ; )

Kommentar von marty55 ,

Darf man dann auch anaIog nicht schreiben? :)

Keine passende Antwort gefunden?

Fragen Sie die Community