Forum:FOST

Forums: Index > Googology > FOST

I found there are two major ordinals related to the FOST:

1) The ordinal $\alpha$ so that $f_\alpha(n)$ has the same growth rate as Ra(n), using natural way of defining fundamental sequences. Formal defintion of "growth rate" can be found here. For naturalness of fundamental sequences we can use the following restriction: no finite-to-finite function is allowed and $\omega[n]$ sets to n. So, for example, the definition of sequence $(\omega*2)[n] = \omega+n^2$ is not natural because it contains the finite-to-finite function $f(n) = n^2$.

2) The smallest ordinal (not FGH up to this ordinal!) which cannot be defined in FOST. Since it operates with infinite sets, it can define not only $f_{\omega}(n)$, $f_{\varepsilon_0}(n)$ and $f_{\Gamma_0}(n)$, but also $\omega$, $\varepsilon_0$ and $\Gamma_{0}$ as well, and there will be also ordinals which are undefinable by FOST.

Any suggestions about what ordinal is larger? Generally, when we deal with notation which works with infinite sets, there would be 2 such ordinals. It would be interesting to find the smallest one for which they are equivalent. Ikosarakt1 (talk ^ contribs) 10:22, April 27, 2014 (UTC)

First of all, there is universal problem of defining "natural" fundamental sequences. As far as it isn't a problem for ordinals describable by notations, the problem already starts for \(\omega^\text{CK}_1\). Rate of growth of this hierarchy might be, in long run, fairly sensitive to exact definition, and there is no way of finding the "most natural" definition, making 1) a bit meaningless.

2) is perfectly well defined. It's easy to see that it's strictly greater than \(\omega^\text{CK}_1\), and I believe it must be recursively inaccessible. I conjecture that this ordinal is strictly greater than \(\Sigma\) (ITTM ordinal) and many of it's relatives which use oracles.

One can also define third ordinal - upper bound on all FOST-definable ordinals. This will be uncountable (as \(\omega_1\) is fairly easily definable) cardinal. LittlePeng9 (talk) 11:04, April 27, 2014 (UTC)

LittlePeng9 is right that there is no way we can define "natural fundamental sequences". We can define a specific set of fundamental sequences up to \(\omega^\text{CK}_1\) though, and quite a bit beyond. However, it doesn't seem likely that we can define fundamental sequences up to the limit of FOST, so 1) has a problem.

The third ordinal LittlePeng9 described is going to be greater than the smallest large cardinal for pretty much all large cardinals I think, so it will be VERY large.Deedlit11 (talk) 13:18, May 8, 2014 (UTC)

What if we plug that ordinal into $\psi$ function and create recursive ordinal? Wouldn't it be larger than Loader's ordinal? Ikosarakt1 (talk ^ contribs) 16:14, May 8, 2014 (UTC)

Note that you can't plug all cardinals into the psi function. \(\psi(I)\) maybe well-defined (I'm not sure), but \(\psi(M)\) is very likely not. Wythagoras (talk) 16:36, May 8, 2014 (UTC)

Deedlit: Are they larger than the Reinhardt cardinals, if they exist?

Also, will the Rayo's function grow faster than the uncomputable Reinhardt cardinals collapsing? Wythagoras (talk) 16:40, May 8, 2014 (UTC)

Wait, I meant the ordinal $\alpha$ plugged into $\psi(\psi_\alpha(\alpha))$. By the way, $\psi(I)$ and $\psi(M)$ aren't technical expressions, they can be only useless shorthands for $\psi(\psi_I(I))$ and $\psi(\psi_M(M))$ respectively. It is like we sometimes shorten $\psi(\psi_{\Omega_2}(\Omega_2))$ to $\psi(\Omega_2)$. Going further using such notation would be ambiguous, $\psi(\Omega_2+\Omega)$ could be either $\psi(\psi_{\Omega_2}(\Omega_2+\Omega))$ or $\psi(\psi_{\Omega_2}(\Omega_2)+\Omega)$. Ikosarakt1 (talk ^ contribs) 16:46, May 8, 2014 (UTC)

@Wyth: I really doubt it will go beyond Reinhardt. LittlePeng9 (talk) 17:19, May 8, 2014 (UTC)

LittlePeng9: I think that the second ordinal is smaller than the first, beacause if FOST can define the fast-growing hierarchy and an ordinal \(\alpha\), Rayo's function must grow faster than \(f_{\alpha}(n)\).

This doesn't give contraction, beacause \(\omega_1\) has no countable fundamental sequence (I found it in the article) and \(\omega_1\) is the smallest uncountable ordinal. Therefore, \(\omega_1\) has no  fundamental sequence, and it can't be defined in the fast-growing hierarchy. Wythagoras (talk) 11:26, April 27, 2014 (UTC)

First, we don't know if FGH is FOST definable (I think it is, but without any certainty). Second, given a countable ordinal \(\alpha\), we'd have to learn to find it's fundamental sequence, which I have no idea how one could do. Third, your argument only shows that second ordinal isn't greater than first (leaving possibility of equality)

Also, now that I think of it, it might be the case that Rayo's function is above FGH! My argument is the following: imagine we can properly define FGH as a function \(F(\alpha,n)\) of ordinal and a number. I think we can formalize in FOST the following set: it'd be a set of ordered pairs of natural numbers, such that the first number appears in exactly one pair. This is formalized notion of a function, let's call it \(f\) here. Now we can say "for all \(\alpha\) we have \(N\) such that, for \(n>N\), we have \(f(n)>F(\alpha,n)\)", which simply means that \(f(n)\) eventually outgrows every FGH function, which makes it impossible for it to be on par with any.

But for me, this is more of an argument on why FGH is undefinable in FOST rather than Rayo(n) is all above FGH. LittlePeng9 (talk) 11:44, April 27, 2014 (UTC)

Oh, I thought that FGH was definable in FOST, beacause of what Ikosarakt said. Wythagoras (talk) 11:52, April 27, 2014 (UTC)

I think FGH is definable in FOST, just not for all ordinals possible. I think we can define FGH up to $f_{\omega}(n)$, $f_{\epsilon_0}(n)$, $f_{\Gamma_0}(n)$ and even $f_{\omega_1^\text{CK}}(n)$. But there will be the first $\alpha$ for which we can't define $\alpha[n]$. So there is a place for another major ordinal. Ikosarakt1 (talk ^ contribs) 13:43, April 27, 2014 (UTC)

We can define FGH up to a very, very large ordinal, far beyond CK ordinal. LittlePeng9 (talk) 17:19, May 8, 2014 (UTC)

Wait, actually, I found one subtle problem with the ordinals I defined, and with FOST in general - namely, what counts as a set? If we made definition "set which is empty and contains an empty set", then this would obviously fail to exist. But what if we defined "the smallest ordinal which has weakly inaccessible cardinality" will it define a set? It depends on existence of weakly inaccessible cardinal, which can be taken as an axiom or not. LittlePeng9 (talk) 12:05, April 27, 2014 (UTC)

Is Rayo's strength dependent on the axioms we use? How dependent? you're.so.pretty! 16:57, April 27, 2014 (UTC)

I think it can be very dependent. Here is an example: imagine we work with Kripke-Platek axioms. From them we can't prove well-foundedness of BH ordinal, so if we define "a non-empty set consisting of all infinite decreasing sequences below BH ordinal", we can't tell if it's a set or not, and if we define \(n\) to be number of elements of that set, or 0 if it's infinite, we can't tell if this is correct definition of a number.

But, if now we switch to usual ZF axioms, we can prove that there are no descending chains in BH ordinal, thereby proving that our set doesn't exist (note the word "non-empty"). Thus \(n\) has invalid definition.

I know that doesn't answer your question, but I know this: if we take set of axioms which is suffiscently small, resulting numbers will be significantly smaller too. LittlePeng9 (talk) 17:35, April 27, 2014 (UTC)

I think I have a better example, possibly answering your question: in Kripke-Platek axioms you can't prove BH to be an ordinal, so if you were to formalize FGH up to some ordinal, you'd need it to be below BH (because KP is consistent with "BH ordinal isn't well-founded", and by adding this axiom FGH above BH wouldn't make sense). But if we add to axioms the existense of recursively inaccessible, we can go far beyond BH, and formalize FGH further, so it provably makes sense, and we can produce numbers larger than with KP axioms alone. LittlePeng9 (talk) 17:42, April 27, 2014 (UTC)

I believe this implies that Rayo's function is ambiguously defined. Can we assume that he meant ZFC? you're.so.pretty! 18:01, April 27, 2014 (UTC)

I think so, but this still leaves some ambiguities related to things independent of ZFC (e.g. set which is non-empty iff continuum hypothesis fails). I think it's reasonable to assume all of these sets are then ill-defined. LittlePeng9 (talk) 18:05, April 27, 2014 (UTC)

Okay, so let's look at some of the things we can do with this information. An obvious step is to create a generalized variant of Rayo's function that lets us plug in not only a maximum length but also a set of axioms to deal with. Evaluation ignores any statements that are inconsistent or independent of the axioms. If we let n be the length and A be the axioms, then we can write "Rayo_A(n)." Presumably, Rayo's number is Rayo_ZFC(10¹⁰⁰).

To make a bit of a leap here, is it possible to provide a set of axioms that work in a second-order set theory? e.g. by allowing variables to represent proper classes? you're.so.pretty! 18:38, April 27, 2014 (UTC)

Yes LittlePeng9 (talk) 18:45, April 27, 2014 (UTC)

Neat.

I'm worried about inconsistency. Does the principle of explosion force us to reject ALL statements in an inconsistent theory? you're.so.pretty! 18:46, April 27, 2014 (UTC)

If there is an inconsistency (in ZFC, say) then everything is provable, so there are no independent statements. The problem is, this just loses it's sense anyway, because one can then prove that empty set contains all natural numbers and other oddities. So yes, we'd have to reject every statement, but for other reason than I explained above. LittlePeng9 (talk) 18:55, April 27, 2014 (UTC)

Since we don't know whether ZFC is consistent (although we're fairly certain), this means that we don't have 100% confidence that Rayo's number exists. Eep.

Related: paraconsistent mathematics. you're.so.pretty! 18:58, April 27, 2014 (UTC)

Rayo's function does not depend on ZFC, or any particular set of axioms. By Rayo_ZFC I presume you mean that we only take those formal statements to be true that can be proven in ZFC. In such a case, we can construct an algorithm that lists all ZFC proofs (and therefore all true statements, according to our assumption). So Rayo_ZFC can grow no faster than a level-1 oracle Busy Beaver function. The same argument will hold if we replace ZFC by any recursively enumerable formal theory.

To get the real strength of Rayo's function, we have to go by some Platonist assumptions; there exists a notion of a true statement in the language of set theory that cannot be captured by any recursively enumerable formal theory. This may be difficult to accept if, for example, you don't accept that there is necessarily a truth value for, say, the Continuum Hypothesis. But, we can still salvage Rayo's function if we accept that some statements are uneqivocally true, some statements are uneqivocally false, and some may not belong to either category. So, for example, we cannot take as a large number "the number n such that 2^aleph_0 = aleph_n" if we do not accept that 2^aleph_0 corresponds to a particular aleph_n. Of course, if our collection of true statements do not extend beyond ZFC or some recursively enumerable formal system, than we haven't gotten anywhere. But, it seems reasonable that there exists a collection of unequivocally true statements that are not recursively enumerable, and allow Rayo's function to be very large.

As for the unprovability of the consistency of ZFC, I think that people make too much hay about it. How do we have confidence in statements that we can prove? Any proof has to be based on starting axioms, so you can only believe in the conclusion if you believe in the axioms used to prove it. If you believe in a statement because of a ZFC proof, you should believe in ZFC as well. It's true that most proofs don't use the full strength of ZFC, but to me, the ZFC axioms seem quite reasonable, and I see no reason not to accept them. Deedlit11 (talk) 13:53, May 8, 2014 (UTC)

I understand your point. However, by the arguments I stated above, wouldn't the size of Rayo's number depend on what set of statements we Platonistically assume to be true? As a bad example, we could take an ultrafinitistic set of statements in which there in which existence of any infinite sets is negated, we would have a very narrow possibilities for large numbers. LittlePeng9 (talk) 14:11, May 8, 2014 (UTC)