이제 선택공리를 통해 하우스도르프 극대원리를 증명해 봅시다. 이 명제의 증명을 위해 필요한 개념과 보조정리가 있어서 그를 먼저 확인할 것입니다. 다만 이 보조정리는 사실상 집합론에서 가장 어려운 증명으로 손꼽아도 무리가 아닐 정도로 호흡도 길고 논리가 복잡합니다. 길이로 따지면 제가 블로그에서 한 여느 증명보다도 긴 것 같네요. 다만 이러한 복잡하고 긴 증명을 하지 않으려면 조금 더 고급 수학 과목의 지식을 가져와야 합니다. 집합론 수준에서는 이러한 증명이 최선이라 보시면 됩니다.
썸네일은 앞으로 유머삼아 만드려고 합니다. '하우스'가 꼭대기에 있음을 상징하는 그림입니다.
1. 허용가능함
정의(S.T) 5-7) 허용가능함 어떤 a∈A 를 생각하자. B⊆A 인 집합 B가 다음 세 조건을 만족할 때, B 를 '허용가능함(admissible)'이라 한다. ① a∈B ② B 가 함수 f 에 대해 닫혀있음 : f(B)⊆B ③ B 의 모든 사슬(전순서 부분집합)의 최소상계가 B 에 속한다.
보조정리(S.T) 5.1) 부분순서집합 (A,≤) 에 대해, 이것의 모든 사슬(전순서 부분집합)들의 최소상계들이 A 에 포함되어 있다고 가정하자. 함수 f:A⟶A 를 모든 a∈A 에 대해 a⟼f(a)≥a 로 정의하면, f(p)=p 를 만족하는 어떤 p∈A 가 반드시 존재한다.
증명) B={Bi}i∈I 를 A 의 모든 허용가능한 부분집합들로 이루어진 집합족(collection, family) 라 하자. A 는 그러면 허용가능한데, 모든 Bi 가 가진 원소를 a∈A 라 하면 말그대로 a∈A 가 성립하고, f(A)⊆A 이며, 가정에 의하여 ③의 조건도 만족되기 때문이다.
1) 허용가능한 집합들의 교집합도 허용가능하다 : T=⋂i∈IBi 라 하면 T 도 허용가능하다. 우선 모든 Bi 들이 허용가능하니 각각의 Bi 가 a∈A 를 가지고 있어서, a∈T 이기 때문이다. 두번째로 x∈T 라 하면 모든 i∈I 에 대하여 Bi 는 허용가능하니 모든 i∈I 에 대하여 x∈Bi, f(x)∈Bi 이다. 이는 f(x)∈T 임을 뜻한다. 마지막으로 Q 를 T 의 한 사슬이라고 하자. 각각의 i∈I 에 대하여 T⊆Bi 가 성립하므로 Q 는 각각의 Bi 의 사슬이기도 하다. 즉, 각각의 i∈I 에 대하여 q:=supQ∈Bi 이기 때문에, q=supQ∈T 이다.
2) 허용가능한 집합들의 교집합에서 순서관계를 집합의 포함관계로 부여했을 때 극소원소는 B0 이다 : a∈A 으로 A≠∅ 이므로 B≠∅ 이다. B 의 모든 원소들의 교집합을 B0 라 하자. 이 역시 허용가능하고, 모든 i∈I 에 대하여 B0⊆Bi 이다. 그러면 B0 의 정의에 의해 B0 는 곧 (B,⊆) 의 극소원소다. B0 보다 작은(= 포함관계로서 집합의 크기가 더 작은 = 순서관계가 밀리는) 집합이 존재한다고 가정하면 이는 B0 정의에 모순이다. 이로부터 부분순서집합 (B,⊆) 은 극소원소 B0=⋂Bi∈BBi 을 가진다는 것을 알 수 있다. 그리고 B0 유일하다.[각주:1]
3) B 를 다음과 같이 생각하자 : 집합 B={x∈A∣x≥a} 를 생각하고 a∈A 에 대하여 집합 B 가 허용가능한지 확인하자. a≥a 임은 자명하다. 한편 임의의 x∈B,,a∈A 에 대하여 가정에 주어진 것과 같이 함수 f 를 정의하면 f(x)≥x≥a 가 성립하여, f(x)≥a 이므로 f(x)∈B 가 된다. 이는 f(B)⊆B 를 뜻한다. 또한 S 를 B⊆A 의 사슬이라고 하자. B 의 정의에 의하여 S 의 모든 원소 s 는 s≥a 를 만족해야 하고, 보조정리의 가정에 의해 S 는 A 의 한 사슬이기도 하니 supS∈A 가 존재하며 supS∈B 이기도 하다. 따라서 B 의 사슬의 최소상계가 B 에 속하기도 하니 B 는 허용가능하다. 이상에서 ⊆{x∈A∣x≥a} 가 허용가능하므로, 2)의 내용과 연결하면 B0⊆{x∈A∣x≥a} 이다. 그러면 모든 x∈B0 에 대하여 x≥a 가 성립한다.
이제부터 할 일은 아래에서 정의할 두 집합 C,D 에 대하여 C=D=B0 임을 보이는 것이다. 우선 4)에서 D=B0 를 보이고 5)에서 C=B0 를 보일 것이다. 참고로 C 집합은 f 를 타고 넘어가도 순서관계가 바뀌지 않으니 f 의 상한 역할을 보여주고, D 는 x 를 기준으로 분할의 역할을 담당한다고 볼 수 있다 결과적으로 세 집합이 같음을 보이면 f(p)=p 인 고정점 p 의 존재를 암시한다.
4) 집합 C={x∈B0∣y∈B0∧y<x⇒f(y)≤x} 를 생각하자.
x∈C∧z∈B0⟹z≤x∨z≥f(x)⋯(1) 임을 보이고 싶다. x∈C 를 고정시키고 D={z∈B0∣z≤x∨z≥f(x)} 라 하자. 3)에서 그러면 a∈B0 이고, x≥z=a 로 z 를 택하면 a∈D 가 만족됨을 알 수 있다. 두번째로 f(D)⊆D 를 보여야 하고, 이는 곧 f(z)∈D 임을 의미하는 것이니 f(z)≤x 또는 f(z)≥f(x) 를 뜻한다.
세번째 조건을 확인하라면 E⊆D 가 D 의 사슬이고 u:=supE 라 하자. 그러면 모든 e∈E 에 대해 e≤x 이거나 e≥f(x) 여야 한다. 전자의 경우 y≤x, 후자의 경우 u≥f(x) 가 성립하니 결국 u∈D 이다. 이상에서 D 는 허용가능한데 D 의 정의를 고려하면 이는 B0 의 원소들로 이루어져 있고 이 집합은 2)에서 유일하고 극소임을 보였다. 결국 D=B0 가 성립한다.
5) 3)에서 보인 내용에 의해 모든 y∈B0 에 대해서 반드시 y≥a 이다. 첫째, 만일 '그리고'로 연결된 문장 y∈B0∧y<a 을 고려하면, 이 명제는 거짓이니, 조건문의 가정[각주:2]이 거짓이면 조건문은 참이므로 a∈C 이다. 둘째, f(C)⊆C 를 확인해야 하고 이것은 임의의 x∈C 에 대해 f(x)∈C 인지를 보이는 것과 같다. 확인해야할 것은 결국
y∈B0∧y<f(x)⟹f(y)≤f(x)⋯(2) 인지에 해당한다.
i) y≥f(x) : y<f(x) 가 거짓이다. 위에서와 동일한 논리로 조건문의 가정이 거짓이 된다. 고로 f(x)∈C ii) y≤x : y=x 이면 f(y)=f(x) 가 되니 (2) 가 참이다. y<x 이면 f(y)≤x≤f(x)[각주:3] 이므로, 다시 (2) 가 참이다.
세번째 조건을 확인하자. G⊆C 가 C 의 사슬이고 w:=supG 라 하자. 보이고 싶은 것은 w∈C 이다. 우선 w=supG 이므로 y<w 인 y∈B0 가 존재한다. 이때 우리는 f(y)≤w 임을 보이면 된다. 그런데 3)으로부터 B0=D 임을 알기 때문에 y∈B0=D 이고, 고로 임의의 g∈G 에 대해 y≤g 또는 y≥f(g) 가 성립해야 한다. 후자가 성립하면 y≥f(g)≥g 에서 y≤g 가 성립하고, g=w 는[각주:4] 모순이다. 고로 y≤g 다.
i) y<g : f(g)≤g≤w 이다. 첫째 부등호는 g∈C 이기 때문에, 둘째 부등호는 g∈G 이기 때문에 성립한다.
ii) y=g : y=g<w⟹y<h 인 h∈G 가 존재한다. 그러면 다시 C 의 정의와 w=supG 로부터 f(y)≤z≤w 가 성립한다.
6) 따라서 i),ii) 모두에 y<w⟹f(y)≤w 가 성립하므로 w∈C 이며, 세 조건을 모두 확인한 결과 C 는 허용가능하다. 2) 에서 B0 는 유일하고 극소원소라고 하였으니 B0=C 이다.
여기까지의 관계를 정리하면 B0=C=D 이다. 그러면 (1) 에서 B0 는 전순서집합이다. 허용가능함의 세 번째 조건에서 p:=supB0=supC 가 존재한다. p 가 최소상계이니 p≤f(p) 이어야 한다. 그러나 애초에 함수 f 의 정의에 의하면 f(p)≥p 이다. 고로, f(p)=p 인 p∈B0 가 존재한다. B0⊆A 이니 p∈A 이기도 하다. ◼
정리(S.T) 5.1) 하우스도르프 극대원리(Hausdorff Maximality Principle) 부분순서집합 (A,≤) 의 모든 전순서 부분집합(사슬)들을 원소로 갖는 집합족을 T 라 하고, T 에 부분순서로서 포함관계 ⊆ 가 주어졌다고 하자. 그러면 (T,⊆) 는 극대원소를 가진다.
증명) 귀류법을 사용하기 위해 T 가 극대원소를 가지지 않는다고 가정하자. 그러면 각각의 T∈T 에 대하여 T∗={T′∈T∣T⊂T′} 라는 집합을 정의할 수 있고 T∗≠∅ 이다.[각주:5] 그러면 선택공리에 의하여 다음과 같은 선택함수 g:{T∗∣T∈T}⟶⋃T∈TT∗ 를 g(T∗)∈T∗ 를 만족하도록 잡을 수 있고, 다시 모든 T∈T 에 대하여 f(T):g(T∗) 가 되도록 함수 f:T⟶T 를 생각할 수 있다.
그 다음으로 (T,⊆) 가 공집합이 아닌 부분순서집합이고, 이것의 모든 사슬이 T 내에 최소상계를 가짐을 보이려고 한다. B 를 (T,⊆) 의 임의의 한 사슬이라 하자.[각주:6] 그러면 ⋃B∈BB 는 사슬 B 에 속하는 모든 집합들의 원소로 이루어진 집합[각주:7]으로, B 의 모든 원소들의 합집합이다.
* B 는 사슬이니, 원소가 집합이다. 반면 반복되어 등장하는 ⋃B∈BB 라는 친구는 원소가 모두 집합이 아니다. 사슬 B 를 구성하는 하나 하나의 집합들 Bi 의 원소들을 전부 다 끌어모은 합집합인 것이다. 둘을 잘 구분해서 따라와야 한다.
이때 T 내의 다른 원소 즉 사슬을 생각하고, 그것이 B 를 포함한다고 해보자. 그러면 그 집합 역시 ⋃B∈BB 를 포함할 것이고, 그리하여 ⋃B∈BB⊆⋃C∈CC 이다.[각주:8] 즉 일단 ⋃C∈CC 는 B 에 대한 T 에 속하는 하나의 상계이다. 그러면 최소상계의 정의를 상기할 때, ⋃B∈BB 는 B 에 대한 (포함관계를 순서로 볼 때) 최소상계(상한)가 된다. ⋃B∈BB∈T 가 B 의 최소상계라는 것은 모든 B∈B 에 대하여 B⊆⋃B∈BB 임과 필요충분조건인데 그러하기 때문이다.
고로, ⋃B∈BB∈T 이며 이것은 최소상계이다. 보조정리(S.T) 5.1) 의 가정에서 부분순서집합으로 (T,≤=⊆) 를 생각하면, 이것의 임의의 사슬 B 의 최소상계 ⋃B∈BB 는 T 에 속한다. 그러므로 보조정리의 가정은 모두 만족되었다. 따라서 보조정리에 의하여 f(T)=T 가 되게 하는 어떤 사슬 T∈T 가 존재한다.
그런데, 맨 처음 함수의 정의에 의하여 f(T)=g(T∗) 로 정의하였다. T∗ 는 정의에 의해 T⊂T′ 인 T′ 으로 이루어진 집합이니 T⊂g(T∗)∈⋃T∈TT∗ 이고, 고로 T⊆f(T) 이다. 따라서 윗 문단에서 보조정리를 사용한 결과 f(T)=T 는 이러한 함수 f 가 존재한다는 것에 모순이다. ◼
댓글