Slow-growing hierarchy: Difference between revisions
→Definition: hide section in wikilink |
m →References: Various citation cleanup (identifiers mostly) using AWB |
||
Line 27: | Line 27: | ||
== References == |
== References == |
||
*{{Citation | last1=Girard | first1=Jean-Yves | author1-link=Jean-Yves Girard | title=Π<sup>1</sup><sub>2</sub>-logic. I. Dilators | doi=10.1016/0003-4843(81)90016-4 | |
*{{Citation | last1=Girard | first1=Jean-Yves | author1-link=Jean-Yves Girard | title=Π<sup>1</sup><sub>2</sub>-logic. I. Dilators | doi=10.1016/0003-4843(81)90016-4 | mr=656793 | year=1981 | journal=Annals of Mathematical Logic | issn=0003-4843 | volume=21 | issue=2 | pages=75–219}} |
||
⚫ | |||
*{{cite journal |jstor=2274873}} |
|||
⚫ | |||
⚫ | *{{citation|mr=1129778|last= Gallier|first= Jean H.|title= What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory|journal= Ann. Pure Appl. Logic|volume= 53 |year=1991|issue= 3|pages= 199–260|url=http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387|doi=10.1016/0168-0072(91)90022-E}} PDF's: [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal1.pdf part 1] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal2.pdf 2] [ftp://ftp.cis.upenn.edu/pub/papers/gallier/kruskal3.pdf 3]. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".) |
||
* {{cite journal |last=Weiermann |first=A. |year=1995 |title= |journal=Archives of Mathematical Logic |volume= 34 |pages=5 |pages=313-330 |doi= }} |
|||
* Wainer, S.S (1989), "[http://www.jstor.org/stable/2274873 Slow Growing Versus Fast Growing]". ''[[Journal of Symbolic Logic]]'' '''54'''(2): 608-614. |
|||
* {{cite journal |doi=10.1016/S0168-0072(97)00033-X}} |
|||
⚫ | * Weiermann, A. (1999), [http://books.google.com/books?id=2IHm3RT2bBoC&lpg=PP1&pg=PA403#v=onepage&q=&f=false "What makes a (pointwise) subrecursive hierarchy slow growing?"] Cooper, S. Barry (ed.) et al., Sets and proofs. Invited papers from the Logic colloquium '97, European meeting of the Association for Symbolic Logic, Leeds, UK, July 6–13, 1997. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 258; 403-423. |
||
⚫ | *{{citation| |
||
* Weiermann, A. (1995),"Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones." ''Arch. Math. Logic'' 34 (5): 313-330. |
|||
* Weiermann, A. (1997), "Sometimes slow growing is fast growing." ''Ann. Pure Appl. Logic'' '''90''' (1-3): 91-99. {{doi|10.1016/S0168-0072(97)00033-X}} |
|||
⚫ | * Weiermann, A. (1999), [http://books.google.com/books?id=2IHm3RT2bBoC&lpg=PP1&pg=PA403#v=onepage&q=&f=false "What makes a (pointwise) subrecursive hierarchy slow growing?"] Cooper, S. Barry (ed.) et al., Sets and proofs. Invited papers from the Logic colloquium '97, European meeting of the Association for Symbolic Logic, Leeds, UK, July |
||
[[Category:Computability theory]] |
[[Category:Computability theory]] |
Revision as of 03:01, 2 September 2011
In computability theory, computational complexity theory and proof theory, the slow-growing hierarchy is an ordinal-indexed family of slowly increasing functions gα: N → N (where N is the set of natural numbers, {0, 1, ...}). It contrasts with the fast-growing hierarchy.
Definition
Let μ be a large countable ordinal such that a fundamental sequence is assigned to every limit ordinal less than μ. The slow-growing hierarchy of functions gα: N → N, for α < μ, is then defined as follows:
- if α is a limit ordinal.
Here α[n] denotes the nth element of the fundamental sequence assigned to the limit ordinal α.
The article on the Fast-growing hierarchy describes a standardized choice for fundamental sequence for all α < ε0.
Relation to fast-growing hierarchy
The slow-growing hierarchy grows much more slowly than the fast-growing hierarchy. Even gε0 is only equivalent to f3 and gα only attains the growth of fε0 (the first function that Peano arithmetic cannot prove total in the hierarchy) when α is the Bachmann–Howard ordinal. (Girard 1981) and (Cichon and Wainer 1983)
However, Girard (1981) proved that the slow-growing hierarchy eventually catches up with the fast-growing one. Specifically, that there exists an ordinal α and integers a, b such that
- gα(n) < fα(n) < gα(n + 1)
where fα are the functions in the fast-growing hierarchy. He further showed that the first α this holds for is the ordinal of the theory ID<ω of arbitrary finite iterations of an inductive definition. (Wainer 1989). However for the Cichon assignment of fundamental sequences the first match up occurs at the level ε0 (Weiermann 1997).
Extensions of the result proved in Wainer 1989 to considerably larger ordinals show that there are very few ordinals below the ordinal of transfinitely iterated -comprehension where the slow and fast growing hierarchy match up (Weiermann 1995).
For the novice it is worth mentioning that the slow growing hierarchy depends extremely sensitive on the choice of the underlying fundamental sequences (Weiermann 1997 and Weiermann 1999).
Relation to term rewriting
Cichon provided an interesting connection between the slow growing hierarchy and derivation length for term rewriting (Cichon 1990).
References
- Girard, Jean-Yves (1981), "Π12-logic. I. Dilators", Annals of Mathematical Logic, 21 (2): 75–219, doi:10.1016/0003-4843(81)90016-4, ISSN 0003-4843, MR 0656793
- Cichon, E. A.; Wainer, S. S. (1983), "The slow-growing and the Grzegorczyk hierarchies", The Journal of Symbolic Logic, 48 (2): 399–408, doi:10.2307/2273557, ISSN 0022-4812, MR 0704094
- . JSTOR 2274873.
{{cite journal}}
: Cite journal requires|journal=
(help); Missing or empty|title=
(help) - Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ0? A survey of some results in proof theory", Ann. Pure Appl. Logic, 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR 1129778 PDF's: part 1 2 3. (In particular part 3, Section 12, pp. 59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)
- Weiermann, A. (1995). Archives of Mathematical Logic. 34: 313–330.
{{cite journal}}
: Missing or empty|title=
(help) - . doi:10.1016/S0168-0072(97)00033-X.
{{cite journal}}
: Cite journal requires|journal=
(help); Missing or empty|title=
(help) - Weiermann, A. (1999), "What makes a (pointwise) subrecursive hierarchy slow growing?" Cooper, S. Barry (ed.) et al., Sets and proofs. Invited papers from the Logic colloquium '97, European meeting of the Association for Symbolic Logic, Leeds, UK, July 6–13, 1997. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 258; 403-423.