크러스컬 나무 정리

수학에서 **크러스컬 나무 정리**(Kruskal's tree theorem)는 정렬 원순서인 표지 집합을 가진 유한 나무의 집합은 위상동형적 매립 하에서 그 자체로 정렬 원순서 집합이 된다는 정리이다.

이 정리를 유한적으로 응용하면 빠르게 성장하는 **TREE 함수**가 존재함을 알 수 있다. TREE(3)은 간단히 정의된 유한한 수 중에서 가장 큰 수 중 하나로, 그레이엄 수나 구골플렉스와 같은 다른 큰 수를 압도한다.

## 역사
이 정리는 언드라시 버조니가 추측하였고 조셉 크러스컬이 증명했다(). 이후 크리스핀 내시윌리엄스(Crispin St. J. A. Nash-Williams)가 짧은 증명을 제시했다(). 이 정리는 역수학에서 산술적 초한 재귀의 한 형태를 포함하는 2차 산술 이론인 ATR0에서 증명할 수 없는 문장의 대표적인 사례가 되었다.

2004년에 이 결과는 나무에서 그래프로 일반화되어 로버트슨-시모어 정리가 되었으며, 이 결과 역시 역수학에서 중요함이 증명되었고 TREE를 압도하는 훨씬 더 빠르게 성장하는 SSCG 함수로 이어진다.

## 내용
여기에 제시된 내용은 내시윌리엄스가 증명한 것이며, 크러스컬의 정식화는 이보다 다소 더 강력하다. 여기서 고려하는 모든 나무는 유한하다.

뿌리가 있는 나무 T와 정점 v, w가 주어졌을 때, 뿌리에서 w로 가는 유일한 경로에 v가 포함되면 w를 v의 자손이라 부르고, 추가로 v에서 w로 가는 경로에 다른 정점이 포함되지 않으면 w를 v의 자식이라 부른다.

(X, \le_X)를 부분 순서 집합이라 하자. T_1, T_2가 X의 표지를 가진 뿌리 있는 나무일 때, 만약 T_1의 정점에서 T_2의 정점으로 가는 다음과 같은 단사 함수 F가 존재하면 T_1이 T_2에 하한 매립(inf-embeddable) 가능하다고 하며 T_1 \leq T_2라고 쓴다.

* T_1의 모든 정점 v에 대해, v의 표지는 F(v)의 표지에 대해 \le_X 관계에 있다.
* w가 T_1에서 v의 자손이면, F(w)는 F(v)의 자손이다.
* w_1, w_2가 v의 서로 다른 두 자식이라면, T_2에서 F(w_1)에서 F(w_2)로 가는 경로는 F(v)를 포함한다 (동치 조건으로, F(w_1)과 F(w_2)는 서로 다른 부분 나무에 속한다).

크러스컬 나무 정리는 다음과 같이 말한다.

: 만약 X가 정렬 원순서 집합이면, X의 표지를 가진 뿌리 있는 나무의 집합은 위에서 정의된 하한 매립 순서 하에서 정렬 원순서 집합이다. (즉, X의 표지를 가진 뿌리 있는 나무의 임의의 무한 수열 T_1, T_2, \ldots에 대해, T_i \leq T_j를 만족하는 i가 존재한다.)

## 하비 프리드먼의 작업
가산 표지 집합 X에 대해, 크러스컬 나무 정리는 2차 산술을 사용하여 표현하고 증명할 수 있다. 그러나 굿스타인의 정리나 파리스-하링턴 정리와 마찬가지로, 이 정리의 일부 특수한 경우와 변형은 정리를 증명할 수 있는 하위 체계보다 훨씬 약한 2차 산술의 하위 체계에서 표현할 수 있다. 이는 1980년대 초 하비 프리드먼이 처음 발견했으며 당시 초기 단계였던 역수학 분야의 초기 성과였다. 위의 나무가 표지가 없는 경우(즉, X의 크기가 1인 경우), 프리드먼은 그 결과가 ATR<sub>0</sub>에서 증명 불가능함을 발견했으며, 이로써 증명 가능하게 비술어적인(impredicative) 증명을 가진 술어적인(predicative) 결과의 첫 번째 사례를 제시하였다. 이 경우의 정리는 여전히 Π-CA0에서 증명 가능하지만, 위의 나무 순서 정의에 "간격 조건(gap condition)"을 추가함으로써 프리드먼은 이 체계에서도 증명 불가능한 정리의 자연스러운 변형을 찾아냈다. 훨씬 후에 로버트슨-세이무어 정리는 Π-CA0에서 증명 불가능한 또 다른 정리를 찾아낸다.

서수 분석은 크러스컬 정리의 강도를 확인해주며, 이 정리의 증명론적 서수는 작은 베블런 서수(때때로 더 작은 아커만 서수와 혼동되기도 함)와 같다.

## 약한 나무 함수
P(n)이 다음과 같은 문장이라고 가정하자.

: T_i가 i+n개의 정점을 가진 표지 없는 뿌리 있는 나무의 유한 수열 T_1, \ldots, T_m일 때, 어떤 i에 대해 T_i \leq T_j가 되는 m이 존재한다.

모든 문장 P(n)은 크러스컬 정리와 쾨니그 보조정리를 통해 참이다. 각 n에 대해 페아노 공리계는 P(n)이 참임을 증명할 수 있지만, 페아노 공리계는 "모든 n에 대해 P(n)이 참이다"라는 문장을 증명할 수 없다. 더욱이 페아노 공리계에서 P(n)의 가장 짧은 증명의 길이는 n의 함수로서 경이적으로 빠르게 증가하며, 예를 들어 임의의 원시 재귀 함수나 아커만 함수보다 훨씬 빠르다. P(n)이 성립하는 최소의 m 또한 n에 따라 매우 빠르게 증가한다.

하비 프리드먼은 아래의 TREE 함수의 약한 버전인 다음 함수를 정의했다. 양의 정수 n에 대해, \text{FFF}(n)을 다음을 만족하는 가장 큰 m으로 정의한다.
: 각 T_i가 i+n-1개의 정점을 가진 뿌리 있는 나무의 수열 T_1, \ldots, T_m이 존재하여, 어떤 i에 대해서도 T_i \leq T_j가 성립하지 않는다.

프리드먼은 이 수열의 처음 몇 항을 \text{FFF}(1)=1, \text{FFF}(2)=2, \text{FFF}(3)=5로 계산했다. 또한 \text{FFF}(4)가 100보다 작을 것으로 추정했지만, \text{FFF}(5)는 갑자기 매우 큰 값으로 폭발한다. 페아노 공리계에서 \text{FFF}(5)가 존재한다는 임의의 증명은 적어도 A(10)개의 기호를 필요로 하며, 여기서 A(n)은 아커만 함수의 단항 버전이다. 그러나 이는 ACA<sub>0</sub>에서 최대 10,000개의 기호로 존재함이 증명될 수 있다.

## TREE 함수
섬네일|alt=Sequence of trees where each node is colored either green, red, blue|3개의 표지(파랑 < 빨강 < 초록) 집합에서 라벨링된 뿌리 있는 나무의 수열. 수열의 <math>n</math>번째 나무는 최대 <math>n</math>개의 정점을 포함하며, 어떤 나무도 수열의 이후 나무에 하한 매립되지 않는다. <math>\text{TREE}(3)</math>은 이러한 수열의 가능한 최대 길이로 정의된다.

표지를 도입함으로써 프리드먼은 훨씬 더 빠르게 성장하는 함수를 정의했다. 양의 정수 n에 대해, \text{TREE}(n)을 다음을 만족하는 가장 큰 m으로 정의한다.

: n개의 표지 집합에서 표지된 뿌리 있는 나무의 수열 T_1, \ldots, T_m이 존재하고, 각 T_i는 최대 i개의 정점을 가지며, 어떤 i에 대해서도 T_i \leq T_j가 성립하지 않는다.

크러스컬 정리에 따라 모든 n에 대해 \text{TREE}(n)은 유한하다. 하지만 TREE 함수는 결국 ACA0 + Π-BI 체계의 모든 증명 가능한 재귀 함수를 압도한다.

수열은 \text{TREE}(1)=1, \text{TREE}(2)=3으로 시작하지만, \text{TREE}(3)에 이르러 갑자기 값이 폭발하여 프리드먼의 n(4)나 그레이엄 수와 같은 다른 많은 "큰" 조합론적 상수조차 이에 비하면 매우 작아진다. n(4)에 대한 하한, 따라서 \text{TREE}(3)에 대한 극도로 약한 하한은 A^{A(187196)}(1)이며, 여기서 A(x)는 A(x)=A(x,x)로 정의된 아커만 함수의 단일 변수 버전이다.

프리드먼은 \text{TREE}(3)이 ACA0 + Π-BI에서 최대 2\uparrow\uparrow1000개의 기호를 사용하여 정지함이 증명될 수 있는 임의의 튜링 기계의 정지 시간보다 크다는 것을 보여주었다. 여기서 \uparrow\uparrow는 테트레이션을 나타낸다.

## 같이 보기
* 파리스-하링턴 정리
* 가나모리–맥앨런 정리
* 로버트슨-세이무어 정리

## 내용주
: 프리드먼은 원래 이 함수를 \text{TR}[n]으로 표기했다.
: n(k)는 k개의 문자로 이루어진 알파벳으로 구성할 수 있는 가장 긴 수열의 길이로 정의되며, 이때 어떤 문자 블록 x_i,\ldots,x_{2i}도 나중의 블록 x_j,\ldots,x_{2j}의 부분 수열이 되지 않아야 한다. 예를 들어 n(1) = 3, n(2) = 11, n(3) > 2 \uparrow^{7197} 158386이다.
: 위첨자는 반복을 나타낸다. 예를 들어 A^{3}(1)은 A(A(A(1)))을 계산하는 것을 의미한다.
: 프리드먼은 실제로 이를 2[1000]으로 썼는데, 이는 그의 표기법으로 높이가 1000인 2의 지수 탑을 나타낸다.

## 각주

## 참고 문헌
* 
* 
* 
* 
* 
* 
* 
* 

분류:수리논리학
분류:순서론
분류:기초관계
분류:이산수학 정리