Previously, Ive shown my simple notation from 1983 expressing that my thinking paralled (and almost duplicated the symbology of) Knuth notation and Chained arrow notation. Now heres the the real largest number studied, from the Googology Wiki site. Rayos number is the largest named number, coined in a large number battle pitting Agustín Rayo against Adam Elga.[1][2] Rayos number is, in Rayos 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 a googol symbols or less. By replacing googol with any positive integer, we get a very quickly growing function Rayo(n). Rayos function is uncomputable; it is impossible for a Turing machine (and, by the Church-Turing thesis, any modern computer) to calculate Rayo(n) or Rayo(10100) without using infinite time and memory. In fact, even an oracle Turing machine, or any order-n Turing machine, cannot compute it. The power of Rayos function comes from diagonalizing over the foundations of modern mathematics itself! It is very difficult to devise a simple system significantly more powerful than Rayo(n), and in fact none have yet been created. Contents[show] Definition Edit Let [ϕ] and [ψ] be Godel-coded formulas and s and t be variable assignments. Define Sat([ϕ],s) as follows: ∀R { { ∀[ψ], s: R([ψ],t) ↔ ([ψ] = xᵢ ∈ xⱼ ∧ t(xᵢ) ∈ t(xⱼ)) ∨ ([ψ] = xᵢ = xⱼ ∧ t(xᵢ) = t(xⱼ)) ∨ ([ψ] = (¬θ) ∧ ¬R([θ], t)) ∨ ([ψ] = ([θ]∧ξ) ∧ R([θ], t) ∧ R([ξ], t)) ∨ ([ψ] = ∃xᵢ(θ) ∧ ∃t′: R([θ], t′)) (where t′ is a copy of t with xᵢ changed) } ⇒ R([ϕ],s) } Call a natural number m Rayo-namable in n symbols if there is a formula ϕ(x1) with less than n symbols and x1 as its only free variable that satisfies the following properties: There is a variable assignment s, assigning x1 :=m, such that Sat([ϕ(x1)],s). For any variable assignment t, if Sat([ϕ(x1)],t), t must have x1=m. Rayo(n), then, is the smallest number greater than all numbers Rayo-namable in n symbols. Explanation 1 Edit A variable assignment is some infinite sequence of objects such as (3,2,6,1/2,{4,π},Canada,ω,65,…). 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: a∈b means that the ath member of the sequence is an element of bth member of the sequence. a=b means that the ath member of the sequence is equal to the bth member of the sequence. (¬e), for formula e, is the negation of e. (e∧f), for formulas e and f, indicates the logical and operation. ∃a(e) indicates that we can modify the ath member of the sequence such that 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 (apple,set of all types of fruits,…) and the result will be true, since apple is a type of fruit. If instead we plug in (cheese,set of all types of fruits,…), the result is not true because cheese is not a type of fruit. 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 ∈ member 2. This works when member 2 is the empty set, such as in the variable assignment (3,{},…) 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 is good with respect to the formula. Now we arrive at the core concept of Rayo-nameability, ignoring the length restriction: There is a formula ϕ such that all good variable assignments must have m as their first argument, and there is at least one such assignment. First we shall prove that 0 is Rayo-nameable. In the ordinal system, 0={}. We need to craft a formula ϕ 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. 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 1 does not have any other elements, we use (¬∃3((3∈1∧(¬3=2)))) = we cannot pick variable 3 such that variable 3 is an element of variable 1, but is not the same as 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. We and all these statements together, we get (((¬∃3(3∈2))∧2∈1)∧(¬∃3((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 (9n2+43n)/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. Why is Rayos function uncomputable? Set theory deals with infinite sets. For example, in (¬∃2((¬2∈1))), 2 is the universal set. With some difficulty, it is possible to define ordinals in the fast-growing and other hierarchies. There is no way an algorithm can possibly iterate over the entire Von Neumann universe. Explanation 2 Edit Rayos number takes advantage of definability theory. A set is definable if and only if it can be uniquely named by a finite expression in first-order logic. Most real numbers we work with are definable, such as e, π, γ, etc. But in fact almost all real numbers are undefinable, and we can never have any hope of using them in a mathematical context. In contrast, all the natural numbers are definable. 0 is defined by the empty set, 1 as the successor of the empty set, 2 as the successor of the successor of the empty set, etc. All the natural numbers are finite, and each one can be named by a finite expression in first-order logic. What happens if we restrict the size of the expressions? Let A(n) denote the set of all natural numbers that can be named in an expression of first-order logic in at most n symbols. Its easy to see that A(n)⊆A(n+1), so the set of numbers weve defined will expand as n increases. It follows that max(A(n))≤max(A(n+1)) and the function R(n)=max(A(n)) is nondecreasing. History Edit Rayo and Elgas number duel was based on an article by Scott Aaronson. In January 2013, Adam Goucher reported that Rayo(n)s growth rate is comparable to fωCKω(n) in the fast-growing hierarchy[3], where ωCKω is the limit of the sequence of admissible ordinals ωCK1, ωCK2, ωCK3, ..., and ωCK1 the Church-Kleene ordinal. He then devised the xi function, whose growth rate is believed to be the first fixed point of α↦ωCKα. However, the claim has turned out to be incorrect, because Goucher misunderstood the definition of Rayos number as the largest integer expressible uniquely by n symbols in first-order arithmetic. Second-order arithmetic is much stronger, and first order set theory is even stronger than that. First-order arithmetics domain of discourse is the natural numbers, but first order set theorys domain of discourse is defined to be sets of the entire von Neumann universe. Therefore, Rayos function is almost certainly more powerful than the xi function, and Rayo(n)s growth rate in FGH is still in search. Author Edit Dr. Agustín Rayo is an Associate Professor of Linguistics and Philosophy at the Massachusetts Institute of Technology where he received his PhD in 2001.[4] O.K. got that?
Posted on: Wed, 30 Oct 2013 07:45:49 +0000
Trending Topics
Recently Viewed Topics
© 2015