Talk: Rayo's number

Archive 1

\(\omega_1^\text{DEF}\)

In the archive 1 someone propose \(\omega_1^\text{DEF}\) as the growth rate of Rayo(n). Can someone please explain me what is this ordinal? I didn't find anything about it :/ Fluoroantimonic Acid (talk) 11:06, June 13, 2015 (UTC)

This ordinal was defined as "the least ordinal undefinable in [some formal system here]", but the community came to the conclusion that it causes too much confusion, as this lead to many people thinking there exists the least undefinable ordinal, which is paradoxical concept. LittlePeng9 (talk) 11:11, June 13, 2015 (UTC)

Ok, thanks Fluoroantimonic Acid (talk) 11:20, June 13, 2015 (UTC)

The main reason it was removed is because it wasn't from any source. -- vel! 15:58, August 3, 2015 (UTC)

Rayo(n) and FOST(n)

Fun fact: Rayo(n) and FOST(n) aren't exactly the same, because for Rayo(n) you don't directly have access to all FOST's alphabet (e.g. you can't use the "implies" symbol directly). Of course you don't really need these, Rayo's microlanguage has everything it needs, but it costs a little more symbols, so FOST(n) will often be a very, very little bigger than Rayo(n) for the same n. I would say that Rayo(n) < FOST(n) < Rayo(2*n) Fluoroantimonic Acid (talk) 13:19, August 3, 2015 (UTC)

I don't see how the definition of Rayo(n) allows use of the "implies" symbol. The definition of Sat clearly states what operators are allowed: ∈ = ¬ ∧ ∃. -- vel! 15:58, August 3, 2015 (UTC)

I think what he is saying is precisely that Rayo(n) doesn't allow it, but "implies" is part of FOST, so FOST(n) would have to allow it. LittlePeng9 (talk) 16:17, August 3, 2015 (UTC)

I don't see how "implies" is part of FOST either, if we have no precise definition of FOST at hand aside from Rayo's. I can argue that ordinal addition is a valid FOST operator since it can be defined in FOST. -- vel! 18:08, August 3, 2015 (UTC)

Did Rayo said the name "FOST"? Just wanna know. Also, I consider that as a first-order language it inherits all symbols of the first-order logic "framework" Fluoroantimonic Acid (talk) 16:46, August 10, 2015 (UTC)

"the smallest natural number that cannot be uniquely identified by a FOST expression of at most n symbols"

"the smallest natural number that cannot be uniquely identified by a FOST expression of at most n symbols" The article says this is a trivial variation on Rayo's function. However, wouldn't this be much, much weaker, as Rayo's function cannot express all integers up to Rayo's number. This should be an approximately exponential growth rate, hardly uncomputable. Am I misunderstanding something? Maybe called Googology Noob (talk) 14:16, January 11, 2016 (UTC)

Fixed. Thanks. -- vel! 00:40, January 12, 2016 (UTC)

Better Bounds

Did you know about Rayo(10^100) > 3.333E98? AarexWikia04 - 22:58, August 1, 2016 (UTC)

Really? Then how do we know it is more powerful than BB(10^100) for example? Or is it just that it grows quite slowly? Mush9 (talk) 20:58, November 20, 2016 (UTC)

Aarex's comment is like saying that Graham's number is bigger than 10^40. This is without a doubt true, but Graham's number is far larger than 10^40. Similarly, Rayo(10^100) is far larger than 3.333E98. As for how we know it is larger than BB(10^100), the idea is that we can define Turing machines and Busy Beaver function is relatively small number of characters (at most a few tens of thousands, I'd believe) and we can in FOST the number BB(10^101) in not many more characters. LittlePeng9 (talk) 21:49, November 20, 2016 (UTC)

Axioms of FOST

Formal system consists of symbols, grammer, axioms and inference rules. FOST defines symbols, grammer, logical axioms and inference rules in the first order logic. However, non-logical axioms are not explicitly declared.

As the domain of discourse of FOST is a von Neumann universe, it is natural to assume that FOST uses ZFC. Is it correct? Then if we use ZFC + "there exists I0 cardinal", we have FOST-I0. FOST-I0 should be stronger than FOST, but how strong is it? Can we also make similar extention to FOOT? 🐟 Fish fish fish ... 🐠 20:36, August 9, 2016 (UTC)

If you want axioms to be relevant, you must be talking about what can be can be proven from those axioms - something like ZFC(n) = "the largest natural number m such that there is a FOST sentence phi of length n or less such that ZFC proves that m is the unique natural number to satisfy phi", or something similar. Such a function cannot significantly outgrow the Busy Beaver function: For each sentence phi, one can define a Turing machine that searches through all ZFC proofs and all m for a proof that phi is uniquely satisfied by m. Then with an oracle for the BB function (and therefore the halting function), we can define an oracle Turing machine that runs through the finitely many phi of n characters or less, picks out the ones that have ZFC proofs that phi is satisfied by some natural number, and finds the largest such natural number - this is ZFC(n).

So, to get significantly beyond the Busy Beaver function, we must abandoned provability in a recursively enumerable theory, and talk about truth in a particular model. For Rayo's function, we take the von Neumann universe V, and use FOST as the language of choice (as opposed to formal theory, which includes axioms that we are not worried about). Of course, to believe this works, we must be sufficiently Platonic to believe that V is well-specified. Deedlit11 (talk) 07:36, August 10, 2016 (UTC)

Oh, I see. I've been thinking that FOST is a kind of first-order logic, but actually it isn't, because it doesn't have axioms. As it is explained in the main text that FOST is a first-order logic, I will note in the text that FOST doesn't include axioms. 🐟 Fish fish fish ... 🐠 11:25, August 10, 2016 (UTC)

I do not know about the axioms of FOST. AarexWikia04 - 11:54, August 10, 2016 (UTC)

No, but basic functions like ZFC(n) = "The largest number F(n) such that there is a proof from the ZFC axioms that is Rayo-nameable in n symbols and proves that F is total" do work, and easily outgrow all functions provably total in ZFC, such as the Busy Beaver function, and oracles, diagonalised oracles, etc. In fact, T(n) = "The largest number F(n) such that there is a proof from [any consistent theory that extends T and whose axioms not in T are collectively Rayo-nameable in n symbols] that is Rayo-nameable in n symbols and proves that F is total" is even faster growing, and all we need to do is have T be strong enough to talk about finite ordinals (e.g. general set theory), and it beats all functions provably recursive in any extension of T with only finitely many extra axioms. Notably, this includes ZFC as we can finitely axiomise it with the one-sorted variant of NBG, and even ZFC + "There exists a strongly compact cardinal," as the latter is a first-order large cardinal axiom. ~εmli 23:03, August 14, 2016 (UTC)

Hmm, I suppose you are saying that ZFC proves the Busy Beaver function total because one can argue that there are some finite number of Turing machines that halt, and we are simply taking the maximum score of all such machines. In a similar sense, for any fast-growing function f whatsoever, we can define g(n) = f(n) if f(n) is defined, and g(n) = 0 otherwise; then ZFC (or presumably much weaker) will prove that g(n) is total, and if f(n) is total (with or without a proof) then g(n) = f(n).

But, I don't see how this is a "fix" for Rayo's function; the issue was that no r.e. consistent formal theory determined Rayo's function for all n, but the same is true for your ZFC(n). Yes, proofs are involved in the definition of ZFC(n), but that seems like a red herring. Deedlit11 (talk) 00:47, August 15, 2016 (UTC)

I disagree, as the proofs involved for the totality of the above ZFC function do not require selecting a specific model, whereas they do for Rayo's function. If what you say is the issue at hand, then I am solving a different problem. ~εmli 14:48, August 15, 2016 (UTC)

Anyway, Does not the Rayo's function have any axioms? I just thought Rayo's function doesn't have any axioms and the axioms to make a large number are arranged in the limited n symbols. However, ZFC or PA need the infinite symbols for define the axiom schemas. The axiom schema of specification or the axiom schema of replacement cannot be defined finite symbols of Rayo language. The mathematical induction in Peano also cannot be defined finite symbols. These schemas needs second order logic for their complete definition. Doesn't Rayo's function become week without these schemas? Koteitan (talk) 07:10, May 4, 2018 (UTC)

Rayo's number isn't defined

Quoting a recent xkcd post:

Rayo's number is undefined. (Rayo's function is too, and basic extensions like Big Foot.)

For the values of Rayo's number to be defined, you have to work in a specific model (a specific set of first order axioms, which could be a rectification to the system, is not sufficient). For a simple example, suppose that we work in ZFC, and \(\beth_1 = \aleph_n\) is independent of ZFC (proven, but we might be working in an extension) for each n, and the formula which is true for only n requires k symbols (k is likely only a few thousand).

Now, as this value is an upper bound for Rayo(k), suppose n, in the model we work in, is larger than that. Contradiction. Note that we've already proven that n is idependent, so either we assume that we can only go off provability in [theory], which is both weak (enumerate all proofs in the theory, assuming Rayo(n) is well defined) and dependent on the theory, or choose a model, which requires choosing a model based on a system where we have no axioms to go off of, which is completely arbitrary.

We can, of course, go one further by noting that the definition of a "natural number" may fail in a non-well founded theory and not fail in a well-founded one. Also, it is quite well known that all first-order theories that have an infinite model have infinitely many (at least one of each infinite cardinality), so even if we added restrictions so that we also have to make an axiomatic system, the idea (at the least, for first-order theories) is failed from the get-go.

Edited to add: Going back to the main point, for Rayo's function to be total, it needs to work in a system of absolute truths, as otherwise there exist sufficiently long formulas (length k and above) which may evaluate to any n (as the result is independent from the system), and this n may be larger than Rayo(k), making Rayo's function undefined for the values >=k. No such system of absolute truths can be formulated in first order logic excepting very basic ones: we either need a complete and consistent axiom system (which we can't have*, due to Gödel's incompleteness theorem), or a theory with a single model (which we can't have**, due to the Löwenheim–Skolem theorem).

If I had to suggest how to "fix" the function, I would say that R(n) is the largest number F(n), such that F can be proven total in a finitely-axiomisable (one-sorted) first-order theory which can be described with at most n symbols [in the way Rayo used]. This function grows faster than any function provably total in ZFC (using a finite axiomisation of the one-sorted variant of NBG), however this might not be the case for stronger theories or second-order theories.

*Unless the theory is very weak i.e. it does not incorporate Robinson Arithmetic.

**As the model must be infinite for our purposes, presumably. It may be possible to measure the size of very large finite models, however this does not seem to hold much promise, and better methods definitely exist. ~εmli 23:03, August 14, 2016 (UTC)

What you write is true; see my post in the section before this one. Rayo's number is meant to be defined for a specific model, namely the von Neumann universe V. If you take the position that truth in V is ambiguous, then Rayo's number will be undefined, as will BIG FOOT. It seems likely that Rayo is a Platonist; I know from talking with Wojowu that he (Wojowu) is quite Platonist. So for them their functions are well-defined, for many others they will not be.

Note that even the Busy Beaver function has this same problem; for any recursively enumerable consistent theory T, T cannot determine the Busy Beaver function beyond a particular point, which means there are models of the theory T which differ on the Busy Beaver function past a certain point. Deedlit11 (talk) 23:04, August 14, 2016 (UTC)

I would say that the busy beaver function doesn't have the same problem: it is everywhere defined (easily), and the truth of such depends on the theory; models don't come into the question. Rayo's function, on the other hand, cannot be proven within the theory without talking about the models, and if we merely restrict our knowledge to a theory, then (unlike BB) we can draw contradictions like shown above. ~εmli 14:48, August 15, 2016 (UTC)

Values

Has anyone tried to get the first several values of Rayo's function? Rayo(1), Rayo(2), etc.?

Well, the first few values don't exist, as the first valid definition of a number is (¬∃2(2∈1)), which defines 0. So Rayo(n) doesn't exist for n<=9, and Rayo(10)=0. I think after that the next few values are also 0.  Tomtom2357 (talk) 08:39, October 3, 2016 (UTC)

As Rayo(n) is defined as "the smallest nonnegative integer" greater than ..., Rayo(0)=0, because it is the smallest nonnegative integer. 🐟 Fish fish fish ... 🐠 04:13, October 4, 2016 (UTC)

Use now ¬∃2:2∈1. We don't need to parenthesize the ¬, nor to use 1 parenthesis pair instead of just a colon for existential quantifier. 80.98.179.160 15:43, December 22, 2017 (UTC)

So, do Rayo (7) exist and is it zero? Tetramur (talk) 10:20, May 28, 2019 (UTC)

It exists under a suitable axiom of second order logic. Maybe it is zero. On the other hand, \(\textrm{Rayo}(10)\) is greater than \(0\), because the \(\textrm{FOST}\)-formula \(\neg (\exists x_1(x_1 \in x_0))\) names \(0\).

EDIT: I mistook the syntax. The formula \(\neg (\exists x_1(x_1 \in x_0))\) should be \((\neg \exists x_2(x_2 \in x_1))\).

p-adic 15:17, May 28, 2019 (UTC)

Rayo's ordinal

Let's define \(\alpha\) to be the first \(\alpha\) so that \(f_\alpha(n)\) can never be hot. Now I define first few terms of \(\alpha[n]\):

\(\alpha[0] = 2+2=4\)

\(\alpha[1] = \text{minus 1, that's 3, quick maths}\)

\(\alpha[2] = \text{logarithm} = 44\)

\(\alpha[3] = \text{Scootnum}\)

\(\alpha[4] = \text{Ratnum}\)

\(\alpha[5] = \text{Oosnah}\)

\(\alpha[6] = \text{Smoke trees}\)

\(\alpha[7] = \text{integral}\)

\(\alpha[8] = \text{Quack quack quack}\)

\(\alpha[9] = \text{Asznee}\)

\(\alpha[10] = \text{Rice Krispie}\)

\(\alpha[11] = \text{Nose long like garden hose}\)

\(\alpha[12] = \text{No ketchup}\)

\(\alpha[13] = \text{Just sauce}\)

\(\alpha[14] = \text{Raw sauce} \)

\(\alpha[15] = \text{Fire, fire, fire in the booth}\)

Ya dun know any other terms of fundamental sequence of \(\alpha\). 185.24.68.84 13:58, November 18, 2016 (UTC)

\(\alpha\) is not well-defined. Also, whatever \(\alpha\) would be, specifying 16 completely arbitrary ordinals doesn't specify the fundamental sequence in the slightest. \(\alpha\), as long as it's limit, will have infinitely many fundamental sequences, yet you have made no progress towards specifying any single one. But since I know the community here at least a little, I suppose Aarex will come and and help you with this helpless task. LittlePeng9 (talk) 14:14, November 18, 2016 (UTC)

  Replaced the whole thing with cooler terms Chronolegends (talk) 18:28, November 18, 2016 (UTC)

Replaced the whole thing with cooler commands. LittlePeng9 (talk) 20:04, November 18, 2016 (UTC)

Replaced the thing with even cooler terms, if I'm not too late. ArtismScrub (talk) 01:38, January 12, 2018 (UTC)

How is it so strong?

How does the Rayo's function go beyond other uncomputable functions like the busy beaver function and xi function? ^{—Preceding unsigned comment added by 172.58.104.162 (talk • contribs) 18:27, November 19, 2016 (UTC)}

The basic idea is that you can define TMs and SKIO calculus in set theory (doing so is tedious, but possible). You can then iterate them and what not. LittlePeng9 (talk) 19:23, November 19, 2016 (UTC)

LittlePeng9 do you happen to know any webpages that have turing machines being defined and iterated by set theory? If you do then could you post those weblinks, so i could visit those webpages? —Preceding unsigned comment added by 172.58.104.162 (talk • contribs)

Wikipedia has a formal definition of Turing machines, but you seem to be asking about a definition in the language of set theory. I doubt anyone has ever done that, since it is an extremely tedious thing to do. The closest thing I can direct you to is this post, in which a description in a semi-formal language is given. Also, I give a description of a description (sic) of a specific Turing machine in FOST here.

As for iterating, what I meant is given a function f(n) defined in FOST (presumably as a set of ordered pairs), you can also define in FOST the function f(f(n)) (for example), and having done this for f=BB you beat BB(n). Calling this set of ordered tuples F, you can define f(f(n)) as a set of ordered tuples FF using (borrowing notation from here):

\((x,y)\in FF\Leftrightarrow\exists A,B,z:x=\mathrm{car}(A)\land z = \mathrm{cdr}(A)\land z = \mathrm{car}(B)\land y = \mathrm{cdr}(B)\land A\in F\land B\in F\). LittlePeng9 (talk) 20:37, November 20, 2016 (UTC)

What if I don't understand formal definitions? 109.236.81.168 20:44, November 20, 2016 (UTC)

Then that's your problem. Writing an informal definition into FOST is not possible without formalizing it. LittlePeng9 (talk) 21:43, November 20, 2016 (UTC)

Okay thanks. —Preceding unsigned comment added by 172.58.107.103 (talk • contribs)

Ordinals

How does Rayo's function go beyond large ordinals like, SVO, LVO, and BHO? —Preceding unsigned comment added by 208.54.83.217 (talk • contribs)

What does it mean that a function goes beyond an ordinal? LittlePeng9 (talk) 20:49, November 23, 2016 (UTC)

He means how the function grows faster than these ordinals applied to a nonnegative integer,using the fast-growing hierarchy.He just worded it badly,but you know what he meant by that,you just wanted it formaly.....,right?Boboris02 (talk) 20:58, November 23, 2016 (UTC)

I was just wondering whether they knew what they were talking about, or whether it's just yet another person throwing words around. LittlePeng9 (talk) 21:11, November 23, 2016 (UTC)

if he were to respond to it as it was, a precedent would be set that incorrect things are true, which could mess up the learning process for newcomers

now, for a proper answer: FGH_x(n) where x is a countable ordinal is computable, and Rayo(n)>BB(n)> all computable functions.Chronolegends (talk) 21:31, November 23, 2016 (UTC)

This isn't strictly correct: leaving aside the issue of having to specify fundamental sequences (which can be done in multiple reasonable ways), we can only possibly claim that \(f_\alpha(n)\) is computable when \(\alpha\) is computable (a.k.a. recursive) ordinal, but not necessarily when it's a larger countable ordinal. So once one replaces "countable" with "recursive", I'd agree. LittlePeng9 (talk) 21:40, November 23, 2016 (UTC)

I didn't know there were ways to make  sequences for those, i guess i still have much research to do myself. That replacement does fix it,  or one could also replace the whole phrase with  " for x < ω₁^Ck   " Chronolegends (talk) 07:04, November 24, 2016 (UTC)

So FOST is a language made up of symbols and you can use those symbols to define computable functions and non computable functions. You can then iterate those functions and go beyond those functions. Is this true? —Preceding unsigned comment added by 172.58.104.199 (talk • contribs)

Yes, that's correct. LittlePeng9 (talk) 14:06, December 1, 2016 (UTC)

Is f(f(n)) an example of function iteration? Does f(n) represent all computable functions? How does n relate to f in f(n)? —Preceding unsigned comment added by 172.56.14.33 (talk • contribs)

Yes, f(f(n)) is such an example. Function iteration simply means applying the same function to an argument multiple times; in this case, we apply the function f to n twice.

The notation f(n) can represent any function, not just computable ones. The letter f is a common notation for arbitrary function.

I'm not sure how to interpret the third question; in the setting we are considering, f is any function and n is any natural number, and a priori we don't consider any relation between them. Once we write f(n), we get a new number which is the value of the function f at n. LittlePeng9 (talk) 18:40, December 1, 2016 (UTC)

So n is like the limit of f (function)? —Preceding unsigned comment added by 172.58.107.127 (talk • contribs)

n is just any number. LittlePeng9 (talk) 21:35, December 1, 2016 (UTC)

Okay. —Preceding unsigned comment added by 172.58.110.254 (talk • contribs)

Bytes

Are symbols the same as bytes? Do symbols represent bytes? —Preceding unsigned comment added by 172.58.110.254 (talk • contribs)

No and no. LittlePeng9 (talk) 08:41, December 2, 2016 (UTC)

Microlanguage

What is a microlanguage? —Preceding unsigned comment added by 208.54.86.184 (talk • contribs)

Please remember to sign your posts. It isn't a meaningful term and it was coined for this article. It should probably be removed. -- vel! 19:37, December 3, 2016 (UTC)

Surge in activity

We're getting a huge amount of traffic on this talk page and also for the busy beaver page. Did we get linked somewhere, or is it just one very persistent person? -- vel! 19:38, December 3, 2016 (UTC)

I want to ask a question about Rayo's function. How come the more symbols you use to define a number, the larger the number will be? For example, Rayo(30) is larger than Rayo(20), because it uses more symbols.

^

Because more symbols allow for a more complex output Chronolegends (talk) 22:19, December 6, 2016 (UTC)

I think a good way to understand it is to think about programs. The largest number that you can output using a C program (to pick a random language) of 100 characters or less will be less than the largest number that you can output with 110 characters or less, since you can take the winning 100 character C program and add 1 to the number, or square it, or run it through a function call more times or with a bigger argument. So the Busy Beaver for pretty much any programming language will keep getting bigger and bigger. You can think of FOST as something like a programming language, but it is more powerful. (It's not restricted to algorithms.) Deedlit11 (talk) 09:56, December 7, 2016 (UTC)

Could someone show me an example of tetration being defined in FOST?172.58.104.184 00:26, December 14, 2016 (UTC)

At the bottom of Vel's page on FOST, you can find implementations for Addition, Multiplication, and Exponentiation, and it shouldn't be too hard to see the pattern. Tetration would go like:

∀x,y,z: ((x, y), z) ∈ Tet ⇔ (x,y,z ∈ ω ∧ ((y = 0 ∧ z = 1) ∨ (∃a,b: Sa = y ∧ (z = apply(Exp, (x, b)) ∧ ((x, a), b) ∈ Tet)))

T = apply(Tet, (a, b))

although, now that I look at it, it doesn't look like Vel defines "apply" anywhere. Deedlit11 (talk) 10:10, December 14, 2016 (UTC)

The idea of using "apply" is to emphasize what set in the definition is the function being defined. Semiformally, apply(F,x) is the result of F(x), or more formally, the unique y such that (x,y) ∈ F. I guess it's not defined on the page because it is not the part of the actual definition of a function. LittlePeng9 (talk) 15:34, December 16, 2016 (UTC)

FGH in FOST

Is anyone able to simulate the fast-growing hierachy in FOST? I don't quite see how ordinals could be included. Mush9 (talk) 14:02, December 16, 2016 (UTC)

This isn't a full answer, but rather an idea. There is a single formula in the language of FOST stating "\(\alpha\) is an ordinal" (which can state, for example "\(\alpha\) is a Transitive set and so is every element of \(\alpha\)"). We can then define FGH as a set \(F\) of quadruples \((n,m,\alpha,N)\), where \(n,m,N\) are natural numbers, \(\alpha\) is an ordinal, and the tuple gives \(f_\alpha^m(n)=N\). The rules of FGH would then be:

• \((n,1,0,n+1)\in F\),
• \((n,m+1,\alpha,N)\in F\) iff for some \(N'\) \((n,m,\alpha,N')\in F\) and \((N',1,\alpha,N)\in F\),
• \((n,1,\alpha+1,N)\in F\) iff \((n,n,\alpha,N)\in F\),
• \((n,1,\alpha,N)\in F\) iff \((n,1,\alpha[n],N)\in F\).

Now, while its easy to see how one would formally translate the first three into FOST, fr=or the last one we have to actually define fundamental sequences in FOST. We again do it using a set of tuples: \((\alpha,n,\beta)\) meaning \(\alpha[n]=\beta\). This is the difficult part, but here is how one might define it for ordinals up to \(\omega^\omega\): we consider the set of infinite tuples \((a_0,a_1,\dots)\) of natural numbers, all but finitely many of which are zero, and we think of them as representing \(a_0\omega^0+a_1\omega^1+\dots\). We can well-order this set by reverse lexicographical order (I think), and theorems on well-orders tell us there is a unique monotonic bijection between this set and \(\omega^\omega\). Once we have this representation, it's quite straightforward to define their fundamental sequences.

For \(\omega^{\omega^\omega}\) we can do something similar, but with lists of lists of natural numbers, and for \(\varepsilon_0\) we can allow arbitrarily nested such lists. In general, the first step is to establish a bijection between an ordinal and certain set which is easier to work with, and define fundamental sequences with help of this set. The details are tedious and I am not going to provide all of them, but feel free to ask more specific questions. LittlePeng9 (talk) 15:59, December 16, 2016 (UTC)

What are characters in Kolmogorov Complexity and FOST? How do they relate?172.58.97.31 01:41, December 20, 2016 (UTC)

The notion of Kolmogorov Complexity is not actually tied to one specific language; the idea is that you pick your favorite suitable language, define Kolmogorov complexity based on that language, and the theorems of Algorithmic Information Theory will still apply, since they are generally phrased like "Given a formal theory T, there exists a constant L such such that for no string s can the statement K(s) >= L be proven in in T." Note that this theorem will not depend on specifics of the language that might change Kolmogorov complexity for a string up to some constant factor, and that is generally the case for theorems of AIT.

FOST contains

Boolean connectives (and, or, not, implies)

Quantifier symbols (there exists, for all)

Formatting symbols (parentheses)

an infinite collection of set variables

a special nonlogical symbol ∈, which means "is a member of"

The exact collection of symbols can vary so long as they are sufficiently expressive. In the main page you can find the symbols for Rayo's microlanguage, namely ∈,=,¬,∧,∃,(,), and the infinite collection of set variables. This is suffiently expressive to describe all the formulas of FOST. We can even cut that down to just ∃,∈,NOR, and the set variables, if I'm not mistaken. (equality can be defined, the Boolean operators can all be defined from NOR, and parentheses can be eliminated by using postfix or prefix notation.) Of course you need to stick to Rayo's version for the normal definition of Rayo's function.

For the question "how are they related," I think the natural answer is "not at all." Note that the natural function Kolmogorov(n) = "the largest natural number whose decimal representation has Kolmogorov complexity of n or less (in your favorite programming language)" is an obvious variant of the Busy Beaver function, and will be outpaced by Rayo's function. Deedlit11 (talk) 07:27, December 20, 2016 (UTC)

                                                                                                          One could say that kolmogorov(n) is to (pick your favorite computer language) what Rayo(n) is to the Rayo microlanguage  so i saw it as a quick way to convey the reason that  Rayo(n) > Rayo(m)  for n>m , but  there is no actual relation beyond that.

Chronolegends (talk) 06:11, December 27, 2016 (UTC)

Rayo + Von Neumann Hierachy?

If we want to include all sets as possible number outputs, we can call the von neumann hierachy our ordinal system. Therefore, we can define HRayo's function as: the smallest von neumann hierachy case in which the largest number defined in at most n symbols of FOST is an element of that case. Here, a case is just 0, 1, 2, ... in the Von Neumann Hierachy.

Would this work?

Mush9 (talk) 10:52, January 3, 2017 (UTC)

The von Neumann definition of ordinals and natural numbers is the normal definition of those things in terms of sets, and I imagine it is what Rayo assumed (for natural numbers) in his specification of Rayo's number. So yes, what you are suggesting would work, and is in fact how Rayo does work. Deedlit11 (talk) 11:44, January 3, 2017 (UTC)

Huh? I thought Rayo was talking about Von Neumann Ordinals, not the hierachy. Also, he mentions nothing of elements of the Von Neumann hierachy for, say, 987.

Mush9 (talk) 16:36, January 3, 2017 (UTC)

Your question makes very little sense to me. "If we want to include all sets as possible number outputs" - what? Most sets aren't numbers in any natural way. "...we can call the von neumann hierachy our ordinal system" - what do you mean by an "ordinal system"? "a case is just 0, 1, 2, ... in the Von Neumann Hierachy" - what does the ... represent here? All natural numbers? All ordinals? All sets? Note that every set is an element of (some level of) the von Neumann hierarchy. LittlePeng9 (talk) 17:18, January 3, 2017 (UTC)

What I mean to say is the following: Let's imagine A, the set of all sets. This set features all Von Neumann Ordinals. However, by defining Von Neumann Ordinals such that there are infinitely more sets which could be mapped to numbers, we limit our ability to define larger numbers. Note: When I say numbers, I refer to what sets map to. As for an "ordinal system", it was a term brought up by this article's explanation. I presume it to relate to the Von Neumann Ordinals, calling it a system. The ellipsis is indeed all natural numbers, but in the hierachy. This would lead to some sets. Your last statement is true, unless that was what to add. Hope that helps. Would be glad if you could verify Deedlit's last phrase is false - my entire perception of googology would shift if not. Mush9 (talk) 21:52, January 3, 2017 (UTC)

First thing first, there is no such thing as the set of all sets. More precisely - the collection of all sets is not itself a set, but rather an object called a proper class. It's not very important here though, at least I believe so.

I don't quite see where you are getting with the phrase "there are infinitely more sets which could be mapped to numbers". Why does it matter for Rayo's function? For Rayo's function we just care about formulas defining natural numbers, and we define "natural numbers" using von Neumann ordinals. In the page, "ordinal system" refers precisely to that - von Neumann's construction of ordinals.

"...all natural numbers, but in the hierachy." What do you mean? Are there any natural numbers outside von Neumann hierarchy?

As for Deedlit, he has admitted on the chat he has confused von Neumann hierarchy with von Neumann ordinals there. So in this regard you were right. LittlePeng9 (talk) 22:27, January 3, 2017 (UTC)

I'll read up on proper classes and so on, but my point is that we can name larger numbers since we apply FOST formulae to all sets, rather than just the von neumann ordinals. "...As for all natural numbers, but in the hierachy." - I meant a level of the hierachy by saying "case". The "but..." bit probably confused you Mush9 (talk) 00:35, January 4, 2017 (UTC)

We can apply FOST formulas to arbitrary sets. Who said we can't? LittlePeng9 (talk) 09:23, January 4, 2017 (UTC)

True. However, our 'largest natural number' at the end must be a von neumann ordinal, in Rayo's. In my theoretical extension, the number at the end can be any set, with its natural number rank largest of all defined variables. Mush9 (talk) 10:36, January 4, 2017 (UTC)

Ah, I think I see what you mean now - so you want to define your HRayo as the largest natural number which appears as a rank of some set definable with an at most \(n\) symbol FOST formula? If so, then this is a valid extension, but isn't much stronger. Once we define a set \(A\) in FOST, we can also define "the least ordinal \(\alpha\) such that \(A\in V_\alpha\)", i.e. the rank of \(A\), in FOST. With that we would have HRayo(n) < Rayo(n+c) for a constant c, probably on the order of a few thousands or even just few hundreds. LittlePeng9 (talk) 10:42, January 4, 2017 (UTC)

Okay, thanks. Mush9 (talk) 11:42, January 4, 2017 (UTC)

So computers and Turing machines output functions (computable functions) the same way functions (computable functions) output large numbers. Is this correct?172.58.111.19 12:40, January 11, 2017 (UTC)

No, generally computers and Turing machines implement functions. So you could have a function f(n) = n^2, and you could have a computer or Turing machine implement that function, so that for example you could input 5 into the computer and it would print 25. Now, you could have the output of a computer or Turing machine be a (suitably encoded) function of some sort; but when we talk about computable functions, for example, that refers to the functions that can be implemented by a computer/Turing machine, not outputted by. Deedlit11 (talk) 06:32, January 12, 2017 (UTC)

Is everything in the language of FOST considered a symbol? Such as, () parentheses and word abbreviations (Exp, Tet, Pen,...etc.)? Are the letters that make up those word abbreviations considered symbols (is each letter by it's self considered a single symbol)?172.58.107.83 21:44, January 31, 2017 (UTC)

Is each left parentheses ( and each right parentheses ), by it's self considered a single symbol in the language of FOST?172.58.107.83 21:49, January 31, 2017 (UTC)

Yes, each instance of ( and each instance of ) is considered to be one symbol. As for the earlier question, all of these symbols are indeed considered to be one symbol; we don't decompose them into letters. LittlePeng9 (talk) 10:11, February 1, 2017 (UTC)

Thanks for the info LittlePeng9.172.58.110.184 21:31, February 1, 2017 (UTC)

If you were to write or type Rayo's number in symbol form, would it be equivalent to writing or typing a Googolplex in full digit form? Just think about it, Rayo's number is defined using a Googol (10^100) symbols and a Googolplex has a Googol (10^100) + 1 number of digits.172.58.111.14 21:44, February 2, 2017 (UTC)

Yes, both would take roughly a googol symbols. Deedlit11 (talk) 07:17, February 3, 2017 (UTC)

Does anyone have that weblink where Rayo's function is extended to Hyper E-notation?172.58.110.130 19:49, February 5, 2017 (UTC)

Erdős number of Agustín Rayo

What is the Erdős number of Agustín Rayo? And of Mariano Rajoy? --84.61.151.82 21:27, October 22, 2017 (UTC)

According to this source, Agustín Rayo has Erdős number 4. I don't think that Mariano Rajoy has finite Erdős number, but I am not sure. --84.61.151.82 19:25, October 23, 2017 (UTC)

WaxPlanck (talk) 19:47, November 21, 2017 (UTC) Whenever people say that Rayo’s number is uncomputable, I disagree because I think that it can be computed, but would need a *HELL* of a lot of time and memory.

Formally, you are right. Indeed, every natural number is computable - we can compute a number N using a Turing machine with N states. When saying that "a number is uncomputable", people usually refer purely to the fact that it is defined using an uncomputable function. LittlePeng9 (talk) 20:00, November 21, 2017 (UTC)

Variable symbol

The article use variable symbols of the form 1, 2, 3, and so on, while they are usually used as constant symbols. Isn't this use of variable symbols confusing for those who do not know formal arguments? I think that it is better to replace 1 by x_1 or something like that so that it can be easier to understand. Does anyone has an opinion?

p-adic 03:45, February 5, 2020 (UTC)

The only one issue is that \(x_1\) might be treated as two symbols: x and 1. Triakula (talk) 08:52, February 5, 2020 (UTC)

I see. Then it is good to explain how we count symbols following syntax in first order logic.

p-adic 09:09, February 5, 2020 (UTC)

Axioms

If we're going to express Rayo's number formally, maybe it is good to write down some set of axioms which defines it explicitly? Triakula (talk) 12:12, February 6, 2020 (UTC)

You can read the issue on axioms here. Rayo has never specified axioms, and hence we can just guess Rayo's intension. I guess that it is some kind of a second order ZFC. At least, as the article explain, ZFC set theory is insufficient.

p-adic 12:46, February 6, 2020 (UTC)

So, if I'm correct, it's like BEAF - defined only by the intuition and there are uncountably many ways to well-define it... Then I think that we must not rely on Rayo's number in comparisons with other numbers. Triakula (talk) 12:53, February 6, 2020 (UTC)

Doesn't that make RAYO(n) ill-defined? Cefe origol (talk) 22:33, February 7, 2020 (UTC)

The point is that the defining formula of Rayo(n) is explicitly given, while that of BEAF is not. So for any sufficiently strong axiom (e.g. a second order ZFC), Rayo(n) can be uniquely defined in the theory. On the other hand, BEAF is not. I can never be uniquely defined in a consistent theory, as long as we fix its defining formula. There can be many candidates, because the description by Bowers does not characterise a single function. For example, we have several works using large cardinals. We naturally regard them as works in ZFC + suitable large cardinal axioms instead of ZFC even if no specific axiom is clarified. The lack of the declaration of axioms is not so serious here, because they work in any sufficiently strong theory. The situation is quite similar to it.

p-adic 00:04, February 8, 2020 (UTC)

Existential quantifier

The article says:

"A formula "(∃x_a(e))" means that we can modify the free occurrence of the ath variable in e so that the formula e is true.".

What's the precise meaning of "modify"? Can we substitute the value of the variable x_a by any value of another variable in the assignment? Or by member of Von Neumann Universe? Or, maybe, by any ordinal?

— Best regards, Triakula 11:37, February 15, 2020 (UTC)

With respect to the canonical semantics of FOST in the definition of Rayo's function (formalised in second order set theory), it means that we can substitute x_a by some member of von Neumann universe so that the resulting formula (with parameters in V) will be true.

p-adic 12:03, February 15, 2020 (UTC)

But there are ordinals which aren't in form V_α. For example, ω+1 is not directly a member of von Neumann universe, right? But it is a member of V_ω+1 (all countable ordinals). So can we have ω+1 in the variable assignment when using substitutions in existential quantifier? — Best regards, Triakula 18:59, February 15, 2020 (UTC)

Yes, it is a member of von Neumann universe. The relation \(\omega+1 \in V_{\omega+1}\) implies that \(\omega+1\) belongs to \(V\). Similarly, every set (in particular, every ordinal) belongs to \(V\) in ZFC set theory. Therefore every set can be used in an assignment for the quantifier.

p-adic 00:04, February 16, 2020 (UTC)

Okay, thank you. — Best regards, Triakula 07:49, February 16, 2020 (UTC)

I note that the original definition does not specify the axiom. If we work in a second order set theory in which axiom of regularity does not necessarily hold, then we need to rephrase "von Neumann universe" by "the class V of all sets". (Since we traditionally assume ZFC set thoery unless specified, I assumed it in the answer above.) If you do not want to assume such an axiom which is not declared in the original definition, then please rephrase it.

p-adic 08:05, February 16, 2020 (UTC)

Recent edit

Shoudl I have moved my sentence 1 sentence earlier? C7X (talk) 02:35, September 30, 2020 (UTC)

If you want to know an example of f_α<Rayo, then Wainer hierarchy is ok. If you want to know an example of f_α>Rayo, then you need to clarify what "non-trivial" means. Say, if you define ω[n] as a function faster than Rayo, then you have f_ω>Rayo. Since "the application to FGH" is not significantly effective in uncomputable googology, any "reasonable" fundamental sequence of ω satisfying f_ω>Rayo is given in this way, while you can continue to reject it by saying "it is trivial". Therefore fixing the meaning of the non-triviality, the question is meaningless. (Of course, you can fix it. But I am doubtful that it is worth mentioning in the main article.)

p-adic 02:42, September 30, 2020 (UTC)

Unreliable source

These are self-published sources and the information cannot be added to Wikipedia due to no peer reviews of the truthfulness of these proofs. Nhatminh0207 (talk) 03:57, 11 January 2023 (UTC)

Right. It is not good for wikipedia to cite these articles as peer-reviewed sources. Indeed, there have already been discovered so many wrong claims without proofs in this wiki. This wiki plays a role of a secondary source, i.e. a collection of first sources. If an article cites some unreliable statement from a user without proofs in this wiki, we should be careful that it cannot be a first source of the truth of the statement, while it can be a first souce of the non-mathematical fact that the user claimed it without proofs.

p-adic 06:01, 11 January 2023 (UTC)