집합론의 선택 공리

By | Dezember 21, 2017

선택 공리는 Zermelo-Fraenkel 집합론의 공리 중에서 가장 논란이 많았던 공리이다. 공리적 집합론이 발달하기 시작한 20세기 초에는 선택 공리를 다른 공리로부터 증명하기 위하여 많은 수학자들이 노력하였으나, 이후 선택 공리는 ZF와는 독립적임이 밝혀졌다. 오늘날 선택 공리는 수학의 여러 분야에서 필수적인 것으로 받아들여지고 있다.

이 포스팅에서는 선택 공리와 동치인 정렬 원리와 Zorn의 보조 정리를 살펴본다. 먼저 선택 공리는 다음과 같은 공리이다.

선택 공리 (AC: Axiom of Choice)
\(F : X \rightarrow Y\)가 함수이고 임의의 \(x\in X\)에 대하여 \(F(x) \neq \varnothing\)이면 함수 \(f : X \rightarrow \cup Y\)가 존재하여 임의의 \(x\in X\)에 대하여 \(f(x) \in F(x)\)를 만족시킨다.

\((X ,\, < )\)가 순서집합라고 하자. 만약 \(X\)의 공집합 아닌 임의의 부분집합이 최소원소를 가지면 \((X ,\, < )\)를 정렬집합(well-ordered set)이라고 부르며, 이때 \(X\)에 주어진 순서관계 \( < \)를 정렬(well-order)이라고 부른다. \(X\)가 집합이고 \(X\)에 적당한 순서관계 순서관계 \( < \)를 부여하여 \((X ,\, < )\)가 순서집합이 되도록 할 수 있으면 \(X\)는 정렬 가능하다고 말한다.

정렬 원리 (WO: Well-Ordering Principle)
임의의 집합은 정렬 가능하다.

\((X,\, < )\)가 순서집합이라고 하자. 이때 \(Y\)가 \(X\)의 사슬(chain)이라 함은 \(Y \subseteq X\)이고 \(Y\)가 \(X\)에 주어진 순서관계에 따라 전순서집합이 되는 것을 의미한다. (\(Y\)의 임의의 원소 \(x,\) \(y\)에 대하여 \(x\leq y\) 또는 \(y\leq x\) 중 하나 이상이 반드시 성립할 때 \(x,\)와 \(y\)는 비교 가능하다(comparable)고 말하는데, \(Y\)가 전순서집합이라 함은 \(Y\)의 임의의 두 원소가 비교 가능하다는 것을 뜻한다.) \(C\)가 순서집합 \(X\)의 부분집합이고 \(x \in X\)일 때, \(x\)가 \(C\)의 상계(upper bound)라는 것은 임의의 \(c \in C\)에 대하여 \(c \leq x\)가 성립하는 것을 뜻한다.

Zorn의 보조정리 (ZL: Zorn's Lemma)
\((X ,\, < )\)가 순서집합이고 \(X\)의 임의의 사슬이 상계를 가지면 \(X\)는 극대원소를 가진다.

우리가 증명할 내용은 이들 세 진술이 서로 동치라는 것이다.

정리. (AC), (WO), (ZL)은 서로 동치이다.

증명. [(WO) ⇒ (AC)의 증명] (WO)가 성립한다고 가정하고, \(F : X \rightarrow Y\)가 임의의 \(x\in X\)에 대하여 \(F(x) \neq \varnothing\)을 만족시킨다고 가정하자. \(\cup Y\)에 정렬을 부여하고, \(F(x)\)의 최소원소를 \(f(x)\)라고 하자. 그러면 \(f\)는 \(F\)의 선택 함수(choice function)이다. 그러므로 (AC)가 성립한다.

[(AC) ⇒ (ZL)의 증명] \((X,\, < )\)가 공집합이 아닌 순서집합이고 \(X\)의 임의의 사슬이 상계를 가진다고 하자. 그리고 \(X\)가 극대원소를 갖지 않는다고 가정하자. 임의의 사슬이 상계를 가진다는 가정으로부터 \(X \neq \varnothing\)을 얻는다. 이제 서수들을 \(X\)의 원소에 대응시키는 함수 \(H\)를 다음과 같이 구성하자.

  • \(H(0) = f(X)\)
  • \(H(s( \alpha )) = f(\left\{ x \in X \,\vert\, x > H( \alpha ) \right\} )\)
  • \(H(\lambda ) = f(Y)\)  (단, \(Y\)는 \(H[\lambda ]\)의 모든 상계의 모임)

\(X \neq \varnothing\)이므로 첫 번째 조건은 유효하다. 다음으로, 만약 \(\left\{ x\in X \,\vert\, x>H(\alpha )\right\}\)가 공집합이라면 \(H(\alpha )\)는 \(X\)의 극대원소가 되어 가정에 모순이므로 두 번째 조건도 유효하다. 끝으로 \(\alpha < \beta\)일 때 \(H(\alpha ) < H(\beta )\)가 되어 \(H[ \lambda ]\)가 사슬이 되므로 세 번째 조건도 유효하다.

그러므로 모든 서수를 \(X\)의 원소에 대응시키는 일대일 함수가 존재한다.

[(ZL) ⇒ (WO)의 증명] Zorn의 보조정리가 성립한다고 가정하자. \(X\)가 집합이라고 하자. \(X\)가 정렬 가능함을 보여야 하는데, 그와 동치인 조건으로서 \(X\)와 서수 사이의 일대일 대응이 존재함을 보여도 된다. \(X ' \subseteq X\)이고 \(f '\)가 \(X '\)으로부터 서수로의 일대일 대응이 되는 쌍 \((X ' ,\, f ')\)들의 모임을 \(\mathcal{F}\)로 나타내자. \(\mathcal{F}\) 위에서의 관계 \(\leq\)를 다음 두 조건을 모두 만족시키는 것으로 정의하자.

  • \(X ' \subseteq X ' ' \)
  • 임의의 \(x\in X ' \)에 대하여 \( f ' (x) = f ' ' (x)\)

함수를 순서쌍들의 모임으로 생각하면 \(f ' \subseteq f ' '\)이 성립한다. 따라서 \(\leq\)는 \(\mathcal{F}\)의 순서관계이다.

이제 Zorn의 보조정리의 가정이 만족됨을 보이자. 즉 임의의 사슬이 상계를 가짐을 보이자. \(\mathcal{C}\)가 사슬이라고 하자. 그리고 \(f\)가 \(\mathcal{C}\)의 원소들의 합집합이라고 하자. \(f\)가 \(x\)의 부분집합으로부터 서수로의 함수임을 보이면 된다. 서로 다른 순서쌍 \((x,\,y ' )\)가 \((x,\, y ' ' )\)이 \(f\)에 속하도록 하는 \(x\)가 존재할 때에만 \(f\)는 함수가 아닌 집합이 된다. 이것은 \(\mathcal{C}\)의 두 함수 \(f ' \)과 \(f ' ' \)에 대하여 \(f ' (x) = y ' \)과 \(f ' ' (x) = y ' ' \)이 성립함을 의미한다. 그러나 \(\mathcal{C}\)가 사슬이므로 \(f ' \)와 \(f ' ' \)은 비교 가능하다. 즉 두 함수 중 하나는 다른 하나보다 더 작다. 여기에서 두 함수의 역할을 바꾸어 생각할 수 있으므로 결과적으로 \(f ' (x) = f ' ' (x)\)를 얻는다. 이제 \(f\)의 치역은 \(\mathcal{C}\)의 원소들의 치역의 합집합이고, \(\mathcal{C}\)의 원소의 치역은 서수이므로 \(f\)의 치역도 서수이다. 그러므로 \((X,\,f)\)는 \(\mathcal{F}\)의 원소이며, 우리가 바라던 대로 사슬의 상계이다.

가정인 Zorn의 보조정리에 의하여 극대원소 \((X_0 ,\, f_0 )\)이 존재한다. 이제 \(X_0 = X\)임을 보이자. 만약 \(X_0 \neq X\)라면 \(x \in X \backslash X_0 \)을 택한다. \(f_0\)의 치역을 \(\alpha\)라고 하고, \(X_1 = X_0 \cup \left\{ x \right\},\) \(f_1 = (x,\, \alpha )\)라고 정의하자. 달리 말하면 \(f_0\)을 확장하여 \(x\)로부터 \(\alpha\)로의 함수로 만드는 것이다. 그러면 \(f_0 < f_1\)이 성립하는데, 이것은 \(f_0\)이 극대원소라는 사실에 모순이다. 그러므로 \(f_0\)은 \(X\)로부터 서수로의 일대일 대응이다.

19세기에 이루어진 위대한 지적 성과 중 하나는 비유클리드 기하학을 발전시킨 것이다. 유클리드가 세심한 관찰과 고찰 끝에 유클리드 기하학을 만들어낸 후 약 2천 년이 지나서야 그것을 대체할만한 기하학이 나타난 것이다. 더욱이 유클리드 기하학에서 자명하게 참이라고 여겨졌던 정리들이 더이상은 참임을 보장받지 못하게 되었다. 수학자들은 정리란 공리로부터 시작하여 추론 규칙에 따라 얻어지는 결과임을 깨달았으며, 공리의 집합이 달라지면 얻어지는 결과 또한 달라질 수 있다는 사실을 인정하게 되었다. 이제 자연과학자들에게는 우리가 사는 세계를 기술하기에 가장 적합한 기하학을 선택해야 하는 문제가 안겨졌다. Einstein은 일반상대성이론을 기술하기 위하여 Riemann에 의하여 만들어진 기하학을 선택하였다.

수학자들은 ZFC 집합론을 대신할 수 있는 집합론의 공리를 찾는 문제를 마주하게 되었다. 공리는 우리가 살고 있는 현실을 기술하기 위한 모델뿐만 아니라 수학자들이 수학의 체계를 만들 때 사용하는 모델을 기술한다. 선택공리로부터 자연스러운 결과(예컨대, 임의의 벡터공간은 기저를 가진다)와 부자연스러운 결과(예컨대, 실수집합의 비가측 부분집합이 존재한다) 모두를 얻어낼 수 있다. 이러한 결과들은 집합에 대한 직관적 사고만으로는 얻어질 수 없다.

집합론에서 정렬 원리나 Zorn의 보조정리와 같이 선택 공리를 대체하는 동치인 공리를 사용할 수 있다. 그러나 선택 공리를 그보다 더 약한 공리, 예컨대 명제논리의 긴밀성과 같은 공리로 대체할 수도 있다. 한편, 선택 공리를 이용하면 임의의 환(ring)이 극대 아이디얼을 가짐을 보일 수 있다. Wilfrid Hodges는 ZF에서 그 역이 성립함을 보였다. 즉 "단위원을 갖는 임의의 환은 극대 아이디얼을 가진다"라는 문장으로부터 선택 공리를 얻을 수 있다. '환'이라는 범위를 축소하여 더 약한 조건을 얻을 수도 있다. 예컨대 "임의의 Bool 환은 극대 아이디얼을 가진다"라는 문장은 명제논리의 긴밀성과 동치이다.

선택 공리보다 더 강한 공리를 사용할 수도 있다. Martin의 공리Jensen의 다이아몬드를 그 예로 들 수 있다.

선택 공리를 없애고 그와는 아예 다른 공리를 사용할 수도 있다. 예컨대 결정 공리(AD: Axiom of Determinacy)는 "비기는 것을 허용하지 않는 두 사람의 경기에서 특정한 사람이 반드시 이기는 전략을 가진다"는 공리이다. 이 공리가 ZF에 추가되면 "실수 집합의 임의의 부분집합은 가측이다"와 같이 ZFC에서와는 다른 정리를 얻는다.

ZFC에서 선택 공리가 아닌 다른 공리를 대체하는 집합론도 생각할 수 있다. Jon Barwise와 Lawrence Moss는 그들의 책 『On the Mathematics of Non-Wellfounded Phenomena』에서 반정칙성 공리(Anti-Foundation Axiom)를 소개하였다.

ZFC에서 무한 공리만 성립하지 않는 유한 집합론(finite set theory)의 모델을 구성할 수도 있다. \(S\)가 \(0\)과 모든 자연수를 원소로 갖는 집합이라고 하자. \(S\)에서 관계 \(\in\)을 다음과 같이 정의한다. 주어진 자연수 \(n\)에 대하여, 이 수를 이진법의 전개식 즉 \(2\)의 서로 다른 거듭제곱들의 합으로 나타낸다. \[n = 2^{m_1} + 2^{m_2} + \cdots\] 이고, \(m_1 ,\) \(m_2 ,\) \(\cdots\)는 음이 아닌 서로 다른 정수이다. 이제 \(x\in n\)일 필요충분조건을 \(x = m_i\)인 \(i\)가 존재하는 것으로 정의한다. 그러면 관계 \(\in\)이 주어진 집합 \(S\)는 무한 공리를 제외한 ZFC의 모든 공리를 만족시킨다.

Schreibe einen Kommentar