Mathematik: Die Gödelschen Unvollständigkeitssätze
Released by matroid on Mo. 30. April 2012 09:37:48 [Statistics]
Written by Gockel - 22485 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)


Die Unvollständigkeitssätze
Der (zweitplatzierte) Satz des Jahres 2012



Wir haben vor kurzem zum zweiten Mal den Satz des Jahres gewählt. Gewonnen hat das Noether-Theorem.



Da jedoch das Jury-Mitglied, welches zugesagt hatte, die Laudatio zu schreiben, sollte das Noether-Theorem gewinnen, kurzfristig absagen musste und kein Ersatzautor gefunden werden konnte, greifen wir stattdessen zu einem anderen Thema.



Dieser Artikel stellt den zweiten Gewinner der Wahlen 2011 und 2012 vor: Die Gödel'schen Unvollständigkeitssätze.





Inhalt



Ein Überblick



Worum soll es gehen? Um das Konzept der Unvollständigkeit natürlich, das sagt schon der Titel. Aber was genau ist das eigentlich? Leider ist das oftmals nicht einfach zu erklären, da die auftretenden Phänomene durchaus subtil sein können und daher oft verwirrend wirken.



In stark vereinfachter Form besagen die Unvollständigkeitssätze folgendes:

Es sei <math>\Phi=\lbrace \phi_0,\phi_1,\ldots \rbrace</math> ein explizites Axiomensystem, das in der Lage ist, über hinreichend viel Arithmetik der natürlichen Zahlen zu reden1. Für solche Axiomensysteme gilt:
  1. Entweder <math>\Phi</math> ist widersprüchlich oder es gibt mind. eine Aussage <math>\phi</math> die unentscheidbar von <math>\Phi</math> ist, d.h. es gibt keinen Beweis, dass <math>\phi</math> aus <math>\Phi</math> folgt, aber es gibt auch keinen Beweis, dass <math>\neg\phi</math> aus <math>\Phi</math> folgt.
  2. Entweder <math>\Phi</math> ist widersprüchlich oder <math>\Phi</math> ist widerspruchsfrei, aber die Widerspruchsfreiheit von <math>\Phi</math> kann von <math>\Phi</math> selbst nicht bewiesen werden.


In diesem Artikel soll präzise geklärt werden, was das eigentlich heißt, dass eine Aussage aus einem Axiomensystem folgt, und es soll versucht werden, typische Missverständnisse über die Unvollständigkeitssätze aufzuklären.



Dazu wollen wir wie folgt vorgehen: Zunächst werden wir viel definieren, um präzise über die Dinge reden zu können, die sonst nur informal benutzt werden. Wir werden als erstes klären, was Terme und Formeln sind. Dann werden wir formal definieren, was ein Beweis ist.
Dies ist die syntaktische Seite des Ganzen, dabei geht es nur um Zeichenketten, die auf eine bestimmte Weise strukturiert sind. Der nächste Schritt besteht für uns darin, die Semantik zu formalisieren, indem wir definieren, was Modelle sind. Damit wird es uns möglich, über Strukturen zu reden, die bestimmte Aussagen erfüllen oder eben nicht erfüllen, also Beispiele oder Gegenbeispiele für Axiomensysteme. Der Korrektheitssatz wird die Brücke schlagen zwischen dem rein syntaktischen Hantieren mit formalen Zeichenketten wie Formeln und Beweisen auf der einen Seite und den konkreten Beispielen einer Theorie und ihrem Verhalten auf der anderen Seite.
Erst, wenn wir diese ganzen Definitionen hinter uns gebracht haben, können wir uns mit wichtigen Sätzen auseinander setzen. Dabei sind vor allem der Vollständigkeitssatz und der Kompaktheitssatz für den weiteren Verlauf entscheidend, da sie uns erlauben, auch nicht-offensichtliche Beispiele für (widerspruchsfreie) Axiomensysteme zu konstruieren.
Ausgehend vom Kompaktheitssatz werden wir die Existenz von Nichtsstandardmodellen der Peano-Arithmetik diskutieren. Deren Existenz ist ein Knackpunkt für uns. Es ist auf den ersten Blick kontraintuitiv, dass es sie geben sollte. Wenn man aber einmal verstanden hat, warum es sie gibt, dann ist man auch nicht mehr weit davon entfernt, die Gödel'schen Unvollständigkeitssätze zu verstehen.
Am Ende des Artikels besprechen wir dann die Unvollständigkeitssätze und werden einen Beweis skizzieren, wie man aus der Unlösbarkeit des Halteproblems den ersten Unvollständigkeitssatz folgern kann. Danach werden wir auf ein paar typische Missverständnisse im Zusammenhang mit den Unvollständigkeitssätzen eingehen und sie hoffentlich verständlich aufklären.



Auf vollständige Beweise muss aus Platzgründen hier leider weitestgehend verzichtet werden. Maximal Beweisskizzen können gegeben werden. Wer sich für Details interessiert, dem sei das Buch von Ebbinghaus, Flum und Thomas empfohlen.

1 Dabei meint "explizit", dass die Menge rekursiv aufzählbar sein muss, d.h. es muss einen Algorithmus geben, der die Axiome auflistet. Das ist für alle endlichen Formelmengen gegeben, aber z.B. auch für PA und ZFC. Was hingegen "hinreichend viel Arithmetik" bedeutet, ist schwieriger zu definieren. Technisch gesprochen muss ein hinreichend großes Fragment von PA in der Theorie "interpretierbar" sein, d.h. vereinfacht gesagt, dass man irgendwie mit den Axiomen eine Konstruktion der natürlichen Zahlen durchführen und innerhalb der Theorie beweisen können muss, dass Addition und Multiplikation genügend viele von den Eigenschaften haben, die wir erwarten. Zum Beispiel könnte man beweisen, dass diese Konstruktion die vollen Peano-Axiome erfüllt (aber das ist mehr als nötig, es würden z.B. auch die Axiome der sogenannten Robinson-Arithmetik ausreichen, die wesentlich schwächer sind).


Syntax - Formeln und Beweise



Wenn man eine Logik-Vorlesung hört, dann ist man zunächst ein paar Wochen mit Sachen beschäftigt, die einem völlig trivial erscheinen, die aber gemacht werden müssen, um die Theorie korrekt aufzubauen. Zum Beispiel muss formal definiert werden, was eigentlich "Formeln", "Aussagen", "Beweise" etc. sein sollen.



Wir werden die Definitionen hier so knapp wie möglich darstellen und auf Lemmata über Normalform etc. verzichten.



Terme und Formeln



In der Mathematik ist man es gewohnt, eine Formelsprache als Ausdrucksmittel zu benutzen. Man schreibt Aussagen formal auf, setzt sie zusammen, zieht Schlüsse daraus uvm.
In der Logik ist es nun so, dass wir die Formeln selbst zum Untersuchungsgegenstand der Theorie erheben. Während es bisher völlig ausreichend war, ein intuitives Verständnis für die Formelsprache zu haben, muss nun also streng definiert werden, worüber man redet, was also eigentlich ein "Term", eine "Aussage" etc. sein soll.



Wir werden diese Begriffe so definieren, dass Terme und Aussagen einfach bestimmte Zeichenketten sind. Diese sind natürlich sehr ähnlich zu den Zeichenketten, die wir bisher als mathematische Terme und Formeln kennen, aber es sei die Warnung ausgesprochen: Es sind erst einmal nur Zeichenketten ohne Bedeutung! Wie diese Zeichenketten interpretiert werden, insbesondere die Unterscheidung in "wahre" und "falsche" Aussagen, wird in diesem Abschnitt nicht festgelegt. Hier müssen wir klar trennen zwischen der Symbolik und ihrer Bedeutung, zwischen Syntax und Semantik.



Mit dieser Warnung im Hinterkopf fangen wir an zu definieren:



Was wir jetzt definieren werden, fällt unter den Begriff "Prädikatenlogik erster Stufe" (oftmals abgekürzt als PL1). Das heißt als erstes, dass unser Zeichenvorrat für die formalen Zeichenketten u.A. aus folgenden Zeichen besteht:
  • Abzählbar viele Symbole, die wir Variablensymbole nennen,
  • das Symbol <math>=</math>,
  • die beiden Klammersymbole <math>(</math> und <math>)</math>,
  • Junktorensymbole <math>\wedge</math>,<math>\vee</math>,<math>\neg</math>,<math>\implies</math>,<math>\iff</math> sowie
  • Quantoren <math>\forall</math> und <math>\exists</math>




Dies sind die Symbole, die in jeder PL1-Sprache enthalten sind. Dann hat jede PL1-Sprache aber noch eigene weitere Symbole:

Eine Symbolmenge <math>\mathcal{S}</math> besteht aus drei paarweise disjunkten Mengen <math>\mathcal{K},\mathcal{R},\mathcal{F}</math>, deren Elemente wir Konstanten-, Relations- bzw. Funktionssymbole nennen, sowie abzählbaren Partitionen der Relations- und Funktionssymbole:
<math>\mathcal{R}=\biguplus\limits_{n=1,2,\ldots} \mathcal{R}_n</math>
<math>\mathcal{F}=\biguplus\limits_{n=1,2,\ldots} \mathcal{F}_n</math>
Wir bezeichnen die Elemente von <math>\mathcal{R}_n</math> und <math>\mathcal{F}_n</math> als <math>n</math>-stellige Relations- bzw. Funktionssymbole.
Beispiel: Gruppentheorie

Für die Zwecke der Gruppentheorie würde man z.B. die folgende Symbolmenge benutzen:
Als Konstantensymbole benutzt man <math>1</math>, Relationssymbole gibt es keine, dafür aber die Funktionssymbole <math>(\cdot)^{-1}</math> für Inversion und <math>\cdot</math> für die Multiplikation, die ein- bzw. zweistellig sind.

Beispiel: Natürliche Zahlen

In den Unvollständigkeitssätzen ist von "Arithmetik" die Rede. Die natürlichen Zahlen kann man auf verschiedene Weisen axiomatisieren.



Sehr sparsam ist z.B. eine Axiomatisierung, die nur das Konstantensymbol <math>0</math> (Ja, Null ist natürlich. Gewöhnt euch dran! ;-)) und das einstellige Funktionssymbol <math>S</math> kennt, welches für die Nachfolgerfunktion stehen soll.



Es gibt auch andere Axiomatisierungen, die die zweistelligen Funktionssymbole <math>+</math> und <math>\cdot</math> zusätzlich in die Symbolmenge aufnehmen. Das ist für die Zwecke der Unvollständigkeitssätze die sinnvollere Variante. Wir werden diese Symbolmenge verwenden. Wenn man ganz besonders großzügig ist, dann wird manchmal auch ein zweistelliges Relationssymbol für das Echt-Kleiner bzw. das Kleiner-oder-gleich mit aufgenommen, darauf kann man zur Not jedoch auch verzichten.

Beispiel: Graphentheorie

Wenn man Graphentheorie betreibt, dann ist die wesentliche Information die Relation, die beschreibt, ob zwei Knoten durch eine Kante verbunden sind. Mit einem einzigen zweistelligen Relationssymbol hat man also eine Symbolmenge gefunden, die für Graphentheorie geeignet ist.



Das sind, wie gesagt, erst einmal nur Symbole und keine echten Funktionen etc.. Wir können also nicht von Dingen wie "Definitionsbereich" oder "Funktionswert an der Stelle ..." sprechen.
Wir werden erst später definieren, wie man formale Symbole tatsächlich interpretiert. Natürlich wird das aber so gestrickt sein, dass eine Grundmenge <math>X</math> existiert, die Konstantensymbole dann tatsächlich als Elemente von <math>X</math>, die <math>n</math>-stelligen Relationssymbole als <math>n</math>-stellige Relationen auf <math>X</math> und die <math>n</math>-stelligen Funktionssymbole als Funktionen <math>X^n\to X</math> interpretiert werden.

Ist <math>\mathcal{S}</math> eine Symbolmenge, dann definieren wir <math>\mathcal{S}</math>-Terme durch folgende Regeln:
  1. Alle Konstantensymbole sind <math>\mathcal{S}</math>-Terme.
  2. Alle Variablensymbole sind <math>\mathcal{S}</math>-Terme.
  3. Sind <math>t_1, t_2, \ldots, t_n</math> <math>\mathcal{S}</math>-Terme und <math>f</math> ein <math>n</math>-stelliges Funktionssymbol, dann ist auch die Zeichenkette
    <math>f t_1 t_2 \ldots t_n</math>
    ein <math>\mathcal{S}</math>-Term.
  4. Zeichenketten, die nicht durch die obigen Regeln erfasst werden, sind keine <math>\mathcal{S}</math>-Terme.
Beispiel: Gruppentheorie

Mit der oben definierten Symbolmenge sind die Zeichenketten <math>1</math>, <math>\cdot g^{-1}g</math> (entspricht <math>g\cdot g^{-1}</math> in gewöhnlicher Schreibweise), <math>\cdot g \cdot h \cdot ^{-1}g^{-1}h</math> (entspricht <math>ghg^{-1} h^{-1}</math>), ... Terme über dieser Symbolmenge (<math>g</math> und <math>h</math> seien Variablensymbole).

Beispiel: Natürliche Zahlen

Wenn nur <math>S</math> und <math>0</math> in der Symbolmenge sind, dann sind die einzigen Terme natürlich die der Form <math>SS\ldots S0</math> und <math>SS\ldots Sx</math> für ein Variablensymbol <math>x</math>.



Wenn man jedoch die größere Symbolmenge nimmt, in der auch <math>+</math> und <math>\cdot</math> enthalten sind, dann sind auch <math>+xy</math> (entspricht <math>x+y</math>) und <math>\cdot y+zx</math> (entspricht <math>y(z+x)</math>) Terme.



Man merkt an diesen beiden Beispielen schon, dass die Notation bei gewöhnlichen Funktionen zwar relativ normal aussieht, bei Operatoren, die normalerweise in Infix-Notation geschrieben werden, aber gewöhnungsbedürftig ist. Die Term-Definition benutzt die sogenannte polnische Notation für Funktionsauswertungen, in der Operatoren vor die Operanden geschrieben werden. Das kann man entweder akzeptieren und so durchziehen oder - und das werden wir tun - vereinbaren, dass wir die uns gewohnten Schreibweisen als Abkürzungen für die formal korrekten Terme verstehen.

Beispiel: Graphentheorie

Da in der Symbolmenge für die Graphentheorie keine Konstanten- oder Funktionssymbole enthalten, sind die Variablensymbole die einzigen Terme.



Terme sind also Kodierungen von "definierbaren" Elementen einer Grundmenge, also der Elemente, die wir mit unseren erlaubten Mitteln, also Konstanten, Variablen und Funktionen, definieren können.

Ist <math>\mathcal{S}</math> eine Symbolmenge, dann definieren wir <math>\mathcal{S}</math>-Formeln durch folgende Regeln:
  1. Sind <math>t_1, t_2</math> <math>\mathcal{S}</math>-Terme, dann ist die Zeichenkette
    <math>(t_1=t_2)</math>
    eine <math>\mathcal{S}</math>-Formel.
  2. Sind <math>t_1,\ldots,t_n</math> <math>\mathcal{S}</math>-Terme und <math>R</math> eine <math>n</math>-stellige Relation, dann ist
    <math>R t_1 \ldots t_n</math>
    eine <math>\mathcal{S}</math>-Formel.
  3. Sind <math>\phi,\phi_1, \phi_2</math> <math>\mathcal{S}</math>-Formeln, dann sind die Zeichenketten
    <math>(\phi_1\wedge\phi_2)</math>,
    <math>(\phi_1\vee\phi_2)</math>,
    <math>(\neg\phi)</math>,
    <math>(\phi_1\implies\phi_2)</math> und
    <math>(\phi_1\iff\phi_2)</math>
    ebenfalls <math>\mathcal{S}</math>-Formeln.
  4. Ist <math>\phi</math> eine <math>\mathcal{S}</math>-Formel und <math>x</math> ein Variablensymbol, dann sind die Zeichenketten
    <math>(\forall x\phi)</math> und
    <math>(\exists x\phi)</math>
    ebenfalls <math>\mathcal{S}</math>-Formeln.
  5. Zeichenketten, die nicht durch die obigen Regeln erfasst werden, sind keine <math>\mathcal{S}</math>-Formeln.


Nachdem wir die formale Definition nun haben, ignorieren wir sie aber fast wieder und vereinbaren sofort die üblichen Abkürzungen: Wir schreiben <math>\forall x,y,z</math> anstelle von <math>\forall x\forall y\forall z</math>, wir schreiben Klammern nur, wenn sie nötig sind, um Eindeutigkeit herzustellen, wenn spezielle Funktionssymbole wie <math>+</math> vorkommen, dann schreiben wir <math>a+b</math> anstelle von <math>+ab</math> und so weiter und so fort.

Beispiel: Gruppentheorie

Formeln sind jetzt z.B. die Gruppenaxiome
  1. <math>\phi_A := \forall x,y,z: x(yz)=(xy)z</math>
  2. <math>\phi_N := \forall x: 1x=x \wedge x=x1</math>
  3. <math>\phi_I := \forall x: xx^{-1} = 1 \wedge x^{-1}x=1</math>
  4. <math>\phi_K := \forall x,y: xy=yx</math>
aber auch gruppentheoretische Aussagen wie <math>(ghg^{-1}h^{-1})^{-1}=hgh^{-1}g^{-1}</math> oder <math>gxg^{-1} = x^{-1}</math>.



In der Tat haben wir an diesem Punkt die Möglichkeit, den Begriff "gruppentheoretische Aussage" präzise zu definieren, nämlich genau als eine Formel über der oben definierten Symbolmenge der Gruppentheorie. Ganz analog kann man jetzt "graphentheoretische Aussage", "ringtheoretische Aussage" etc. präzise definieren.



Übungsaufgabe 1: Schreibe "G enthält einen Kreis der Länge k" als Formel der Graphentheorie. (Auflösung weiter unten)
Übungsaufgabe 2: Finde eine gruppentheoretische Formel, die zu "G ist nilpotent der Klasse k" äquivalent ist.


Beispiel: Natürliche Zahlen

Die allermeisten Aussagen der elementaren Zahlentheorie lassen sich als Formeln in der Sprache der natürlichen Zahlen von oben formulieren. Beispielsweise kann man <math>a\equiv b \mod n</math> als <math>\exists k: a=b+kn \vee b=a+kn</math> formulieren (wir können nicht <math>a-b=kn</math> schreiben, weil das Symbol für Subtraktion nicht existiert in unserer Symbolmenge).



Es ist relativ trickreich, aber auch möglich, Rekursionen in dieser Sprache zu formulieren. Dadurch kann man auch Dinge wie <math>a=b^c</math>, <math>a=\binom{n}{m}</math> etc. als Formeln in dieser Sprache kodieren.



Formeln sind also genau die Zeichenketten, die wir als sinnvolle mathematische Aussagen interpretieren würden in unserem Kontext. Jede sinnvolle Kombination aus logischen Operatoren und den gegebenen Relationen lässt sich als <math>\mathcal{S}</math>-Formel darstellen.



Mit ganz analogen rekursiven Definitionen kann man weitere Begriffe präzisieren, die man sonst für Formeln benutzt. Beispielsweise kann man definieren, was eine freie Variable einer Formel ist (es ist genau das, was man sonst darunter versteht: Jede Variable, die vorkommt, außer denen, die direkt auf einen Quantor folgen, heißt frei) und dass eine Formel ohne freie Variablen Aussage genannt wird.



Eine Anmerkung: Man kann sich leicht davon überzeugen, dass Terme und Formeln eindeutig wieder "zerlegt" werden können, d.h. es gibt für jeden Term und jede Formel genau eine Möglichkeit, sie durch Anwendung dieser Regeln zu erhalten. Das liegt unter anderem daran, dass wir vollständig geklammert haben.



Es sei außerdem angemerkt, dass wir auf einige der Quantoren und Junktoren hätten verzichten können, weil wir die Interpretationen der Formeln natürlich so wählen werden, dass beispielsweise <math>\neg(\phi\wedge\psi)</math> und <math>\neg\phi\vee\neg\psi</math> äquivalent sein werden. Ob man weniger oder mehr Quantoren und Junktoren benutzt, ist letztlich Geschmackssache.



Beweise



Genau wie die Formeln müssen wir auch Beweise formalisieren, wenn wir etwas über Beweise und Beweisbarkeit beweisen wollen. Beweise werden ebenfalls gewisse formale Zeichenketten sein. Es gilt dieselbe Warnung wie zuvor: Obwohl angelehnt an die inhaltlichen Schlussweisen, sind alle Zeichenketten hier eben nicht mehr als das: Formale Zeichenketten ohne irgendeine wie auch immer geartete Bedeutung.



Es gibt verschiedene äquivalente Möglichkeiten, Beweise zu formalisieren. Wir entscheiden uns hier für den sogenannten "Sequenzenkalkül". Dazu fixieren wir für den Rest dieses Abschnittes eine Symbolmenge <math>\mathcal{S}</math> und verstehen alle Formeln und Terme hier als <math>\mathcal{S}</math>-Formeln bzw. <math>\mathcal{S}</math>-Terme. Dann definieren wir:

Eine Sequenz ist eine endliche Folge
<math>\phi_1 \phi_2 ... \phi_n</math>
von Formeln. Der Kürze halber schreibt man oft
<math>\Gamma \phi_1 ... \phi_n</math>
wenn man nur ein Endstück der Folge mit Namen versehen will und das Anfangsstück im Moment nicht interessiert.


Um besser zu verstehen, wie die Regeln des Sequenzenkalküls funktionieren, hilft es, so zu tun, als hätte die formale Zeichenkette <math>\Gamma \phi</math> die Bedeutung "Unter den Voraussetzungen <math>\Gamma</math> gilt <math>\phi</math>". Wenn man diese Interpretation im Hinterkopf behält, dann wird leicht einsichtig, wie der Sequenzenkalkül genau funktioniert.



Der Sequenzenkalkül besteht nun aus einer endlichen Anzahl von Regeln, wie man aus vorhandenen Sequenzen neue basteln kann. Das wird normalerweise in der Form
<math>\begin{array}{cccc} \Gamma & \phi_1^{(1)} & \ldots & \phi_{n_1}^{(1)} \\ \vdots \\ \Gamma & \phi_1^{(k)} & \ldots & \phi_{n_k}^{(k)} \\ \hline \Gamma & \psi_1 & \ldots & \psi_m \end{array}</math>
geschrieben, womit man eine Regel meint, die es erlaubt, aus den <math>k</math> Sequenzen über dem Strich die Sequenz unter dem Strich zu erzeugen.



Wir verzichten darauf, die Regeln des Sequenzenkalküls vollständig wiederzugeben. Die Regeln sind eine Formalisierung der bekannten Schlussregeln der klassischen Logik. Daher wäre es nur eine Auflistung von Selbstverständlichkeiten. Natürlich gehört eine explizite Formulierung aller Regeln zu einer korrekten Behandlung des Sequenzenkalküls, aber hier wollen wir uns darauf beschränken, ein paar Beispiele zu geben, um zu verdeutlichen, wie sich typische Schlussweisen im Sequenzenkalkül äußern.



Dazu gehören Regeln wie
<math>\begin{array}{cc} \Gamma & \phi\wedge\psi \\ \hline \Gamma & \phi \end{array}</math>
und
<math>\begin{array}{cc} \Gamma & \phi\wedge\psi \\ \hline \Gamma & \psi \end{array}</math>
die besagen, dass, wenn <math>\phi\wedge\psi</math> gegeben ist, die beiden Bestandteile <math>\phi</math> bzw. <math>\psi</math> gefolgert werden dürfen. Die Regeln
<math>\begin{array}{cc} \Gamma & \phi \\ \hline \Gamma & \phi\vee\psi \end{array}</math>
und
<math>\begin{array}{cc} \Gamma & \phi \\ \hline \Gamma & \psi\vee\phi \end{array}</math>
besagen anders herum, dass bei gegebenem <math>\phi</math> die zusammengesetzten Formeln <math>\phi\vee\psi</math> bzw. <math>\psi\vee\phi</math> gefolgert werden können. (Man beachte, dass diese Formeln im Allgemeinen echt voneinander verschieden sind! Das sind ja nur Zeichenketten. Dass wir diesen Zeichenketten denselben Wahrheitswert zuordnen würden, spielt keine Rolle!)



Die Regeln

<math>\begin{array}{cc}  &  \\ \hline \Gamma & \phi\vee\neg\phi \end{array}</math>,

<math>\begin{array}{cc}  & \\ \hline \Gamma & \phi \end{array}</math>, falls <math>\phi</math> in <math>\Gamma</math> enthalten ist
und

<math>\begin{array}{cc}  & \\ \hline \Gamma & t=t \end{array}</math> für alle Terme <math>t</math>.
modellieren Trivialitäten, um ganz ohne Voraussetzungen die Gültigkeit von Tautologien abzuleiten.



Neben diesen elementaren Regeln, gibt es Regeln, die echte Schlussfolgerungen modellieren. Wichtig ist etwa die Regel vom Modus Ponens, welche die wesentliche Eigenschaft von Implikationen modelliert:
<math>\begin{array}{cc} \Gamma & \phi\implies\psi \\ \Gamma & \phi \\ \hline \Gamma &\psi \end{array}</math>
Dies würde man so interpretieren: Wenn man (unter den Voraussetzungen <math>\Gamma</math>) weiß, dass sowohl die Implikation <math>\phi\implies\psi</math> als auch die Voraussetzung <math>\phi</math> gelten, dann gilt auch die Konklusion <math>\psi</math>. Das ist also wirklich exakt das, was man braucht, um mit Implikationen zu arbeiten.



Außerdem gibt es beispielsweise auch die Regel von der Fallunterscheidung:
<math>\begin{array}{ccc} \Gamma & \phi & \psi \\ \Gamma & \neg\phi & \psi \\ \hline \Gamma & \psi & \end{array}</math>
und die Regel vom Widerspruchsbeweis:
<math>\begin{array}{ccc} \Gamma & \neg\phi & \psi \\ \Gamma & \neg\phi & \neg\psi \\ \hline \Gamma & \phi & \end{array}</math>.
Wenn man sich vor Augen hält, wie wir diese Zeichenketten interpretieren wollen, dann ist einleuchtend, dass hier tatsächlich die Schlussweise einer Fallunterscheidung und eines Widerspruchsbeweises modelliert werden.



Die restlichen Regeln des Sequenzenkalküls sind ebenso einleuchtend. Wer sich für die Details interessiert, kann den kompletten Regelsatz des Sequenzenkalküls z.B. bei Ebbinghaus [1] oder natürlich auch bei Wikipedia nachlesen.



Wenn wir nun glauben, dass die Regeln des Sequenzenkalküls genau die Schlussweisen eines mathematischen Beweises formalisieren, dann können wir nun auch endlich definieren, was ein Beweis sein soll, nämlich einfach eine Anwendung dieser Regeln:



Sei <math>\Gamma</math> eine Sequenz. Wir schreiben
<math>\vdash\Gamma</math>
und sagen <math>\Gamma</math> sei ableitbar, falls eine endliche Folge <math>\emptyset=\Gamma_0, \Gamma_1, \ldots, \Gamma_n=\Gamma</math> von Sequenzen existieren, sodass für alle <math>k=1,\ldots,n</math> stets <math>\Gamma_k</math> durch die Anwendung einer der Regeln des Sequenzenkalküls aus <math>\Gamma_0,\ldots,\Gamma_{k-1}</math> erhalten werden kann. Eine solche Folge nennen wir ggf. einen Beweis von <math>\Gamma</math>.



Wenn <math>\Phi</math> eine (möglicherweise unendliche!) Menge von Formeln ist, so schreiben wir
<math>\Phi\vdash\phi</math>
und sagen <math>\phi</math> sei beweisbar bzw. ableitbar aus <math>\Phi</math>, wenn es endlich viele <math>\phi_1, \ldots,\phi_n\in\Phi</math> gibt, sodass
<math>\vdash\phi_1 ... \phi_n \phi</math>
gilt.



Bemerkungen



Wir haben bis jetzt nur mit formalen Zeichenketten gearbeitet, ohne diese irgendwie mit einer Bedeutung versehen zu haben. Der Sequenzenkalkül erlaubt es uns (genau wie andere formale Beweiskalküle), Teile des Beweisprozesses völlig vom Nachdenken zu befreien und sie zum Beispiel einem Computer zu übergeben.



Das Verifizieren eines Beweises ist z.B. problemlos maschinell machbar, sobald der Beweis einmal im Sequenzenkalkül aufgeschrieben wurde. Da es an jedem Punkt des Beweises nur endlich viele bereits bewiesene Sequenzen gibt und der Kalkül nur endlich viele Regeln enthält, um daraus eine neue Sequenz zu erzeugen, kann man einfach an jedem Punkt des Beweises alle Möglichkeiten ausprobieren und so feststellen, ob der aktuelle Beweisschritt tatsächlich durch eine Regel gerechtfertigt ist.



Tatsächlich ist die Menge aller Beweise (wenn sie geeignet kodiert wird) rekursiv aufzählbar: Man kann ein Programm schreiben, dass die Regeln immer und immer wieder anwendet und so schließlich jeden überhaupt möglichen Beweis erreicht.



Reduziert das also die Mathematik auf stumpfsinnige Arbeit? Nein!



Zum einen gibt es da das Problem der praktischen Umsetzbarkeit. Die Anzahl der Regeln des Sequenzenkalküls ist endlich, aber trotzdem groß genug, dass der Baum der möglichen Beweise mit zunehmender Tiefe extrem groß wird. Ihn vollständig zu durchsuchen, hat exponentielle Laufzeit: Wenn der kürzeste Beweis der gegebenen Formel die Länge <math>n</math> hat, benötigt die Suche <math>O(c^n)</math> Schritte, um diesen Beweis zu finden. Solche Laufzeiten sind für alle außer den wirklich kurzen Beweisen unrealistisch. Es gibt wenig Hoffnung, etwa einen Beweis des großen Satzes von Fermat auf diese Weise zu finden, bevor das Sonnensystem unbewohnbar wird.



Eine Möglichkeit, automatische Beweissoftware auch für längere Beweise praktisch einzusetzen, besteht darin, eine Beweisskizze vorzugeben, d.h. ein Mensch teilt dem Computerprogramm möglichst viele (vermutete) Zwischenergebnisse mit und der Rechner sucht dann nur noch nach den Verbindungsstücken dieses Beweises.



Ein anderes, prinzipielles Problem ist eben das Phänomen der Unvollständigkeit. In diesem Kontext äußert es sich wie folgt: Die Menge aller Beweise ist zwar rekursiv aufzählbar, aber nicht entscheidbar. Das heißt, dass das beschriebene Computerprogramm (theoretisch) in der Lage ist, für eine vorgegebene Aussage einen Beweis zu finden, wenn es denn einen gibt. Es kann jedoch kein Programm geben, dass feststellen kann, ob eine beliebige vorgegebene Aussage keinen Beweis hat. Dies erscheint zunächst kontraintuitiv. Man könnte ja meinen, dass man einfach das ursprüngliche Programm auf die Negation der Aussage ansetzen könnte und so eine Widerlegung finden würde. Genau hier schlägt jedoch die Unvollständigkeit zu: Es gibt Aussagen, sodass weder die Aussage selbst noch ihre Negation einen Beweis haben.



Woran das liegt, werden wir im weiteren Verlauf des Artikels erkunden.



Semantik - Interpretationen und Modelle



Bisher haben wir rein syntaktisch gearbeitet. Unsere Gegenstände waren formale Zeichenketten ohne Bedeutung, die durch pure Textersetzung manipuliert werden durften. Der tatsächliche mathematische Inhalt wurde völlig ausgeblendet. Das wollen wir jetzt ändern.



Dazu wollen wir definieren, was ein Modell ist.



Ist <math>\mathcal{S}</math> eine Symbolmenge, dann besteht eine <math>\mathcal{S}</math>-Struktur <math>\mathfrak{A}=(A,\mathfrak{a})</math> aus einer Menge <math>A</math> und einer Abbildung <math>\mathfrak{a}</math>, die
  1. Konstantensymbole auf Elemente von <math>A</math>,
  2. <math>n</math>-stellige Relationssymbole auf Teilmengen von <math>A^n</math> und
  3. <math>n</math>-stellige Funktionssymbole auf Funktionen <math>A^n\to A</math>
schickt. Wenn wir keinen eignen Bezeichner für die Abbildung <math>\mathfrak{a}</math> vergeben wollen, dann schreiben wir <math>x^\mathfrak{A}</math> für das Bild eines Konstanten-, Relations- oder Funktionssymbols <math>x</math>.



Ist eine <math>\mathcal{S}</math>-Struktur <math>\mathfrak{A}=(A,\mathfrak{a})</math> gegeben, dann ist eine Belegung eine Abbildung, die jedem Variablensymbol ein Element von <math>A</math> zuordnet.



Eine Interpretation ist dann definiert als ein Paar <math>\mathfrak{I}=(\mathfrak{A},\beta)</math> bestehend aus einer Struktur und einer Belegung.



Eine Struktur macht also aus formalen Symbolen konkrete, mathematische Objekte. Eine Interpretation legt zusätzlich für jedes Variablensymbol einen Wert fest.



Wenn wir die Symbole erst einmal mit einer Bedeutung versehen haben, können wir jetzt rekursiv auch definieren, welchen Wert Terme haben und was es für Formeln heißt, wahr bzw. falsch zu sein.

Sei <math>\mathcal{S}</math> eine Symbolmenge und <math>\mathfrak{I}=(\mathfrak{A},\beta)</math> eine Interpretation von <math>\mathcal{S}</math>. Dann definiere <math>\mathfrak{I}(t)</math> für Terme <math>t</math> durch folgende Rekursion:
  1. Ist <math>t=c</math> ein Konstantensymbol, dann setze
    <math>\mathfrak{I}(t):=c^\mathfrak{A}</math>.
  2. Ist <math>t=v</math> ein Variablensymbol, dann setze
    <math>\mathfrak{I}(t):=\beta(v)</math>.
  3. Ist <math>t=f(t_1,\ldots,t_n)</math> für ein <math>n</math>-stelliges Funktionssymbol <math>f</math> und Terme <math>t_1,\ldots,t_n</math>, dann setze
    <math>\mathfrak{I}(t):=f^\mathfrak{A}(\mathfrak{I}(t_1),\ldots,\mathfrak{I}(t_n))</math>.


Terme werden also ausgewertet, wie man es erwartet: Der Term gibt die Bildungsvorschrift für ein Element von <math>A</math> vor.



Als nächstes steht auf dem Plan, dass wir präzisieren, was es heißt, dass eine Formel von einer Interpretation erfüllt wird. Das funktioniert ebenfalls über so eine Rekursion:



Sei <math>\mathcal{S}</math> eine Symbolmenge. Die Relation <math>\models</math> zwischen Interpretationen und Formeln sei wie folgt definiert:
  1. Gleichheit:
    Sind <math>t_1</math> und <math>t_2</math> Terme, dann gelte
    <math>\mathfrak{I}\models(t_1=t_2)</math> gdw. <math>\mathfrak{I}(t_1)=\mathfrak{I}(t_2)</math> gilt.
  2. Relationen:
    Ist <math>R</math> ein <math>n</math>-stelliges Prädikatssymbol und <math>t_1,\ldots,t_n</math> Terme, dann gelte
    <math>\mathfrak{I}\models R(t_1,\ldots,t_n)</math> gdw. <math>(\mathfrak{I}(t_1),\ldots, \mathfrak{I}(t_n))\in\ R^\mathfrak{A}</math> gilt.
  3. Junktoren:
    Sind <math>\phi, \phi_1, \phi_2</math> Formeln, dann gelte
    • <math>\mathfrak{I}\models(\phi_1\wedge\phi_2)</math> gdw. <math>\mathfrak{I}\models\phi_1</math> und <math>\mathfrak{I}\models\phi_2</math> gilt,
    • <math>\mathfrak{I}\models(\phi_1\vee\phi_2)</math> gdw. <math>\mathfrak{I}\models\phi_1</math> oder <math>\mathfrak{I}\models\phi_2</math> gilt,
    • <math>\mathfrak{I}\models(\neg\phi)</math> gdw. nicht <math>\mathfrak{I}\frakI\models\phi</math> gilt,
    • <math>\mathfrak{I}\models(\phi_1\implies\phi_2)</math> gdw. <math>\mathfrak{I}\models\phi_1 \implies \mathfrak{I}\models\phi_2</math> gilt sowie
    • <math>\mathfrak{I}\models(\phi_1\iff\phi_2)</math> gdw. <math>\mathfrak{I}\models\phi_1 \iff \mathfrak{I}\models\phi_2</math> gilt.
  4. Quantoren:
    Ist <math>\phi</math> eine Formel und <math>x</math> ein Variablensymbol, dann gelte
    • <math>\mathfrak{I}\models\forall x\phi</math> gdw. für alle <math>a\in A</math> stets <math>\mathfrak{I}\frac{a}{x}\models\phi</math> gilt und
    • <math>\mathfrak{I}\models\exists x\phi</math> gdw. es ein <math>a\in A</math> gibt, sodass <math>\mathfrak{I}\frac{a}{x}\models\phi</math> gilt.
Dabei bezeichnet <math>\mathfrak{I}\frac{a}{x}</math> die Interpretation die entsteht, wenn man die Belegung des Variablensymbols <math>x</math> auf <math>a</math> ändert und den Rest gleich lässt.



Wenn <math>\mathfrak{I}\models\phi</math> gilt, dann sagen wir auch, dass <math>\mathfrak{I}</math> die Formel <math>\phi</math> erfüllt oder auch, dass <math>\mathfrak{I}</math> ein Modell von <math>\phi</math> sei.



Wenn <math>\Phi</math> eine (eventuell unendliche) Menge von Formeln ist, dann schreiben wir analog <math>\mathfrak{I}\models\Phi</math> und sagen ebenfalls, <math>\mathfrak{I}</math> erfülle <math>\Phi</math> bzw. sei ein Modell von <math>\Phi</math>, falls <math>\mathfrak{I}\models\phi</math> für alle <math>\phi\in\Phi</math> gilt.



Falls die Formeln in <math>\Phi</math> keine freien Variablen enthalten, dann spielt die Wahl der Belegung <math>\beta</math> keine Rolle für die Gültigkeit von <math>(\mathfrak{A},\beta)\models\Phi</math> und wir schreiben daher kurz <math>\mathfrak{A}\models\Phi</math>.



Erfüllbarkeit ist also ebenfalls genauso definiert, wie wir es erwarten würden: Man dröselt die Formel solange auf, bis man atomare Aussagen wie "Zwei Terme sind gleich" oder "die Terme ... erfüllen die Relation ..." erhält, welche man mit der gegebenen Interpretation nachprüft.



Wenn wir uns für <math>\Phi</math> ein Axiomensystem einer Theorie denken, dann haben wir hiermit also formal definiert, was es für eine Struktur heißt, ein Beispiel für ein Axiomensystem zu sein.
Na gut, diese Erkenntnis war ja jetzt antiklimaktisch. Der Aufwand scheint sich bis jetzt nicht gelohnt zu haben, nur um den Begriff des "Beispiels" konkret zu definieren. Er macht sich aber bezahlt, wenn man nun tatsächlich Modelltheorie betreiben will. Es stellt sich heraus, dass es durchaus unerwartete Phänomene gibt, die wir uns in der Folge genauer ansehen werden.



Zunächst wollen wir jedoch noch ein semantisches Analogon zur Ableitbarkeitsrelation <math>\Phi\vdash\phi</math> zwischen Formelmengen und Formeln definieren:



Sei <math>\mathcal{S}</math> eine Symbolmenge, <math>\Phi</math> eine Menge von <math>\mathcal{S}</math>-Formeln und <math>\phi</math> eine einzelne <math>\mathcal{S}</math>-Formel.



Wir schreiben <math>\Phi\models\phi</math> und sagen <math>\phi</math> ist eine Konsequenz von <math>\Phi</math>, falls alle Modelle von <math>\Phi</math> auch immer Modelle von <math>\phi</math> sind.



Dies ist der inhaltliche Folgerungsbegriff, mit dem wir in der Mathematik am häufigsten arbeiten und denken. Formale Beweise sind für uns ja nur Mittel zum Zweck. Eigentlich sind wir an genau dieser semantischen Frage interessiert: "Wenn ein Dings die Axiome <math>\Phi</math> erfüllt, erfüllt sie dann auch automatisch <math>\phi</math>?" und wenn die Antwort "nein" lautet, dann fragen wir nach einem Gegenbeispiel. Die obige Definition von Modellen und Konsequenz-Relation präzisiert genau diese Art von Fragestellungen.

Beispiel: Gruppentheorie

Die Formelmenge <math>\Phi_\text{Grp}:=\lbrace\phi_A,\phi_N,\phi_I\rbrace</math> (siehe oben) axiomatisiert genau die Gruppentheorie: Die Modelle dieser Formelmenge sind exakt die Gruppen. Ebenso werden die kommutativen Gruppen von <math>\Phi_\text{Grp}\cup\lbrace \phi_K\rbrace</math> axiomatisiert.



Die Formeln
<math>\phi_p := \exists x: x\neq 1 \wedge \underbrace{x\cdots x}_{p}=1</math>
für alle <math>p\in\mathbb{P}</math> axiomatisieren die Existenz eines Elements der Ordnung <math>p</math>. Die Modelle der Formelmenge <math>\Phi_\text{Grp}\cup\lbrace\neg\phi_p | p\in\mathbb{P}\rbrace</math> sind daher exakt die torsionsfreien Gruppen.



Man kann jedoch nicht alle Klassen von Gruppen so charakterisieren. Beispielsweise die Torsionsgruppen sind nicht auf diese Weise charakterisierbar.

Beispiel:Natürliche Zahlen

Die Peano-Axiome für die natürlichen Zahlen sind etwas komplizierter als die Gruppenaxiome. Zunächst gibt es den arithmetischen Anteil, der aus den folgenden Axiomen besteht:
  • <math>\forall x: 0\neq Sx</math>
  • <math>\forall x,y: Sx=Sy \implies x=y</math>
  • <math>\forall x: x+0=x</math>
  • <math>\forall x,y: x+Sy=S(x+y)</math>
  • <math>\forall x: x\cdot 0=0</math>
  • <math>\forall x,y: x\cdot Sy=xy+x</math>
Dann folgt das sogenannte Induktionsschema, eine abzählbare unendliche Anzahl weiterer Axiome, die alle wie folgt aufgebaut sind: Für jede Formel <math>\phi</math> über der Symbolmenge der natürlichen Zahlen <math>\lbrace 0,S,+,\cdot\rbrace</math>, welche genau eine freie Variable enthält, definiere das Induktionsaxiom für <math>\phi</math> als folgende Formel:
<math>\text{IND}_\phi := \quad (\phi(0) \wedge (\forall x: (\phi(x)\implies\phi(x+1)))) \implies (\forall x: \phi(x))</math>
Dabei meint <math>\phi(x)</math> die Formel, die entsteht, wenn man die freie Variable in <math>\phi</math> durch <math>x</math> ersetzt. Diese Formel modelliert also eine vollständige Induktion für die Aussage <math>\phi</math>. Wenn wir für alle möglichen Formeln ein solches Axiom haben, beschreibt das also alle2 möglichen Induktionen.



Die Menge aller dieser Formeln wird als Peano-Axiome (erster Stufe) bezeichnet. Wir kürzen sie als <math>PA</math> ab.



Das Modell, das man im Sinne hat, wenn man diese Axiome aufschreibt, ist das sogenannte Standardmodell, d.h. die natürlichen Zahlen <math>\mathbb{N}</math>, wobei die Symbole <math>0,S,+,\cdot</math> wie üblich als die Zahl <math>0</math>, die Funktion <math>n\mapsto n+1</math>, die Addition bzw. die gewöhnliche Multiplikation interpretiert werden.



Ein auf den ersten Blick gänzlich überraschender Fakt ist jedoch, dass es neben dem Standardmodell unendlich viele weitere, echt verschiedene Modelle der Peano-Axiome gibt, sogenannte Nichtstandardmodelle. Wir werden darauf noch eingehen.

2 Das ist nicht ganz korrekt, weil wir nur die Induktionen erfassen, bei denen sich die Induktionsbehauptung auch wirklich als PA-Formel schreiben lässt. Es gibt andere Induktionsargumente, die wir damit nicht erfassen können. Das ist eine der Beschränkungen der Prädikatenlogik erster Stufe.

Beispiel: Graphentheorie

Wenn man das Symbol für die Relation "durch eine Kante verbunden" nun einfach mit einem Strich bezeichnet, dann könnte man z.B. folgende Formeln betrachten:
<math>\forall x: \neg(x \text{---} x)</math>
<math>\forall x,y: x \text{---} y \iff y \text{---} x</math>
Die Modelle dieser beiden Formeln sind die schlichten, ungerichteten Graphen. Wenn wir die zweite Formel weglassen, erhalten wir die gerichteten Graphen ohne Schlaufen und wenn wir auch die erste Forderung noch fallen lassen, dann erhalten wir gerichtete Graphen mit Schlaufen.



Wir haben weiter oben schon angedeutet, dass die Existenz von Kreisen der Länge <math>k</math> als Formel geschrieben werden kann. Mit einer Kurzschreibweise etwa so:
<math>\kappa_k := \quad \exists x_1,\ldots,x_k: \left(\bigwedge_{1\leq i<j\leq k} x_i \neq x_j\right) \wedge \left(\bigwedge_{i\in\mathbb{Z}/k\mathbb{Z}} x_i \text{---} x_{i+1}\right)</math>
Die Graphen, die (gerichtete) Kreise der Länge <math>k</math> enthalten, sind dann genau die Modelle von <math>\kappa_k</math>. Modelle von <math>\lbrace \neg\kappa_k | k\in\mathbb{N}_{\geq 1}\rbrace</math> wären die kreisfreien Graphen, also die Bäume im ungerichteten bzw. die azyklischen Graphen im gerichteten Fall.



Und zum Schluss will ich die Gelegenheit nicht verstreichen lassen, meinen Lieblingswortwitz aus der Graphentheorie hier unterzubringen. Ein gerichteter Kreis heißt auf englisch auch "cycle". Definiere ein "bicycle" also als eine Folge <math>x_1,\ldots,x_k</math> von Knoten, die in beide Richtungen gelesen jeweils einen gerichteten Kreis bilden. Analog zu oben wird die Existenz von bicycles der Länge <math>k</math> durch folgende Formel beschrieben:
<math>\beta_k := \quad \exists x_1,\ldots,x_k: \left(\bigwedge_{1\leq i<j\leq k} x_i \neq x_j\right) \wedge \left(\bigwedge_{i\in\mathbb{Z}/k\mathbb{Z}} x_i \text{---} x_{i+1} \wedge x_{i+1} \text{---} x_i\right)</math>
Die Modelle von <math>\lbrace\neg\beta_k | k\in\mathbb{N}_{\geq 1}\rbrace</math> sind nun exakt diejenigen Graphen, die keine bicycles besitzen. Fachbegriff dafür: Pedestrian, zu deutsch Fußgänger.



Zusammenfassung bis hierher



Bis jetzt haben wir vor allem Definitionen gesammelt. Folgende Dinge sollte man über diese Definitionen im Hinterkopf behalten:

  • Terme, Formeln und Aussagen sind formale Zeichenketten, a priori ohne Bedeutung.
  • Terme kodieren Elemente der Grundmenge und geben an, wie sie sich aus den Konstanten und den Funktionen zusammensetzen lassen.
  • Formeln und Aussagen sehen genauso aus, wie wir es von mathematischen Aussagen erwarten. Sie sind aus Relationen und Gleichheiten zwischen Termen sowie den logischen Operationen zusammengesetzt.
  • Formeln und Aussagen unterscheiden sich darin, dass Aussagen keine freien Variablen enthalten dürfen.
  • Beweise sind endliche Folgen von Formeln. Man kommt von einer zur nächsten, indem man eine der elementaren Beweisregeln anwendet.
  • Strukturen und Interpretationen versehen die formalen Symbole mit konkreten Bedeutungen.
  • Strukturen und Interpretationen unterscheiden sich darin, dass eine Interpretation auch den Variablensymbolen konkrete Werte zuordnet.
  • Interpretationen sind nötig, um die formalen Zeichenketten mit Bedeutung zu versehen! Erst in Bezug auf eine Interpretation kann man sagen, welchen Wert ein Term hat oder welchen Wahrheitsgehalt eine Formel.
  • Modelle einer Formelmenge sind Interpretationen, die alle Formeln der Menge erfüllen. Mit anderen Worten: Modelle sind nichts anderes als konkrete Objekte, für die die Axiome gelten, welche durch die Formelmenge gegeben sind.


Modelle, Modelle, Modelle



Wir wollen nun zum ersten Mal in diesem Artikel echte Sätze kennenlernen, die diese Definitionen mit Leben füllen. Zunächst nehmen wir uns drei Klassiker vor, die die Verbindung zwischen den rein syntaktischen Informationen, wie sie in Beweisen vorkommen, mit den inhaltlichen Informationen von Modellen verbinden.

Korrektheits-, Vollständigkeits- und Kompaktheitssatz



Der erste ist der Korrektheitssatz:

Korrektheitssatz

Sei <math>\mathcal{S}</math> eine Symbolmenge, <math>\Phi</math> eine Menge von <math>\mathcal{S}</math>-Formeln und <math>\phi</math> eine einzelne <math>\mathcal{S}</math>-Formel.



Gilt <math>\Phi\vdash\phi</math>, dann gilt auch <math>\Phi\models\phi</math>.



Dieser Satz behauptet einfach, dass eine Aussage, die formal aus einer Menge von Axiomen ableitbar ist, auch in allen Modellen dieser Axiomenmenge erfüllt wird. Unsere Definitionen von "<math>\phi</math> ist aus <math>\Phi</math> ableitbar" und "<math>\mathfrak{I}</math> erfüllt <math>\phi</math>" sind also in dieser Hinsicht sinnvoll gewesen. Jedes andere Verhalten würde nicht zu unserem Verständnis davon, was ein Beweis und was ein Modell ist, passen.



Wenn wir uns kurz erinnern, wie man beispielsweise in der Gruppentheorie zeigen würde, dass eine Aussage nicht aus den Gruppenaxiomen folgt - nämlich durch Angabe einer Gruppe, die sie nicht erfüllt - dann liefert der Korrektheitssatz auch eine Anleitung, wie wir zeigen können, dass bestimmte Beweise nicht existieren. Es gibt keinen Beweis für <math>\Phi\vdash\phi</math>, falls es ein Modell von <math>\Phi</math> gibt, welches kein Modell von <math>\phi</math> ist. So funktionieren typischerweise die Unentscheidbarkeitsbeweise für "konkrete" Theorien, wie die Gruppentheorie oder die Graphentheorie. Der Beweis der Unvollständigkeitssätze ist komplizierter, wie wir gleich noch sehen werden.



Der Beweis des Korrektheitssatzes ist eine längliche, aber letztendlich triviale Inspektion der Definitionen. Man muss sich für jede Regel des Sequenzenkalküls davon überzeugen, dass eine <math>\mathcal{S}</math>-Interpretation, welche die Sequenzen in der Voraussetzung erfüllt, auch stets die Sequenz in der Folgerung erfüllt. Weil die Regeln des Sequenzenkalküls eben genau so gewählt sind, dass sie die Schlussregeln der klassischen Logik modellieren, ist die Überprüfung der Korrektheit jeder einzelnen Regel eine Trivialität (aber eben länglich aufzuschreiben).
Wenn man das nun überprüft hat und ein Beweis <math>\Gamma_0, \ldots, \Gamma_n</math> von <math>\Phi\vdash\phi</math> vorliegt, dann folgt per Induktion aus der Korrektheit der Regeln, dass alle Sequenzen <math>\Gamma_i</math> erfüllt werden. Insbesondere die letzte Sequenz wird erfüllt, d.h. für gewisse Formeln <math>\phi_1,\ldots,\phi_n\in\Phi</math> wird <math>\phi_1\wedge\ldots\wedge\phi_n\implies\phi</math> erfüllt. Wenn eine Interpretation nun alle Formeln in <math>\Phi</math> und diese Implikation erfüllt, dann erfüllt sie aufgrund der Korrektheit von Modus ponens auch die Formel <math>\phi</math>. Das ist genau die Behauptung.



Während der Korrektheitssatz eine triviale Konsequenz der Definitionen ist, ist der nächste Satz nichttrivial und extrem wichtig, weil er die Umkehrung zum Korrektheitssatz liefert.

Vollständigkeitssatz

Sei <math>\mathcal{S}</math> eine Symbolmenge, <math>\Phi</math> eine Menge von <math>\mathcal{S}</math>-Formeln und <math>\phi</math> eine einzelne <math>\mathcal{S}</math>-Formel.



Gilt <math>\Phi\models\phi</math>, dann gilt auch <math>\Phi\vdash\phi</math>.



Dies ist nun eine nichttriviale und bei genauerem Hinsehen auch irgendwie unerwartete Aussage! Wenn jedes Modell eines Axiomensystems <math>\Phi</math> die Formel <math>\phi</math> erfüllt, dann gibt es auch einen formalen Beweis, der <math>\phi</math> aus <math>\Phi</math> ableitet.



Das ist nicht selbstverständlich, denn mit einem formalen Beweis können wir ja nur innerhalb der Grenzen bleiben, die uns durch die Wahl der Symbolmenge und des Axiomensystems vorgegeben sind!



Es ist aber durchaus vorstellbar, dass Argumente aus völlig anderen Gebieten der Mathematik dazu führen, dass man mehr über die Modelle einer Theorie weiß als durch rein formale Beweise innerhalb der Theorie. Es ist etwa üblich, topologische Argumente für gruppentheoretische Beweise einzusetzen. Der Vollständigkeitssatz sagt uns dann, dass der Umweg über diese anderen Gebiete unnötig war, weil man das Ergebnis auch formal aus den Axiomen ableiten kann.
Natürlich sagt uns der Vollständigkeitssatz aber nichts über die Komplexität oder gar die Länge eines solchen Beweises. Er ist eine reine Existenzaussage. Der "Umweg" kann also trotzdem bevorzugt werden, weil er kürzer oder eleganter ist oder einfach mehr Einsicht in das Problem liefert.



Eine andere, jedoch auch sehr wichtige Grenze ist die Tatsache, dass wir uns in der "ersten Stufe" bewegen. Das heißt, dass alle Variablen den gleichen Typ, nämlich "Element der Grundmenge" haben: Die Quantoren werden so interpretiert, dass sie über die Elemente der Grundmenge der jeweiligen <math>\mathcal{S}</math>-Struktur quantifizieren. Das führt dazu, dass wir Aussagen der Form "Für alle Teilmengen der Struktur ..." nicht treffen können.
Wenn wir uns beispielsweise in der Sprache der Gruppentheorie bewegen, dann kann keine Aussage der Form "Es gibt eine Untergruppe mit ..." in der ersten Stufe formuliert werden. (Das heißt aber nicht, dass nicht für spezielle Aussagen Formeln gefunden werden können, die zu so einer Aussage äquivalent sind).
Auch hier hilft uns der Vollständigkeitssatz: Selbst dann, wenn wir solche Argumente in Zwischenschritten verwenden, können wir auch eine formale Ableitung aus den Axiomen für die Formel, die wir beweisen wollen, finden, solange diese Formel eine <math>\mathcal{S}</math>-Formel ist.



Es gibt verschiedene, äquivalente Formulierungen des Vollständigkeitssatzes. Oft beweist man z.B. den folgenden Satz:

Vollständigkeitssatz, Version 2

Sei <math>\mathcal{S}</math> eine Symbolmenge und <math>\Phi</math> eine Menge von <math>\mathcal{S}</math>-Formeln.



Wenn <math>\Phi</math> widerspruchsfrei ist, dann ist <math>\Phi</math> auch erfüllbar.



Dabei bedeutet widerspruchsfrei, dass <math>\Phi \not\vdash \bot</math> gilt. <math>\bot</math> steht dabei für jeden Widerspruch, d.h. eine Formel der Form <math>\phi\wedge\neg\phi</math>. Man kann sich leicht davon überzeugen, dass es egal ist, welches <math>\phi</math> man dafür verwendet. Wenn man einen Widerspruch ableiten kann, dann kann man jeden Widerspruch ableiten (in der Tat gilt das Prinzip ex falso quodlibet, aus Falschem folgt Beliebiges).



Erfüllbar bedeutet einfach, dass es ein Modell von <math>\Phi</math> gibt.



Der Korrektheitssatz besagt in der Formulierung mit diesen beiden Begriffen: Jede erfüllbare Formelmenge ist auch widerspruchsfrei. Der Vollständigkeitssatz macht wieder die umgekehrte Aussage.



Ein Beweis des Vollständigkeitssatzes funktioniert in dieser Formulierung dann so wie man denkt: Es wird eine Konstruktion angegeben, um aus widerspruchsfreiem <math>\Phi</math> ein Modell von <math>\Phi</math> zu erhalten.
Das Wort "Konstruktion" ist dabei allerdings nicht überzubewerten. Man braucht für überabzählbare <math>\Phi</math> i.A. das Auswahlaxiom und selbst für abzählbare <math>\Phi</math> ist der Beweis nicht explizit genug, um z.B. einen Algorithmus anzugeben, der die Aufgabe erledigt. (In der Tat kann so ein Algorithmus nicht existieren).



In diesen Themenkreis fällt nun auch der dritte Satz, den ich in diesem Abschnitt erwähnen will, der Kompaktheitssatz:

Kompaktheitssatz

Sei <math>\mathcal{S}</math> eine Symbolmenge, <math>\Phi</math> eine Menge von <math>\mathcal{S}</math>-Formeln und <math>\phi</math> eine einzelne <math>\mathcal{S}</math>-Formel.

  1. <math>\Phi</math> ist erfüllbar genau dann, wenn jede endliche Teilmenge <math>\Phi_0\subseteq\Phi</math> erfüllbar ist.
  2. <math>\Phi\models\phi</math> gilt genau dann, wenn <math>\Phi_0\models\phi</math> für eine geeignete endliche Teilmenge <math>\Phi_0\subseteq\Phi</math> gilt.


Der Beweis ist mit dem Vollständigkeitssatz recht einfach, weil sich die Aussagen damit auf die Erkenntnis reduzieren, dass in jedem formalen Beweis von <math>\Phi\vdash\phi</math> nur eine endliche Teilmenge von <math>\Phi</math> benutzt wird.



Die Sätze von Löwenheim-Skolem



Der Kompaktheitssatz gibt uns erstmals die Möglichkeit, die Existenz von Modellen zu überprüfen, ohne sie explizit hinschreiben zu müssen. Das ist ein mächtiges Werkzeug.



Wenn wir uns Fragen stellen wie "Ist folgende Aussage aus dem Axiomenensystem <math>\Phi</math> ableitbar?", dann ist das nach dem Vollständigkeitssatz dazu äquivalent, dass alle Modelle von <math>\Phi</math> die fragliche Aussage erfüllen. Um so etwas zu überprüfen, müssen wir also etwas über "alle Modelle" aussagen können. Dazu ist es immer sinnvoll, sich Gedanken darüber zu machen, wie Modelle überhaupt aussehen können, ob und wie sie sich voneinander unterscheiden können etc.



Die erste Frage, die man sich da z.B. stellen kann, ist, ob die Größe der Grundmenge eindeutig festgelegt ist. Manchmal ist das der Fall, z.B. könnte das Axiomensystem ja die folgende Formel enthalten:
<math>\exists x,y,z: x\neq y \wedge y\neq z \wedge x\neq z \wedge (\forall a: a=x \vee a=y \vee a=z)</math>
Wenn eine Struktur diese Aussage erfüllen wollte, muss die zugrundeliegende Menge offenbar genau drei Elemente haben. Natürlich kann man das Prinzip verallgemeinern und zu jeder endlichen Mächtigkeit eine (längliche) Formel hinschreiben, die genau die Mengen dieser Mächtigkeit charakterisiert.



Wie sieht es aber mit unendlichen Mächtigkeiten aus? Wenn wir beispielsweise über die Arithmetik der natürlichen Zahlen, d.h. die Peano-Axiome reden wollen, dann erwarten wir, dass die Modelle dieser Axiome eben die natürlichen Zahlen beschreiben. Insbesondere sollten sie also abzählbar unendlich sein. Ist das so?



Interessanterweise nicht! Der Vollständigkeitssatz und der Kompaktheitssatz implizieren die beiden Sätze von Löwenheim-Skolem, die im Wesentlichen aussagen, dass die Größe von Modellen im unendlichen Fall nicht kontrolliert werden kann:

Sätze von Löwenheim-Skolem.

Sei <math>\mathcal{S}</math> eine Symbolmenge und <math>L^\mathcal{S}</math> die Menge aller <math>\mathcal{S}</math>-Formeln. Sei <math>\Phi\subseteq L^\mathcal{S}</math> eine erfüllbare Menge von Formeln.



Absteigender Satz von L.S.: Es gibt ein Modell von <math>\Phi</math> mit Mächtigkeit höchstens <math>|L^\mathcal{S}|</math>.



Aufsteigender Satz von L.S.: Falls <math>\Phi</math> ein Modell der unendlichen Kardinalität <math>\kappa</math> besitzt, dann besitzt <math>\Phi</math> auch Modelle der Mächtigkeit <math>\lambda</math> für alle <math>\lambda\geq\kappa</math>.



Am Beispiel der Peano-Axiome liefert uns das, dass es durchaus abzählbare Modelle (wie das Standardmodell), aber eben auch beliebig große überabzählbare Modelle der Peano-Axiome gibt! Das ist eine echte Überraschung.



Was bedeutet das für uns? Es bedeutet u.A. dass wir viel weniger Kontrolle darüber haben, was in den Modellen abgeht und was nicht. Und jetzt rückt langsam der erste Unvollständigkeitssatz ins Bild: Wenn der Satz nicht stimmt und in der Situation wir tatsächlich von jeder Aussage entweder einen Beweis oder einen Gegenbeweis finden können, dann hieße das laut Vollständigkeitssatzes, dass sich alle Modelle "gleich" verhalten in dem Sinne, dass jede Formel entweder von allen Modellen erfüllt wird oder von allen Modellen nicht erfüllt wird. Das hieße, dass die Struktur der Modelle schon durch die Axiome sehr stark eingeschränkt wäre.
Andererseits sagt uns der Satz von Löwenheim-Skolem, dass wir die Modelle eben nicht beliebig stark einschränken können. Schon die Mächtigkeit entzieht sich völlig unserer Kontrolle.
Das ist natürlich noch kein starkes Argument (in der Tat sind die Größe und die Erfüllbarkeit von Formeln zwei weit auseinanderliegende Eigenschaften von Modellen. Es ist durchaus möglich, dass nur eins von beidem unkontrollierbar ist, das andere aber gut kontrollierbar). Trotzdem gibt uns der Satz von Löwenheim-Skolem den Hinweis, dass die Situation viel komplizierter ist, als sie auf den ersten Blick scheint.
Ein naiver Versuch, den ersten Gödelschen Unvollständigkeitssatz zu widerlegen, könnte ja beispielsweise darin bestehen, einfach zu zeigen, dass alle Modelle der betrachteten Theorie zueinander isomorph sind. Der aufsteigende Satz von Löwenheim-Skolem zeigt, dass dies zum Scheitern verurteilt ist, weil es Modelle beliebig großer Kardinalitäten gibt.



Nichtstandardmodelle der Peano-Axiome



Für die Unvollständigkeit von Bedeutung sind besonders die Nichtstandardmodelle der Peano-Axiome. Der Kompaktheitssatz gibt uns die Möglichkeit zur Konstruktion solcher Modelle.



Dazu betrachten wir eine Menge von neuen Konstantensymbolen <math>\mathcal{C}</math> und zu allen Symbolen <math>c,c"\in\mathcal{C}</math> und zu allen Standard-natürlichen Zahlen <math>k\in\mathbb{N}</math> die folgenden Formeln:
<math>\phi_{c,k} := \quad c \neq \underbrace{1+1+\ldots+1}_{k}</math>
<math>\psi_{c,c"} := \quad c\neq c"</math>
Jetzt wenden wir den Kompaktheitssatz an. Jede endliche Teilmenge <math>\Phi_0\subseteq PA\cup\lbrace\phi_{c,k}, \psi_{c,c"} | c,c"\in\mathcal{C}, k\in\mathbb{N}\rbrace</math> wird vom Standardmodell <math>\mathbb{N}</math> der Peano-Axiome erfüllt, indem wir die endlich vielen vorkommenden Konstantensymbole <math>c,c"</math> einfach auf hinreichend große, natürliche Zahlen festlegen. <math>\Phi_0</math> enthält ja nur endlich viele der Ungleichungen <math>\phi_{c,k}</math>, d.h. wenn wir <math>\mathfrak{I}(c)</math> größer wählen als die endlich vielen vorkommenden <math>k</math>, dann erfüllt diese Interpretation die Menge <math>\Phi_0</math>.



Damit haben wir gezeigt, dass jede endliche Teilmenge von <math>PA\cup\lbrace\phi_{c,k}, \psi_{c,c"} | c,c"\in\mathcal{C}, k\in\mathbb{N}\rbrace</math> erfüllbar ist. Der Kompaktheitssatz liefert uns die Existenz eines Modells für diese Formelmenge.



Solch ein Modell muss insbesondere ein Modell der Peano-Axiome sein. Dies kann aber nicht <math>\mathbb{N}</math> sein, denn die Formeln <math>\phi_{c,k}</math> sagen aus, dass <math>c</math> echt verschieden von allen Standard-natürlichen Zahlen <math>0,1,1+1,1+1+1,\ldots</math> ist. <math>c</math> wird also als unendlich große Zahl interpretiert und so etwas gibt es im Standardmodell <math>\mathbb{N}</math> nicht.



Die Formeln <math>\psi_{c,c"}</math> sagen einfach, dass die Konstanten als paarweise verschiedene Elemente interpretiert werden. Wenn wir <math>\mathcal{C}</math> als überabzählbare Menge wählen, dann sind also auch die Modelle, die wir so erhalten, überabzählbar. (In der Tat funktioniert der Beweis des aufsteigenden Satzes von Löwenheim-Skolem völlig analog.)



Wenn wir die Menge <math>\mathcal{C}</math> hingegen abzählbar wählen, dann ist die (erweiterte) Symbolmenge abzählbar, also auch die Menge aller Formeln über dieser Menge. Daher liefert uns der absteigende Satz von Löwenheim-Skolem abzählbare Nichtstandardmodelle der Peano-Axiome.



Dieselbe Methode erlaubt es uns, eine beliebige Anzahl beispielsweise von Nichtstandard-Primzahlen zu erzeugen. Dazu nehmen wir einfach Formeln hinzu, die sagen, dass die <math>c</math> Primzahlen sind (man überlege sich, dass die Primzahleigenschaft wirklich als PA-Formel geschrieben werden kann).



Rekursionen und berechenbare Funktionen



Wir hatten oben einmal angedeutet, dass die Peano-Axiome in der Lage sind, Rekursionen zu definieren. Zunächst wollen wir kurz skizzieren, wie das funktioniert.



Der erste Schritt ist der chinesische Restsatz, etwa in Form der Aussage (in verkürzter Schreibweise wie üblich)
<math>{\forall p,q,a,b: ggT(p,q)=1 \implies \exists! n: 0\leq n<pq \wedge n \equiv a \mod p \wedge n \equiv b \mod q}</math>
Man kann sich überlegen, dass diese Aussage aus den Peano-Axiomen ableitbar ist, indem man einen (elementaren, rein zahlentheoretischen) Beweis hiervon nimmt und ihn formalisiert.



Wenn man sich davon überzeugt hat, dann gilt der chinesische Restsatz also in allen Modellen von PA. Das eröffnet uns die Möglichkeit, über endliche Folgen zu quantifizieren! Das ist so in der Sprache von PA nicht vorgesehen, denn per definitionem laufen alle Quantoren ja nur über die Elemente der Modelle, also die (ggf. Nichtstandard-) natürlichen Zahlen. Mit dem chinesischen Restsatz kann man aber Formeln der folgenden Form aufschreiben:
<math>\begin{array}{rl} exp(x,n,z) := & \exists A,B: \\ & \left(\forall 1\leq k\leq n-1: A \textrm{ MOD } ((k+1)B+1) = x\cdot(A \textrm{ MOD } (kB+1))\right) \\ & \wedge x = A \textrm{ MOD } B+1 \\ & \wedge z = A \textrm{ MOD } nB+1 \end{array}</math>
wobei MOD für den modulo-Operator steht, d.h. <math>A \textrm{ MOD } N</math> ist der eindeutige Restklassenvertreter von A in <math>\lbrace{0,1,\ldots,N-1\rbrace</math>. Wenn wir abkürzend <math>z_k := A \textrm{ MOD } kB+1</math> schreiben, dann haben wir hiermit nämlich die Rekursion <math>z_1=x, z_{k+1} = x\cdot z_k</math> kodiert. Zusammen mit der Bedingung <math>z_n=z</math> beschreibt <math>exp(x,n,z)</math> also die Aussage <math>x^n = z</math>.



Wieso funktioniert das? Es gibt für jedes <math>n\in\mathbb{N}</math> unendlich viele natürliche Zahlen <math>B</math>, sodass die Zahlen <math>k\cdot B+1</math> paarweise teilerfremd sind (z.B. <math>B=(2n!)^m</math> für alle <math>m\geq 1</math>). Eine endliche Folge <math>z_1,\ldots,z_n</math> kann nun dank chinesischem Restsatz zu einer einzigen Zahl <math>A</math> kombiniert werden, sodass <math>z_k = A \textrm{ MOD } kB+1</math> für alle <math>k=1,\ldots,n</math> ist. (Dazu brauchen wir, dass <math>z_k<kB+1</math> für alle <math>k</math> ist. Das kann aber durch eine hinreichend große Wahl von <math>B</math> sichergestellt werden.)
Wenn wir umgekehrt beliebige <math>A</math> und <math>B</math> gegeben haben, dann können wir diese Reste rekonstruieren und erhalten eine endliche Folge. Auf diese Weise können wir also alle endlichen Folgen natürlicher Zahlen mit einer expliziten Bildungsvorschrift durch zwei natürliche Zahlen Zahlen <math>A,B</math> kodieren!



Das ist die entscheidende Erkenntnis, um mit Hilfe der Arithmetik eine Vielzahl von diskreten mathematischen Objekten zu kodieren. Ab jetzt ist es nämlich nicht mehr schwierig, alle primitiv rekursiven Funktionen durch PA-Formeln zu definieren. Wenn man genauer hinsieht, schafft man es sogar, alle rekursiven Funktionen zu kodieren. Man kann also für jede (partielle) berechenbare Funktion <math>f:\mathbb{N}\to\mathbb{N}</math> eine Formel <math>\phi_f(n,z)</math> mit den freien Variablen <math>n,z</math> zu finden, sodass <math>\mathbb{N}\models\phi_f(\underbrace{1+\ldots+1}_{n},z)</math> genau dann erfüllt ist, wenn f auf der Eingabe <math>n\in\mathbb{N}</math> definiert ist und <math>f(n)=z</math> gilt.



Das eröffnet uns die Möglichkeit, Phänomene aus der Berechenbarkeitstheorie in Zahlentheorie zu übersetzen. Zum Beispiel sind jetzt Aussagen wie "Der Algorithmus A hält für alle Eingaben n" als PA-Formel kodierbar. Dazu müssen wir den Algorithmus als PA-Formeln kodieren, indem wir die Rekursionen nach obigem Prinzip ausdröseln. Die Formeln werden nicht wirklich schön, aber es ist alles explizit durchführbar, wenn man den Algorithmus explizit kennt.



Unentscheidbarkeit aus der Berechenbarkeitstheorie



Wenn wir einmal an diesem Punkt angekommen sind, dann können wir tatsächlich schon den ersten Unvollständigkeitssatz mit Hilfe des Halteproblems beweisen. Zum Halteproblem siehe auch [2] und [3].



Wir wollen nicht die sehr allgemeine Variante aus der Einleitung benutzen, da uns das mit zusätzlichen technischen Details belasten würde. Wir beweisen daher folgenden Satz:

Erster Gödel'scher Unvollständigkeitssatz

Es gibt eine PA-Formel <math>\phi</math> mit <math>PA \not\vdash \phi</math> und <math>PA \not\vdash \neg\phi</math>.



Die allgemeine Version für allgemeinere Axiomensysteme lässt sich als Korollar dieses Satzes auffassen, da jedes Axiomensystem, das "über hinreichend viel Arithmetik der natürlichen Zahlen reden" kann, wie wir es in der Einleitung formuliert hatten, auch in der Lage ist, den folgenden Beweis für sich zu formalisieren und daher vom Unvollständigkeitsphänomen ganz genauso betroffen ist wie PA selbst. Unvollständigkeit ist also kein Zeichen dafür, dass PA ein schlechtes Axiomensystem ist, es ist ein allgemeines Phänomen. Wir entscheiden uns nur für PA, weil wir damit leichter umgehen können, um das Prinzip zu demonstrieren.



Der Beweis des ersten Unvollständigkeitssatzes funktioniert nun wie folgt: Da das Axiomensystem <math>PA</math> rekursiv aufzählbar ist, kann man einen Algorithmus schreiben, der alle Beweise von aus <math>PA</math> ableitbaren Formeln rekursiv aufzählt.
Wir nutzen jetzt die Kodierung von Algorithmen aus dem vorherigen Abschnitt. Damit können wir für jede Turingmaschine T die Aussage "T hält für die leere Eingabe." als PA-Formel kodieren.
Falls nun wirklich <math>PA\vdash\phi</math> oder <math>PA\vdash\neg\phi</math> für alle Aussagen gelten würde, dann kann der Algorithmus, der die Beweise auflistet, zu jedem Algorithmus entweder einen Beweis für die Kodierung von "T hält" oder einen Gegenbeweis liefern.
Aufgrund des Korrektheitssatzes ist dann eine der beiden Aussagen "T hält" oder "T hält nicht" für das Standardmodell <math>\mathbb{N}</math> gültig, d.h. der Algorithmus, der die Beweise auflistet, entscheidet für jede Turingmaschine, ob sie anhält oder nicht. So einen Algorithmus kann es aufgrund der Unentscheidbarkeit des Halteproblems nicht geben. QED.



Andere Kodierungen - Diophantische Gleichungen



Man kann Turingmaschinen wie eben gesehen durch Formeln kodieren. Es ist hochgradig nichttrivial, aber möglich, die Kodierung der Turingmaschinen sogar derart zu gestalten, dass es ein Polynom <math>p\in\mathbb{Z}[X_1,\ldots,X_n,Y]</math> gibt, sodass die <math>m</math>-te Turingmaschine genau dann anhält, wenn
<math>\mathbb{N}\models\exists x_1,\ldots,x_n: p(x_1,\ldots,x_n,m)=0</math>
gilt. Das Polynom <math>p</math> ist dabei sogar (mit hinreichend viel Freizeit) explizit hinschreibbar!



Eine der von PA unbeweisbaren Formeln ist also die Behauptung der Lösbarkeit einer diophantischen Gleichung. Beweis: Wenn PA alle Formeln der Form <math>\exists x_1,...,x_n: p(x_1,\ldots,x_n)=0</math> für alle Polynome entweder beweisen oder widerlegen könnte, dann wäre der Algorithmus, der alle PA-Beweise auflistet, analog wie oben dazu in der Lage, das Halteproblem zu entscheiden.



Das ist nun schon sehr überraschend, dass ein so konkretes Problem wie die Lösbarkeit einer polynomiellen Gleichung unentscheidbar sein sollte. Es gibt weitere, sehr konkrete Aussagen aus der diskreten Mathematik (z.B. aus der Ramsey-Theorie), die von den Peano-Axiomen nicht entschieden werden können.



Konsequenzen aus den Unvollständigkeitssätzen



Was heißt das nun? Welche Konsequenzen haben die Unvollständigkeitssätze? Ich möchte hier die Gelegenheit nutzen, um mit ein paar Missverständnissen aufzuräumen.

Der erste Unvollständigkeitssatz



Missverständnis 1:
Der Unvollständigkeitssatz sagt, dass es neben "wahr" und "falsch" immer auch die dritte Möglichkeit "unentscheidbar" gibt.
Diese Aussage ist nicht korrekt, weil sie Begriffe vermischt, die man in der Logik und eben speziell im Zusammenhang mit den Unvollständigkeitssätzen strikt trennen muss:
  • Richtig ist: Der Unvollständigkeitssatz für die davon betroffenen Theorien sagt aus, dass es neben "<math>\phi</math> ist aus den Axiomen <math>\Phi</math> beweisbar" und "<math>\neg\phi</math> ist aus den Axiomen <math>\Phi</math> beweisbar" für gewisse Theorien auch die dritte Möglichkeit "weder das eine noch das andere" gibt.
  • Die unpräzise Verwendung von "wahr" und "falsch" ist hier das Grundproblem. Wir bewegen uns weiterhin in der klassischen, zweiwertigen Logik. Daran hat der Unvollständigkeitssatz nichts geändert. "Wahr" und "falsch" sind also immer noch die einzigen Optionen. In jedem einzelnen Modell einer Theorie ist jede Aussage entweder wahr oder falsch. Der springende Punkt bei der Unvollständigkeit ist ein anderer nämlich, dass es verschiedene Modelle einer Theorie geben kann, die sich eben nicht einig sind darüber, welche Aussagen sie für richtig oder falsch halten. Jedes einzelne Modell hat jedoch eine feste Meinung darüber!
  • Richtig ist: Falls die Voraussetzungen des Unvollständigkeitssatzes erfüllt sind, dann gibt es unentscheidbare Aussagen.
  • Falsch ist jedoch die Annahme, das gelte für alle Theorien. Der Unvollständigkeitssatz ist weitreichend, das ist richtig, aber trotzdem gibt es genügend Theorien, die die Voraussetzungen nicht erfüllen und daher nicht Gegenstand des Unvollständigkeitssatzes sind. Beispielsweise kann man zeigen, dass die Theorie der reell abgeschlossenen Körper entscheidbar ist. Man kann sogar einen Algorithmus angeben, der zu jeder vorgegebenen Aussage in endlicher (jedoch unrealistisch langer) Zeit einen Beweis oder einen Gegenbeweis findet.




Missverständnis 2:
Die Lösbarkeit einer diophantische Gleichung muss doch aber entscheidbar sein: Man probiere alle natürlichen Zahlen 0,1,2,... der Reihe nach durch. Entweder findet man eine Lösung oder nicht. Also ist die Gleichung entweder lösbar oder eben nicht. Da kann es doch keine dritte Option geben.
Dies ist in gewisser Weise ein Spezialfall des ersten Missverständisses, denn mit "0,1,2,..." erfasst man nur Standard-natürliche Zahlen! In der Tat ist innerhalb des Standardmodells jede diophantische Gleichung entweder lösbar oder nicht lösbar (denn es gibt nur die Optionen "wahr" oder "falsch", siehe Missverständnis Nr.1). Das Problem sind die Nichtstandardmodelle in denen es nach den Standardzahlen 0,1,2,... eben auch noch Nichtstandardzahlen geben kann, die man nicht einfach so durch Abzählen erfassen kann.
Wenn die diophantische Gleichung eine Standardzahl als Lösung hat, dann findet man die in der Tat nach endlicher Zeit durch Ausprobieren und hat damit dann die Lösbarkeit der Gleichung auch wirklich bewiesen.
Wenn die Gleichung jedoch keine Standardlösungen hat, kann es trotzdem Modelle von PA mit Nichtstandardlösungen der Gleichung geben. Die Nichtstandardlösung kann man nicht durch Abzählen finden. Damit ist die Gleichung im Standardmodell nicht lösbar, in einem Nichtstandardmodell jedoch schon. Damit hat man ein Beispiel, wo die Aussage "p=0 ist lösbar" erfüllt ist und eins, wo die Aussage nicht erfüllt ist. Das zeigt, dass die Lösbarkeitsaussage von den Peano-Axiomen unentscheidbar ist. Obwohl wir also in dem Bereich, in dem wir Lösungen haben wollen (nämlich <math>\mathbb{N}</math>), keine Lösungen finden, können wir das nicht mit den Peano-Axiomen beweisen.

Der zweite Unvollständigkeitssatz



Missverständnis:
Version 1: Es lässt sich nicht beweisen, dass die Mathematik widerspruchsfrei ist.
Version 2: Die Widerspruchsfreiheit der Mathematik muss man einfach glauben.
Der Grund, weshalb Version 1 ein Missverständnis ist, ist einfach der, dass "Die Mathematik" zu unpräzise ist.
  • Richtig ist: Die Widerspruchsfreiheit einer für Mathematik geeigneten Theorie kann nicht aus ihr selbst heraus bewiesen werden.
  • Jedoch: Der Unvollständigkeitssatz macht eine Aussage über eine einzelne Theorie und das, was diese eine Theorie in der Lage ist zu beweisen oder eben nicht. Was jedoch dadurch keinesfalls ausgeschlossen wird, ist, dass es eine weitere Theorie geben kann, die die Widerspruchsfreiheit der ursprünglichen beweist.
    Die Zusammenhänge zwischen verschiedenen Theorien können in der Tat sehr komplex sein und vielfältige Phänomene beinhalten.
    Eine Beispielklasse ist die Hierachie der "großen Kardinalzahlen", welche im Moment sehr aktives Thema der Forschung ist. Unter diesem Stichwort fasst man eine Reihe von mengentheoretischen Aussagen zusammen, die sich anscheinend (das ist noch nicht in allen Fällen bewiesen) in eine Ordnung bringen lassen, sodass immer eine dieser Aussagen (zusammen mit ZF oder ZFC) die Widerspruchsfreiheit der vorangegangen Aussagen auf dieser Liste beweist.
    Es gibt auch Paare von Theorien T und T', sodass T die Widerspruchsfreiheit von T' und T' die Widerspruchsfreiheit von T beweist.
  • Ganz konkret gegen die Version 2 muss man sagen, dass die Widerspruchsfreiheit von PA beispielsweise mit Hilfe der Mengenlehre ZFC beweisbar ist. ZFC beweist, dass es das Standardmodell gibt, und der Korrektheitssatz zeigt uns, dass eine Theorie, die ein Modell hat, nicht widersprüchlich sein kann. In der Tat reicht schon sehr, sehr viel weniger als ZFC. Gentzen hat gezeigt, dass transfinite Induktion bis <math>\epsilon_0</math> bereits ausreichend ist. Dies ist wirklich ein Beweis der Widerspruchsfreiheit der Peano-Arithmetik. Noch dazu ein sehr elementarer (wenn man ihn geeignet auseinanderdröselt). So gut wie jeder Mathematiker wird dies auch als Beweis akzeptieren (Es gibt Ausnahmen, die an den absoluten Grundlagen zweifeln, wie z.B. der Existenz der natürlichen Zahlen selbst. Dann kommt man natürlich mit der Mathematik nicht weit und kann über Widerspruchsfreiheit erst recht nicht vernünftig reden. Das führt aber jetzt zu weit.).
  • Überhaupt lässt sich ein sehr großer Teil der Mathematik bereits mit einem kleinen Teil der ZFC-Axiome formalisieren. Es kann auch in diesen Situationen vorkommen, dass die vollen ZFC-Axiome die Widerspruchsfreiheit des kleineren Axiomensystems beweisen kann.




Missverständnis:
Moment einmal... Wenn die Widerspruchsfreiheit von PA unentscheidbar ist, dann heißt das doch, dass es ein Modell gibt, in dem die Widerspruchsfreiheit nicht erfüllt ist. Das heißt also, dass ich in diesem Modell einen Beweis für <math>1=0</math> finden kann. Dieser Beweis zeigt doch dann, dass es in PA ganz sicher Widersprüche gibt.
Das ist schon ein fortgeschritteneres Missverständnis. Hier muss man genauer auf die Formulierungen achten. Die Aussage "PA ist widerspruchsfrei" wird ja bei uns als "Es gibt kein n, dass die Eigenschaft XYZ hat" hat, wobei XYZ eine komplizierte Kodierung von "n ist ein Beweis von 1=0" darstellt.
Es stimmt, dass die Unentscheidbarkeit dieser Aussage zeigt, dass es mindestens ein Modell geben muss, in welchem diese Aussage falsch ist, wo es also wirklich ein n gibt, das die Eigenschaft XYZ hat. Aus diesem n können wir jedoch keinen echten Beweis rekonstruieren, denn es wird sich dabei um eine Nichtstandardzahl handeln. Nichtstandardzahlen können fiese Eigenschaften haben, die solch eine Rekonstruktion unmöglich machen. Beispielsweise kann ihre Primfaktorzerlegung unendlich viele Primfaktoren enthalten und keiner der Faktoren muss überhaupt eine Standard-Primzahl sein. All das macht es unmöglich, das n mit der Eigenschaft XYZ in einen Beweis für 1=0 zurückzuübersetzen.



Abschluss



Man könnte natürlich noch viel mehr sagen. Wenn man die Unvollständigkeitssätze einmal kennt und gut verstanden hat, dann fängt es ja erst an, interessant zu werden. Es ist aus diesen Sätzen ein tiefgehendes und hochinteressantes Theoriegebäude gewachsen, das weitreichende Auswirkungen auch auf sehr konkrete Bereiche der Mathematik hat. Nicht nur, dass es inzwischen eine unüberschaubare Liste an Beispielen für unentscheidbare Sätze aus beinahe allen Disziplinen der Mathematik gibt, die Techniken etwa aus der Modelltheorie finden inzwischen ebenfalls Anwendungen außerhalb der Logik.



Es gibt auch noch viel zu den Unvollständigkeitssätzen selbst zu sagen. Natürlich kann man sich jetzt die Beweise im Detail anschauen, die hier weggelassen wurden. Man kann der Frage nachgehen, wie allgemein die Voraussetzungen wirklich sein müssen. Wir haben ja vor allem aus Bequemlichkeit mit dem Axiomensystem PA gearbeitet und nur angedeutet, dass die Unvollständigkeitssätze auch für andere Axiomensysteme gelten. Man kann z.B. untersuchen, wie viel Arithmetik tatsächlich sein muss. Man kann Theorien suchen, die vom Unvollständigkeitssatz nicht betroffen sind. Solche Theorien haben interessante Anwendungen z.B. in der Informatik gefunden. Es gibt also noch viel zu entdecken.



Damit möchten wir die Ausführungen über den Zweitplatzierten Satz der Jahre 2011 und 2012 aber vorerst beenden. Natürlich gibt es nächstes Jahr einen neuen Satz des Jahres und neue Artikel. Wir freuen uns auf eine spannende Wahl und einen interessanten Siegersatz.



Für die rege Beteiligung auch in diesem Jahr bedanken sich
Die Jury - Buri, Gockel, Kitaktus, PhysikRabe, TomS, Wally und Wauzi
sowie
Der Chef - matroid



Literatur

  1. [1] Heinz-Dieter Ebbinghaus, Jorg Flum, Wolfgang Thomas - Einführung in die mathematische Logik, Spektrum Akademischer Verlag, 2007, 5.Auflage.
    Eine etwas ältere, englische Version ist auch bei google books einsehbar.
  2. [2] Heiße AlgoRhythmen: Grenzen der Berechenbarkeit.
  3. [3] Halting problem bei Wikipedia.
  4. [4] Godehard Link - Collegium Logicum Logische Grundlagen der Philosophie und der Wissenschaften, Band 2, Mentis Verlag GmbH, 2012.


Querverweis

Zum Satz des Jahres 2011 (Residuensatz).
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:

Die Gödelschen Unvollständigkeitssätze [von Gockel]  
Ein Crash-Kurs in den Grundkonzepten aus der Logik und Modelltheorie, die für das Verständnis von Gödels erstem Unvollständigkeitssatz notwendig sind. Typische Missverständnisse im Zusammenhang mit den Gödelschen Sätzen werden exemplarisch besprochen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 22485
 
Aufrufstatistik des Artikels
Insgesamt 771 externe Seitenaufrufe zwischen 2012.05 und 2021.07 [Anzeigen]
DomainAnzahlProz
https://google.com70.9%0.9 %
http://google.de63382.1%82.1 %
http://google.hu283.6%3.6 %
https://google.de455.8%5.8 %
http://google.fr131.7%1.7 %
http://google.it151.9%1.9 %
http://www.bibsonomy.org50.6%0.6 %
https://www.bing.com20.3%0.3 %
http://www.facebook.com30.4%0.4 %
http://mail.qq.com20.3%0.3 %
https://duckduckgo.com20.3%0.3 %
http://www.bing.com40.5%0.5 %
http://de.search.yahoo.com20.3%0.3 %
http://m.facebook.com10.1%0.1 %
http://suche.t-online.de10.1%0.1 %
http://www.delta-search.com10.1%0.1 %
http://suche.web.de10.1%0.1 %
http://www.fireball.de10.1%0.1 %
http://www.ecosia.org10.1%0.1 %
http://google.at10.1%0.1 %
http://avira-int.ask.com10.1%0.1 %
http://www.nibbo.com10.1%0.1 %
https://www.startpage.com10.1%0.1 %

Häufige Aufrufer in früheren Monaten
Insgesamt 734 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2018 (180x)http://google.de/url?sa=t&rct=j&q=
201305-05 (75x)http://google.de/url?sa=t&rct=j&q=unvollständigkeitssätze
201306-06 (47x)http://google.de/url?sa=t&rct=j&q=zweiter gödelscher unvollständigkeits...
201209-09 (45x)http://google.de/url?sa=t&rct=j&q=was heißt mp in dem satz treffen wir uns...
201212-12 (40x)http://google.de/url?sa=t&rct=j&q=matroid unvollständigkeitssatz
201210-10 (40x)http://google.de/url?sa=t&rct=j&q=unvollständigkeitssätze mathematische...
201211-11 (35x)http://google.de/url?sa=t&rct=j&q=unvollständigkeitssatz
201302-02 (28x)http://google.hu/url?sa=t&rct=j&q=
201301-01 (28x)http://google.de/url?sa=t&rct=j&q=gödelsche unvollständigkeitssatz
201408-10 (26x)http://google.de/url?sa=t&source=web&cd=7&ved=0CCwQFjAG
2020-2021 (25x)https://google.de/
201304-04 (23x)http://google.de/url?sa=t&rct=j&q=torsionsgruppe prädikatenlogik
201303-03 (18x)http://google.de/url?sa=t&rct=j&q=unvollständigkeitssatz erklärung
201205-05 (17x)http://google.de/url?sa=t&rct=j&q=widerlegung unvollständigkeitssatz
2020-2021 (17x)https://google.de
201207-07 (15x)http://google.de/url?sa=t&rct=j&q=vereinfachter skolem löwenheim satz
201312-12 (14x)http://google.de/url?sa=t&rct=j&q=gödels unvollständigkeitssatz google ...
201310-10 (13x)http://google.fr/search?q=nichtstandardzahlen -analysis
201505-05 (10x)http://google.de/url?sa=t&rct=j&q=prädikatenlogik " gerichteter" graph sy...
201208-08 (9x)http://google.it/url?sa=t&rct=j&q=matheplanet
201307-07 (8x)http://google.de/url?sa=t&rct=j&q=schlussfolgerung aus goedelschem satz
201504-04 (6x)http://google.it/url?sa=t&rct=j&q=
201309-09 (5x)http://google.de/url?sa=t&rct=j&q=gödel unvollständigkeitssatz baum
201206-06 (5x)http://google.de/url?sa=t&rct=j&q=pa sagt ableitbar phi
2020-2021 (5x)https://google.com/

[Top of page]

"Mathematik: Die Gödelschen Unvollständigkeitssätze" | 16 Comments
The authors of the comments are responsible for the content.

Re: Die Gödelschen Unvollständigkeitssätze
von: Ex_Mitglied_40174 am: Mo. 30. April 2012 10:02:21
\(\begingroup\)
Gibts das auch als PDF?\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Martin_Infinite am: Mo. 30. April 2012 12:24:33
\(\begingroup\)
Danke für diesen Artikel.

Man kann übrigens recht "konkret" ein ganzzahliges Polynom in 53 Unbestimmten hinschreiben, dessen Lösbarkeit nicht entscheidbar ist (James P. Jones, Universal Diophantine Equation, Journal of Symbolic Logic 47 (1982), pp. 549-571). Das hatte mich wirklich vom Hocker gehauen! In diesem Zusammenhang sollte natürlich auch die Widerlegung von Hilberts 10. Problem genannt werden.
 
Ich würde gerne etwas Kritik loswerden. Es wurde im Artikel viel Wert darauf gelegt, die Grundbegriffe aus der Logik und Modelltheorie zu definieren und verständlich zu erklären. Das ist durchaus gelungen (wobei das wohl lieber die Leser beurteilen sollten, die den Stoff noch nicht kannten). Allerdings macht dies 90% des Artikels aus. Und der eigentlich - meiner Meinung nach - interessante Teil kommt viel zu kurz. Der Beweis des Unvollständigkeitssatzes wird recht schnell abgearbeitet. Die ausführlichen Erklärungen, die man sonst immer hatte, fehlen hier. Grundlegende Kenntnisse der Berechenbarkeitstheorie werden auf einmal vorausgesetzt.
 
Auf die mathematischen und philosophischen Konsequenzen des Unvollständigkeitssatzes wird nicht eingegangen. Die Missverständnisse sind zwar sehr klar dargestellt worden, aber vielleicht sollte man dazu zunächst einmal überhaupt ein Verständnis haben? Das Argument "der Artikel ist schon zu lang" zieht hier nicht, weil man viele Teile der formalen Logik auch hätte weglassen oder vereinfachen können; beim Beweis kamen sie doch überhaupt nicht zum Einsatz. Es sollte doch zumindest einmal klar gesagt werden, dass die im Satz von Gödel konstruierte Aussage quasi so definiert ist, dass sie von sich selbst behauptet, nicht beweisbar zu sein.
 
Nach der Lektüre dieses Artikels könnte man sich wohl zu Recht die Frage stellen: Und was soll mich dieser Satz nun interessieren?

Ich möchte das hier nicht nachreichen, zumal es ja genügend Literatur darüber schon gibt. Der Gödelsche Unvollständigkeitssatz hat die Mathematik vor 80 Jahren in ihren Grundfesten erschüttert und hat daraufhin die mathematische Logik revolutioniert. Das gehört quasi in den ersten Absatz eines Artikels über den Gödelschen Unvollständigkeitssatz. Der mathematisch-historische Kontext von Gödel ist natürlich auch sehr spannend und dient auch zum Verständnis des Satzes.
 
Ich bin zwar eher ein Gegner vom populärwissenschaftlicher Entstellung von hochspannender Mathematik, aber: Im Fall von Gödel sind doch die Konsequenzen und die anschauliche Bedeutung viel wichtiger. Einen ganz einfachen und verständlichen Zugang hat zum Beispiel Albrecht Beutelspacher in einer Folge von "Mathematik zum Anfassen" gewählt:

Mathematik zum Anfassen - Gibt es Grenzen der Erkenntnis?

Der Beweis wird ebenfalls sehr anschaulich skizziert. Vielleicht daher ein konstruktiver Vorschlag: Erst das Video anschauen, dann den Artikel lesen.
 
Der zentrale Punkt des Beweises des Satzes ist meiner Meinung nach die Selbstbezüglichkeit: Wie kann es sein, dass eine Aussage über sich selbst sprechen kann? Darüber könnte man noch genauer nachdenken. Im Artikel hat man sich ja auf das Halteproblem zurückgezogen; es funktioniert aber auch mit Hilfe des arithmetischen Fixpunktsatzes, dessen Beweis auf mathoverflow mit Leben gefüllt worden ist. Seitdem ist jedenfalls für mich der Satz von Gödel kein Mysterium mehr.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Gockel am: Mo. 30. April 2012 15:35:09
\(\begingroup\)
Hi Martin.

Der hier skizzierte berechenbarkeitstheoretische Beweise funktioniert anders als der Originalbeweis von Gödel, den du beschreibst! Die unentscheidbare Aussage, die hier konstruiert wird, ist von der Form "Die Turingmaschine mit der Nummer m hält" bzw. eben "Die diophantische Gleichung p=0 ist lösbar". Es ist nicht der Gödel-Satz "Dieser Satz ist unbeweisbar". Genau deshalb ist dieser Beweis des ersten Unvollständigkeitssatzes ja so schön kurz, weil das ganze Gewusel mit dem Fixpunktsatz nicht gemacht werden muss. Die einzige Selbstreferenzialität steckt im Halteproblem und dort ist sie mE viel besser verständlich als im Fixpunktsatz.

Die erste Hälfte ist für mich im Wesentlichen unkürzbar gewesen, eben weil es auch für Leute ohne Vorkenntnisse in der Logik verständlich sein sollte. Die strenge Trennung zwischen Syntax und Semantik und die Erkenntnis, dass eine Formel auch verschiedene Wahrheitswerte in verschiedenen Modellen haben kann, war mir zu wichtig, um es halbherzig und händewedelnd abzuhaken.

Und ich berufe mich trotzdem auf das Argument, dass der Artikel schon so wie er ist, extrem lang ist. Wenn ich (selbst bei drastischer Kürzung der ersten Hälfte) noch auf die philosophischen Konsequenzen, den historischen Rahmen etc. eingegangen wäre, hätte der Artikel jeden sinnvollen Rahmen gesprengt. Beachte auch, dass dies als Ersatz für die Gewinner-Laudatio gedacht ist. Einen "normalen" Artikel von mir hätte es in dieser Form gar nicht gegeben. Ich hätte unter normalen Umständen eine Artikelserie aus dem Thema gemacht.

Es steht ja auch jedem frei, die fehlenden Aspekte selbst in weiteren Artikeln hinzuzufügen. Die entsprechenden Links kann man hier ja ohne Problem noch ergänzen. Falls mich im Laufe des Jahres noch die Langeweile packen sollte, würde ich z.B. den Originalbeweis von Gödel vom ersten und zweiten Unvollständigkeitssatz und/oder die Unentscheidbarkeit des Satzes von Parris-Harrington aus der Ramsey-Theorie in Artikelform bringen.


@Anonymous:
Nein, noch nicht. Das könnte aber leicht behoben werden. Auch hier gilt: Wenn ich einmal Langeweile habe, ...

mfg Gockel.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Martin_Infinite am: Mo. 30. April 2012 20:25:17
\(\begingroup\)
Nun, ehrlich gesagt verstehe ich deinen Beweis nicht so wirklich. Das fällt mir erst jetzt auf. Ich dachte, wegen des Halteproblems sei es sowieso eine selbstbezügliche Aussage.

Wie kann denn "Die n.te Turingmaschine hält" ein Satz sein? Hier kommt die Variable n frei vor. Meiner Meinung nach ist es gerade die Formel mit einer freien Variablen, auf die man den Fixpunktsatz anwenden muss, um Gödels Satz zu erhalten.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Gockel am: Mo. 30. April 2012 20:55:01
\(\begingroup\)
Hi Martin.

Nein, n kommt nicht frei in dieser Aussage vor. Das sind abzählbar viele Aussagen, für jedes n eine. Und für mindestens ein n muss diese Formel unentscheidbar sein.
Aber du hast Recht, das ist missverständlich aufgeschrieben. Ich werde das korrigieren (lassen).

mfg Gockel.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Martin_Infinite am: Di. 01. Mai 2012 10:40:26
\(\begingroup\)
Jetzt ist das Argument klarer, danke. Aber wenn man sich nun einmal den Beweis zum Halteproblem anschaut, so setzt man dort ja auch den Algorithmus in sich selbst ein und erhält dann hier im Wesentlichen Gödels Satz. Das ist auch genau die Argumentation beim Fixpunktsatz. Siehe dazu auch die Antworten der oben verlinkten MO-Diskussion.
 
Noch einmal zum allgemeinen Logik-Teil: Wenn ihr den Beweis von Gödels Satz sowieso nur für PA führt (was ja auch völlig ausreicht), dann hätte man viele Dinge nicht in der Allgemeinheit einführen müssen. Jeder weiß, was eine zahlentheoretische Formel ist, wenn man ein paar Beispiele hinschreibt. Die Beispiele zur Gruppen- und Graphentheorie zeigen, dass der Artikel im Prinzip darauf ausgerichtet ist, Grundlagen der Logik zu vermitteln. Meiner Meinung nach man muss man das nicht machen, um Gödels Satz für PA zu erklären, motivieren und sogar skizzenhaft zu beweisen.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Gockel am: Di. 01. Mai 2012 15:46:50
\(\begingroup\)
Weshalb sollte der Gödelsatz dabei herauskommen? Der Gödelsatz ist viel, viel komplizierter gestrickt als beispielsweise "Die diophantische Gleichung p=0 hat eine Lösung". Darin kommt weder das Beweisbarkeitsprädikat noch eine Gödelnummerierung vor.
Du beißt dich zu stark an der Selbstreferenzialität fest, glaube ich. Das ist ein netter Trick, aber keineswegs unverzichtbar, um den ersten Unvollständigkeitssatz zu beweisen! Es gibt z.B. auch Chaitins Beweis, der das Prinzip der Kolmogorov-Komplexität verwendet. Es gibt einen Beweis, der das Berry-Paradoxon verwendet anstelle des Lügner-Paradoxons. (Okay, das ist auch selbstreferenziell, hat aber eine andere Struktur)
Beachte auch, dass man für andere algorithmisch unlösbare Problem weitere Beweise bekommt und längst nicht alle sind zum Halteproblem identisch (Stichwort Turing-Degrees) oder sind in irgendeiner Form selbstreferenziell.

EDIT: Und wo wir gerade dabei sind, uns MO-Links um die Ohren zu hauen... ;-)
Hier wurde die Frage gestellt, ob ein Kontext, indem der Unvollständigkeitssatz gilt, stets einen Mechanismus zur Selbstreferenzialität enthalten muss:
http://mathoverflow.net/q/78819/3041

mfg Gockel.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: gaussmath am: Fr. 04. Mai 2012 11:23:19
\(\begingroup\)
Der eingeplante Autor für den 1. Satz sprang ab, ok, aber warum seid ihr dann auf den 2. Sieger ausgewichen? Ich kann mir kaum vorstellen, dass das Noether-Theorem ein weitaus größeres "Kaliber" als der Unvollständigkeitssatz ist...\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Ex_Mitglied_40174 am: Fr. 04. Mai 2012 15:33:19
\(\begingroup\)
@gaussmath: es hat sich halt kein Anderer (oder keine Anderen) gefunden.
Ich denke, dass ein einfache Darstellung des Noether-Theorems auch nicht unbedingt Sinn eines Artikels wäre, da es dazu ja bereits viele Artikel im Netz gibt; wichtiger wird wohl seine praktische Anwendung sein, sprich wo genau wurde in letzter Zeit in der Physik eine Erhaltungsgröße entdeckt, die zuvor ein Theoretiker (vllt sogar eine Theoretikerin) als Invariante ausgemacht hat. Das dürften wohl nur Physiker wissen, die auch in der Forschung tätig, aber hier offenbar nicht sehr zahlreich vertreten sind.
\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Gockel am: Fr. 04. Mai 2012 15:53:48
\(\begingroup\)
Es ist wie Anonymous schreibt: Es hat sich auf mehrfache Nachfrage niemand gefunden, der den entsprechenden Artikel für das Noether-Theorem hätte schreiben wollen.
Aber doch: Eine einfache Darstellung des Theorems wäre definitiv Teil des Artikels gewesen, sonst wäre er nicht als Laudatio geeignet gewesen.

Es steht übrigens weiterhin jedem MPler frei, einen solchen Artikel noch zu schreiben! Der Satz ist ja das ganze Jahr über der Gewinner. Dafür wird es auch wie im letzten Jahr ein Stäbchen geben.

mfg Gockel.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Wauzi am: Sa. 05. Mai 2012 02:04:20
\(\begingroup\)
Warum so kritische Reaktionen auf diesen Artikel? Sicher kann man sich das eine oder andere noch wünschen, oder auch das Weglassen einiger Punkte für besser halten. Das aber sind dann schon sehr subjektive Meinungen, die natürlich auch vom eigenen Kenntnisstand beeinflußt sind.
Ich finde, daß dieser Artikel rundum gelungen ist. Er bleibt nie an der Oberfläche, nimmt den Leser aber dank eines lockeren Schreibstils immer mit und eröffnet Einblicke in Bereiche der Mathematik, die sicher manchen bis jetzt verschlossen geblieben sind. Ich zB habe während meines gesamten Studiums nie etwas von axiomatischer Logik gehört, so etwas gab es damals in Regensburg noch nicht. D.h uns wurde gesagt, man kann das so formalisieren, aber das würde hier zu weit führen. Deshalb war ich besonders von dieser umfangreichen Einführung in die Grundlagen, die Gockel gegeben hat, sehr angetan. Ein Buch darüber würde ich mittlerweile nie mehr durcharbeiten, aber aus diesem Artikel habe ich doch einiges mitnehmen können.

Für mich gehören die Artikel von Gockel schon seit langem zu den absoluten highlights, und da reiht sich dieser Beitrag passend ein.

Gruß Wauzi
 
\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: matroid am: Di. 08. Mai 2012 22:02:42
\(\begingroup\)
Mein Dank an die Jury-Mitglieder (Kitaktus, PhysikRabe, Wally, Buri, TomS, Gockel, Wauzi), die aus allen Vorschlägen die Vorauswahl für unsere diesjährige Abstimmung zum Satz des Jahres getroffen und die 10 ausgesuchten Sätze auf dem Abstimmungsformular vorgestellt haben. haben. Herzlichen Dank an Gockel für diesen großartigen Artikel. Wauzi hat das sehr schön gesagt, ich schließe mich an. Danke an Bilbo, der am Artikel mitgearbeitet hat.

Für mich ist jetzt ein guter Abschluss gefunden worden.
Bis zum nächsten Mal!
Euer Matroid\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Gockel am: Mo. 04. Juni 2012 17:18:06
\(\begingroup\)
Und noch ein MO-Link:
http://mathoverflow.net/a/98768/3041
Joel David Hamkins hat hier eine Liste von verschiedenen Zugängen zum Beweis des ersten Unvollständigkeitssatzes gepostet. Der Beweis hier im Artikel wird im zweiten Abschnitt skizziert, die angedeutete Verallgemeinerung vom Halteproblem auf andere algorithmisch unentscheidbare Probleme im dritten Absatz.

EDIT (05.10.2013):
Eine weitere Diskussion auf Mathoverflow hat jemanden dazu bewogen, verschiedenen Beweisansätze aufzuschreiben und zu vergleichen:
http://mathoverflow.net/a/72151/3041
Der Sinn dieses Posts geht eher in die Richtung, in einem halbwegs sinnvollen Sinne zu zeigen, dass die verschiedenen Beweise des ersten Unvollständigkeitssatzes nicht alle äquivalent zueinander sind.

mfg Gockel.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Ex_Mitglied_40174 am: Mo. 21. Juli 2014 07:42:31
\(\begingroup\)
Ich hätte folgende Frage:

Wie Wikipedia schreibt, ist ein Satz "in der Mathematik eine widerspruchsfreie logische Aussage, die mittels eines Beweises als wahr erkannt, das heißt, aus Axiomen und bereits bekannten Sätzen hergeleitet werden kann".

Das bedeutet, dass die Gödelschen Unvollständigkeitssätze auf irgendwelchen Axiomen fußen müssen. Meine Frage: Auf welchen Axiomen fußen sie? Von welchen Axiomen sind die Gödelschen Unvollständigkeitssätze abgeleitet?

Die Gödelschen Unvollständigkeitssätze stehen nämlich im Widerspruch zur Klassischen Aussagenlogik, weil dort das Prinzip "tertium non datur" gilt - also es keine paradoxen Aussagen geben kann. Also kann den Gödelschen Sätzen nicht das Axiomensystem der Klassischen Aussagenlogik zugrunde liegen.

Siehe auch: cdvolko.blogspot.co.at/2014/07/gibt-es-paradoxien.html

\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Gockel am: Mo. 21. Juli 2014 12:48:18
\(\begingroup\)
Hi Anonymous.

Und siehe auch den obigen Artikel, wo dein Missverständnis bzgl. Tertium non datur aufgeklärt wird.

mfg Gockel.\(\endgroup\)
 

Re: Die Gödelschen Unvollständigkeitssätze
von: Ex_Mitglied_43988 am: Sa. 09. Mai 2015 19:40:52
\(\begingroup\)
Hi, Gockel.

Gockel schreibt:
Genau deshalb ist dieser Beweis des ersten Unvollständigkeitssatzes ja so schön kurz, weil das ganze Gewusel mit dem Fixpunktsatz nicht gemacht werden muss.

Gödel beweist in seiner Originalarbeit gar nicht den Fixpunksatz im Allgemeinen. Man könnte sagen, dass er es nur am Beispiel seiner Formel, die ihre eigene Unbeweisbarkeit behauptet, tut. Das ist alles andere als Gewusel! Tatsächlich ist Gödels Originalbeweis des ersten Unvollständigkeitssatzes ziemlich kurz und elegant. (Vielleicht werde ich einen eigenen Artikel schreiben, in dem ich mit der originalen Beweisidee den Gödel'schen Unvollständigkeitssatz schnell herleite.) Der Unvollständigkeitssatz lässt sich auch mithilfe des Satzes von Löb im Affenzahn beweisen (ohne nennenswerte Vorkenntnisse). Ich würde deinen Beweis des Unvollständigkeitssatzes, den ich nicht gelesen habe, als unnötig komplex bezeichnen, da du auf dem Fakt aufbaust, dass das Halteproblem unlösbar ist.

mfg asdf.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]