FANDOM


Rayo's number is one of the largest named numbers, coined in a large number battle pitting Agustín Rayo against Adam Elga.[1][2] 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)\) (alternatively expressed as \(\text{FOST}(n)\)[3]). 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)\). Rayo's function is one of the most fast-growing functions ever to arise in professional mathematics[citation needed]; only a few functions, especially its generalization, 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 is ill-defined.

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 {
  {
    ∀[ψ], s: R([ψ],t) ↔ ([ψ] = "xi ∈ xj" ∧ t(x1) ∈ t(xj))
                      ∨ ([ψ] = "xi = xj" ∧ t(x1) = 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-namable 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:

  1. There is a variable assignment \(s\), assigning \(x_1 := m\), such that \(\text{Sat}([\phi(x_1)], s)\).
  2. 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-namable in \(n\) symbols.

Explanation 1

A variable assignment is some infinite sequence of objects such as \((3, 2, 6, 1/2, \{4, \pi\}, \text{Canada}, \omega, 65, \ldots)\). A formula is some statement about a variable assignment, such as "the third variable is relatively prime to the second one" or "the second variable is the set of all real numbers except for 3.2".

Rayo defined a very specific and abstract micro-language for describing how a formula works:

  • "ab" means that the ath member of the sequence is an element of bth member of the sequence.
  • "a=b" means the ath member of the sequence is equal to the bth member of the sequence.
  • e", the negation of the formula e.
  • "ef", for formulas e and f, indicates the logical and operation.
  • "∃a:e" indicates we can modify the ath member of the sequence so the formula e is true.

For example, take the formula "1∈2". This says "the member 1 is an element of the member 2," so we can plug in the variable assignment \((\text{apple}, \text{set of all types of fruits}, \ldots)\) and the result will be true since apple is a type of fruit. If instead we plug in \((\text{cheese}, \text{set of all types of fruits}, \ldots)\), the result is not true because cheese is not a type of fruit. (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: "¬∃1:1∈2". This says, "it is not true that there exists a member 1 such that member 1 is an element of member 2." In other words, we cannot pick member 1 such that member 1 is an element of member 2. This works when member 2 is the empty set, such as in the variable assignment \((3, \{\}, \ldots)\) No matter what we change the \(3\) to, it can never be a member of the empty set.

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 "¬∃2:2∈1" = "we cannot pick variable 2 such that variable 2 is a member of variable 1" = "we cannot pick an element of variable 1" = "variable 1 has no elements" = "variable 1 is empty set".

Now we need to find a way to Rayo-name \(1=\{\{\}\}\). We first put the empty set in variable 2 using the same trick as above: "¬∃3:3∈2". We also need "2∈1" to ensure that variable 1 is not an empty set. To ensure that 1 does not have any other elements, we use "¬∃3∈1:¬3=2" = "we cannot pick variable 3 an element of variable 1, to not be variable 2" = "if variable 3 is an element of variable 1, it must be variable 2" = "variable 2 is the only element of variable 1 (if variable 1 has any element)". We "and" all these statements together, we get "(¬∃3:3∈2)∧2∈1∧¬∃3∈1:¬3=2".

We can continue with this pattern, defining each natural number using this method. It allows us to name the number \(n\) in \(\frac{9n^2+47n+20}2\) symbols. (Unless we assume Zermelo constructs, with it, we can do it in \(16n+10\)!) 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.

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. With more effort, one can even construct oracle Turing machines and define their analogs of Busy Beaver function.

Example Rayo strings and their values

\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_2 \in x_1 \land x_3 \in x_1) \land (\neg x_2 = x_3))) \\ & & \land (\neg \exists x_2((x_2 \in x_1 \land \exists x_3(\exists x_4((x_3 \in x_2 \land x_4 \in x_3)))))) \ \textrm{(57 symbols)} \end{eqnarray*}

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 determining 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.

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 the Busy Beaver function because it can only define numbers defined with provable functions in a recursively enumerable theory. 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.

History

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.

In January 2013, Adam Goucher claimed that \(\text{Rayo}(n)\) grows slower than his xi function.[4] However, the claim turned out to be incorrect, because 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.

Rayo's number was honored as the largest named number until 2014 when BIG FOOT was defined, using a non-naive extension of n-th order set theory, the first-order oodle theory. Note that 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. Although Rayo's number was previously surpassed in 2013 by Fish number 7, it was debatable whether that number was a good enough extension to be honored as breaking the record. 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 namability 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 of Linguistics and Philosophy at the Massachusetts Institute of Technology where he received his Ph.D. in 2001.[5]

Sources

  1. Big Number Duel
  2. Profs Duke It Out in Big Number Duel
  3. http://snappizz.com/foot
  4. Goucher, Adam. The Ξ function. Retrieved 2013-03-21.
  5. MIT philosophy faculty: Agustín Rayo. Retrieved February 2013.

See also

Community content is available under CC-BY-SA unless otherwise noted.