개요
쾨니그 보조정리(Kőnig補助定理, 영어: Kőnig's lemma, Kőnig's infinity lemma)는 그래프 이론에서 어떤 무한 그래프가 무한 경로를 갖기 위한 충분 조건을 제시하는 정리이다. 헝가리 출신의 수학자 쾨니그 데네시(Dénes Kőnig)가 1927년에 발표한 논문 "Über eine Schlussweise aus dem Endlichen ins Unendliche"에서 처음 증명하였다.
정의
쾨니그 보조정리는 여러 동등한 형태로 표현될 수 있다. 가장 일반적인 형태는 다음과 같다.
연결되어 있고(connected), 국소적으로 유한하며(locally finite, 즉 각 꼭짓점이 유한 개의 이웃만을 가짐), 무한 개의 꼭짓점을 갖는 그래프 G에 대하여, G는 무한 경로(ray)를 포함한다. 여기서 무한 경로란 한 꼭짓점에서 시작하여 반복되는 꼭짓점 없이 무한히 많은 꼭짓점을 지나는 단순 경로를 뜻한다.
다른 동등한 표현으로는 다음이 있다. 임의의 그래프 G에 대하여, 다음 네 명제 가운데 적어도 하나가 성립한다.
- G는 유한 개의 꼭짓점을 갖는다.
- G는 무한 개의 연결 성분을 갖는다.
- G는 차수(degree)가 무한한 꼭짓점을 갖는다.
- G는 무한 경로를 갖는다.
특히 유용한 특수 경우로는, 무한 트리(infinite tree)에 대하여, 각 꼭짓점이 유한 개의 자식을 가질 경우(finitely branching) 그 트리는 무한 경로를 포함한다는 형태가 있다. 이는 Wolfram MathWorld 등에서 "유한 분기 트리는 무한 경로를 갖는 것과 무한하다는 것이 동치이다"라고 서술되기도 한다.
증명 개요
증명은 수학적 귀납법을 사용하여 이루어진다. 무한한 꼭짓점을 갖고, 유한 개의 연결 성분을 가지며, 모든 꼭짓점의 차수가 유한한 그래프에서, 길이가 n인 경로의 끝점이 남아 있는 무한 연결 성분에 속한다고 가정할 때, 그 꼭짓점에서 연결된 이웃 가운데 하나를 골라 길이가 n+1인 경로로 확장할 수 있음을 보인다. 이 과정을 반복하면 무한 경로를 구성할 수 있다.
집합론적 성질
쾨니그 보조정리는 체르멜로-프렝켈 집합론(ZF)에서는 일반적으로 증명될 수 없으나, 의존적 선택 공리(axiom of dependent choice)를 추가한 체르멜로-프렝켈 집합론에서는 증명된다. 다만, 그래프가 가산 무한 개의 꼭짓점만을 갖는 경우에는 ZF 집합론에서도 증명된다.
이 정리는 선택 공리와 밀접한 관련이 있다. 쾨니그 보조정리는 각 노드에서 유한하게 분기하는 관계에 국한된 의존적 선택 공리의 제한 형태로 볼 수 있다. 특히 "모든 무한 유한 분기 트리는 무한 경로를 갖는다"는 형태의 쾨니그 보조정리는 유한 집합들로 이루어진 모든 가산 집합족이 선택 함수를 갖는다는 원리, 즉 유한 집합에 대한 가산 선택 공리와 동치이다. 이 형태의 선택 공리는 ZF에서 증명될 수 없다.
계산 가능성 및 역수학적 측면
쾨니그 보조정리의 계산 가능성 측면은 수리논리학, 특히 계산 가능성 이론에서 깊이 연구되었다. 다음과 같은 형태로 서술되기도 한다: ω^<ω의 임의의 무한 유한 분기 부분 트리는 무한 경로를 갖는다.
이와 관련된 주요 결과로는 다음이 있다.
- 약한 쾨니그 보조정리(Weak Kőnig's lemma): 모든 무한 이진 트리(각 수열의 모든 항이 0 또는 1인 트리)는 무한 가지를 갖는다. 이는 역수학(reverse mathematics)에서 WKL₀ 서브시스템을 정의하는 데 사용된다.
- WKL₀ 위에서 쾨니그 보조정리의 완전한 형태는 증명될 수 없으며, 이는 더 강한 서브시스템인 ACA₀와 동치이다.
- RCA₀ 위에서 약한 쾨니그 보조정리는 증명될 수 없으므로, 이를 추가한 WKL₀는 RCA₀보다 엄밀히 강하다.
구성적 수학과의 관계
위에 제시된 증명은 일반적으로 구성적(constructive)이지 않은 것으로 간주된다. 각 단계에서 특정 성질을 만족하는 이웃 꼭짓점의 존재를 귀류법으로 보이고, 선택 공리의 약한 형태에 의존하기 때문이다. 이 정리의 계산 가능성 측면에 대한 연구 결과는 구성적 수학의 주요 학파가 구성적이라고 인정할 만한 증명이 존재하지 않음을 시사한다.
브라우어(L. E. J. Brouwer)의 부채 정리(fan theorem, 1927)는 고전적 관점에서 쾨니그 보조정리의 한 형태의 대우(contrapositive)에 해당한다.
일반화
집합의 범주에서, 비어 있지 않은 유한 집합들로 이루어진 역계(inverse system)의 역극한(inverse limit)은 비어 있지 않다. 이는 쾨니그 보조정리의 일반화로 볼 수 있으며, 유한 집합들을 콤팩트 이산 공간으로 보고 티호노프 정리(Tychonoff's theorem)를 사용하여 증명할 수 있다.
또한 쾨니그 보조정리를 더 높은 기수로 일반화할 경우 반례가 존재할 수 있다는 점이 알려져 있으며, 이와 관련된 개념으로 아론샤인 트리(Aronszajn tree)가 있다.
역사
쾨니그 데네시가 1927년에 증명하여 발표하였다. 원본 논문은 헝가리 세게드(Szeged)의 《Acta Scientiarum Mathematicarum Universitatis Szegediensis》 제3권에 게재되었다. 미리암 프란켈라(Miriam Franchella)의 연구(1997)는 쾨니그 무한 보조정리의 기원에 대해 다루고 있다.
응용
쾨니그 보조정리는 수리논리학의 완전성 증명, 구성적 수학, 증명 이론, 계산 가능성 이론 등 다양한 분야에서 활용된다. 또한 컴퓨터 과학의 알고리즘 분석 및 역수학 연구에서 중요한 도구로 사용된다.
