Gödelscher Unvollständigkeitssatz

Grundbegriffe

Aussagen sind Folgen von Zeichen, die ähnlich wie ein Programm einer Programmiersprache einer gewissen Syntax genügen müssen. Für solche Aussagen definiert man auf naheliegende Weise das Konzept der Gültigkeit oder Wahrheit in Strukturen (siehe Modelltheorie). Dabei kann die Wahrheit einer Aussage durchaus von der betrachteten Struktur abhängen: Eine Aussage mit der intendierten Bedeutung „Es gibt ein Element, das echt größer als 0 und echt kleiner als 1 ist“ gilt zum Beispiel in der Struktur der reellen Zahlen, nicht jedoch in der Struktur der natürlichen Zahlen.

Ein formales System ist ein System, in dem sich mathematische Aussagen beweisen lassen. Jedes formale System besteht aus einer Sprache, die die Menge der wohlgeformten Formeln und Aussagen spezifiziert, einer Menge von Axiomen und einer Menge von Schlussregeln, mit denen aus bereits bewiesenen Aussagen neue Aussagen hergeleitet werden können. Ein formales System bestimmt eine Theorie, die Menge aller im System herleitbaren Aussagen. Wichtig ist dabei, dass die Korrektheit eines Beweises im formalen System auf mechanische Weise verifiziert werden kann. Damit sind beispielsweise Kalküle mit unendlich großen Beweisen keine formalen Systeme in diesem Sinne. Im Sinne der Berechenbarkeitstheorie entspricht dies der formalen Forderung, dass die Theorie rekursiv aufzählbar sein muss.

Ein System T heißt widerspruchsfrei oder konsistent, wenn es keine Aussage A gibt, sodass aus T sowohl A als auch die Verneinung (Negation) von A folgt. Diese Bedingung ist, wie man leicht zeigen kann, äquivalent dazu, dass nicht jede Aussage aus T folgt.

Ein System T heißt vollständig, wenn für alle Aussagen A aus T die Aussage A oder deren Negation folgt.