Berry-Paradox

Das Berry-Paradoxon (auch: Berry-Paradox) ist ein selbstreferenzierendes Paradoxon, das sich aus dem Ausdruck „die kleinste ganze Zahl, die nicht durch eine gegebene Anzahl von Wörtern definierbar ist“ ergibt. Bertrand Russell, der sich als erster schriftlich mit dem Paradoxon auseinandersetzte, ordnete es G. G. Berry (1867-1928), einem jungen Bibliothekar der Bodleian Library Oxfords zu^[1], der das eingeschränktere Paradoxon „die erste undefinierbare Ordinalzahl“ vorgeschlagen hatte.

Das Paradoxon

Gegeben sei der Ausdruck:

„Die kleinste positive ganze Zahl, die nicht mit unter vierzehn Wörtern definierbar ist.“

Da es endlich viele Wörter gibt, gibt es auch endlich viele Sätze aus 14 Wörtern, und daher endlich viele positive ganze Zahlen, die nach dem Schubfachprinzip durch Sätze von unter 14 Wörtern definiert werden können. Weil es unendlich viele positive ganze Zahlen gibt, muss es positive ganze Zahlen geben, die nicht mit einem Satz von unter 14 Wörtern definiert werden können – nämlich jene, die die Eigenschaft haben, „nicht mit weniger als 14 Wörtern definiert werden zu können“. Nach dem Wohlordnungssatz muss es in der Menge der diese Eigenschaft erfüllenden Zahlen eine kleinste geben; demzufolge gibt es eine kleinste positive ganze Zahl mit der Eigenschaft „nicht definierbar in unter 14 Wörtern“. Dies ist die Ganzzahl, auf die sich der obige Ausdruck bezieht; das bedeutet, diese Ganzzahl wird durch den obigen Ausdruck definiert. Der gegebene Ausdruck ist aber nur 13 Wörter lang; diese Ganzzahl wird also definiert mit unter 14 Wörtern. Also ist sie definierbar mit weniger als 14 Wörtern und demzufolge nicht die kleinste positive ganze Zahl, die nicht mit weniger als 14 Wörtern definiert werden kann, und wird daher letztendlich nicht durch diesen Ausdruck definiert. Dies ist ein Paradoxon: Es muss eine Ganzzahl geben, die mit diesem Ausdruck definiert wird, aber da der Ausdruck widersprüchlich ist (jede Ganzzahl, die es definiert, ist offensichtlich definierbar mit unter 14 Wörtern), kann es keine Ganzzahl geben, die er definiert.

Auflösung

Das oben beschriebene Berry-Paradoxon ergibt sich aufgrund der systematischen Ambiguität des Wortes „definierbar“. In anderen Formulierungen des Berry-Paradoxons, beispielsweise „…nicht benennbar mit weniger als…“, übernehmen andere Wörter diese systematische Ambiguität. Formulierungen dieser Art legen den Grundstein für Teufelskreis-Irrtümer. Weitere Begriffe dieser Eigenschaft sind erfüllbar, wahr, falsch, funktionieren, Eigenschaft, Klasse, Beziehung, kardinal und ordinal^[2]. Um ein solches Paradoxon aufzulösen, ist zunächst genau festzustellen, an welcher Stelle ein Fehler im Sprachgebrauch gemacht wurde, um dann Regeln zur Vermeidung dieses Fehlers aufzustellen.

Das oben angeführte Argument „Weil es unendlich viele positive ganze Zahlen gibt, muss es positive ganze Zahlen geben, die nicht mit einem Satz von unter 14 Wörtern definiert werden können“ setzt voraus, dass „es eine Ganzzahl geben muss, die mit diesem Ausdruck definiert wird“, was widersinnig ist, weil die meisten Sätze „mit unter 14 Wörtern“ mehrdeutig sind hinsichtlich ihrer Definition einer Ganzzahl, wofür obiger 13-Wort-Satz ein Beispiel ist. Die Annahme, man könne Sätze in eine Beziehung zu Zahlen setzen, ist eine Fehlannahme^[3].

Noch rigoroser kann diese Familie von Paradoxa aufgelöst werden, indem man Klassifizierungen der Wortbedeutung einführt. Ausdrücke mit systematischer Ambiguität können mit Subskripten versehen werden, die die bevorzugte Bedeutungsinterpretation signalisieren: Die Zahl, die nicht mit weniger als vierzehn Wörtern benennbar₀ ist, kann benennbar₁ sein in weniger als vierzehn Wörtern.^[4]

Formale Analogien

Mit Programmen oder Beweisen einer gewissen Länge ist es möglich, eine Entsprechung des Berry-Ausdrucks in einer formal-mathematischen Sprache zu formulieren, wie geschehen durch Gregory Chaitin. Obwohl die formale Entsprechung nicht zu einem logischen Widerspruch führt, beweist sie doch bestimmte unmögliche Ergebnisse.

George Boolos konstruierte 1989 eine formalisierte Version von Berrys Paradoxon, um den Gödelschen Unvollständigkeitssatz auf neue und einfachere Weise zu beweisen. Die Grundidee dieses Beweises ist, dass eine für x getroffene Annahme als Definition für n herangezogen werden kann, wenn x = n für eine Natürliche Zahl gilt, und dass die Menge {(n, k): n hat eine Definition der Länge k Symbole} mit Gödelnummern dargestellt werden kann. Dann kann die Annahme „m ist die erste Zahl, die nicht mit weniger als k Symbolen definiert werden kann“ formalisiert und als Definition in oben genanntem Sinne akzeptiert werden.

Zusammenhang zur Kolmogorow-Komplexität

→ Hauptartikel: Kolmogorow-Komplexität

Es ist möglich, eindeutig zu definieren, was die minimal benötigte Zahl von Symbolen ist, um eine gegebene Zeichenkette zu beschreiben. In diesem Kontext können die Begriffe Kette und Zahl austauschbar verwandt werden, da eine Zahl tatsächlich eine Kette von Symbolen ist, also ein deutsches Wort (wie das Wort „vierzehn“ in dem Paradoxon), während es andererseits möglich ist, jedes Wort mit einer Zahl darzustellen, z. B. mit der Zahl seiner Position in einem gegebenen Wörterbuch oder durch passende Kodierung. Manche lange Zeichenketten können durch weniger Symbole exakt beschrieben werden, als für die vollständige Darstellung nötig wären, wie es oft bei Datenkompression vorkommt. Die Komplexität einer gegebenen Zeichenkette ist dann definiert als die minimale Länge, die eine Beschreibung benötigt, um (eindeutig) die volle Repräsentation dieser Zeichenkette darzustellen.

Die Kolmogorow-Komplexität wird mithilfe formaler Sprachen oder Turingmaschinen definiert, die die Vermeidung von Ambiguitäten zulassen, welche Zeichenkette aus einer gegebenen Beschreibung resultiert. Nachdem diese Funktion definiert ist, kann bewiesen werden, dass sie nicht berechenbar ist. Der Beweis durch Widerspruch zeigt, dass wenn es möglich wäre, die Kolmogorow-Komplexität zu berechnen, es auch möglich wäre, systematisch Paradoxa wie dieses zu generieren, das heißt Beschreibungen, die kürzer sind als die Komplexität der beschriebenen Zeichenkette impliziert. Das bedeutet, die Definition der Berryzahl ist paradox, weil nicht tatsächlich berechenbar ist, wieviele Wörter nötig sind, um eine Zahl zu definieren, und wir wissen, dass eine solche Berechnung aufgrund des Paradoxons nicht durchführbar ist.

Fußnoten

1. ↑ http://books.google.com/books?id=obY48lTt-2AC&pg=PA63&lpg=PA63&dq=g+g+berry+only+person+bertrand+russell&source=bl&ots=vWW5uE7oWs&sig=R9domCGlXAOHSCFcaUuEOVJ-B50&hl=en&ei=7dSpSczPBJDMnQeiwrTrDw&sa=X&oi=book_result&resnum=3&ct=result Russell (1927).
2. ↑ Russell und Whitehead (1927)
3. ↑ French demonstrierte 1988, dass eine unendliche Anzahl von Zahlen eindeutig mit den exakt selben Wörtern beschrieben werden kann.
4. ↑ Willard Quine: Ways of Paradox. Harvard Univ. Press 1976

Siehe auch

• Fleißiger Biber

Quellen

• Charles H. Bennett (1979) "On Random and Hard-to-Describe Numbers." IBM Report RC7483.
• George Boolos (1989) "A new proof of the Gödel Incompleteness Theorem," Notices of the American Mathematical Society 36: 388–90; 676. Nachgedruckt 1998 in Logic, Logic, and Logic. Harvard Univ. Press: 383-88.
• Gregory Chaitin (1995) "The Berry Paradox,." Complexity 1: 26-30.
• French, James D. (1988) "The False Assumption Underlying Berry's Paradox," Journal of Symbolic Logic 53: 1220–1223.
• Bertrand Russell (19nn) "Les paradoxes de la logique," Revue de métaphysique et de morale 14: 627–650
• Bertrand Russell und Alfred N. Whitehead (1927) Principia Mathematica. Cambridge University Press. 1962 teilw. Paperback-Neuausgabe bis *56.

Weblinks

• Roosen-Runge, Peter H. (1997) "Berry's Paradox."
• Eric W. Weisstein: Berry Paradox auf MathWorld (englisch)
• Weisstein, Eric W. "Berry paradox,"
• Wolfram Researchs MathWorld