크루스칼의 트리 정리

수학에서 크루스칼의 트리 정리는 잘 정렬된 레이블 집합 위의 유한 트리 집합은 동형 임베딩 하에서 잘 정렬된 것 자체라고 말합니다.

역사

이 정리는 앤드루 바소니에 의해 추측되었고 조셉 크러스칼(1960)에 의해 증명되었고, 크리스핀 내쉬-윌리엄스(1963)에 의해 짧은 증명이 이루어졌습니다. 그 후₀ ATR에서는 증명할 수 없는 문장(수학적 트랜스피니트 재귀의 형태를 가진 2차 산술 이론)으로 역수학의 중요한 예가 되었습니다.

2004년, 그 결과는 나무에서 그래프로 로버트슨으로 일반화되었습니다.Seymour 정리는 역수학에서도 중요한 것으로 입증되었으며 TREE(3)를 왜소하게 만드는 훨씬 더 빠르게 성장하는 SSCG 함수로 이어지는 결과입니다. 정리를 최종적으로 적용하면 빠르게 성장하는 TREE 함수의 존재를 알 수 있습니다.

진술

여기에 제공된 버전은 내쉬-윌리엄스에 의해 입증되었습니다. 크루스칼의 공식은 다소 강합니다. 우리가 고려하는 모든 나무는 유한합니다.

루트가 있는 트리 T가 주어지고 정점 v, w가 주어지면 루트에서 w로의 고유 경로가 v를 포함하는 경우 w를 v의 계승자라고 부르고 v에서 w로의 경로가 다른 정점을 포함하지 않는 경우 w를 v의 바로 계승자라고 부릅니다.

X를 부분 순서 집합으로 삼습니다. T₁, T가₂ X로 표시된 꼭짓점을 가진 근 트리라면, T는₁ T로₂ 인입 가능하다고 말하고, T의₁ 꼭짓점에서 T의₂ 꼭짓점으로 가는 인젝션 맵 F가 있으면₁ T ≤ T라고₂ 적으면 다음과 같습니다.

• T의₁ 모든 정점 v에 대하여, v의 레이블은 F(v)의 레이블 앞에,
• 만약 w가 vin₁ T의 어떤 계승자라면, F(w)는 F(v)의 계승자이고,
• 만약₁ w, w가₂ v의 두 개의 서로 다른 바로 뒤에 있는 것이라면, T의₂ F(w₁)에서 F(w₂)로 가는 경로는 F(v)를 포함합니다.

크루스칼의 트리 정리는 다음과 같습니다.

만약 X가 잘 준순서화된다면, X에 레이블을 가진 근 트리들의 집합은 위에서 정의된 inf-embeddable 순서에 따라 잘 준순서화됩니다. (즉, X에 레이블을 단 근 트리들의 임의의 무한수열₁ T₂, T, …이 주어졌을 때, T_i ≤ T가_j 되도록 i < j가 존재합니다.)

프리드먼의 작품

셀 수 있는 레이블 집합 X에 대해 크루스칼의 트리 정리는 2차 산술을 사용하여 표현되고 증명될 수 있습니다. 그러나 Goodstein의 정리나 파리-해링턴 정리와 같이 이 정리의 몇 가지 특별한 경우와 변형은 증명될 수 있는 하위 시스템보다 훨씬 약한 2차 산술의 하위 시스템에서 표현될 수 있습니다. 이것은 1980년대 초 하비 프리드먼에 의해 처음으로 관찰되었는데, 이는 당시 초기 역수학 분야의 초기 성공이었습니다. 위의 트리가 레이블이 지정되지 않은 경우(즉, X가 1차인 경우), 프리드먼은 ATR에서₀ 결과를 증명할 수 없음을 발견했으며,^[1] 따라서 예측 가능한 증거를 가진 예측 결과의 첫 번째 예를 제공합니다.^[2] 이 정리의 경우는 여전히 π-CA에 의해 증명 가능하지만, 위의 트리에 대한 순서의 정의에 "갭 조건"을 추가함으로써, 그는 이 체계에서 증명할 수 없는 정리의 자연스러운 변형을 발견했습니다. 훨씬 후에 로버트슨 호는시모어 정리는 π-CA에 의해 증명될 수 없는 또 다른 정리를 제공할 것입니다.

순서 분석은 크루스칼 정리의 증명 이론 순서가 작은 베블렌 순서와 동일한 것으로(때로는 작은 아커만 순서와 혼동되기도 함) 크루스칼 정리의 강도를 확인합니다.^{[citation needed]}

약한 트리 기능

P(n)이 다음 문장이라고 가정합니다.

만약 T₁,...,T가_m 레이블이 없는 근 트리의 유한 수열이라면, T가_i i+n개의 정점을 갖는 경우, 일부 i < j에 대하여 T_i ≤ T가_j 됩니다.

크루스칼의 정리와 크루스칼의 보조정리의 결과로 모든 문장 P(n)은 참입니다. 각각의 n에 대하여, 페아노 산술은 P(n)이 참임을 증명할 수 있지만, 페아노 산술은 "P(n)이 모든 n에 대하여 참"이라는 문장을 증명할 수 없습니다.^[6] 게다가 페아노 산술에서 P(n)의 가장 짧은 증명의 길이는 n의 함수로서 경이적으로 빠르게 증가하며, 예를 들어 어떤 원시 재귀 함수나 아커만 함수보다 훨씬 빠릅니다.^{[citation needed]} P(n)가 유사하게 유지되는 최소 m은 n과 함께 매우 빠르게 성장합니다.

약한 트리 함수인 트리(n)를 가장 큰 m으로 정의하여 다음과 같은 결과를 얻을 수 있습니다.

레이블이 지정되지 않은 근 트리의 시퀀스 T₁,...,T가_m 있으며, 여기서 각_i T는 최대 i개 + n개의 정점을 가지므로 T_i ≤ T는_j 어떤 i < j ≤ m에 대해서도 성립하지 않습니다.

수목(1) = 2, 수목(2) = 5, 수목(3) ≥ 844424930131960, tree(4) > Graham의 수(로트 단위)이지만 Tree(3)(인수가 레이블 수를 지정함, 아래 참조)가 ${\displaystyle {\mathrm{tree}}^{}}$ ${\displaystyle {{{\mathrm{}}^{}}^{}}^{}}$ ${\displaystyle {{{{\mathrm{}}^{}}^{}}^{}}^{}}$ ${\displaystyle {{{{\mathrm{tree}}^{}}^{}}^{}}^{}}$ ${\displaystyle {{{{{\mathrm{}}^{}}^{}}^{}}^{}}^{}}$ 8${\displaystyle {{{{{}^{}7}^{}){}^{}}^{}}^{}}^{}}$(${\displaystyle {{7^{}}^{}}^{}}$)${\displaystyle {{{}^{}}^{}{7)}^{}}^{}}$ ($displaystyle \mathrm {tree} ^{\mathrm {tree$} $^{\$mathrm {$tree} ^{\mathrm {tree} ^{\$mathrm {tree} ^{\$mathrm {tree}$$^{8}(7)}(7)}(7)}(7)}(7)}$.

두 기능을 구별하기 위해 모든 문자가 대문자로 표시된 TREE는 큰 TREE 기능이고 소문자로 표시된 모든 문자가 있는 TREE는 약한 TREE 기능입니다.

TREE 함수

Friedman은 레이블을 통합하여 훨씬 더 빠르게 성장하는 기능을 정의했습니다.^[7] 양의 정수 n일 때, 다음을 가지려면 TREE(n)^[a]가 가장 커야 합니다.

n개의 레이블 집합에서 레이블이 지정된 근 트리의 시퀀스₁ T,...,T가_m 있으며, 여기서 각각의_i T는 최대 i개의 정점을 가지므로_i T ≤ T는_j 어떤 i < j ≤ m에 대해서도 성립하지 않습니다.

TREE 시퀀스는 TREE(1) = 1, TREE(2) = 3으로 시작한 다음 갑자기 TREE(3)가 너무 큰 값으로 폭발하여 프리드먼의 n(4), n(5), 그레이엄의 수와 같은 다른 많은 "큰" 조합 상수는 비교적 매우 작습니다. n(4)에 대한 하한값, 따라서 TREE(3)에 대한 하한값은^A(187196) A(1)입니다.^[c][8] 예를 들어, 그레이엄의 수는 하한 A(1)보다^A(187196) 훨씬 작습니다. $대략$ g ${\displaystyle 3_{}}$ ↑ ${\displaystyle {{1871963}^{}}_{}}$ $displaystyle g_{3\uparrow ^{$187196$\}$3}}이며, 여기서 g는 Graham의 함수입니다.

참고 항목

• 파리-해링턴 정리
• 카나모리-맥알룬 정리
• 로버트슨 –시모어 정리

메모들

^{^ a} Friedman은 원래 이 함수를 TR[n]로 표시했습니다.

n(k)는 문자 x,...,x가 나중 블록 x,...,x의 후속 블록 x,...,. n(1 3$,$ (2) = 11, 및 n(3) > 2 ↑ 7197 158386 {\display n(1) = 3, n(2) = 11,\,{\textrm {and$}}\,$$n(3)>2\uparrow ^{7197}158386}$.

하나의 인수를 취하는 A(x)는 A(x, x)로 정의되며, 여기서 두 인수를 취하는 A(k, n)는 A(1, n) = 2n, A(k+1, 1) = A(k, 1), A(k+1, n+1) = A(k, A(k+1, n)로 정의되는 아커만 함수의 특정 버전입니다.

참고문헌

인용

서지학

• Friedman, Harvey M. (2002), Internal finite tree embeddings. Reflections on the foundations of mathematics (Stanford, CA, 1998), Lect. Notes Log., vol. 15, Urbana, IL: Assoc. Symbol. Logic, pp. 60–91, MR 1943303
• Gallier, Jean H. (1991), "What's so special about Kruskal's theorem and the ordinal Γ₀? A survey of some results in proof theory" (PDF), Ann. Pure Appl. Logic, 53 (3): 199–260, doi:10.1016/0168-0072(91)90022-E, MR 1129778
• Kruskal, J. B. (May 1960), "Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture" (PDF), Transactions of the American Mathematical Society, American Mathematical Society, 95 (2): 210–225, doi:10.2307/1993287, JSTOR 1993287, MR 0111704
• Marcone, Alberto (2001). "Wqo and bqo theory in subsystems of second order arithmetic" (PDF). Reverse Mathematics. 21: 303–330.
• Nash-Williams, C. St.J. A. (1963), "On well-quasi-ordering finite trees", Proc. Camb. Phil. Soc., 59 (4): 833–835, Bibcode:1963PCPS...59..833N, doi:10.1017/S0305004100003844, MR 0153601, S2CID 251095188
• Rathjen, Michael; Weiermann, Andreas (1993). "Proof-theoretic investigations on Kruskal's theorem". Annals of Pure and Applied Logic. 60 (1): 49–88. doi:10.1016/0168-0072(93)90192-g.
• Simpson, Stephen G. (1985), "Nonprovability of certain combinatorial properties of finite trees", in Harrington, L. A.; Morley, M.; Scedrov, A.; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 87–117
• Smith, Rick L. (1985), "The consistency strengths of some finite forms of the Higman and Kruskal theorems", in Harrington, L. A.; Morley, M.; Scedrov, A.; et al. (eds.), Harvey Friedman's Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, North-Holland, pp. 119–136