[math(\text{TREE}(3))]의 설명 영상.[1]
1. 개요
[math(\text{TREE}(3))]는 트리 그래프 이론에서 제시된 매우 큰 수로, 수학적으로 의미가 있고 실제 증명에서 사용된 큰 수 중에서 그레이엄 수보다 큰 몇 안되는 수들 중 하나이다.2. 정의
- 각각의 트리 [math(T_i)]은 최대 [math(i)]개의 정점(vertices)를 지닌다.
- 모든 트리 중 어떤 트리도 무한히 보존되지 않으며, 순서대로 트리 뒤에 삽입(embeddable)된 트리에 삽입되는 것을 보존하지 않는다.
- 이때 [math(\text{TREE}(k))]는 어떤 수 [math(k)]를 줄 때, [math(k)]가지의 정점으로 트리를 연속해서 개수가 최대가 되게 그릴 수 있는 트리의 개수이다.
2번 정의의 '보존되지 않는다'라는 의미를 위의 유튜브 영상에서 'Forest is die(숲이 죽는다)'라고 표현했다. 즉, 이전 트리에 포함되는 트리를 그리는 순간 '숲이 죽어버려서' 다시 처음부터 [math(T_1)] , [math(T_2)] ...를 그려야 한다.
2.1. 설명
여기서 "포함"이라는 말이 무엇일까? 앞과 같은 조건에서, 어떤 한 점 A에서 한붓 그리기로 갈 수 있고, A보다 아래에 있는 점을 계승자(successor), 간단하게 후손이라 하고, 반대로 A를 선조라고 하자.위 사진에서는 초록색과 파란색 점이 선조, 붉은색 점이 후손, 즉 계승자이다.
이렇게 트리 A의 붉은색 점의 가장 가까운 선조인 초록색과 파란색 점이 트리 B의 가장 가까운 선조와 겹치므로 트리 A는 B를 포함하고, 수열이 끝난다.
3. TREE(3)
먼저 [math(\text{TREE}(1))]은 1가지의 점으로 그릴 수 있는 트리들의 최대 개수이다. 따라서 [math(\text{TREE}(1) = 1)]이다. 예를 들어 빨간색 점으로 시작한다면 빨간색 점 하나와 그 후손을 그리는 순간 포함이 되기 때문에 더 그릴 수 없고 수열이 끝나게 되어 최대 점의 개수는 1개가 된다.[math(\text{TREE}(2))]는 마찬가지로 2가지의 점으로 그릴 수 있는 트리들의 최대 개수이다. 많이 그릴 수 있다고 생각할 수도 있지만 이전 트리에 포함되면 수열이 끝난다는 규칙 때문에 [math(\text{TREE}(2) = 3)]이다.
여기에서 3번째 점이 2번째 점에 포함된다고 생각할 수도 있지만, 포함되는 관계는 양쪽이 아니라 뒤에서 앞이기 때문에 바로 뒤쪽의 트리만 포함하지 않으면 된다.
[math(\text{TREE}(3))]도 마찬가지로 최대 3가지의 점으로 그릴 수 있는 트리들의 최대 개수이다. 직접 해보면 알겠지만, 조금만 해봐도 정말 많이 그릴 수 있다는 것은 알게 될 것이다.
얼핏 보면 무한히 그릴 수 있는것처럼 보인다. 하지만 [math(\text{TREE(3)})]은 이미 유한함이 증명되었다. [math(\text{TREE(3)})]의 값은 그냥 [math(\text{TREE}(3))]이다.
더 나아가 색이 4개인 [math(\text{TREE}(4))], 5개인 [math(\text{TREE}(5))], [math(\text{TREE}()][math(10^{100})][math())], [math(\text{TREE}()][math(G(64))][math())], [math(\text{TREE}()][math(TREE(3))][math())] 등을 생각해볼 수 있다. 이 수들 각각이 전의 숫자와는 비교가 불가능한 크기를 가지고 있으나, [math(\text{TREE}(3))]만 돼도 충분히 큰 수기 때문에 잘 다뤄지지 않는다.[2]
3.1. 크기
[math(\text{TREE}(3))]는 정말 막대하게 크며, 일반적인 표기법으로는 나타내는 것이 불가능하다. BEAF로 나타내더라도 군단 배열에 쓰이는 & 배열 표기법 이상이 아니면 그레이엄 수보다도 훨씬 더 많은 숫자가 들어간다.다음은 TREE(3)이나 TREE(n) 함수의 여러 근사치이다.
- Reverse mathematics의 표기를 이용해 TREE(n) 함수의 성장률은 [math(\text{ACA}_0+\Pi^1_2+\text{BI})]인 재귀함수보다 빠르게 성장한다. 좀더 정확히 말하자면 프리드먼은 TREE(3)가 [math(\text{ACA}_0+\Pi^1_2+\text{BI})]내에서 21000개 이하의 기호로 정지성을 증명할 수 있는 튜링머신의 정지시간보다 크다는 것을 증명했다. 이는 최소 초월정수와 비슷하며 다만 최소 초월정수는 ZFc 공리계내에서 정지성을 증명할수 있는 모든 함수를 지배하기 때문에 크기는 비교불가이다.
- fgh에서는 TREE(n)은 [math(f_{\psi(\Omega^{\Omega^\omega\omega})}(n))] 혹은 [math(f_{\vartheta(\Omega^\omega\omega)}(n))], [math(f_{\theta(\Omega^\omega\omega)}(n))]으로 표현할 수 있으며 TREE(3)은 [math(f_{\theta(\Omega^\omega\omega)}(3))]이상, 또는 [math(f_{\psi(\Omega^{\Omega^\omega+3})+\psi(\Omega^{\Omega^\omega})}(f_{\psi(\Omega^{\Omega^\omega})}(844424930131957)))] 이라는 비교적 근접한 근삿값으로 표기할 수 있다.[3]
- BEAF 배열의 친척(?)격인 버드의 배열 표기법을 이용해, [math(\text{TREE}[3] > \{3, 6, 3 [1 [1 \neg 1,2] 2] 2\})]이다.
- BEAF로는 {X,X+1,(1)2}&10 또는 {10,10(1)100} & 10 에 근사할 수 있다. 10&10&10[4] 보다 조금(?) 크고, 3&3&3&3[5]보다는 비교도 안되게 훨씬 작다. 3&3&3&3의 크기는 SSCG(3)보다도 커서 얼씬도 못 한다. 굳이 근사하자면 10&10&10에 10 대신 그레이엄 수를 넣으면 된다.
물론 이보다 더 큰 수도 있다. 예를 들면 그 어떤 계산 가능한 함수보다 더 빠르게 증가하는 바쁜 비버 함수나 라요 수, 이를 이용한 피쉬 수 4번과 7번, 그 마저도 초월한 거대수 정원수가 있고, TREE(3)과 비슷한 규칙을 가지지만, 더 큰 성장률을 보이는 SSCG(3) 이나 SCG(13) 같은 서브큐빅 그래프[6] 함수 등이 있다. 이 수들과 TREE(3)을 비교하자면, TREE(3)과 그레이엄 수는 물론 3이랑 비교하는 것 보다 훨씬 작다.
TREE(3)을 8로 나눈 나머지가 3이라는 것이 알려져 있다.
4. 약한 tree 수열
위의 그림에서, 2개 색깔로 만들 수 있는 많은 가능성을 모두 무시하고 4번째 그래프를 정점 1개짜리 그래프로 바꿔도 수열을 길게 이어나갈 수 있다. 물론 추가 정점이 3개면 하한이 1000조도 넘지 못하지만 4개부터는 상상이 안 가는 수준으로 커진다. 이처럼 색깔을 하나만 사용하되, [math(k)]번째 트리의 정점 숫자를 [math(n + k)]개로 제한한 것을 약한 tree 수열(weak tree sequence)이라고 부른다. [math(tree(1) = 2)], [math(tree(2) = 5)]인 것을 약간의 시행착오를 거쳐 알 수 있다. 일단 여기까지는 TREE(n)보다 빠르다. 어차피 3을 넘으면 TREE(n) 쪽이 압도적이지만 함수 안에 수를 1로 한 채 재귀할 때만큼은 약한 tree 수열이 빠르다.[7] [math(tree(3))]은 [math(844424930131960)] 이상이고, [math(tree(4))]부터 그레이엄 수 보다 한참 커진다. 그레이엄 수는 물론, [math(f_{\epsilon_0}(G(64)))]보다도 크다.[8] 그 이후 부터는 [math(f_{\Gamma_0}(n))]이상의 성장률을 보인다.[9]5. 일반화 tree 수열
원래 tree 수열과 약한 tree 수열의 아이디어를 합쳐 색깔을 [math(m)]개 사용하고, [math(k)]번째 트리의 정점 숫자를 [math(n + k)]개로 제한한 일반화 tree 수열(general tree sequence) [math(\text{TREE}(m,n))]을 생각할 수 있다. 늘어나는 속도는 TREE(n)보다 약간(?) 빠르다.5.1. 성질
- [math(\text{TREE}(0,n)=0)] [10]
- [math(\text{TREE}(n,0)=\text{TREE}(n))]
- [math(\text{TREE}(1,n)=\text{tree}(n))]
- [math(\text{TREE}(n,1)=\text{TREE}(n+1,0)-1)]
- 모든 음이 아닌 정수 [math(m,n)]에 대해 [math(\text{TREE}(m+1,n)>\text{TREE}(m,n+1))][11]
[1] 유튜브명은 Numberphile이다. Tony Padilla가 설명한다.[2] [math(\text{TREE}(3))]의 크기가 너무나 크기 때문에 이미 그 단계에서는 아무리 수를 올려도 [math(\text{TREE}(3))]를 얼마나 재귀하던, 심지어 [math(\text{TREE}^{\text{TREE}(3)}(3))]처럼 [math(\text{TREE(3)})]번 재귀, 이 이상 재귀해도 거의 제자리걸음이나 마찬가지기 때문이다.[3] 참고로 그레이엄 수는 [math(f_{ω+1}(64))]보다 작은 수고, 그레이엄 수를 그레이엄 수 번 재귀한 하이퍼 그레이엄도 [math(f_{ω2}(3))], [math(f_{ω+2}(f_{\omega+1}(64)))](이 두 수는 {3,3,3,2}와 비슷하다)보다 작은 수다.[4] {10,3/2}[5] {3,4/2}[6] 트리(그래프)는 단순하지만 서브큐빅 그래프처럼 각각의 트리가 많이 모여서 만들어진 복잡한 그래프는 그 만큼 성장률이 월등해진다.[7] 전자는 아무리 재귀해도 1이지만 후자는 2번만 재귀해도 엄청나게 커진다. 참고로 1번 재귀하면 5이다.[8] 이 정도 성장률은 하이퍼 그레이엄은 당연, BEAF의 선형 배열 ~ 하이퍼 초차원 배열에 있는 모든 수들보다도 훨씬 크다. 피쉬 수 중에서도 초반부는 이 수보다 훨씬 작다.[9] 물론 [math(\text{TREE(3)})]와 비교하면 tree수열은 한참 작아지는데 [math(tree(G(64)))]보다 [math(\text{TREE(3)})]가 비교도 할 수 없을 만큼 훨씬 크다. tree는 성장률이 [math(f_{\theta(\Omega^\omega)}(n))]인지라(단 n이 5를 넘을때부터의 성장률이다.) TREE의 성장률 [math(f_{\theta(\Omega^\omega\omega)}(n))] 보다는 한참 작다. 연구결과에 따르면, [math(\text{TREE(3)})]은 [math(tree_5(7))], 자세하게는 [math(\text{tree}^{\text{tree}^{\text{tree}^{\text{tree}^{\text{tree}^{8}(7)}(7)}(7)}(7)}(7))]보다도 크다고 밝혀졌다.[10] 색깔을 0개 사용하면 n이 어떤 값이어도 트리를 그릴 수 없으므로 자명하다. n의 값이 무한인 등 부정형은 예외.[11] 수학적 귀납법을 적용하면 [math(\text{TREE}(m+n)>\text{TREE}(m,n))]이 되어 일반화 tree 수열이 원래 tree 수열보다 의미있게 월등한 성장률을 보여주지 않는다는 직접적인 증명이 된다.