쾨니그 보조정리

3. 증명

쾨니그 보조정리의 증명은 주로 수학적 귀납법을 사용한다. 주어진 그래프에서 무한 경로를 단계별로 구성해 나가는 방식으로 진행되며, 비둘기집 원리와 귀류법 등이 증명 과정에 활용된다.

증명에 앞서 그래프에 포함된 무한 개의 각 점을 ''v''_i 형태로 나타내고, 그래프는 연결되어 있다고 가정한다.

우선, 임의의 정점 ''v''₁을 선택한다. 그래프의 무한 개의 점은 ''v''₁에서 시작하는 단순 경로로 도달할 수 있으며, 이러한 경로는 모두 ''v''₁에 연결된 유한 개의 점 중 하나에서 시작한다. 이 점들 중, 해당 점에서 무한 개의 점에 ''v''₁을 거치지 않는 경로로 도달할 수 있는 점이 존재한다. 만약 그러한 점이 없다면 그래프 전체가 유한 집합의 유한 합이 되어, 그래프가 무한하다는 가정에 모순되기 때문이다. 여기서, 그러한 점을 하나 선택하여 ''v''₂로 한다.

이제 그래프의 무한 개의 점은 ''v''₂에서 시작하는, ''v''₁을 거치지 않는 단순 경로로 도달할 수 있다. 그러한 경로는 모두 ''v''₂에 연결된 유한 개의 점 중 하나에서 시작한다. 위에서 수행한 것과 유사하게, 무한 개의 점에 도달할 수 있는 경로의 시작점을 선택하여 ''v''₃으로 한다.

이와 같은 논의를 수학적 귀납법을 통해 반복하면 무한 단순 경로를 얻을 수 있다. 각 단계에서 귀납법의 가정은 ''v''_i에서 시작하는 하나의 단순 경로를 통해, 어떤 유한 집합을 거치지 않고 무한 개의 점에 도달할 수 있다는 것이다. 귀납법의 논의는 ''v''_i를 해당 유한 집합에 추가해도 인접점이 귀납법의 가정을 만족함으로써 성립한다. 같은 점이 두 번 추가되지 않는다는 것도 구성법에서 보장되며, 결과적으로 임의의 ''n''에 대해 원하는 경로를 이루는 ''v''_''n''을 선택할 수 있다.

이 증명은 각 단계에서 무한 개의 점에 도달할 수 있는 인접점이 존재한다는 것을 귀류법으로 제시하기 때문에 구성적이지 않다고 여겨질 수 있다.

좀 더 자세하게 살펴보면 다음과 같다.

$G$가 다음 성질들을 만족시키는 그래프라고 가정한다.

• $G$는 무한한 수의 꼭짓점을 갖는다.
• $G$는 유한 개의 연결 성분을 갖는다.
• $G$의 모든 꼭짓점의 차수는 유한하다.
• $G$는 길이가 $n\backslash in\backslash mathbb\; N$인 경로 $v\_0v\_1\backslash dots\; v\_n$을 갖는다.
• $v\_n$은 $G\backslash setminus\backslash \{v\_0,v\_1,\backslash dots,v\_\{n-1\}\backslash \}$의 연결 성분 가운데 무한한 크기의 성분 $G\_n$에 포함된다.

• $G$는 길이가 $n+1$인 경로 $v\_0v\_1\backslash dots\; v\_nv\_\{n+1\}$을 가지며, 또한 $v\_\{n+1\}$은 $G\backslash setminus\backslash \{v\_0,v\_1\backslash dots,v\_n\backslash \}$의 연결 성분 가운데 무한한 크기의 성분 $G\_\{n+1\}$에 포함된다.

4. 역사

쾨니그 데네시가 1927년에 쾨니그 보조정리를 증명하였다.^[6][7] 쾨니그 데네시는 헝가리의 수학자로, 그래프 이론의 발전에 큰 기여를 하였다.

5. 구성적 수학 및 콤팩트성과의 관계

쾨니그 보조정리의 증명은 각 단계에서 무수히 많은 다른 정점에 도달할 수 있는 인접한 정점이 존재함을 증명하기 위해 귀류법을 사용하고, 선택 공리의 약한 형태에 의존하기 때문에 일반적으로 구성적으로 간주되지 않는다. 보조 정리에 대한 계산적 측면의 사실은 주요 구성적 수학 학파에서 구성적이라고 간주될 수 있는 증명은 제시될 수 없음을 시사한다.

브라우어르의 팬 정리는 고전적인 관점에서 쾨니그 보조 정리의 한 형태의 대우이다.^[5] 팬 정리는 분리 가능한 모든 bar가 균일하다는 것이다. 여기서 bar는 <math>\{0,1\}^{\omega}</math>의 부분 집합 S에 대해 <math>\omega</math>에서 <math>\{0,1\}</math>로의 모든 함수가 S에 초기 세그먼트를 갖는 경우를 의미한다. bar는 모든 수열이 bar에 있거나 bar에 없는 경우 분리 가능하며, <math>N</math>이라는 숫자가 있어서 <math>\omega</math>에서 <math>\{0,1\}</math>로의 모든 함수가 길이가 <math>N</math> 이하인 bar의 초기 세그먼트를 갖는 경우 균일하다.

이는 고전적인 설정에서 bar를 콤팩트 위상 공간 <math>\{0,1\}^\omega</math>의 열린 덮개로 간주하여 증명할 수 있다. bar의 각 수열은 이 공간의 기본 열린 집합을 나타내고, 이러한 기본 열린 집합은 가정에 따라 공간을 덮는다. 콤팩트성에 의해 이 덮개는 유한 부분 덮개를 갖는다. 팬 정리의 N은 유한 부분 덮개에 있는 기본 열린 집합인 가장 긴 수열의 길이로 취할 수 있다. 이 위상적 증명은 고전 수학에서 다음 형태의 쾨니그 보조 정리가 성립함을 보이기 위해 사용될 수 있다. 즉, 임의의 자연수 k에 대해 트리 <math>\{0,\ldots,k\}^{\omega}</math>의 임의의 무한 부분 트리는 무한 경로를 갖는다.^[5]

6. 선택 공리와의 관계

쾨니그 보조정리는 선택 원리로 간주될 수 있다.^[3] 첫 번째 증명은 보조정리와 의존 선택 공리 사이의 관계를 보여주는데, 귀납법의 각 단계에서 특정 속성을 가진 정점을 선택해야 하기 때문이다.^[3] 적어도 하나의 적절한 정점이 존재한다는 것이 증명되었지만, 적절한 정점이 둘 이상인 경우 표준적인 선택이 없을 수 있다.^[3]

그래프가 가산적인 경우, 쾨니그 보조정리는 산술적 이해 공리를 사용한 2차 산술에서 증명할 수 있으며, ZF 집합론에서도 증명 가능하다.^[3]

쾨니그 보조정리는 본질적으로 각 $x$에 대해 $xRz$를 만족하는 $z$가 유한개만 존재하는 전체 관계 $R$에 의존 선택 공리를 제한한 것이다.^[3] 일반적으로 선택 공리가 의존 선택 원리보다 강하지만, 의존 선택의 이러한 제한은 선택 공리의 제한과 동등하다.^[3]

특히, 각 노드의 분기가 가산적이라고 가정하지 않은 임의의 집합의 유한 부분 집합에서 수행될 때 "모든 무한 유한 분기 트리는 무한 경로를 갖는다"라고 말하는 쾨니그 보조정리의 형식은 모든 가산 집합의 유한 집합이 선택 함수, 즉 유한 집합에 대한 가산 선택 공리를 갖는다는 원리와 동등하다.^[3] 선택 공리 (및 따라서 쾨니그 보조정리)의 이러한 형식은 ZF 집합론에서 증명할 수 없다.

7. 계산 가능성 측면

쾨니그 보조정리의 계산 가능성 측면은 계산 가능성 이론에서 중요하게 연구되어 왔다.^[2] 쾨니그 보조정리는 ω^<ω (자연수의 모든 유한 시퀀스를 노드로 하는 트리)의 무한 유한 분기 서브트리가 무한 경로를 갖는다는 형태로 표현될 수 있다. 여기서 각 유한 시퀀스는 부분 함수로, 무한 경로는 전체 함수로 식별되어 계산 가능성 이론을 통해 분석 가능하다.^[2]

ω^<ω의 서브트리 T에 대해, Ext(T)는 무한 경로가 있는 T의 노드 집합을 나타낸다. T가 계산 가능하더라도 Ext(T)는 계산 가능하지 않을 수 있다. 하지만, T가 무한 경로를 가질 때 경로는 Ext(T)에서 단계별로 계산 가능하며, 각 단계에서 Ext(T)의 후속자를 탐욕적으로 선택한다.^[2]

산술적 경로나 초산술적 경로가 없는 비-유한 분기 계산 가능 서브트리가 존재하지만,^[2] 경로가 있는 ω^<ω의 모든 계산 가능 서브트리는 클레이니의 O에서 계산 가능한 경로를 갖는다. 이는 T가 계산 가능할 때 Ext(T)가 항상 Σ¹₁이기 때문이다.^[2]

계산 가능하게 제한된 트리에 대한 더 세밀한 분석도 이루어졌다. ω^<ω의 서브트리는 각 시퀀스의 n번째 요소가 계산 가능한 함수 f(n)보다 작거나 같은 경우 계산 가능하게 제한된다고 한다. 이러한 트리에 대해 다음과 같은 기저 정리가 적용된다.^[2]

• 정지 문제를 결정할 수 있는 0'에서 계산 가능한 경로를 갖는다.
• low인 경로를 갖는다. (low 기저 정리)
• 초 면역 자유인 경로를 갖는다.
• ω의 비 계산 가능 부분 집합 X에 대해, X를 계산하지 않는 경로를 갖는다.

8. 일반화

집합 범주에서, 공집합이 아닌 유한 집합들의 역 시스템의 역극한은 공집합이 아니다. 이는 쾨니그 보조정리의 일반화로 볼 수 있으며, 유한 집합을 컴팩트 이산 공간으로 간주하고, 유한 교차 속성을 사용하여 콤팩트성을 특징짓는 티호노프 정리로 증명할 수 있다.

참조

_[1] Harvtxt
_[2] Harvtxt
_[3] Harvtxt
_[4] 문서
_[5] 문서
_[6] 저널 Über eine Schlussweise aus dem Endlichen ins Unendliche http://acta.fyx.hu/a[...] 2015-01-01
_[7] 저널 On the origins of Dénes König’s infinity lemma 1997-07-22