緩成長階層のソースを表示

'''緩成長階層'''（かんせいちょうかいそう、英:slow-growing hierarchy）は[[順序数]]<math>\alpha</math>に対し関数<math>g_a:N \rightarrow N</math>（<math>N</math>は[[自然数]]）を定義する階層である。名前の通り、[[急成長階層|急増加階層]]や[[ハーディ階層|ハーディー階層]]よりも遅く成長する。<ref>{{Cite web|和書|title=緩増加関数 |url=https://googology.fandom.com/ja/wiki/%E7%B7%A9%E5%A2%97%E5%8A%A0%E9%96%A2%E6%95%B0 |website=巨大数研究 Wiki |accessdate=2022-03-09 |language=ja}}</ref><ref>{{Cite journal|last=Weiermann|first=Andreas|date=1997-12-15|title=Sometimes slow growing is fast growing|url=https://www.sciencedirect.com/science/article/pii/S016800729700033X|journal=Annals of Pure and Applied Logic|volume=90|issue=1|pages=91–99|language=en|doi=10.1016/S0168-0072(97)00033-X|issn=0168-0072}}</ref>

== 定義 ==
<math>g_0(n)=0</math>

<math>g_{\alpha+1}(n)=g_{\alpha}(n)+1</math>

<math>g_{\alpha}(n)=g_{\alpha[n]}(n)</math>（<math>\alpha</math>が[[極限順序数]]のとき、<math>\alpha[n]</math>は<math>\alpha</math>の<math>n</math>番目の[[順序数]]）

<!--
== 他の表記との比較 ==
<math>g_0(n)=0</math>

<math>g_1(n)=1</math>

<math>g_m(n)=m</math>

<math>g_\omega(n)=n</math>

<math>g_{\omega+1}(n)=n+1=f_0(n)</math>

<math>g_{\omega+m}(n)=n+m</math>

<math>g_{\omega2}(n)=2n=f_1(n)</math>

<math>g_{\omega m}(n)=mn</math>

<math>g_{\omega^2}(n)=n^2\approx f_2(n)</math>

<math>g_{\omega^m}(n)=n^m</math>

<math>g_{\omega^\omega}(n)=n^n</math>

<math>g_{\omega^{\omega^\omega}}(n)=n^{n^n}</math>

<math>g_{\epsilon_0}(n)=n\uparrow\uparrow n\approx f_3(n)</math>

<math>g_{\epsilon_1}(n)\approx n\uparrow\uparrow(2n)</math>

<math>g_{\epsilon_2}(n)\approx n\uparrow\uparrow(3n)</math>

<math>g_{\epsilon_\omega}(n)\approx n\uparrow\uparrow(n^2)</math>

<math>g_{\epsilon_{\omega2}}(n)\approx n\uparrow\uparrow(2\cdot n^2)</math>

<math>g_{\epsilon_{\omega^2}}(n)\approx n\uparrow\uparrow(n^3)</math>

<math>g_{\epsilon_{\omega^\omega}}(n)\approx n\uparrow\uparrow(n^n)</math>

<math>g_{\epsilon_{\omega^{\omega^\omega}}}(n)\approx n\uparrow\uparrow(n^{n^n})</math>

<math>g_{\epsilon_{\epsilon_0}}(n)\approx n\uparrow\uparrow n\uparrow\uparrow n</math>

<math>g_{\zeta_0}(n)\approx n\uparrow\uparrow\uparrow n\approx f_4(n)</math>

<math>g_{\zeta_1}(n)\approx n\uparrow\uparrow\uparrow(2n)</math>

<math>g_{\zeta_\omega}(n)\approx n\uparrow\uparrow\uparrow(n^2)</math>

<math>g_{\zeta_{\omega^2}}(n)\approx n\uparrow\uparrow\uparrow(n^3)</math>

<math>g_{\zeta_{\omega^\omega}}(n)\approx n\uparrow\uparrow\uparrow(n^n)</math>

<math>g_{\varphi(3,0)}(n)\approx n\uparrow^4 n\approx f_5(n)</math>

<math>g_{\varphi(4,0)}(n)\approx n\uparrow^5 n\approx f_6(n)</math>

<math>g_{\varphi(\omega,0)}(n)\approx n\uparrow^n n\approx f_\omega(n)</math>
-->

== 出典 ==

* {{Cite journal|last=Gallier|first=Jean H.|year=1991|title=What's so special about Kruskal's theorem and the ordinal Γ<sub>0</sub>? A survey of some results in proof theory|url=http://stinet.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA290387|journal=Ann. Pure Appl. Logic|volume=53|issue=3|pages=199–260|doi=10.1016/0168-0072(91)90022-E|mr=1129778|authorlink=Jean Gallier|doi-access=free}} 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.&nbsp;59–64, "A Glimpse at Hierarchies of Fast and Slow Growing Functions".)

== 脚注 ==
<references />
{{Normdaten}}
{{Mathlogic-stub}}
{{DEFAULTSORT:かんせいちょうかいそう}}
[[Category:計算可能性理論]]
[[Category:数理論理学的階層]]
[[Category:証明論]]
[[Category:数学に関する記事]]