1931 veröffentlichte der österreichische Logiker Kurt Gödel seinen Unvollständigkeitssatz, ein Ergebnis, das weithin als eine der größten intellektuellen Errungenschaften der Neuzeit gilt.
Der Satz besagt, dass es in jedem vernünftigen mathematischen System immer wahre Aussagen geben wird, die nicht bewiesen werden können. Das Ergebnis war ein großer Schock für die mathematische Gemeinschaft, in der die vorherrschende Meinung ein unerschütterlicher Optimismus hinsichtlich der Macht und Reichweite ihres Fachs war. Man ging davon aus, dass Mathematik „vollständig“ sei, das heißt, alle mathematischen Aussagen seien entweder beweisbar oder widerlegbar. Der 25-jährige Gödel zeigte, dass dies falsch war, indem er eine wahre Aussage konstruierte, die nicht beweisbar war. Mathematik, verkündete er, habe ihre Grenzen.
Das Unvollständigkeitstheorem veränderte das Studium der Grundlagen der Mathematik und würde ein wichtiges Ergebnis für die Informatik werden, da es zeigt, dass alle formalisierten Systeme, wie beispielsweise Programmiersprachen, in ihrer Leistungsfähigkeit Grenzen haben.
Der Satz ist auch das Herzstück des heutigen Rätsels, zu dem wir gleich kommen werden.
Gödels Beweis seines Theorems basiert auf Selbstreferenz: In einer formalen mathematischen Umgebung ist die Aussage „Dieser Satz ist unbeweisbar“ sowohl wahr als auch formal unbeweisbar.
Die technischen Details des Beweises sind hart. Doch der amerikanische Logiker Raymond Smullyan (1919-2017) hat einen brillanten Weg gefunden, den Kern des Unvollständigkeitssatzes mit einfachen Logikrätseln über Wahrheitserzähler und Lügner zu vermitteln. Der heutige Teaser, komponiert in Zusammenarbeit mit Professor Benedikt Löwe des Churchill College, Cambridge, ist von Smullyans Ansatz inspiriert.
Die zwei Stämme von If
Im Ozean der Deduktion liegt die logische Insel If. Die hier geborenen Menschen gehören einem von zwei Stämmen an: den Alethiern und den Pseudern. Die einzige Möglichkeit, einen Alethianer von einem Pseudonym zu unterscheiden, besteht darin, mit ihnen zu sprechen. Alethianer sagen immer die Wahrheit, egal was sie sagen. Pseudonyme werden immer Unwahrheiten äußern, egal was sie sagen.
Im Zentrum der Insel führt der Meister der Alethianer das Ledger of Identity, ein Buch, das die Namen aller auf der Insel Geborenen zusammen mit ihrem Stamm auflistet. Die Informationen im Ledger of Identity sind korrekt und für jeden, der danach fragt, frei zugänglich.
Eines Tages kommt ein unerschrockener Entdecker auf If an. Sie begegnet verschiedenen Bewohnern und identifiziert sie durch geschickte Fragen als Alethier und Pseuder.
Nach mehreren erfolgreichen Begegnungen trifft sie einen Mann namens Kurt. Die Forscherin kennt seine Stammeszugehörigkeit nicht, aber bevor sie Zeit hat, ihm eine Frage zu stellen, sagt er: “Sie werden nie konkrete Beweise haben, die bestätigen, dass ich ein Alethianer bin.”
1. Ist Kurt ein Alethianer, ein Pseudianer oder keiner von beiden?
2. Wie könnte dies mit dem Unvollständigkeitssatz von Gödel zusammenhängen?
Bitte kehren Sie um 17:00 Uhr in Großbritannien zurück, um die Lösungen und eine Diskussion zu erhalten.
NICHTS VERRATEN. Poste stattdessen bitte deine Lieblingslogikwitze.
Das heutige Gödelsche Puzzle ist eine Vorfeier des UNESCO-Weltlogiktages, der jährlich am 14. Januar stattfindet. (Das Datum wurde gewählt, da es sowohl der Tag ist, an dem Gödel 1978 starb, als auch der Tag, an dem der Logiker Alfred Tarski geboren wurde 1901.)
Um mehr über den World Logic Day 2022 – diesen Freitag – zu erfahren und eine Liste aller geplanten Veranstaltungen zu lesen klicken Sie hier.
Ich setze hier alle zwei Wochen an einem Montag ein Puzzle. Ich bin immer auf der Suche nach tollen Rätseln. Wenn Sie einen vorschlagen möchten, senden Sie mir eine E-Mail.
Ich bin Autor mehrerer Rätselbücher, zuletzt das Rätselbuch für Sprachliebhaber. Ich halte auch Schulvorträge über Mathematik und Rätsel (online und persönlich). Bei Interesse an Ihrer Schule melden Sie sich bitte.