Talk:Fast-growing hierarchy

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Foundations, logic, and set theory

fε0(n)[edit]

Am I understanding this correctly as being: fn↑↑n(n)? — Preceding unsigned comment added by 216.163.254.2 (talk) 12:28, 24 June 2011 (UTC)

No, that's not correct. In the Wainer hierarchy, fn↑↑n(n) ≤ fω+1(n) for all n > 0. (In fact, even fn↑nn(n) ≤ fω+1(n) for all n > 0, where n↑nn is the nth Ackermann number.)
When the subscript is a limit ordinal α (so α-1 does not exist), fα(n) is defined to be fα[n](n), where α[n] is the nth term of the specified fundamental sequence for α. As defined in the article, the fundamental sequence for ε0 is ε0[n] = ω↑↑(n-1) for n > 0; however, some authors (e.g. [Prӧmel, et al., 1991]) do take take ε0[n] = ω↑↑n instead. (Here ω↑↑n denotes ω↑(...ω↑(ω↑(ω))...) with n omegas.) For n > 1 in either case, ε0[n] is not a finite ordinal like n↑↑n or n↑nn, but is an exponential tower of ωs (still a limit ordinal), which must then be replaced by the nth term of its fundamental sequence, etc. etc., until eventually obtaining a successor ordinal (which might still be infinite!). When the subscript is a successor ordinal, say β, the next step is to replace fβ(n) by the n-fold iteration fβ-1(...fβ-1(fβ-1(n))...), then to continue by applying the appropriate reduction to fβ-1(n), etc. etc. For any n > 1, this process applied to fε0(n) eventually produces a finite formula that contains no infinite ordinals at all, but the formula is much more complex than fn↑↑n(n) or fn↑nn(n).
Here's an example showing a few steps, using the more-convenient alternative definition ε0[n] = ω↑↑n:
fε0(2)
= fωω(2) because (ε0)[2] = ωω
= fω2(2) because (ωω)[2] = ω2
= fω·2(2) because (ω2)[2] = ω·2
= fω+2(2) because (ω·2)[2] = ω+2
= fω+1(fω+1(2)) because (ω+2)-1 = ω+1
= fω+1(fω(fω(2))) because (ω+1)-1 = ω
= fω+1(fω(f2(2))) because (ω)[2] = 2
= fω+1(ff2(2)(f2(2))) because (ω)[f2(2)] = f2(2)
= fω(...fω(fω(fω(ff2(2)(f2(2)))))) with ff2(2)(f2(2)) "fω"s, because (ω+1)-1 = ω
= fω(...fω(fω(fff2(2)(f2(2))(ff2(2)(f2(2)))))) with ff2(2)(f2(2)) - 1 "fω"s, because ω[ff2(2)(f2(2))] = ff2(2)(f2(2))
= fω(...fω(ffff2(2)(f2(2))(ff2(2)(f2(2)))(fff2(2)(f2(2))(ff2(2)(f2(2)))))) with ff2(2)(f2(2)) - 2 "fω"s, because ω[fff2(2)(f2(2))(ff2(2)(f2(2)))] = fff2(2)(f2(2))(ff2(2)(f2(2)))
= ... with one fewer "fω" at each step, until none of the ff2(2)(f2(2)) "fω"s remain ...
= fX(X) where X is a very lengthy finite formula containing no ωs.
Note that f2↑↑2(2) is far less than even the number of "fω"s involved in the evaluation of fε0(2).
(Contrast this "complexity" of fε0(n) with that of fω(n), for which a finite formula free of infinite ordinals is immediately given by fω[n](n) = fn(n).)
r.e.s. (talk) 20:09, 26 June 2011 (UTC)
I understand now. Thank you. Just to make sure I understand one small sub-point:
fω2(2) = f88(8), right? Not f2(8)?
In other words, if you have fω2(2), you can't just convert the ω to n. You have to treat it as fω(fω(2)), the first ω becoming n, and the second ω becoming f2(2), right?
This is how I interpreted things based on your kind extrapolation of ε0 into a finite ordinal, but I wanted to be sure. — Preceding unsigned comment added by 216.163.254.2 (talk) 16:56, 22 July 2011 (UTC)
Almost, but not quite. It should be fω2(2) = fω(fω(2)) = fω(f2(2)) = fω(8) = f8(8)
r.e.s. (talk) 18:05, 22 July 2011 (UTC)
Ahh not sure why I put an 8 there. But that's what I meant. Thanks.

fε0(2) is much larger than Graham's number since: fω+1(64) = fω64(64) > fω64(6) > G and fε0(2) = fω+1(f8(8)) — Preceding unsigned comment added by 216.163.255.2 (talk) 15:52, 29 August 2011 (UTC)

Is this function total computable? I think so, because we can use transfinite induction to prove that fε0(n) can be converted to form without epsilon number. Similiary we can prove than fεx(n) can be converted to form with at most fε(x-1)(n) (I think) 83.21.59.98 (talk) 18:49, 16 April 2012 (UTC)

fω(n)?[edit]

I'm having a hard time understanding what is meant by this function. How is fω(n) not infinite?

The article states fω(n) = A(n, n)

To me it seems like something infinite is somehow supposed to be equal to something finite.

What am I missing here? — Preceding unsigned comment added by 216.163.254.2 (talk) 18:20, 14 June 2011 (UTC)

Actually, the article says
fω(n) = fn(n) > 2 ↑n - 1 n > 2 ↑n − 2 (n + 3) − 3 = A(n, n) for n ≥ 2
i.e., it's an inequality relation: fω(n) > A(n, n) for n ≥ 2.
Possibly you're confused by the mere appearance of the symbol ω in the name of this function (fω).
if fω(n) = fn(n) then why the use of omega? see here: http://en.wikipedia.org/wiki/Large_numbers#Systematically_creating_ever_faster_increasing_sequences this article explicitly states that the symbol ω is meant to refer to the infinite ordinal. so to me it still seems as though fω(n) should refer to an infinite function. and if that article was indeed using ω to refer to n, should I assume that this article is using ε0 to refer to n↑↑n? why not just say that? and what's so special about tetration? why not n↑↑↑n or n→n→n→...(n →'s)...→n?
For any nonnegative integer n, fω(n) means exactly fn(n), which is always a nonnegative integer (not infinite).
r.e.s. (talk) 17:33, 15 June 2011 (UTC)
then ω in this context is not the infinite ordinal i'm used to. because fa(n) increases as a increases. it doesn't limit off as a increases. therefore if a = ω, then fω(n) is at least ω. the wainer hierarchy converts infinite ordinals to finite things. — Preceding unsigned comment added by 216.163.255.2 (talk) 11:52, 22 June 2011 (UTC)

Would just like to say (now that I understand this stuff perfectly), that my question could have been answered, and understanding could have been bestowed by anyone willing to simply point out that the hierarchy in question is a diagonalization process. And to mention that for infinite ordinals, we evaluate the ordinal as the nth element of the ordinal's set. Or the nth element of a set of which the ordinal is the supremum.

I know most of this is implied by the article, but it makes no mention of diagonalization whatsoever. — Preceding unsigned comment added by 216.163.246.2 (talk) 11:44, 26 July 2011 (UTC)

fundamental sequence rule[edit]

  • if λ = α + β, with β < α, then λ[n] = α + β[n],

I still don't think that this is right. what if α = ω3 + ω and β = ω2?

I think this should be something like if β is the smallest power of ω in the Cantor normal form of λ. What do you guys think? Cheers, — sligocki (talk) 05:37, 4 November 2009 (UTC)

You're right. I think it would be enough to just say at the beginning, "For λ < ε0, written in Cantor normal form:" (according to Gallier, p.61.) Thanks for catching these points.
r.e.s. (talk) 13:10, 4 November 2009 (UTC)
If α = ω3 + ω and β = ω2, then α + β = ω3 + ω2, because ω + ω2 = ω2. In other words, the ordering, "ω followed by a copy of ω2" has order type ω2. Addition is associative, but not commutative, with order-types. — Preceding unsigned comment added by 76.102.84.197 (talk) 21:08, 14 December 2012 (UTC)
And, to belabor the point, we get λ[n] = ω3 + ωn, but α + β[n] = ω3 + ω(n+1). Ben Standeven (talk) 17:59, 2 February 2013 (UTC)

Löb–Wainer hierarchy?[edit]

Is this the same as the Löb–Wainer hierarchy referred to by Rose (1984)? Originally from Löb–Wainer (1970-71), Hierarchies of number theoretic functions? Rose uses a different definition, but this looks like what he's referring to. Cheers, — sligocki (talk) 18:46, 4 November 2009 (UTC)

Except for using n instead of n + 1 iterations, this is the same hierarchy that Rose attributes to "Tait, Lob, Wainer, et al". A 1991 paper by Proemel, Thumser, and Voigt, "Fast growing functions based on Ramsey theorems", p. 345, (available online) calls this the "Wainer hierarchy", and says it is actually a modification due to Ketonen & Solovay in 1981. I haven't seen the latter paper, but I suspect that's where the modified number of iterations might have originated. — r.e.s. (talk) 15:38, 5 November 2009 (UTC)

Omega[edit]

Why is omega used for the set of natural numbers, instead of N? —Anonymous DissidentTalk 02:47, 7 November 2009 (UTC)

N (unlike ω) is ambiguous about whether 0 is an element. Of course this could be stated explicitly. -- r.e.s. (talk) 14:41, 7 November 2009 (UTC)
It also seemed a little weird to me to use omega, so I switched it and wrote explicitly the numbers. Cheers, — sligocki (talk) 18:47, 7 November 2009 (UTC)

Hardy hierarchy and slow-growing hierarchy[edit]

Motivated by WP:Make stubs, I started articles for both Hardy hierarchy and slow-growing hierarchy based on the very limited information I have. Please edit/expand/fix as needed. Cheers, — sligocki (talk) 07:39, 1 December 2009 (UTC)

Copy of article[edit]

Does anyone have a copy of the original (Löb and Wainer 1970) paper? I'd appreciate any help in getting a hold of a copy. Cheers, — sligocki (talk) 23:52, 7 December 2009 (UTC)

Never mind, got it. Cheers, — sligocki (talk) 20:07, 9 December 2009 (UTC)

Are all f computable?[edit]

I'm concerned about this statement:

Specifically, I believe that it depends upon the fundamental sequences being computable. For example, I could define the fundamental sequence for ω to be ω[n] = Σ(n) (the busy beaver function). But even for less perverse systems it's unclear. For example, let's choose only computable functions for fundamental sequences up to the Church-Kleene ordinal, ωCK. Then we could define a fundamental sequence for ωCK by ωCK[n] = the largest ordinal represented by one of the first n enumerated computable functions. This fundamental sequence is clearly not computable and I don't think there's any reason to believe that fωCK would be computable. Cheers, — sligocki (talk) 01:06, 9 December 2009 (UTC)

The fundamental sequences for limit ordinals not greater than ε0 (all of which are computable) are specified in the article, so this question pertains to their definition for limit ordinals larger than ε0. I think we can safely say that computability is tacitly assumed, if not explicitly stated, for any fundamental sequence assigned to a recursive limit ordinal. I don't have a source that mentions extending the fast-growing hierarchy beyond the recursive ordinals, so I'm not sure the question concerning the Church-Kleene ordinal actually pertains to this hierarchy.
— r.e.s. 17:34, 9 December 2009 (UTC)
I completely agree that this statement is true for the defined levels of the hierarchy up to ε0. However, the section says:
Following are some relevant points of interest about the fast-growing hierarchy {fα| α < μ}:
with μ unconstrained. The hierarchy can be defined up to any ordinals we can define fundamental sequences for. And, as I've stated, there is a way to define a fundamental sequence for the Church-Kleene ordinal even though no such sequence is computable. I think that the statement just needs to be reworded. We could be conservative and say: for all α < ε0 given the above fundamental sequences. Or we could be a little more liberal and allow all α < μ for arbitrary μ, but require that all the fundamental sequences be computable.
As a personal aside, this came up because I have been considering the extension of the fast-growing hierarchy to the Church-Kleene ordinal and I am curious if I could show anything about fωCK. For example, is it uncomputable? Cheers, — sligocki (talk) 19:42, 9 December 2009 (UTC)
My comment was concerning "the" fast-growing hierarchy, which I take to be some particular one that presumably appears in published sources (as per WP subject matter). It seems extremely likely that any published source that actually specifies a particular fast-growing hierarchy will have chosen the fundamental sequences to be computable, even though this is not a requirement. E.g., as in Buchholz & Wainer [1987](p. 180), in a section titled "The Fast Growing Hierarchy" (italics are mine):
By 'a fast growing' hierarchy we simply mean a transfinitely extended version of the Grzegorczyk hierarchy i.e. a transfinite sequence of number theoretic functions Fα defined recursively at successor levels and diagonalisation over suitable fixed fundamental sequences at limit levels. [...] We are concerned with the ordinals below ε0 [...] The version of The Fast Growing Hierarchy we shall choose is the following [...]
I think an improved opening paragraph to the present article would be along similar lines:
In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy) is an ordinal-indexed family of rapidly increasing functions fα: NN (where N is the set of natural numbers {0, 1, ...}, and α ranges up to some large countable ordinal). A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε0. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity.
Various adjustments would then be needed in other sections for consistency with this usage of "a" as opposed to "the" hierarchy.
— r.e.s. 15:04, 14 December 2009 (UTC)
Ah, yes. Thank you very much r.e.s.! This has been above and beyond clarified. Cheers, — sligocki (talk) 21:45, 14 December 2009 (UTC)

Does fε0 dominate the Goodstein function?[edit]

The present section "Functions in the hierarchy" states that

fε0(n) is the first function in the hierarchy which dominates the Goodstein function (based on the fundamental sequence chosen in this article).

However, the fundamental sequences in the article are those used by Gallier[1991], according to whom (in his Theorem 12.6) the Goodstein function—let's call it G here— dominates Hε0 in the Hardy hierarchy. Doesn't it then follow that G dominates fε0? (Other authors simply state that G has "approximately" the same growth-rate as fε0, dominating every fα for which α < ε0.) In any case, I'm unaware of a proof that fε0 dominates G -- is there a source for this?
— r.e.s. 14:58, 9 December 2009 (UTC)

--

It's original research on my part, here's my reasoning:

 H_{\epsilon_0}(n) = H_{\omega \uparrow \uparrow n}(n) given our fundamental sequences (using a natural extension of Knuth up-arrow notation to the ordinals)

Likewise, by Cichon's characterization of the Goodstein function (Cichon 1983, see Goodstein function#References)

 \mathcal{G}((2 \uparrow \uparrow n) - 1) = H_{\omega \uparrow \uparrow n}(1) - 1

So,

 H_{\epsilon_0}(n) > \mathcal{G}((2 \uparrow \uparrow n) - 1) > \mathcal{G}(n)

QED

As for the contradiction with Gallier, I don't know what to say. Gallier does not prove that Goodstein majorizes H_epsilon, he only claims it is due to Kirby and Paris. But I see no mention of the Hardy hierarchy in Kirby and Paris... I haven't been able to get ahold of the Buchholz and Wainer paper which Gallier also cites. Cheers, — sligocki (talk) 20:07, 9 December 2009 (UTC)

Actually, I found another problem with Gallier recently. He claims that Girard proved that there is an ordinal such that slow-growing and fast-growing hierarchies meet and that ordinal is the Howard ordinal (Theorem 12.4). He says that Cichon and Wainer (1983) provide an alternative proof. They do not, they show that g_\alpha reaches f_{\epsilon_0} when α is the Howard ordinal. This is very different! I have tried to read Girard to find out the original statement, but his monogram is long, technical and difficult and I haven't been able to come up with anything. However, Cichon and Wainer actually prove their statement while Gallier only claims it. This leads me to wonder what else in Gallier is suspect. Cheers, — sligocki (talk) 20:28, 9 December 2009 (UTC)

--

Very nice — thanks for resolving this issue. Now that I know what to look for, I can see that your results are implicit in the paper by Caicedo ("Goodstein's function") cited at Goodstein's theorem#References, which restates some of Cichon's work and gives all the necessary relationships among the two different versions of the Goodstein function, the fast-growing hierarchy, and the Hardy hierarchy. As you've pointed out elsewhere, this H version of the Hardy hierarchy is not quite the same as the h version, due to using very slightly different fundamental sequences; but this makes no difference in the results, since both Hε0 and hε0 (and hence fε0) dominate both versions of the Goodstein function.
— r.e.s. 06:44, 10 December 2009 (UTC)

Relation with the Grzegorczyk Hierarchy[edit]

At level 1, the proposed function does not "coincide with [that] of the Grzegorczyk hierarchy": \lambda x.2x vs. \lambda x.x^2+2, the problem being that you cannot generate \mathcal{E}^2 from \lambda x.2x. Löb and Wainer (1970) or Wainer (1972) have some specific definitions for the functions at level 0 or 1 in order to fix this, e.g. F_1(x)=(x+1)^2 in Wainer (1972).

Sylvain Schmitz (talk) 18:50, 18 May 2010 (UTC)

Part of the problem is that the term "Grzegorczyk hierarchy" is used in two distinct ways in the literature. Historically, it refers to the hierarchy of *sets* of functions described in the article on the Grzegorczyk hierarchy; however, more-recent literature also uses the same term in reference to the finite-index (α < ω) initial segment of the fast-growing hierarchy. I've edited the article in an attempt to clarify this, but still haven't found a convenient and clear terminology to distinguish these. ("Grzegorczyk hierarchy of indexed sets of functions" and "Grzegorczyk hierarchy of indexed functions" seems awkward.)
r.e.s. (talk) 16:17, 19 May 2010 (UTC)

Relationship to the Hardy hierarchy[edit]

In the Points of Interest section, the article had stated

The Wainer hierarchy of functions fα is related to the Hardy hierarchy of functions hα by the relation fα(n) = hωα(n). Hence, fε0 = hε0. (Gallier 1991)

I've corrected this to reflect that the equality relation holds only for α < ε0, and that although fε0hε0, nevertheless there is the result stated in Gallier:
At α = ε0, the Hardy hierarchy "catches up" to the Wainer hierarchy, in the sense that fε0(n-1) ≤ hε0(n) ≤ fε0(n+1).
r.e.s. (talk) 15:24, 4 June 2010 (UTC)