[목차] == 개요 == [[큰 수]]들의 크기를 비교할 때 쓰이는 계층구조. FGH는 커지면 커질수록 뭔가가 더 붙는 다른 큰 수 함수들과는 다르게 간결하고 매우 강력하여 큰 수들을 비교할때 요긴하게 쓰인다. == 정의 및 설명 == 1. [math( f_0(n) = n+1 )] 1. [[서수(수학)|서수]] [math( \alpha )]에 대해 [math( f_{\alpha +1}(n) = f_{\alpha}^n (n) )] 1. [math( \alpha )]가 극서수라면 [math( f_{\alpha}(n) = f_{\alpha [n]}(n) )] 이해를 돕기 위해서 정의를 풀어서 다시 쓰면 다음과 같다. 1. 서수 0에 해당하는 함수는 '다음 수'라는 연산이다. 1. 서수가 다른 서수 [math(\alpha)]의 다음 서수인 경우, [math(\alpha)]에 대응하는 함수를 [math(n)]번 합성한다. 1. 서수가 더 작은 서수들의 극한서수인 경우, 그 서수를 정의하는 더 작은 서수들의 수열(fundamental sequence)에서 [math(n)]번째 서수를 대입한다. 각 단계는 하나의 함수를 가리킨다. 정의 (2)에 의해서 같은 단계의 함수에 더 큰 수를 집어넣는 것보다 단계를 높이는 것이 결과값을 훨씬 크게 만든다. 서수가 조금만 커져도 우주 원자 수 정도는 가뿐히 넘는다. 대신 1, 2를 대입한다면 매우 큰 가산서수를 가져와도 값이 3을 넘지 못하는 경우가 있기 때문에 높은 단계의 크기를 체감하고 싶을 때에는 보통 [math(n)]에 3을 대입하는 경우가 많다. == 계산 예시 == 정의에 의해 서수 0에 해당하는 함수는 '다음 수'라는 연산이다. [math( f_0(n) = n+1,\ f_0(100)=101 )] 서수 1에 해당하는 함수는 '다음 수'를 [math(n)]번 반복한 것이므로 [math( n+n=2n )]이다. [math( f_1(n) = 2n,\ f_1(100)=200 )] 서수 2에 해당하는 함수는 2배하기를 [math(n)]번 반복하는 것이므로[* [math(n)]을 [math(n)]번 더하는게 아니라 '자기 자신을 더하는 것'을 [math(n)]번 반복하는 것임에 유의해야 한다.] [math(2 \times 2 \times ... \times 2 \times n = n \times 2^n)]이다. [math(f_2(n) = n \times 2^n,\ f_2(100)=100 \times 2^{100} \sim 1.267)]구 서수 3에 해당하는 함수는 [math( n \times 2^n, (n \times 2^n) \times 2^{(n \times 2^n)}, ... )] 이런식으로 [math(n)]번 합성하는 것이다.[* 예를 들어 [math(f_3(3))]은 [math((3×2^3)×2^{(3×2^3)})×2^{((3×2^3)×2^{(3×2^3)})}))]과 같고 이는 [math(24×2^{24}×2^{24×2^{24}})] 이므로 약 [math(6.89×10^{121210694})]이다.]줄임표를 사용하지 않고 정확하게 나타내기는 힘들고 근삿값은 [math( (2^n)^{(2^n)^{...^{(2^n)}}} )]으로 [math( 2^n \uparrow \uparrow n )]과 같다. [math( \uparrow \uparrow )]의 의미는 [[커누스 윗화살표 표기법]] 참고. 서수 4에 해당하는 함수는 위의 함수를 [math( n )]번 합성한 것이므로 근삿값으로 [math( 2 \uparrow \uparrow 2 \uparrow \uparrow.. \uparrow \uparrow n )]이고 이것은 [math( 2 \uparrow \uparrow \uparrow n)]보다 크다. 서수 5에 해당하는 함수는 위의 함수를 [math(n)]번 합성한 것이므로 근삿값으로 [math(2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow 2 \uparrow \uparrow \uparrow ... \uparrow \uparrow \uparrow n)]이고 이것은 [math(2 \uparrow \uparrow \uparrow \uparrow n)]보다 크다. 즉 유한 서수 [math(a+1)]에 대한 함수는 대략 크누스의 윗 화살표 표기법으로 화살표가 [math(a)]개 있는 것과 비슷하다. (화살표 앞뒤에 붙는 수의 크기는 2 이상이기만 하면 크게 중요하지 않다.) 그러면 윗화살표 표기법만 가지고 모든 단계를 근사할 수 있을까? 아니다. 아직 정의 (3)은 쓰지도 않았다. 여기서 가장 작은 극서수인 [math(\omega)]가 등장한다. 서수 [math(\omega)]에 해당하는 함수는 정의(3)에 의해 [math(\omega)]에 n을 대입해서 n단계 함수가 된다. [math(\omega)]의 fundamental sequence의 [math(n)]번째 항은 [math(n)]이기 때문이다. 즉 [math(f_{\omega}(100)=f_{100}(100))]이다. 서수 [math(\omega+1)] 에 해당하는 함수 [math(f_{\omega+1}(n))]은 절대 [math(f_{n+1}(n))]가 '''아니다'''. [math(\omega+1)]은 극서수가 아니기 때문에 정의 (2)에 의하여 [math(f_{\omega+1}(n))]은 [math(f_{\omega}(n))]를 [math(n)]번 중첩하는 것인데, [math(f_{100}(100))]을 계산해서 나오는 엄청 큰 수를 [math(A)]라고 하면 서수 [math(A)]에 해당하는 함수인 [math(f_A(A))]를 계산해야 하고 그 결과를 또 단계에 넣고 하는 것을 100번 반복해야 [math(f_{\omega+1}(100))]이 나온다. [math(f_{\omega2}(n))]는 [math(\omega2)]가 서수의 수열 [math(\omega+1, \omega+2, \cdots)]로 정의되기 때문에, 정의 (3)에 의해 [math(f_{\omega+n}(n))]와 같다.[* [math(2 \times \omega)]라고 쓰면 안된다. 서수 연산에서는 교환법칙이 성립하지 않아서, [math( 2 \times \omega)]와 [math( \omega)]가 같다.] 이를 반복하면 [math(f_{\omega (m+1)}(n))]는 [math(f_{\omega m+n})]가 된다. [math(f_{\omega^2}(n))]는 같은 원리로 정의 (3)을 사용하여 [math(f_{\omega n}(n))]가 되고, [math(f_{\omega^\omega}(n))]는 [math(f_{\omega^n}(n))]이 된다. 이제 몇몇 큰 수들을 이 표기법으로 어떻게 나타낼 수 있는지 알아보자. [[구골]]의 경우, 약간의 계산을 거치면 [math(f_{2}(323)=323\times2^{323}\lt10^{100}\lt324\times2^{324}=f_{2}(324))]임을 알 수 있다. 하지만 서수 3에 대한 함수로는 [math(f_{3}(2)=2048\lt10^{100}\lt f_{3}(3))]이 되어, 비교하는 의미가 없어진다. [[스큐스 수]]의 경우, 대략 [math(f_3(4)\lt e^{e^{e^{79}}}\lt f_3(5)\lt f_4(2))]이다. [[그레이엄 수]]의 경우, 윗 화살표가 [math(g_{63})]개이므로 유한 서수로 나타내기에는 너무 크다. 대신, [math(g_{1}=3\uparrow\uparrow\uparrow\uparrow3\lt f_{64}(64))]에서 시작하여 [math(g_{2}\lt f_{f_{64}(64)}(f_{64}(64)))]를 보이고, 이 과정을 64번 반복하면 [math(g_{64}\lt f_{\omega+1}(64))]인 것을 알 수 있다.[* 더 정확히는 [math(f^{63}_{\omega}(4))]로 근사할 수 있다.] 이처럼 큰 수들은 그 크기에 "대응"하는 서수를 가지는 경우가 많기 때문에, 큰 수들의 크기를 편리하게 비교할 수 있다. == 큰 수의 서열 == * 서수 2에 대응: [math(f_2(3)=24)]에서 [math(f_3(3)\approx2^{402000000})]까지. * 서수 3에 대응: [math(f_3(3))]에서 [math(f_4(3))]까지. [[테트레이션]]으로 쉽게 나타낼 수 있는 수들이 여기 대응된다. * [math(\omega)]에 대응: 아커만 함수, [[커누스 윗화살표 표기법]] * [math(\omega+1)]: [[모우저]], [[그레이엄 수]] * [math(\omega2)]: [[BEAF]]에서 {a,b,n,2} * [math(\omega^2)]: [[콘웨이 연쇄 화살표 표기법]] * [math(\omega^2+1)]: [[피쉬 수|피쉬 수1]] * [math(\omega^{\omega^{\omega}})]: [[BEAF]]에서 {a,b\(0,1\)2} * [math(\epsilon_0)]: [[굿스타인 정리|굿스타인 함수]] * [math(\psi(\Omega^{\Omega^\omega}))]([[서수(수학)/큰 가산서수 #s-5|작은 베블런 서수]]): 약한 tree 수열의 값 [* 정작 유명한 TREE(3)은 정확한 크기가 측정되지 않았다.] == FGH의 단계 == === 오메가 이전 단계 === * [math(f_{0}(n) = n+1)] * [math(f_{1}(n) = n+n = 2n)] * [math(f_{2}(n) = f{_{1}^{n}}(n) = 2(2(...2(2n))) = 2^{n}n>2 \uparrow n = 2^{n})] * [math(f_{3}(n) \approx 2^{n} \uparrow \uparrow n > 2 \uparrow \uparrow n)] * [math(f_{4}(n) \approx f_{3}(n) \uparrow\uparrow\uparrow n \geq (2^{n} \uparrow \uparrow n) \uparrow\uparrow\uparrow n)] * [math(f_{m}(n) \approx f_{m-1}(n) \uparrow^{m-1} n \geq ((...(2\uparrow n)\uparrow^2n)\uparrow^3n)...)\uparrow^{m-1} n)] [* 여기서 [math(\uparrow^{m-1})]은 윗방향 화살표가 [math(m-1)]개 있다는 뜻이다.] === 오메가 단계 1(선형~다항식 단계) === *[math(f_{ω}(n)\approx f_{n-1}(n) \uparrow^{n-1} n \geq ((...(2\uparrow n)\uparrow^2n)\uparrow^3n)...)\uparrow^{n-1} n)] *[math(f_{ω+1}(n)=\underbrace {f_{ω}(f_{ω}(f_{ω}(...f_{ω}(n)...)))}_{n})] *[math(f_{ω+a+1}(n)=\underbrace {f_{ω+a}(f_{ω+a}(f_{ω+a}(...f_{ω+a}(n)...)))}_{n})] *[math(f_{ω2}(n)=f_{ω+ω}(n)=f_{ω+n}(n))] *[math(f_{ω3}(n)=f_{ω2+ω}(n)=f_{ω2+n}(n)=\underbrace {f_{ω2+n-1}(f_{ω2+n-1}(f_{ω2+n-1}(...f_{ω2+n-1}(n)...)))}_{n})] === 오메가 단계 2(지수화 단계 이상) === *[math(f_{ω^2}(n)=f_{ωω}(n)=f_{ωn}(n)=f_{ω(n-1)+ω}(n))] *[math(f_{ω^3}(n)=f_{ω^2×ω}(n)=f_{ω^2×n}(n)=f_{ω^2×(n-1)+ω^2}(n))] *[math(f_{ω^ω}(n)=f_{ω^n}(n)=f_{ω^{n-1}×ω}(n)=f_{ω^{n-1}×n}(n)=f_{ω^{n-1}×(n-1)+ω^{n-1}}(n))] *[math(f_{ω^{ω+1}}(n)=f_{ω^ω×ω}(n)=f_{ω^ω×n}(n)=f_{ω^ω×(n-1)+ω^ω}(n))] *[math(f_{ω^{ω2}}(n)=f_{ω^{ω+ω}}(n)=f_{ω^{ω+n}}(n)=f_{ω^{ω+(n-1)}×ω}(n)=f_{ω^{ω+(n-1)}×n}(n)=f_{ω^{ω+(n-1)}×(n-1)+ω^{ω+(n-1)}}(n))] *[math(f_{ω^{ω^2}}(n)=f_{ω^{ωω}}(n)=f_{ω^{ωn}}(n)=f_{ω^{ω(n-1)+ω}}(n))] *[math(f_{ω^{ω^ω}}(n)=f_{ω^{ω^n}}(n)=f_{ω^{ω^{n-1}×ω}}(n))] === 엡실론 단계 === [math(\epsilon_0)]은 [math(\{1,ω,ω^ω,ω^{ω^ω},\cdots\})]의 극서수이고, [math(\epsilon_{a+1})]은 [math(\{\epsilon_a+1,ω^{\epsilon_a+1},ω^{ω^{\epsilon_a+1}},\cdots\})]의 극서수이다. *[math(f_{\epsilon_0}(n)=f_{ω↑↑(n-1)}(n))] *[math(f_{\epsilon_{a+1}}(n)=f_{ω^{ω^{\cdot^{\cdot^{\cdot^{\epsilon_a+1}}}}}}(n))] ([math(ω)]가 [math(n-1)]개)[* [math(\epsilon_a)]다음에 나오는 [math(+1)]의 위치에 유의한다.] === 제타-에타 단계 === *[math(f_{\zeta_0}(n)=f_{\epsilon_{\epsilon_{._{._{._{\epsilon_0}}}}}}(n))] ([math(\epsilon)]가 [math(n-1)]개) *[math(f_{\zeta_{a+1}}(n)=f_{\epsilon_{\epsilon_{._{._{._{\zeta_a+1}}}}}}(n))] ([math(\epsilon)]가 [math(n-1)]개) *[math(f_{\eta_0}(n)=f_{\zeta_{\zeta_{._{._{._{\zeta_0}}}}}}(n)=f_{\zeta_{\eta_0}}(n))] ([math(\zeta)]가 [math(n-1)]개) *[math(f_{\eta_{a+1}}(n)=f_{\zeta_{\zeta_{._{._{._{\eta_a+1}}}}}}(n))] ([math(\zeta)]가 [math(n-1)]개) === 베블런 함수 단계 === 그리스 문자는 무한하지 않기 때문에, 다음 단계로 나아가기 위해 앞의 극서수들을 일반화한 베블런 함수 [math(\varphi(n))]을 사용한다. 1. [math(\varphi_0(a)=\omega^a )] 2. 서수 [math(\alpha)]에 대해, [math(\varphi_\alpha(0)[n]=\varphi^n_{\alpha-1}(0))] 3. [math(\varphi_\alpha(m)[n]=\varphi^n_{\alpha-1}(\varphi_\alpha(m-1)+1))] 4. [math(\alpha)]가 극서수라면, [math(\varphi_\alpha(0)[n]=\varphi_n(0))] 5. [math(\varphi_\alpha(m)[n]=\varphi_n(\varphi_\alpha(m-1)+1))] ==== 일변수 파이 단계 ==== *[math(f_{\varphi_0(a)}(n)=f_{\omega^a}(n))] *[math(f_{\varphi_1(a)}(n)=f_{\epsilon_a}(n))] *[math(f_{\varphi_2(a)}(n)=f_{\zeta_a}(n))] *[math(f_{\varphi_3(a)}(n)=f_{\eta_a}(n))] *[math(f_{\varphi_4(0)}(n)=f_{\eta_{\eta_{._{._{._{\eta_0}}}}}}(n))] ([math(\eta)]가 [math(n-1)]개) *[math(f_{\varphi_{\alpha+1}(0)}(n)=f_{\varphi_{\alpha}(\varphi_{\alpha}(...\varphi_{\alpha}(0)...))}(n))] ([math(\varphi_\alpha)]가 [math(n-1)]개) *[math(f_{\varphi_{\alpha+1}(\beta+1)}(n)=f_{\varphi_{\alpha}(\varphi_{\alpha}(...\varphi_{\alpha+1}(\beta)...))}(n))] ([math(\varphi_\alpha)]가 [math(n-1)]개) *[math(f_{\varphi_{\alpha}(\beta)}(n)=f_{\varphi(\alpha,\beta)}(n))] ==== 감마 단계 ==== *[math(f_{\Gamma_0}(n)=f_{\varphi(1,0,0)}=f_{\varphi_{\varphi_{\varphi_{...\varphi_{0}(0)...}(0)}(0)}(0)}(n))] ([math(\varphi)]가 [math(n-1)]개) [math(=f_{\varphi(\varphi(\varphi(...\varphi(0,0)...,0),0),0)})]) ([math(\varphi)]가 [math(n-1)]개) ==== 다변수 파이 단계 ==== *[math(f_{\varphi(a,b,c...d,e+1)}(n)=f_{\varphi(a,b,c...d-1,\varphi(a,b,c...d-1,\varphi(a,b,c...d-1,\varphi(a,b,c...d,e)...))}(n))] ([math(\varphi)]가 [math(n-1)]개) *[math(f_{\varphi(a,b,c...d+1,0,0,0...0)}(n)=f_{\varphi(a,b,c...d,\varphi(a,b,c...d,\varphi(a,b,c...d,...\varphi(a,b,c...d,0,0,0...0)...)0,0...0)0,0...0)}(n))] ([math(\varphi)]가 [math(n-1)]개) *[math(f_{\varphi(0,0,0....0,a,b,0,c)}(n)=f_{\varphi(a,b,0,c)}(n))] *[math(\varphi(1,0,0,0))]을 아커만 서수라고 하고, [math(\varphi(\underbrace{1,0,0,...,0,0)}_\omega)]를 작은 베블런 서수라고 한다. === 서수 붕괴 함수 단계 === 이 문서에서는 서수 붕괴 함수가 어떻게 커지는지만 중점적으로 다룬다. 자세한 원리는 [[서수(수학)/큰 가산서수]] 문서의 [[서수(수학)/큰 가산서수 #s-5|5번째 문단]] 참고. ==== 바흐만의 프사이 함수 단계 1 ==== *[math(f_{\psi(0)}(n)=f_{\epsilon_0}(n))] *[math(f_{\psi(1)}(n)=f_{\epsilon_1}(n))] *[math(f_{\psi(\omega)}(n)=f_{\epsilon_\omega}(n))] *[math(f_{\psi(\Omega)}(n)=f_{\zeta_0}(n))] *[math(f_{\psi(\Omega+1)}(n)=f_{\epsilon_{\zeta_0+1}}(n))] *[math(f_{\psi(\Omega+a)}(n)=f_{\epsilon_{\zeta_0+a}}(n))] *[math(f_{\psi(\Omega2)}(n)=f_{\psi(\Omega+\Omega)}(n)=f_{\zeta_1}(n))] *[math(f_{\psi(\Omega3)}(n)=f_{\zeta_2}(n))] *[math(f_{\psi(\Omega^2)}(n)=f_{\psi(\Omega×\Omega)}(n)=f_{\eta_0}(n)=f_{\varphi_3(0)}(n))] *[math(f_{\psi({\Omega^2}2)}(n)=f_{\psi(\Omega^2 +\Omega^2)}=f_{\eta_1}(n))] *[math(f_{\psi(\Omega^3)}=f_{\varphi_4(0)}(n))] *[math(f_{\psi(\Omega^\omega)}(n)=f_{\varphi_\omega(0)}(n)=f_{\varphi(\omega,0)}(n))] *[math(f_{\psi(\Omega^\Omega)}(n)=f_{\varphi(1,0,0)}(n)=f_{\Gamma_0}(n))] *[math(f_{\psi(\Omega^{\Omega^2})}(n)=f_{\varphi(1,0,0,0)}(n))] *[math(f_{\psi(\Omega^{\Omega^\omega})}(n)=f_{\varphi(1,\underbrace{0,0,...,0,0)}_\omega}(n))] 더 나아가 *[math(f_{\psi(\Omega^{\Omega^\Omega})}(n))] 를 생각 할 수 있고, 이 밑첨자를 큰 베블런 서수(Large Veblen Ordinal)라고 한다. ==== 바흐만의 프사이 함수 단계 2 ==== *[math(f_{\psi_1(0)}(n)=f_{\psi(\epsilon_{\Omega+1})}(n)=f_{\psi(\Omega^{\Omega^{\Omega^{^{.^{.^.}}}}})}(n))] *[math(f_{\psi_1(1)}(n)=f_{\psi(\epsilon_{\Omega+2})}(n))] *[math(f_{\psi_1(\Omega)}(n)=f_{\psi(\zeta_{\Omega+1})}(n))] *[math(f_{\psi_1(\Omega^2)}(n)=f_{\psi(\eta_{\Omega+1})}(n))] *[math(f_{\psi_1(\Omega^{\Omega})}(n)=f_{\psi(\Gamma_{\Omega+1})}(n))] *[math(f_{\psi_2(0)}(n)=f_{\psi_1({\epsilon_{\Omega+1}})}(n)=f_{\psi_1(\Omega^{\Omega^{\Omega^{^{.^{.^.}}}}})}(n))] *[math(f_{\psi_{\psi(0)}(0)}(n)=f_{\psi_{\epsilon_0}(0)}(n)=f_{\psi_{\omega^{\omega^{\omega^{.^{.^.}}}}}(0)}(n))] *[math(f_{\psi_{\psi_1(0)}(0)}(n)=f_{\psi_{\psi(\epsilon_{\Omega+1})}(0)}(n)=f_{\psi_{\psi(\Omega^{\Omega^{.^{.^.}}})}(0)}(n))] *[math(f_{\psi_{\psi_{\psi(0)}(0)}(0)}(n)=f_{\psi_{\psi_{\epsilon_0}(0)}(0)}(n))] == 왜 3이 기준인가? == [math(\Gamma_0)]에 대해, [math(f_{\Gamma_0}(2))]를 구해보자. 이 서수는 [math(\{1, \varphi_1(0), \varphi_{ \varphi_1(0)}(0), \varphi_{ \varphi_{ \varphi_1(0)}(0)}(0), \cdots\})]의 극서수이므로 이것은 [math(f_{\varphi_1(0)}(2)=f_{\epsilon_0}(2))]과 같다. [math(\epsilon_0)]은 [math(\{1, \omega, \omega^\omega, \omega^{\omega^\omega} \cdots\})]의 극서수라서, 이것은 [math(f_{\omega}(2))]와 같고, [math(f_{\omega}(2)=f_{2}(2)=8)]이 된다. 이렇듯 많은 극서수를 정의하는 수열이 1부터 시작하므로, 2 이하의 수는 계산이 너무 쉽게 끝나게 된다. 만약 [math(\Gamma_0+1)]과 같이 극서수가 아니라 따름서수라면 [math(f_{\Gamma_0+1}(2)=f_{\Gamma_0}(f_{\Gamma_0}(2))=f_{\Gamma_0}(8))]처럼 재귀를 통해 값이 3 이상이 되어 그나마 낫다. 나아가서 1을 넣으면 서수가 무엇이든 결과값이 2로 고정된다. fundamental sequence가 1로 시작하는 극서수[* 그렇지 않은 극서수도 있다. 예를 들어 [math(\omega2)]는 [math(\omega+1)]로 시작한다. 그러나 이렇게 따름서수가 되더라도 [math(\omega+1)]에서 [math(+1)]은 사라지고 값은 늘리지 못한채 더 작은 극서수(이 경우에는 [math(\omega)])가 되어 끝내는 1이 된다.]인 [math(\alpha)]에 대해 [math(f_\alpha(1))]를 계산하면 [math(f_1(1)=f_0(1)=2)]가 된다. [math(\alpha)]가 따름서수라도 한번만 재귀하게 되어 [math(f_{\alpha}(1)=f_{\alpha-1}(1))]이므로 재귀를 통해 값을 늘릴 수도 없다. == 관련 항목 == * [[큰 수]] [[분류:큰 수]]