Quelltext der Seite Berry-Paradoxon

Das '''Berry-Paradoxon''' (auch: Berry-Paradox) ist ein [[Selbstreferenzialität|selbstreferenzierendes]] [[Paradoxon]], das sich aus dem Ausdruck „die kleinste [[ganze Zahl]], die nicht durch eine gegebene Anzahl von [[Wort|Wörtern]] definierbar ist“ ergibt. [[Bertrand Russell]], der sich 1908 als erster schriftlich mit dem Paradoxon auseinandersetzte, ordnete es [[George Godfrey Berry]] (1867–1928) zu, einem [[Bibliothekar]] der [[Bodleian Library]] [[Oxford]]s.<ref name="Russell">Russell: [http://www.cfh.ufsc.br/~dkrause/pg/cursos/selecaoartigos/Russell(1905).pdf ''Mathematical logic as based on the theory of types''] (PDF; 1,9&nbsp;MB) In: ''[[American Journal of Mathematics]]'', Band 30 (1908), S. 223 (4). Im englischen Original sind es neunzehn Silben statt vierzehn Wörter.</ref>

== Das Paradoxon ==
Gegeben sei der Ausdruck:
{{Zitat
 |Text=Die kleinste [[Positive und negative Zahlen|positive ganze Zahl]], die nicht mit unter vierzehn<!-- bitte nicht durch Ziffern ersetzen, da sonst nicht deutlich als Wort erkennbar --> Wörtern definierbar ist.
 |ref=<ref name="Russell" />}}

Da es [[Endliche Menge|endlich]] viele Wörter gibt, gibt es auch endlich viele Sätze aus 14 Wörtern, und damit nur endlich viele positive ganze Zahlen, die 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“. Da die [[Natürliche Zahl|natürlichen Zahlen]] [[wohlgeordnet]] sind, 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 [[Bezeichnung|benennbar]] mit weniger als…“, übernehmen andere Worte diese systematische Ambiguität. Formulierungen dieser Art legen den Grundstein für [[Teufelskreis]]-Irrtümer. Weitere Begriffe dieser Eigenschaft sind ''[[Variable (Logik)|erfüllbar]]'', ''[[Wahrheit|wahr]]'', ''[[Wahrheitswert|falsch]]'', ''[[Funktion (Objekt)|funktionieren]]'', ''[[Eigenschaft]]'', ''[[Klasse (Mengenlehre)|Klasse]]'', ''[[Relation (Philosophie)|Beziehung]]'', ''[[Kardinalzahl (Mathematik)|kardinal]]'' und ''[[Ordinalzahl|ordinal]]''.<ref>Russell und Whitehead (1927)</ref> 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 Worten 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 Worten“ 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.<ref>French demonstrierte 1988, dass eine unendliche Anzahl von Zahlen eindeutig mit den exakt selben Worten beschrieben werden kann.</ref>

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 [[Tiefstellung|Subskripten]] versehen werden, die die bevorzugte Bedeutungsinterpretation signalisieren: ''Die Zahl, die nicht mit weniger als vierzehn Worten benennbar<sub>0</sub> ist, kann benennbar<sub>1</sub> sein in weniger als vierzehn Worten.''<ref>[[Willard Van Orman Quine|Willard Quine]]: ''Ways of Paradox''. Harvard Univ. Press 1976</ref>

== 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ödelscher Unvollständigkeitssatz|Gödelschen Unvollständigkeitssatz]] auf neue und einfachere Weise zu beweisen. Die Grundidee dieses Beweises ist, dass eine für <math>x</math> getroffene Annahme als ''Definition'' für <math>n</math> herangezogen werden kann, wenn <math>x = n</math> für eine natürliche Zahl gilt, und dass die Menge <math>\left\{(n, k): n \mbox{ hat eine Definition der Länge }k\right\}</math> mit [[Gödelnummer]]n dargestellt werden kann. Dann kann das Prädikat „<math>m</math> ist die erste Zahl, die nicht mit weniger als <math>k</math> Symbolen definiert werden kann“ formalisiert und als Definition in oben genanntem Sinne akzeptiert werden.

== Zusammenhang zur Kolmogorow-Komplexität ==
''siehe 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.&nbsp;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 [[Formale Sprache|formaler Sprachen]] oder [[Turingmaschine]]n definiert, die Ambiguitäten, welche Zeichenkette aus einer gegebenen Beschreibung resultiert, vermeiden. 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. Das bedeutet, die Definition der Berryzahl ist paradox, weil nicht tatsächlich berechenbar ist, wie viele Wörter nötig sind, um eine Zahl zu definieren, und wir wissen, dass eine solche Berechnung aufgrund des Paradoxons nicht durchführbar ist.

== Siehe auch ==
* [[Fleißiger Biber]]

== Literatur ==
* Charles H. Bennett: [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.27.3492&rep=rep1&type=pdf ''On Random and Hard-to-Describe Numbers''.] (PDF) IBM Report RC7483, 1979.
* [[George Boolos]]: ''A new proof of the Gödel Incompleteness Theorem''. In: ''Notices of the American Mathematical Society'', 36, 1989, S. 388–390, 676. Nachgedruckt 1998 in ''Logic, Logic, and Logic''. Harvard Univ. Press, S. 383–88.
* [[Gregory Chaitin]]: ''The Berry Paradox''. In: ''Complexity'', 1, 1995, S. 26–30, [[doi:10.1002/cplx.6130010107]].
* James D. French: ''The False Assumption Underlying Berry’s Paradox''. In: ''Journal of Symbolic Logic '', 53, 1988, S. 1220–1223, [http://www.jstor.org/pss/2274615 jstor.org].
* [[Bertrand Russell]]: ''Les paradoxes de la logique''. In: ''Revue de métaphysique et de morale'', 14, S. 627–650
* Bertrand Russell, [[Alfred N. Whitehead]] (1927) ''[[Principia Mathematica]]''. Cambridge University Press. 1962 teilw. Paperback-Neuausgabe bis *56.

== Weblinks ==
* Peter H. Roosen-Runge: [https://web.archive.org/web/20020205181710/http://www.cs.yorku.ca/~peter/Berry.html Berry’s Paradox.] 1997
* {{MathWorld |id=BerryParadox |title=Berry Paradox}}

== Einzelnachweise ==
<references />

[[Kategorie:Philosophie der Mathematik]]
[[Kategorie:Paradoxon]]