Rayo's number is one of the largest named numbers, coined in a large number battle pitting Agustín Rayo against Adam Elga on 26 January 2007.[1][2][3][4] Rayo's number is, in Rayo's own words, "the smallest positive integer bigger than any finite positive integer named by an expression in the language of first-order set theory with googol symbols or less."
By letting the number of symbols range over the natural numbers, we get a very quickly growing function \(\text{Rayo}(n)\). Rayo's number is \(\text{Rayo}(10^{100})\). Rayo's function is uncomputable, which means that it is impossible for a Turing machine (and, by the Church–Turing thesis, any modern computer) to calculate \(\text{Rayo}(n)\).[note 1]
Although the second order set theory was unspecified in the original definition and is clarified as the philosophic (but mathematically ill-defined) collection of formulae which the real world philosophically "satisfy", it is reasonable to assume that \(\textrm{ZFC}\) set theory is a first order segment of the unspecified set theory because the majority of mathematicians and googologists are interested in \(\textrm{ZFC}\) set theory. Under the assumption, Rayo's function outgrows all functions definable in \(\textrm{ZFC}\) set theory. Throughout this article, we always use the same assumption except for Axiom section which more deeply explains the issue on the lack of the clarification of the second order set theory.
Rayo's function is one of the most fast-growing functions ever to arise in professional mathematics; only a few functions, especially its extension, Fish number 7 surpasses it. Since Rayo's function uses difficult mathematics, there are several trials to generalise it which result in failure. For example, the FOOT (first-order oodle theory) function was also considered to surpass it, but it is ill-defined.
Rayo's function can never be outgrown by a fast-growing hierarchy \(f_\alpha(n)\) for a countable ordinal \(\alpha\) and a fixed system of fundamental sequences for ordinals \(\leq \alpha\) if the hierarchy is defined in \(\textrm{ZFC}\) set theory by the definition of \(\text{Rayo}\).[note 2]
Definition[]
Let \([\phi]\) and \([\psi]\) be Gödel-coded formulas and \(s\) and \(t\) be variable assignments. Define \(\text{Sat}([\phi], s)\) as follows:
∀R { { ∀[ψ], t: R([ψ],t) ↔ ([ψ] = "xi ∈ xj" ∧ t(xi) ∈ t(xj)) ∨ ([ψ] = "xi = xj" ∧ t(xi) = t(xj)) ∨ ([ψ] = "(¬θ)" ∧ ¬R([θ], t)) ∨ ([ψ] = "(θ∧ξ)" ∧ R([θ], t) ∧ R([ξ], t)) ∨ ([ψ] = "∃xi(θ)" ∧ ∃t′: R([θ], t′)) (where t′ is a copy of t with xi changed) } ⇒ R([ϕ],s) }
Call a natural number \(m\) "Rayo-nameable in \(n\) symbols" if there is a formula \(\phi(x_1)\) with less than \(n\) symbols and \(x_1\) as its only free variable that satisfies the following properties:
- There is a variable assignment \(s\), assigning \(x_1 := m\), such that \(\text{Sat}([\phi(x_1)], s)\).
- For any variable assignment \(t\), if \(\text{Sat}([\phi(x_1)], t)\), \(t\) must have \(x_1 = m\).
\(\text{Rayo}(n)\), then, is the smallest number greater than all numbers Rayo-nameable in \(n\) symbols.
Note that the x_i's in t(xi) ∈ t(xj) and t(xi) = t(xj) in the definition of \(\text{Sat}\) above were x_1 in the original definition. Although x_1 is the only free variable allowed to occur in a Rayo-name, the variable assignment for x_i is actually referred to in the satisfaction of ∃-fourmulae. Therefore the original definition did not work as Rayo actually intended, and has been updated by Rayo himself.[1](Retrieved 19/05/2020)
Explanation[]
Explanation 1[]
There are many terminologies of formal logic depending on authors. We explain one of such terminologies. A formal language is a set of constant term symbols, variable term symbols indexed by natural numbers, function symbols, and relation symbols. A formula in a formal language \(L\) is formal strings built from constant term symbols in \(L\), variable term symbols in \(L\), function symbols in \(L\), relation symbols in \(L\), quantifiers, and logical connectives following a certain syntax.
Formally adding every set as a constant term symbol, we can canonically extend \(L\) to a formal language \(L'\) with parameters in \(V\). An interpretation of formulae in \(L\) is canonically extended to an interpretation of formulae in \(L'\). A variable assignment is some countably infinite sequence of mathematical objects such as \(A = (3, 2, 6, 1/2, \{4, \pi\}, \omega, 65, \ldots)\). Given a variable assignment, we can convert a formula in \(L'\) into a closed formula in \(L'\) by replacing free occurrences of variable term symbols by the parameter given by the corresponding entry in the variable assignment.
For example, the formula "the third variable is relatively prime to the second variable" in \(L\) is interpreted by \(A\) as the closed formula "\(6\) is relatively prime to \(2\)" in \(L'\), and the formula "the second variable is the set of all real numbers except for \(3.2\)" in \(L'\) is interpreted by \(A\) as the closed formula "\(2\) is the set of all real numbers except for \(3.2\)" in \(L'\).
An interpretation of formulae in \(L\) is a map which assigns a constant to each constant term symbol, a function to each function symbol, and a relation to each relation symbol. Given an interpretation of formulae in \(L\), every closed formula in \(L'\) will be evaluated as true or false as long as a truth predicate is formalisable, because it corresponds to a formula on parameters in \(V\). In particular, given a variable assignment and an interpretation, we can ask whether a given formula in \(L\) is true or false as long as a truth predicate is formalisable. In order to formalise a truth predicate, we need a sufficiently strong set theory. For example, ZFC set theory is not suitable for this purpose.
Rayo defined a very specific and abstract formal language together with a canonical choice of an interpretation:
- An atomic formula "xa∈xb" means that the ath variable is an element of bth variable.
- An atomic formula "xa=xb" means the ath variable is equal to the bth variable.
- A formula "(¬e)" for a formula e means the negation of e.
- A formula "(e∧f)" for formulas e and f means the conjunction (the logical and) of e and f.
- A formula "∃xa(e)" means that we can modify the free occurrence of the ath variable, i.e. substitute xa by another member of the class \(V\) of all sets, in e so that the formula e is true.
An atomic formula is a special sort of a formula.
For example, take the formula "(x1∈x2)". This says "the first variable is an element of the second variable," so we can plug in the variable assignment \((\emptyset, \{\emptyset\}, \ldots)\) and the result will be true since \(\emptyset\) is an element of \(\{\emptyset\}\). If instead we plug in \((\{\emptyset\}, \emptyset, \ldots)\), the result is not true because \(\{\emptyset\}\) is not an element of \(\emptyset\). (If you're familiar with propositional logic, you might be curious about the absence of the universal quantifier ∀. This is because ∀x(e) is the same as (¬(∃x((¬e)))), and it's not needed.)
A more complicated example: "(¬(∃x1(x1∈x2)))". This says, "it is not true that there exists an \(x\) such that "the first variable is an element of the second variable" is not true when we replace "the first variable" by \(x\). In other words, we cannot pick an \(x\) such that \(x\) is an element of the second variable. Given a variable assignment, this is true when the second entry is the empty set. For example, this is true for the variable assignment \((3, \{\}, \ldots)\), but is false for the variable assignment \((3,\{1\},\ldots)\).
If a formula returns true when a variable assignment is plugged into it, we say that the variable assignment "satisfies" that formula.
Now we arrive at the core concept of Rayo-nameability, ignoring the length restriction:
- There is a formula \(\phi\) such that all satisfactory variable assignments must have \(m\) as their first argument, and there is at least one such assignment.
First we shall show that 0 is Rayo-nameable. In the ordinal system, \(0 = \{\}\). We need to craft a formula \(\phi\) that forces \(\{\}\) as its first argument. One such string is "(¬(∃x2(x2∈x1)))" = "we cannot pick an \(x\) such that \(x\) is an element of the first variable" = "we cannot pick an element of the first variable" = "the first variable has no elements" = "the first variable is the empty set".
Now we need to find a way to Rayo-name \(x_1=\{\{\}\}\). The first variable needs an element: "∃x2(x2∈x1)". Then, to ensure that the element is the empty set, we use "(¬(∃x2((x2∈x1∧∃x3(x3∈x2)))))" = "we cannot pick an \(x\) such that \(x\) is an element of the first variable and the third variable is an element of \(x\)" = "we cannot pick an \(x\) such that \(x\) is an element of the first variable and has an element" = "we cannot pick an \(x\) such that \(x\) is an element of the first variable and is not the empty set" = "if the first variable has an element, it must be the empty set". We "and" all these statements together, we get "(∃x2(x2∈x1)∧(¬(∃x2((x2∈x1∧∃x3(x3∈x2))))))".
We can continue with this pattern, defining each natural number using this method. It allows us to name the number \(n\) in \(O(n^2)\) symbols. With larger values, it is possible to define recursive operations, allowing us to Rayo-name larger and larger numbers using compact notation. Given a sufficiently large number, a Rayo string that defines exponentiation would need less symbols than our naïve technique.
Note that the symbol xn is counted as a single symbol - it should not be broken into separate symbols x and n.
We have all the pieces in place to define Rayo's function:
- Rayo's function \(\text{Rayo}(n)\) is defined as the smallest non-negative integer greater than all non-negative integers Rayo-nameable in at most \(n\) symbols.
Why is Rayo's function uncomputable? Using Rayo's microlanguage one can construct a set whose elements are so-called instantaneous descriptions of a Turing machine, and from this, it's just a small step to define Busy Beaver function (see below). With more effort, one can even construct oracle Turing machines and define their analogs of Busy Beaver function.
Known values of Rayo's function[]
The currently known best Rayo strings for 0, 1, and 2 are: \begin{eqnarray*} 0 & = & \{\} = (\neg\exists x_2(x_2 \in x_1)) \ \textrm{(10 symbols)} \\ 1 & = & \{\{\}\} = (\exists x_2(x_2 \in x_1) \land (\neg\exists x_2((x_2 \in x_1 \land \exists x_3(x_3 \in x_2))))) \ \textrm{(30 symbols)} \\ 2 & = & \{\{\},\{\{\}\}\} \\ & = & (\exists x_2(\exists x_3((x_3 \in x_2 \land (x_2 \in x_1 \land x_3 \in x_1)))) \\ & & \land (\neg \exists x_4(\exists x_2(\exists x_3((x_4 \in x_3 \land (x_3 \in x_2 \land x_2 \in x_1))))))) \ \textrm{(56 symbols)} \end{eqnarray*}
Thus:
\begin{eqnarray*} \text{Rayo}(0) &=& 0 \\ \text{Rayo}(10) &\ge& 1 \\ \text{Rayo}(30) &\ge& 2 \\ \text{Rayo}(56) &\ge& 3 \\ \end{eqnarray*}
Although this argument just gives lower bounds, the precise values for small values are given by Googology Wiki users Plain'N'Simple, Emk, and Ytosk:[5][6][7][8]
\begin{eqnarray*} \text{Rayo}(0) &=& 0 \\ &\vdots& \\ \text{Rayo}(9) &=& 0 \\ \text{Rayo}(10) &=& 1 \\ &\vdots& \\ \text{Rayo}(29) &=& 1 \\ \text{Rayo}(30) &\ge& 2 \\ \end{eqnarray*}
In addition, Ytosk has shown that \(\text{Rayo}(88)\ge 4\) and \(\text{Rayo}(34+20n)>n\).[9]
Starting from April 2020, there was a lot of research on how to represent the number \(65536=2\uparrow\uparrow 4\), and similarly, all power towers of 2, using a Rayo string. Plain'N'Simple was the first to accomplish this task, showing that \(\text{Rayo}(835+96n) > 2 \uparrow\uparrow n\).[10] Of course, there were a lot of early improvements to be made, for instance: 12AbBa (Zongshu Wu) shaved it off to \(\text{Rayo}(728+75n) > 2 \uparrow\uparrow n\), and P進大好きbot then obtained \(\text{Rayo}(731+65n) > 2\uparrow\uparrow n\).
Finally, through various efforts by Plain'N'Simple, P進大好きbot, and Ytosk, it was later shown that \(\text{Rayo}(260+20n) > 2\uparrow\uparrow n\), which is a drastically better bound.[11][12][13][14] Therefore: \begin{eqnarray*} \text{Rayo}(320) &>& 16 \\ \text{Rayo}(340) &>& 65536 \\ \text{Rayo}(360) &>& 2^{65536} \\ \text{Rayo}(380) &>& 2^{2^{65536}} \\ \end{eqnarray*}
Using these bounds, we can create a graph of the known bounds of Rayo's function, shown to the right. Note that it is a bit inaccurate, since the points should not be connected by a line, but rather the graph should look like somewhat like a floor function.
Emk has shown that \(\text{Rayo}(7901)>\text{S}(2^{65536}-1)\), where \(\text{S}(n)\) is the maximum shifts function.[15] However, since his blog post uses an outdated Rayo string to represent \(2^{65536}\), the bound is not as strong as could be. Using the latest bounds it can be determined that \(\text{Rayo}(7339)>\text{S}(2^{65536}-1)\).
Explanation 2[]
We will open with Berry's paradox:
- Let x be the smallest natural number greater than all ones definable in at most fifteen English words. Then x can be defined as "the smallest natural number greater than all ones definable in at most fifteen English words." We just defined x using at most fifteen English words, so therefore x cannot be greater than all natural numbers definable in at most fifteen English words. This is a contradiction.
The source of the paradox is the ambiguity of the word "definable", and more fundamentally the ambiguity of the English language itself. Rayo's function circumvents these mathematical sins by replacing English with the language called first-order set theory (FOST). FOST is the language of first-order logic with the von Neumann universe as the domain. Specifically, FOST is capable of describing set membership, quantifying over the universe, and applying logical operators. The nitty-gritty details of how this works are given above.
We fix the loophole that causes Berry's paradox, resulting in the following definition of Rayo(n), which is:
- the smallest natural number greater than all natural numbers that can be uniquely identified by a FOST expression of at most n symbols
The paradox is gone now because the definability has been replaced with a formal language. FOST is subject to Tarski's undefinability theorem, which says we can't formally define truth, let alone definability, so FOST can't invoke FOST the way English can invoke English.
Discussion[]
Axiom[]
In order to define a natural number using set theory, we need to fix under what axioms we define it. A problem in the definition of Rayo's number is that Rayo did not clarify the axioms. In mathematics, we traditionally omit the declaration of the axioms in which we are working as long as we are working in \(\textrm{ZFC}\) set theory. By the tradition, several googologists think that Rayo's number is defined in \(\textrm{ZFC}\) set theory, or is irrelevant to axioms, but it is wrong.
At least, since \(\textrm{ZFC}\) set theory is not able to formalize truth predicate at von Neumann universe, Rayo's number is ill-defined in \(\textrm{ZFC}\) set theory unless we interpret the definition of Rayo's number in terms of provability. Even if we interpret the definition in that way, the resulting large number will not be significantly larger than, for example, \(\Sigma(10^{100})\) (where \(\Sigma\) is the busy beaver function) because the provability in a recursively enumerable theory is decidable using the information of the termination of a Turing machine. To get significantly beyond the Busy Beaver function, we must abandon provability, and talk about truth in a particular model, whose existence is not provable under \(\textrm{ZFC}\) set theory as long as \(\textrm{ZFC}\) set theory is consistent.
On the other hand, FOST is just a formal language, which is irrelevant to axioms by the definition, but it does not mean Rayo's number is irrelevant to axioms. The irrelevance of FOST and axioms or the relation between the Busy Beaver function and the proof-based interpretation of the definition of Rayo's number might be the main reasons of the misunderstanding that Rayo's number is irrelevant to axioms.
As Rayo wrote that he uses second-order set theory in order to formalize the primitive semantics vocabulary in the original description, Rayo's number is defined under certain axioms of second-order set theory, which are not clarified. It is important to clarify axioms in uncomputable googology, because uncomputable large numbers can be compared with each other only when they share axioms used in their definitions. Fortunately, there are many choices of axioms of second-order set theory which enable us to define Rayo's number. As a conclusion, Rayo's number is well-defined for googologists who do not care about clarification of axioms and is ill-defined for googologists who care about clarification of axioms. That is why this article belongs to Category:Incomplete.
In 2020, Rayo added the following new description of the way to deal with Rayo's number:[1]
- Note: Philosophers sometimes assume a realist interpretation of set-theory. On this interpretation,set-theoretic expressions have "standard" meanings, which determine a definite truth-value for each sentence of the language, regardless of whether it is in principle possible to know what those truth-values are. (See, for instance, this article by Vann McGee.) During the competition, Adam and I took for granted that the language of (second-order) set-theory was interpreted standardly, which guarantees that the final entry corresponds to a definite number. If the language had instead been interpreted on the basis of an axiom system, the final entry would have been invalid. This is because every (consistent) axiomatization of the language has non-isomorphic models and there is no guarantee that the final entry will correspond to the same number with respect to different models.
This means that Rayo considers a philosophical "interpretation" of set theoretic formulae with respect to the "truth" in the real world, which is unformalisable in mathematics, and does not intend a specific choice of axioms. It is one of reasonable directions of googology outside mathematics. On the other hand, the issue in the last sentence looks like an excuse about why they take the unformalisable "truth" for granted, but it does not make sense because the dependency of the value of a given number on a model is irrelevant to the "invalidity". In mathematics, there are many well-defined notions which are not absolute, i.e. depend on a model, e.g. the unique natural number \(n\) satisfying \((\text{CH} \to n=0) \land (\neg \text{CH} \to n=1)\). In googology, there are many large numbers which depend on a model, e.g. values of Busy Beaver function and especially \(S(1919)\), where \(S\) denotes maximum Shift function. In Big Number Duel, there is no rule prohibiting a number which depends on a model, and indeed it even allowed to skip to fix axioms.
History[]
When Rayo's number was defined[]
Rayo and Elga's number duel was inspired by the large number competitions described in the article "Who Can Name the Bigger Number?" by Scott Aaronson.
After Rayo's number was defined[]
- In January 2013, Adam P. Goucher claimed that \(\text{Rayo}(n)\) grows slower than his xi function.[16] However, the claim turned out to be incorrect.[note 3]
- In October 2013, Fish defined Fish number 7 as an extention of Rayo's number.[note 4] Fish number 7 has a same issue with Rayo's number which is described in Axiom section.
- In October 2014, Wojowu defined BIG FOOT using a non-naive extension of n-th order set theory, the first-order oodle theory, and it was honored as the largest named number.[note 5] However, BIG FOOT turned out to be ill-defined in 2018.
Currently, all the largest named numbers share the same concept of Rayo's function, i.e. referring to the nameability of natural numbers, and all the non-naive extensions such as the FOOT function.
Author[]
The number was invented by Dr. Agustín Rayo, an Associate Professor (at the time when he created Rayo's number) of Linguistics and Philosophy at the Massachusetts Institute of Technology where he received his Ph.D. in 2001.[19]
See also[]
- Rayo's number on Wikipedia.
Footnotes[]
- ↑ Indeed, if \(f\) is a function definable in a first order segment of the second order set theory assumed in the definition of Rayo's function, the defining formula \(\Phi(n,m)\) of the predicate \(m = f(n)\) gives a lower bound of the composition of \(\text{Rayo}(n)\) and a sufficiently slow growing function depending on the growth rate of the length of \(\exists m(\Phi(\ulcorner n \urcorner,m))\) regarded as a function on \(n\), where \(\ulcorner n \urcorner\) is a fixed formalisation of \(n\) in the language of first order set theory.
- ↑ However, Rayo's function naturally can be outgrown by \(f_\alpha(n)\) for some countable \(\alpha\) in the fast-growing hierarchy equipped with a fixed system of fundamental sequences for ordinals \(\leq \alpha\). Indeed, it is outgrown by \(f_{\omega}(n)\) with respect to the fundamental sequence \(\omega[n] = \text{Rayo}(n)\).
- ↑ Goucher misunderstood the definition of Rayo's function as the "largest integer expressible uniquely by n symbols in first-order arithmetic (the language of Peano arithmetic).". The Second-order arithmetic is much stronger, and first-order set theory is even stronger than that. First-order arithmetic's domain of discourse is the natural numbers, but first-order set theory's domain of discourse is defined to be sets of the entire von Neumann universe. In fact, it can be shown that Rayo's function is much more powerful than the xi function.
- ↑ Cookiefonster wrote that "Although Rayo's number was previously surpassed in 2013 by Fish number 7, it is debatable whether that number is a good enough extension to be honored as breaking the record.",[17] even after it turned out[18] that no one regards Fish number 7 as a naive extention. Note that Cookiefonster just agrees with Vel!, and Vel! says Fish number 7 is not a naive extention.
- ↑ Naive extensions like \(\text{FOST}^{100}(10^{100})\) where recursion/iteration notation is used are not honored as breaking the record of Rayo's number.
References[]
- ↑ 1.0 1.1 1.2 A. Rayo, "Big Number Duel", 2007
- ↑ M. T. Manzari, "Profs Duke It Out in Big Number Duel", The Tech, Vol. 126, Issue 64, 2007
- ↑ A. Rayo, "El duelo des los números grandes", Investigación y Ciencia, No. 383, Prensa Científica, 2008.
- ↑ A. Rayo, "Optional: The Big Number Duel", On the Brink of Paradox, MIT Press, 2019
- ↑ Plain'N'Simple, Proof that Rayo(n) is 0 for n less than 10, Googology Wiki user blog.
- ↑ Emk, Rayo(10) is exactly 1 (not a lower bound), Googology Wiki user blog.
- ↑ Plain'N'Simple, Proof that Rayo(n) is 1 for n between 10 and 19, Googology Wiki user blog.
- ↑ Ytosk, Small improvements to bounds on values of Rayo's function, Googology Wiki user blog.
- ↑ Ytosk, Small improvements to bounds on values of Rayo's function, Googology Wiki user blog.
- ↑ Plain'N'Simple, A Rayo string that returns 65536, Googology Wiki user blog.
- ↑ Plain'N'Simple, An even shorter Rayo name for 65536: Who needs ordered pairs?, Googology Wiki user blog.
- ↑ p進大好きbot, Rayo name of 65536, Googology Wiki user blog.
- ↑ Ytosk, Rayo name of 65536 with 346 symbols, Googology Wiki user blog.
- ↑ Ytosk, Small improvements to bounds on values of Rayo's function, Googology Wiki user blog.
- ↑ Emk, A Rayo name larger than BB(10^100), Googology Wiki user blog.
- ↑ Goucher, Adam. The Ξ function. Retrieved 2013-03-21.
- ↑ Cookiefonster's edit on 31 July 2015
- ↑ Talk:Fish_number_7#Is Fish number 7 naive extension of Rayo's number?
- ↑ MIT philosophy faculty: Agustín Rayo. Retrieved February 2013.
Busy beaver numbers (based on Turing theories): \(\Sigma(1919)\) (1919th busy beaver number) · Fish number 4 · \(\Xi(10^6)\) · \(\Sigma_{\infty}(10^9)\)
Rayo's numbers (based on Set theories): Rayo's number (Rayo(10100)) · Fish number 7 · BIG FOOT (FOOT10(10100)) · Little Bigeddon · Sasquatch · Large Number Garden Number
Miscellany: Hollom's number · Oblivion · Utter Oblivion · (Ultimate Oblivion) · (Hyper oblivion) · (Ultra Oblivion)