Rayo's number is a
large number
Large numbers are numbers significantly larger than those typically used in everyday life (for instance in simple counting or in monetary transactions), appearing frequently in fields such as mathematics, cosmology, cryptography, and statistical m ...
named after Mexican philosophy professor
AgustÃn Rayo which has been claimed to be the largest named number. It was originally defined in a "big number duel" at
MIT
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...
on 26 January 2007.
Definition
The definition of Rayo's number is a variation on the definition:
The smallest number bigger than any finite number named by an expression in the language of first-order set theory with a googol symbols or less.
Specifically, an initial version of the definition, which was later clarified, read "The smallest number bigger than any number that can be named by an expression in the language of first-order set-theory with less than a googol (10
100) symbols."
The formal definition of the number uses the following
second-order formula, where
†is a
Gödel-coded formula and s is a variable assignment:
For all R
Given this formula, Rayo's number is defined as:
The smallest number bigger than every finite number m with the following property: there is a formula φ(x1) in the language of first-order set-theory (as presented in the definition of ''Sat'') with less than a googol symbols and x1 as its only free variable such that: (a) there is a variable assignment s assigning m to x1 such that Sat( †(x1)s), and (b) for any variable assignment t, if Sat( †(x1)t), then t assigns m to x1.
Explanation
Intuitively, Rayo's number is defined in a
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
, such that:
* "x
i∈x
j" and "x
i=x
j" are atomic formulas.
* If θ is a formula, then "(~θ)" is a formula (the
negation of θ).
* If θ and ξ are formulas, then "(θ∧ξ)" is a formula (the
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
of θ and ξ).
* If θ is a formula, then "∃x
i(θ)" is a formula (
existential quantification
In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, ...
).
Notice that it is not allowed to eliminate parenthesis. For instance, one must write "∃x
i((~θ))" instead of "∃x
i(~θ)".
It is possible to express the missing
logical connectives
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary c ...
in this language. For instance:
*
Disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor S ...
: "(θ∨ξ)" as "(~((~θ)∧(~ξ)))".
*
Implication: "(θ⇒ξ)" as "(~(θ∧(~ξ)))".
*
Biconditional
In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective (\leftrightarrow) used to conjoin two statements and to form the statement " if and only if ", where is known as t ...
: "(θ⇔ξ)" as "((~(θ∧ξ))∧(~((~θ)∧(~ξ))))".
*
Universal quantification
In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other ...
: "∀x
i(θ)" as "(~∃x
i((~θ)))".
The definition concerns formulas in this language that have only one
free variable
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation (symbol) that specifies places in an expression where substitution may take place and is not ...
, specifically x
1. If a formula with length n is satisfied
iff
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicon ...
x
1 is equal to the finite
von Neumann ordinal
In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets.
A finite set can be enumerated by successively labeling each element with the leas ...
k, we say such a formula is a "Rayo string" for k, and that k is "Rayo-nameable" in n symbols. Then, Rayo(n) is defined as the smallest k greater than all numbers Rayo-nameable in at most n symbols.
Examples
To Rayo-name 0, which is the empty set, one can write "(¬∃x
2(x
2∈x
1))", which has 10 symbols. It can be shown that this is the optimal Rayo string for 0. Similarly, (∃x
2(x
2∈x
1)∧(¬∃x
2((x
2∈x
1∧∃x
3(x
3∈x
2))))), which has 30 symbols, is the optimal string for 1. Therefore, Rayo(n)=0 for 0≤n<10, and Rayo(n)=1 for 10≤n<30.
Additionally, it can be shown that Rayo(34+20n)>n and Rayo(260+20n)>
n2.
References
{{Use dmy dates, date=February 2018
Large integers