Rayo’s number

Un utente ha richiesto la protezione semi di questa pagina per 1 anno. Il motivo indicato è: Recentemente vandalizzato.

Il numero di Rayo è uno dei più grandi numeri nominati, coniato in una battaglia di grandi numeri che contrappone Agustín Rayo contro Adam Elga. Il numero di Rayo è, nelle parole di Rayo, ” il più piccolo intero positivo più grande di qualsiasi intero positivo finito chiamato da un’espressione nel linguaggio della teoria degli insiemi del primo ordine con simboli googol o meno.”

anche se il secondo ordine, in teoria non era specificato nella definizione originale e viene chiarito come il filosofico (ma matematicamente mal definite) insieme di formule che il mondo reale filosoficamente “soddisfare”, è ragionevole supporre che \(\textrm{ZFC}\) la teoria degli insiemi è un primo ordine del segmento non specificato in teoria, perché la maggior parte dei matematici e googologists sono interessati a \(\textrm{ZFC}\) la teoria degli insiemi. Sotto l’ipotesi, la funzione di Rayo supera tutte le funzioni definibili nella teoria degli insiemi \ (\textrm {ZFC}\). In tutto questo articolo, usiamo sempre la stessa ipotesi tranne che per la sezione Assioma che spiega più profondamente il problema sulla mancanza del chiarimento della teoria degli insiemi del secondo ordine.

La funzione di Rayo è una delle funzioni più in rapida crescita mai a sorgere in matematica professionale; solo poche funzioni, in particolare la sua estensione, numero di pesce 7 lo supera. Poiché la funzione di Rayo utilizza una matematica difficile, ci sono diverse prove per generalizzarla che si traducono in un fallimento. Ad esempio, la funzione FOOT (first-order oodle theory) è stata anche considerata superiore, ma è mal definita.

Definizione

Lasciate che \(\) e \(\) siano formule codificate da Gödel e \(s\) e \(t\) siano assegnazioni di variabili. Definire \(\text{Sat} (, s)\) come segue:

\(\text {Rayo} (n)\), quindi, è il numero più piccolo maggiore di tutti i numeri Rayo-namable nei simboli \(n\).

Si noti che gli x_i in t (xi) t t(xj) e t(xi) = t(xj) nella definizione di \(\text{Sat}\) sopra erano x_1 nella definizione originale. Sebbene x_1 sia l’unica variabile libera consentita in un Rayo-name, l’assegnazione della variabile per x_i è effettivamente indicata nella soddisfazione di ∃-fourmulae. Pertanto la definizione originale non ha funzionato come Rayo effettivamente inteso, ed è stato aggiornato da Rayo stesso. (Recuperato 19/05/2020)

Spiegazione 1

Ci sono molte terminologie della logica formale a seconda degli autori. Spieghiamo una di queste terminologie. Un linguaggio formale è un insieme di simboli a termine costante, simboli a termine variabile indicizzati da numeri naturali, simboli di funzione e simboli di relazione. Una formula in un linguaggio formale \(L\) è stringhe formali costruite da simboli a termine costante in \(L\), simboli a termine variabile in \(L\), simboli di funzione in \(L\), simboli di relazione in \(L\), quantificatori e connettivi logici che seguono una certa sintassi.

Un’interpretazione delle formule in \(L\) è una mappa che assegna una costante a ciascun simbolo di termine costante, una funzione a ciascun simbolo di funzione e una relazione a ciascun simbolo di relazione. Data un’interpretazione delle formule in \(L\), ogni formula chiusa in \(L’\) sarà valutata come vera o falsa finché un predicato di verità è formalizzabile, perché corrisponde a una formula sui parametri in \(V\). In particolare, data un’assegnazione variabile e un’interpretazione, possiamo chiedere se una data formula in \(L\) è vera o falsa finché un predicato di verità è formalizzabile. Per formalizzare un predicato di verità, abbiamo bisogno di una teoria degli insiemi sufficientemente forte. Ad esempio, la teoria degli insiemi ZFC non è adatta a questo scopo.

Rayo ha definito un linguaggio formale molto specifico e astratto insieme ad una scelta canonica di interpretazione:

  • Una formula atomica “xa x xb” significa che la variabile ath è un elemento della variabile bth.
  • Una formula atomica “xa = xb” indica che la variabile ath è uguale alla variabile bth.
  • Una formula ” (e) “per una formula e significa la negazione di e.
  • Una formula” (e f f) “per le formule e e f significa la congiunzione (la logica e) di e e f.
  • Una formula” x xa(e) ” significa che possiamo modificare l’occorrenza libera della variabile ath, i.e. sostituire xa con un altro membro della classe \(V\) di tutti gli insiemi, in e in modo che la formula e sia vera.

Una formula atomica è un tipo speciale di formula.

Se una formula restituisce true quando viene inserita un’assegnazione variabile, diciamo che l’assegnazione variabile “soddisfa” quella formula.

Ora arriviamo al concetto di base di Rayo-nameability, ignorando la restrizione della lunghezza:

Esiste una formula \(\phi\) tale che tutte le assegnazioni di variabili soddisfacenti devono avere \(m\) come primo argomento, e c’è almeno una di queste assegnazioni.

Possiamo continuare con questo modello, definendo ogni numero naturale usando questo metodo. Ci permette di nominare il numero\ (n\) in\ (O (n^2)\) simboli. Con valori più grandi, è possibile definire operazioni ricorsive, permettendoci di Rayo-name numeri sempre più grandi usando la notazione compatta. Dato un numero sufficientemente grande, una stringa Rayo che definisce l’esponenziazione avrebbe bisogno di meno simboli della nostra tecnica naïve.

Si noti che il simbolo xn viene conteggiato come un singolo simbolo – non deve essere suddiviso in simboli separati x e n.

Abbiamo tutti i pezzi in atto per definire la funzione di Rayo:

La funzione di Rayo \(\text{Rayo}(n)\) è definita come il più piccolo numero intero non negativo maggiore di tutti gli interi non negativi Rayo-nominabile al massimo in simboli \(n\).

Perché la funzione di Rayo non è calcolabile? Usando il microlinguaggio di Rayo si può costruire un insieme i cui elementi sono le cosiddette descrizioni istantanee di una macchina di Turing, e da questo, è solo un piccolo passo per definire la funzione Busy Beaver. Con più sforzo, si può anche costruire macchine oracle Turing e definire i loro analoghi della funzione Busy Beaver, che l’utente Wiki di Googology EmK ha fatto.

Esempio Rayo stringhe e dei loro valori

Quindi:

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

anche se questo argomento dà solo il limite inferiore, i valori precisi per piccoli valori sono forniti da Googology Wiki utenti Pianura N”Simple e 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*}

Il Rayo funzione ha appena radice quadrata tasso di crescita per piccoli valori, ma se si aggiunge un sacco di simboli, possiamo rappresentare numeri ben più grandi.

So:

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

E così via. Plain’N’Semplice dice anche che \(\text {Rayo}(10000) > 2 \ uparrow \ uparrow \ uparrow65536\), anche se non fornisce una prova.

Emk ha mostrato che \(\text {Rayo}(7901) > \text{S}(2^{65536} – 1)\), dove \(\text{S} (n)\) è la funzione di spostamento massimo.

Spiegazione 2

Apriremo con il paradosso di Berry:

Sia x il più piccolo numero naturale maggiore di tutti quelli definibili in un massimo di quindici parole inglesi. Quindi x può essere definito come ” il più piccolo numero naturale maggiore di tutti quelli definibili al massimo in quindici parole inglesi.”Abbiamo appena definito x usando al massimo quindici parole inglesi, quindi x non può essere maggiore di tutti i numeri naturali definibili al massimo in quindici parole inglesi. Questa è una contraddizione.

La fonte del paradosso è l’ambiguità della parola “definibile”, e più fondamentalmente l’ambiguità della lingua inglese stessa. La funzione di Rayo elude questi peccati matematici sostituendo l’inglese con la lingua chiamata teoria degli insiemi del primo ordine (FOST). FOST è il linguaggio della logica del primo ordine con l’universo di von Neumann come dominio. In particolare, FOST è in grado di determinare l’appartenenza all’insieme, quantificare l’universo e applicare operatori logici. I dettagli nitty-gritty di come funziona sono dati sopra.

Risolviamo la scappatoia che causa il paradosso di Berry, risultante nella seguente definizione di Rayo (n), che è:

il più piccolo numero naturale maggiore di tutti i numeri naturali che possono essere identificati in modo univoco da un’espressione FOST di al massimo n simboli

Il paradosso è scomparso ora perché la definibilità è stata sostituita con un linguaggio formale. FOST è soggetto al teorema di indefinibilità di Tarski, che dice che non possiamo definire formalmente la verità, per non parlare della definibilità, quindi FOST non può invocare FOST nel modo in cui l’inglese può invocare l’inglese.

Assioma

Per definire un numero naturale usando la teoria degli insiemi, dobbiamo fissare sotto quali assiomi lo definiamo. Un problema nella definizione del numero di Rayo è che Rayo non ha chiarito gli assiomi. In matematica, tradizionalmente omettiamo la dichiarazione degli assiomi in cui stiamo lavorando finché stiamo lavorando nella teoria degli insiemi \(\textrm{ZFC}\). Secondo la tradizione, diversi googologi pensano che il numero di Rayo sia definito nella teoria degli insiemi \(\textrm{ZFC}\), o sia irrilevante per gli assiomi, ma è sbagliato.

Almeno, poiché la teoria degli insiemi \(\textrm{ZFC}\) non è in grado di formalizzare il predicato di verità nell’universo di von Neumann, il numero di Rayo è mal definito nella teoria degli insiemi \(\textrm{ZFC}\) a meno che non interpretiamo la definizione del numero di Rayo in termini di provabilità. Anche se interpretiamo la definizione in questo modo, il numero elevato risultante non sarà significativamente più grande di, ad esempio, \(\Sigma(10^{100})\) (dove \(\Sigma\) è la funzione busy beaver) perché la provabilità in una teoria ricorsivamente enumerabile con una restrizione della lunghezza è decidibile da una macchina di Turing. Per andare significativamente oltre la funzione Busy Beaver, dobbiamo abbandonare la provabilità e parlare della verità in un particolare modello, la cui esistenza non è dimostrabile sotto la teoria degli insiemi \(\textrm{ZFC}\) purché la teoria degli insiemi \(\textrm{ZFC}\) sia coerente.

D’altra parte, FOST è solo un linguaggio formale, che è irrilevante per gli assiomi dalla definizione, ma non significa che il numero di Rayo sia irrilevante per gli assiomi. L’irrilevanza di FOST e assiomi o la relazione tra la funzione Busy Beaver e l’interpretazione basata sulle prove della definizione del numero di Rayo potrebbero essere le ragioni principali del malinteso che il numero di Rayo sia irrilevante per gli assiomi.

Come Rayo ha scritto che usa la teoria degli insiemi del secondo ordine per formalizzare il vocabolario della semantica primitiva nella descrizione originale, il numero di Rayo è definito sotto certi assiomi della teoria degli insiemi del secondo ordine, che non sono chiariti. È importante chiarire gli assiomi in googology non calcolabile, perché i numeri grandi non calcolabili possono essere confrontati tra loro solo quando condividono gli assiomi utilizzati nelle loro definizioni. Fortunatamente, ci sono molte scelte di assiomi della teoria degli insiemi del secondo ordine che ci permettono di definire il numero di Rayo. In conclusione, il numero di Rayo è ben definito per i googologi che non si preoccupano della chiarificazione degli assiomi ed è mal definito per i googologi che si preoccupano della chiarificazione degli assiomi. Ecco perché questo articolo appartiene alla categoria: Incompleto.

Nel 2020, Rayo ha aggiunto la seguente nuova descrizione del modo di trattare il numero di Rayo:

Nota: I filosofi a volte assumono un’interpretazione realista della teoria degli insiemi. Su questa interpretazione, le espressioni teoriche degli insiemi hanno significati “standard”, che determinano un valore di verità definito per ogni frase della lingua, indipendentemente dal fatto che sia in linea di principio possibile sapere quali sono quei valori di verità. (Vedi, per esempio, questo articolo di Vann McGee.) Durante la competizione, Adam e io abbiamo dato per scontato che il langauge della teoria degli insiemi (secondo ordine) è stato interpretato in modo standard, il che garantisce che la voce finale corrisponda a un numero definito. Se il langauge fosse stato invece interpretato sulla base di un sistema di assiomi, la voce finale non sarebbe stata valida. Questo perché ogni assiomatizzazione (coerente) del linguaggio ha modelli non isomorfi e non vi è alcuna garanzia che la voce finale corrisponda allo stesso numero rispetto a modelli diversi.

Ciò significa che Rayo considera una “interpretazione” filosofica delle formule teoriche degli insiemi rispetto alla” verità ” nel mondo reale, che non è formalizzabile in matematica e non intende una scelta specifica di assiomi. È una delle direzioni ragionevoli della googologia al di fuori della matematica. D’altra parte, il problema nell’ultima frase sembra una scusa sul perché danno per scontata la “verità” non formalizzabile, ma non ha senso perché la dipendenza del valore di un dato numero su un modello è irrilevante per la “invalidità”. In matematica, ci sono molte nozioni ben definite che non sono assolute, cioè dipendono da un modello, ad esempio il numero naturale unico \(n\) che soddisfa \((\text{CH} \to n=0) \land (\neg \text{CH} \to n=1)\). In googology, ci sono molti grandi numeri che dipendono da un modello, ad esempio valori della funzione Busy Beaver e in particolare \(S(1919)\), dove \(S\) denota la funzione di spostamento massima. In Big Number Duel, non esiste una regola che proibisca un numero che dipende da un modello, e in effetti ha persino permesso di saltare per correggere gli assiomi.

Storia

Il duello numero di Rayo ed Elga è stato ispirato dalle grandi competizioni numeriche descritte nell’articolo ” Chi può nominare il numero più grande?”di Scott Aaronson.

Nel gennaio 2013, Adam P. Goucher ha affermato che \(\text{Rayo}(n)\) cresce più lentamente della sua funzione xi. Tuttavia, l’affermazione si è rivelata errata, perché Goucher ha frainteso la definizione della funzione di Rayo come il “più grande intero esprimibile in modo univoco da n simboli nell’aritmetica del primo ordine (il linguaggio dell’aritmetica di Peano).”. L’aritmetica del secondo ordine è molto più forte e la teoria degli insiemi del primo ordine è ancora più forte di quella. Il dominio del discorso dell’aritmetica del Primo ordine sono i numeri naturali, ma il dominio del discorso della teoria degli insiemi del primo ordine è definito come insiemi dell’intero universo di von Neumann. In effetti, si può dimostrare che la funzione di Rayo è molto più potente della funzione xi.

Il numero di Rayo è stato onorato come il più grande numero nominato fino al 2014 quando è stato definito BIG FOOT, utilizzando un’estensione non ingenua della teoria degli insiemi di ordine n-esimo, la teoria di oodle del primo ordine. Si noti che estensioni ingenue come \(\text{FOST}^{100}(10^{100})\) dove viene utilizzata la notazione di ricorsione/iterazione non sono onorati come battere il record del numero di Rayo. Anche se il numero di Rayo è stato precedentemente superato in 2013 dal numero di pesce 7, era discutibile se quel numero fosse un’estensione abbastanza buona per essere onorato come battere il record. Tuttavia, BIG FOOT si è rivelato mal definito nel 2018. Attualmente, tutti i numeri più grandi con nome condividono lo stesso concetto di funzione di Rayo, cioè riferendosi alla namability dei numeri naturali, e tutte le estensioni non ingenue come la funzione del PIEDE.

Autore

Il numero è stato inventato dal Dr. Agustín Rayo, professore associato di Linguistica e Filosofia presso il Massachusetts Institute of Technology dove ha ricevuto il suo dottorato di ricerca nel 2001.

Fonti

Vedi anche

  • Il numero di Rayo su Wikipedia.
  • Occupato Castoro
  • BIG FOOT
  • Little Bigeddon
  • Grande numero Giardino Numero
  • Funzione Uncomputable
Grandi numeri nei computer
Articolo principale: Numeri in aritmetica computerizzata

127 · 128 · 256 · 32767 · 32768 · 65536 · 2147483647 · 4294967296 · 9007199254740991 · 9223372036854775807 · FRACTRAN numeri di catalogo
Bignum Bakeoff concorrenti: 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 * caricatore.c
Sistemi di canali: sistema di canali con perdita · sistema di canali prioritari
Funzioni non calcolabili: Busy beaver funzione * Massima turni funzione * Funzione Doodle * Numero Betti * Funzione Xi * ITTM busy beaver * Rayo (n) * PIEDE(n)
Concetti: Ricorsione

Lascia un commento

Il tuo indirizzo email non sarà pubblicato.