Rayos Nummer

Ein Benutzer hat den Schutz dieser Seite für 1 Jahr beantragt. Der Grund dafür ist: Vor kurzem vandalisiert.

Rayos Zahl ist eine der größten benannten Zahlen, die in einem großen Zahlenkampf gegen Agustín Rayo gegen Adam Elga geprägt wurde. Rayos Zahl ist, in Rayos eigenen Worten, „die kleinste positive ganze Zahl, die größer ist als jede endliche positive ganze Zahl, die durch einen Ausdruck in der Sprache der Mengenlehre erster Ordnung mit Googol-Symbolen oder weniger benannt wird.“

Obwohl die Mengenlehre zweiter Ordnung in der ursprünglichen Definition nicht spezifiziert war und als die philosophische (aber mathematisch schlecht definierte) Sammlung von Formeln geklärt ist, die die reale Welt philosophisch „befriedigt“, ist es vernünftig anzunehmen, dass \(\textrm {ZFC}\) Mengenlehre ist ein Segment erster Ordnung der nicht spezifizierten Mengenlehre, weil die Mehrheit der Mathematiker und Googologen an \ (\textrm {ZFC}\) Mengenlehre interessiert ist. Unter der Annahme, dass Rayos Funktion über alle Funktionen hinausgeht, die in \(\textrm{ZFC}\) Mengenlehre definiert werden können. In diesem Artikel verwenden wir immer die gleiche Annahme, mit Ausnahme des Axiomabschnitts, der das Problem der fehlenden Klärung der Mengenlehre zweiter Ordnung eingehender erklärt.

Rayos Funktion ist eine der am schnellsten wachsenden Funktionen, die jemals in der professionellen Mathematik entstanden sind; nur wenige Funktionen, insbesondere seine Erweiterung, Fisch Nummer 7 übertrifft es. Da Rayos Funktion schwierige Mathematik verwendet, gibt es mehrere Versuche, sie zu verallgemeinern, die zum Scheitern führen. Zum Beispiel wurde die FOOT-Funktion (Oodle-Theorie erster Ordnung) ebenfalls als übertroffen angesehen, ist jedoch schlecht definiert.

Definition

Seien \(\) und \(\) Gödel-kodierte Formeln und \(s\) und \(t\) Variablenzuweisungen. Definieren Sie \(\text{Sat}(, s)\) wie folgt:

\(\ text{Rayo} (n)\) ist also die kleinste Zahl, die größer ist als alle Zahlen, die in \(n\) -Symbolen Rayo-benennbar sind.

Beachten Sie, dass die x_i in t(xi) ∈ t(xj) und t(xi) = t(xj) in der obigen Definition von \(\text{Sat}\) x_1 in der ursprünglichen Definition waren. Obwohl x_1 die einzige freie Variable ist, die in einem Raynamen vorkommen darf, wird die Variablenzuweisung für x_i tatsächlich in der Definition von ∃-fourmulae . Daher funktionierte die ursprüngliche Definition nicht wie von Rayo beabsichtigt und wurde von Rayo selbst aktualisiert. (Abgerufen 19/05/2020)

Erklärung 1

Es gibt viele Terminologien der formalen Logik, die von den Autoren abhängen. Wir erklären eine dieser Terminologien. Eine formale Sprache ist eine Menge von konstanten Termsymbolen, variablen Termsymbolen, die durch natürliche Zahlen indiziert sind, Funktionssymbolen und Beziehungssymbolen. Eine Formel in einer formalen Sprache \ (L\) sind formale Zeichenfolgen, die aus konstanten Termsymbolen in \(L\), variablen Termsymbolen in \(L\), Funktionssymbolen in \ (L\), Relationssymbolen in \ (L\), Quantifizierern und logischen Verknüpfungen nach einer bestimmten Syntax aufgebaut sind.

Eine Interpretation von Formeln in \(L\) ist eine Karte, die jedem konstanten Termsymbol eine Konstante, jedem Funktionssymbol eine Funktion und jedem Beziehungssymbol eine Relation zuweist. Bei einer Interpretation von Formeln in \(L\) wird jede geschlossene Formel in \(L’\) als wahr oder falsch bewertet, solange ein Wahrheitsprädikat formalisierbar ist, da es einer Formel über Parameter in \(V\) entspricht. Insbesondere können wir bei einer Variablenzuweisung und einer Interpretation fragen, ob eine gegebene Formel in \(L\) wahr oder falsch ist, solange ein Wahrheitsprädikat formalisierbar ist. Um ein Wahrheitsprädikat zu formalisieren, brauchen wir eine ausreichend starke Mengenlehre. Zum Beispiel ist die ZFC-Mengenlehre für diesen Zweck nicht geeignet.

Rayo definierte eine sehr spezifische und abstrakte Formensprache zusammen mit einer kanonischen Interpretationswahl:

  • Eine Atomformel „xa∈xb“ bedeutet, dass die ath-Variable ein Element der b-ten Variablen ist.
  • Eine Atomformel „xa=xb“ bedeutet, dass die ath-Variable gleich der b-ten Variablen ist.
  • Eine Formel „(e)“ für eine Formel e bedeutet die Negation von e.
  • Eine Formel „(e∧f)“ für die Formeln e und f bedeutet die Konjunktion (das logische und) von e und f.
  • Eine Formel „∃xa(e)“ bedeutet, dass wir das freie Vorkommen der ath-Variablen modifizieren können, d.h.e. Ersetzen Sie xa durch ein anderes Mitglied der Klasse \(V\) aller Mengen in e, damit die Formel e wahr ist.

Eine Atomformel ist eine spezielle Art von Formel.

Wenn eine Formel true zurückgibt, wenn eine Variablenzuweisung eingefügt wird, sagen wir, dass die Variablenzuweisung diese Formel „erfüllt“.

Nun kommen wir zum Kernkonzept der Rayo-Nameability und ignorieren die Längenbeschränkung:

Es gibt eine Formel \(\phi\), so dass alle zufriedenstellenden Variablenzuweisungen \(m\) als erstes Argument haben müssen, und es gibt mindestens eine solche Zuweisung.

Wir können mit diesem Muster fortfahren und jede natürliche Zahl mit dieser Methode definieren. Es erlaubt uns, die Zahl \ (n\) in \ (O (n ^ 2) \) Symbolen zu benennen. Mit größeren Werten ist es möglich, rekursive Operationen zu definieren, die es uns ermöglichen, immer größere Zahlen in kompakter Notation zu benennen. Bei einer ausreichend großen Zahl würde eine Rayo-Zeichenfolge, die die Potenzierung definiert, weniger Symbole benötigen als unsere Naïve-Technik.

Beachten Sie, dass das Symbol xn als einzelnes Symbol gezählt wird – es sollte nicht in separate Symbole x und n unterteilt werden.

Wir haben alle Teile, um Rayos Funktion zu definieren:

Rayos Funktion \(\text{Rayo}(n)\) ist definiert als die kleinste nicht negative ganze Zahl, die größer ist als alle nicht negativen ganzen Zahlen, die Rayo höchstens in \(n \) Symbolen benennen kann.

Warum ist Rayos Funktion nicht komprimierbar? Mit Rayos Mikrosprache kann man eine Menge konstruieren, deren Elemente sogenannte Momentanbeschreibungen einer Turing-Maschine sind, und daraus ist es nur ein kleiner Schritt, eine bestimmte Funktion zu definieren. Mit mehr Aufwand kann man sogar Oracle Turing-Maschinen konstruieren und ihre Analoga der Beaver-Funktion definieren, was Googology Wiki-Benutzer EmK getan hat.

Beispiel Rayo-Strings und ihre Werte

Also:

\begin{eqnarray*}\text{Rayo}(0) &=& 0 \\\ text{Rayo}(10) &\ge& 1 \\\text{Rayo}(30) &\ge& 2 \\\text{Rayo}(56) &\ge& 3 \\\end{eqnarray*}

Obwohl dieses Argument nur untere Grenzen angibt, werden die genauen Werte für kleine Werte von den Googology Wiki-Benutzern Plain’N’Simple und Emk:

\begin{eqnarray*}\text{Rayo}(0) &=& 0 \\\ text {Rayo}(1) &=& 0 \\&\ vdots& \\\text{Rayo}(9) &=& 0 \\\ text {Rayo}(10) &=& 1 \\\ text {Rayo}(11) &=& 1 \\&\ vdots& \\\text{Rayo}(19) &=& 1 \\\ end{eqnarray*}

Die Rayo-Funktion hat kaum eine Quadratwurzelwachstumsrate für kleine Werte, aber wenn wir eine Menge Symbole hinzufügen, können wir viel größere Zahlen darstellen.

So:

\begin{eqnarray*}\text{Rayo}(861) &>& 4 \\\ text {Rayo}(926) &>& 16 \\\ text {Rayo}(984) &>& 65536 \\\ text {Rayo}(1026) &>& 2^{65536} \\\ end{eqnarray*}

Und so weiter. Plain’N’Simple sagt auch, dass \(\text{Rayo}(10000) > 2\uparrow\uparrow\uparrow65536\) , obwohl er keinen Beweis gibt.

Emk hat gezeigt, dass \(\text{Rayo}(7901) > \text{S}(2^{65536} – 1)\), wobei \(\text{S}(n)\) die maximale Verschiebungsfunktion ist.

Erklärung 2

Wir werden mit Berrys Paradoxon beginnen:

Sei x die kleinste natürliche Zahl, die größer ist als alle, die in höchstens fünfzehn englischen Wörtern definiert werden können. Dann kann x definiert werden als „die kleinste natürliche Zahl, die größer ist als alle, die in höchstens fünfzehn englischen Wörtern definiert werden können.“ Wir haben x nur mit höchstens fünfzehn englischen Wörtern definiert, daher kann x nicht größer sein als alle natürlichen Zahlen, die in höchstens fünfzehn englischen Wörtern definiert werden können. Das ist ein Widerspruch.

Die Quelle des Paradoxons ist die Ambiguität des Wortes „definierbar“ und grundlegender die Ambiguität der englischen Sprache selbst. Rayos Funktion umgeht diese mathematischen Sünden, indem sie Englisch durch die Sprache ersetzt, die als Mengenlehre erster Ordnung (FOST) bezeichnet wird. FOST ist die Sprache der Logik erster Ordnung mit dem Von-Neumann-Universum als Domäne. Insbesondere ist FOST in der Lage, die Mengenzugehörigkeit zu bestimmen, über das Universum zu quantifizieren und logische Operatoren anzuwenden. Die Nitty-gritty Details, wie dies funktioniert, sind oben angegeben.

Wir beheben die Lücke, die Berrys Paradoxon verursacht, was zu der folgenden Definition von Rayo(n) führt:

die kleinste natürliche Zahl größer als alle natürlichen Zahlen, die durch einen FOST-Ausdruck von höchstens n Symbolen eindeutig identifiziert werden kann

Das Paradoxon ist jetzt weg, weil die Definierbarkeit durch eine formale Sprache ersetzt wurde. FOST unterliegt Tarskis Undefinierbarkeitssatz, der besagt, dass wir die Wahrheit nicht formell definieren können, geschweige denn die Definierbarkeit, so dass FOST FOST nicht so aufrufen kann, wie Englisch Englisch aufrufen kann.

Axiom

Um eine natürliche Zahl mit der Mengenlehre zu definieren, müssen wir festlegen, unter welchen Axiomen wir sie definieren. Ein Problem bei der Definition von Rayos Zahl ist, dass Rayo die Axiome nicht geklärt hat. In der Mathematik verzichten wir traditionell auf die Deklaration der Axiome, in denen wir arbeiten, solange wir in der Mengenlehre \(\textrm{ZFC}\) arbeiten. Traditionell denken einige Googologen, dass Rayos Zahl in der Mengenlehre \(\textrm{ZFC}\) definiert ist oder für Axiome irrelevant ist, aber es ist falsch.

Da die \(\ textrm{ZFC}\) Mengenlehre das Wahrheitsprädikat im Von-Neumann-Universum nicht formalisieren kann, ist Rayos Zahl in der \(\textrm{ZFC}\) Mengenlehre schlecht definiert, es sei denn, wir interpretieren die Definition von Rayos Zahl in Bezug auf die Beweisbarkeit. Selbst wenn wir die Definition auf diese Weise interpretieren, ist die resultierende große Zahl nicht signifikant größer als beispielsweise \(\Sigma(10^{100})\) ( wobei \(\Sigma\) die Länge (Funktion) ist, weil die Beweisbarkeit in einer rekursiv aufzählbaren Theorie mit einer Beschränkung der Länge durch eine Turing-Maschine entscheidbar ist. Um deutlich über die Busy Beaver-Funktion hinauszukommen, müssen wir die Beweisbarkeit aufgeben und über die Wahrheit in einem bestimmten Modell sprechen, dessen Existenz unter \(\textrm{ZFC}\) Mengenlehre nicht beweisbar ist, solange \(\textrm{ZFC}\) Mengenlehre konsistent ist.

Andererseits ist FOST nur eine formale Sprache, die für Axiome per Definition irrelevant ist, aber es bedeutet nicht, dass Rayos Zahl für Axiome irrelevant ist. Die Irrelevanz von FOST und Axiomen oder die Beziehung zwischen der Busy Beaver-Funktion und der beweisbasierten Interpretation der Definition von Rayos Zahl könnten die Hauptgründe für das Missverständnis sein, dass Rayos Zahl für Axiome irrelevant ist.

Da Rayo schrieb, dass er die Mengenlehre zweiter Ordnung verwendet, um das primitive Semantikvokabular in der ursprünglichen Beschreibung zu formalisieren, wird Rayos Zahl unter bestimmten Axiomen der Mengenlehre zweiter Ordnung definiert, die nicht geklärt sind. Es ist wichtig, Axiome in der unkomprimierbaren Googologie zu klären, da unkomprimierbare große Zahlen nur dann miteinander verglichen werden können, wenn sie Axiome teilen, die in ihren Definitionen verwendet werden. Glücklicherweise gibt es viele Möglichkeiten von Axiomen der Mengenlehre zweiter Ordnung, die es uns ermöglichen, Rayos Zahl zu definieren. Als Schlussfolgerung ist Rayos Zahl für Googologen, die sich nicht um die Klärung von Axiomen kümmern, gut definiert und für Googologen, die sich um die Klärung von Axiomen kümmern, schlecht definiert. Deshalb gehört dieser Artikel zur Kategorie:Unvollständig.

Im Jahr 2020 fügte Rayo die folgende neue Beschreibung des Umgangs mit Rayos Zahl hinzu:

Hinweis: Philosophen gehen manchmal von einer realistischen Interpretation der Mengenlehre aus. Bei dieser Interpretation haben mengentheoretische Ausdrücke „Standard“ -Bedeutungen, die für jeden Satz der Sprache einen bestimmten Wahrheitswert bestimmen, unabhängig davon, ob es prinzipiell möglich ist, diese Wahrheitswerte zu kennen. (Siehe zum Beispiel diesen Artikel von Vann McGee.) Während des Wettbewerbs gingen Adam und ich davon aus, dass die Sprache der Mengenlehre (zweiter Ordnung) standard interpretiert wurde, was garantiert, dass der endgültige Eintrag einer bestimmten Zahl entspricht. Wenn die Sprache stattdessen auf der Grundlage eines Axiomensystems interpretiert worden wäre, wäre der endgültige Eintrag ungültig gewesen. Dies liegt daran, dass jede (konsistente) Axiomatisierung der Sprache nicht-isomorphe Modelle hat und es keine Garantie gibt, dass der endgültige Eintrag in Bezug auf verschiedene Modelle derselben Nummer entspricht.

Dies bedeutet, dass Rayo eine philosophische „Interpretation“ mengentheoretischer Formeln in Bezug auf die „Wahrheit“ in der realen Welt in Betracht zieht, die in der Mathematik nicht formalisierbar ist, und keine spezifische Auswahl von Axiomen beabsichtigt. Es ist eine der vernünftigen Richtungen der Googologie außerhalb der Mathematik. Auf der anderen Seite sieht das Problem im letzten Satz wie eine Ausrede aus, warum sie die unformalisierbare „Wahrheit“ für selbstverständlich halten, aber es macht keinen Sinn, weil die Abhängigkeit des Wertes einer gegebenen Zahl von einem Modell für die „Ungültigkeit“ irrelevant ist. In der Mathematik gibt es viele gut definierte Begriffe, die nicht absolut sind, dh von einem Modell abhängen, z. B. die eindeutige natürliche Zahl \(n\) \ \((\text{CH} \ bis n = 0) \land (\neg \text{CH} \ bis n = 1) \). In der Googologie gibt es viele große Zahlen, die von einem Modell abhängen, z. B. Werte der maximalen Verschiebungsfunktion und insbesondere \ (S (1919) \), wobei \ (S \) die maximale Verschiebungsfunktion bezeichnet. In Big Number Duel gibt es keine Regel, die eine Zahl verbietet, die von einem Modell abhängt, und in der Tat erlaubt es sogar zu überspringen, um Axiome zu fixieren.

Geschichte

Das Nummernduell von Rayo und Elga wurde von den im Artikel „Wer kann die größere Nummer nennen?“ von Scott Aaronson.

Im Januar 2013 behauptete Adam P. Goucher, dass \(\text{Rayo}(n)\) langsamer wächst als seine xi-Funktion. Die Behauptung stellte sich jedoch als falsch heraus, da Goucher die Definition von Rayos Funktion als „größte durch n Symbole ausdrückbare ganze Zahl“ in der Arithmetik erster Ordnung (der Sprache der Peano-Arithmetik) missverstanden hatte.“. Die Arithmetik zweiter Ordnung ist viel stärker, und die Mengenlehre erster Ordnung ist noch stärker. Die Diskursdomäne der Arithmetik erster Ordnung sind die natürlichen Zahlen, aber die Diskursdomäne der Mengenlehre erster Ordnung ist definiert als Mengen des gesamten Von-Neumann-Universums. Tatsächlich kann gezeigt werden, dass Rayos Funktion viel leistungsfähiger ist als die xi-Funktion.

Rayos Zahl wurde als die größte benannte Zahl geehrt, bis 2014, als BIG FOOT definiert wurde, eine nicht-naive Erweiterung der Mengenlehre n-ter Ordnung, der Oodle-Theorie erster Ordnung, verwendet wurde. Beachten Sie, dass naive Erweiterungen wie \(\text{FOST}^{100}(10^{100})\) wo Rekursions- / Iterationsnotation verwendet wird, wird nicht als Brechen des Datensatzes von Rayos Nummer geehrt. Obwohl Rayos Nummer zuvor im Jahr 2013 von der Fischnummer 7 übertroffen wurde, war es fraglich, ob diese Zahl gut genug war, um als Rekordbrecher geehrt zu werden. BIG FOOT erwies sich jedoch 2018 als schlecht definiert. Gegenwärtig teilen alle größten benannten Zahlen das gleiche Konzept der Rayo-Funktion, dh sie beziehen sich auf die Benennbarkeit natürlicher Zahlen und alle nicht naiven Erweiterungen wie die Fußfunktion.

Autor

Die Zahl wurde von Dr. Agustín Rayo erfunden, einem außerordentlichen Professor für Linguistik und Philosophie am Massachusetts Institute of Technology, wo er 2001 promoviert wurde.

Quellen

Siehe auch

  • Rayos Nummer auf Wikipedia.
  • Busy Beaver
  • BIG FOOT
  • Little Bigeddon
  • Große Anzahl Gartennummer
  • Unkomprimierbare Funktion
Große Zahlen in Computern
Hauptartikel: Zahlen in der Computerarithmetik

127 · 128 · 256 · 32767 · 32768 · 65536 · 2147483647 · 4294967296 · 9007199254740991 · 9223372036854775807 · FRACTRAN Katalognummern
Bignum Bakeoff Teilnehmer: pete-3.c * pete-9.c * pete-8.c * harper.c * ioannis.c * chan-2.c * chan-3.c * pete-4.c * chan.c * pete-5.c * pete-6.c * pete-7.c * marxen.c * Loader.c
Kanalsysteme: verlustbehaftetes Kanalsystem * Prioritätskanalsystem
Unkomprimierbare Funktionen: Busy Beaver-Funktion * Maximale Verschiebungen Funktion · Doodle-Funktion · Betti-Nummer · Xi-Funktion · ITTM Busy Beaver · Rayo (n) · FUß (n)
Konzepte: Rekursion

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.