집합의 기수

By | Januar 10, 2018

유한집합의 크기는 원소의 개수로 나타낼 수 있다. 하지만 무한집합의 크기는 자연수로 나타낼 수 없다. 대신 '원소의 개수'라는 개념을 확장하여 '기수'를 사용할 수 있다. 기수를 정의하는 방법은 '기수 공리'를 이용하는 공리적 방법과 서수로부터 기수를 정의하는 '구성적 방법'이 있다. 여기서는 구성적 방법을 살펴보자.

1. 기수의 정의

먼저 서수를 이용하여 기수를 정의한다.

정의 1.  집합의 기수.

\(\alpha\)가 서수이고 \(\alpha\)의 임의의 절단(section)이 \(\alpha\)와 대등하지 않을 때 \(\alpha\)를 기수(cardinal number)라고 부른다.

유한집합의 기수를 유한기수라고 부르며 무한집합의 기수를 초한기수 또는 무한기수라고 부른다. 기수의 정의에 의하면 \(0\)과 모든 자연수는 기수이다. 또한 \(\omega\)는 가장 작은 초한기수이다. 반면 \(\omega +1\)은 기수가 아니다. 왜냐하면 \(\omega\)는 \(\omega +1\)과 대등한 절단이기 때문이다.

\(X\)가 집합이라고 하자. \(X\)가 유한집합인 경우에는 \(X\)와 대등한(원소의 개수가 같은) 서수는 단 하나 존재하지만 \(X\)가 무한집합인 경우에는 \(X\)와 대등한 서수가 여러 개 존재한다. 그러한 서수 중 가장 작은 것이 \(X\)의 기수이다. 이것을 서수의 용어로 정의한 것이 정의 1이다. 정의 1이 기수의 정의로서 타당하기 위해서, 즉 기수의 정의가 잘 정의된(well-defined) 것으로 인정받으려면 다음 정리가 필요하다.

정리 2.  기수의 존재성.

임의의 집합 \(X\)에 대하여 \(X\)와 대등한 기수가 유일하게 존재한다.

증명. 정렬 원리에 의하여 \(X\)는 정렬 가능하다. 즉 \(X\)로부터 적당한 서수로의 일대일 대응이 존재한다. \(X\)와 일대일 대응되는 서수 중 가장 작은 것을 \(\alpha\)라고 하자. 그러면 \(\alpha\)는 기수이다. 만약 \(\alpha\)의 절단이 \(\alpha\)와 일대일 대응된다면 그 절단은 \(X\)와도 일대일 대응되므로 \(\alpha\)가 \(X\)와 일대일 대응되는 가장 작은 서수라는 사실에 모순이다.

\(X\)가 두 기수 \(\alpha ,\) \(\beta\) 모두와 각각 일대일 대응된다고 가정하자. 만약 \(\alpha \neq \beta\)라면 \(\alpha\)의 최소성에 의하여 \(\alpha\)는 \(\beta\)의 절단이 되어야 한다. 그러면 \(\beta\)는 자신의 절단과 일대일 대응되므로 기수가 아니다. 즉 \(X\)와 일대일 대응되는 기수는 유일하게 존재한다.

\(X\)가 집합일 때 \(X\)의 기수를 \(\lvert X \rvert\)로 나타내자. [\(X\)의 기수를 \(\# X \) 또는 \(\text{card} X\)로 나타내기도 한다.] 특히 기수는 그 자체로서 집합이므로 \(\alpha\)가 기수이면 \(\lvert \alpha \rvert = \alpha\)이다.

Cantor는 초한기수를 나타내는 방법으로 알레프 기호(aleph notation)를 사용하였다. 알레프 기호는 서수를 초한기수에 대응시키는 함수이며, 다음과 같이 귀납적으로 정의된다. [\(\aleph\)는 알레프(aleph)라고 읽는다.]

  • \(\aleph_{0} := \omega ,\)
  • \(\aleph_{s(\alpha )} := \) (\(\aleph_{\alpha}\)보다 큰 기수 중 가장 작은 기수),
  • \(\lambda\)가 극서수일 때 \(\aleph_{\lambda} := \bigcup_{\beta < \lambda} \aleph_{\beta}\).

서수의 합집합은 서수이므로, 위와 같은 정의에서 \(\aleph_{\lambda}\)는 서수이다. 이제 \(\aleph_{\lambda}\)가 기수라는 사실을 증명해 보자. 결론에 반하여 \(\aleph_{\lambda}\)가 기수가 아니라고 가정하자. 그러면 \(\aleph_{\lambda}\)의 절단 \(C\)와 일대일 대응 \(f : \aleph_{\lambda} \rightarrow C\)가 존재한다. \(\aleph_{\beta}\) 중에서 절단 \(C\)의 원소가 되는 것은 존재하지 않는다. 그러면 \(f\)의 정의역을 \(\aleph_{\beta}\)로 축소시킨 함수는 치역이 \(\aleph_{\beta}\)의 절단인 일대일 함수가 되므로 모순이다. 그러므로 \(\aleph_{\lambda}\)는 기수이다.

\(\omega\)와 \(\aleph_0\) 모두 \(0\)과 모든 자연수의 집합을 나타내는 기호이다. 보통, 자연수를 서수로 여길 때에는 \(\omega\)를 사용하고, 자연수를 기수로 여길 때에는 \(\aleph_0\)을 사용한다. 참고로 \(\aleph_1\)은 최소비가산서수이다.

기수는 서수이기 때문에 다음과 같이 대소비교를 할 수 있다.

\(\lvert X \rvert \leq \lvert Y \rvert\)일 필요충분조건은 \(X\)로부터 \(Y\)로의 일대일 함수가 존재하는 것이다.

또한 \(\lvert X \rvert \leq \lvert Y \rvert\)일 때 \(\lvert X \rvert \subseteq \lvert Y \rvert\)이다. \(\alpha\)와 \(\beta\)가 기수이고 \(f : \alpha \rightarrow \beta\)가 일대일 함수라고 하자. 그러면 \(\alpha\)로부터 \(\beta\)보다 작은 서수로의 일대일 대응이 존재한다. 그러므로 \(\alpha\)는 \(\beta\)보다 크지 않다.

정리 3.  기수의 대소 비교

\(X\)와 \(Y\)가 집합이라고 하자. 만약 \(\lvert X \rvert \leq \lvert Y \rvert\)이고 \(\lvert Y \rvert \leq \lvert X \rvert\)이면 \(\lvert X \rvert = \lvert Y \rvert\)이다.

증명. Schröder–Bernstein 정리에 의하여 성립한다.

모든 기수의 모임을 \(CD\)로 나타내자. 서수와 마찬가지로 \(CD\)는 집합이 아닌 고유클래스이다. 왜냐하면, 만약 \(CD\)가 집합이라면 \(\bigcup CD\) 또한 기수가 되는데, 임의의 \(\alpha \in CD\)에 대하여 \(\alpha < \bigcup CD\)가 되어 모순이기 때문이다.

2. 기수의 연산

모든 기수는 서수이며, 서수의 연산이 이미 정의되어 있으므로 기수의 연산도 자연스럽게 따라간다. 하지만 서수의 연산을 정의했을 때처럼 기수의 연산도 합집합과 카르테시안 곱을 이용하여 정의할 수 있다.

두 기수 \(\alpha ,\) \(\beta\)에 대하여 다음과 같이 정의한다.

  • \(\alpha + \beta := \lvert ( \alpha \times \left\{ 0 \right\} ) \cup ( \beta \times \left\{ 1 \right\} ) \rvert ,\)
  • \(\alpha \cdot \beta := \lvert \alpha \times \beta \rvert ,\)
  • \(\alpha ^{\beta} := \left\lvert \alpha^{\beta} \right\rvert .\)

여기서 마지막 식의 우변은 \(\beta\)로부터 \(\alpha\)로의 모든 함수의 집합의 기수를 나타낸다. 모든 기수는 서수이고, 모든 서수는 집합이기 때문에 이러한 표기법을 사용할 수 있다.

위 정의는 집합을 이용하여 나타낼 수도 있다. 즉 \(A,\) \(B\)가 집합일 때 다음이 성립한다.

  • \(A \cap B = \varnothing\)일 때 \(\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert ,\)
  • \(\lvert A \times B \rvert = \lvert A \rvert \cdot \lvert B \rvert ,\)
  • \(\left\lvert A^B \right\rvert = \lvert A \rvert ^{\lvert B \rvert} .\)

기수의 합, 곱에 대해서 결합법칙, 교환법칙, 분배법칙이 성립하며, 기수의 거듭제곱에 대해서 지수법칙이 성립한다. 하지만 여기서는 이러한 평범한 성질보다는 기수가 가진 독특한 성질을 살펴보자.

정리 4.  초한기수의 합과 곱에 관한 성질.

\(\alpha\)와 \(\beta\)가 기수이고 둘 중 하나 이상이 초한기수이면 다음이 성립한다. \[\alpha + \beta = \max \left\{ \alpha ,\, \beta \right\} \tag{1}\] 특히 \(\alpha\)와 \(\beta\) 중 어느것도 \(0\)이 아니면 다음이 성립한다. \[\alpha \cdot \beta = \max \left\{ \alpha ,\, \beta \right\} \tag{2}\]

증명. \(\alpha\)가 초한기수라고 하자. \[\alpha \cdot \alpha = \alpha \tag{3}\] 임을 보이기만 하면 증명으로서 충분하다. 이 사실을 먼저 증명하자.

만약 \(\beta \leq \alpha\)이면 \(\alpha \times \beta\)로부터 \(\alpha \times \alpha\)로의 일대일 함수가 존재한다. 즉 \[(\alpha \times \left\{ 0 \right\} ) \times (\beta \times \left\{ 1 \right\})\] 로부터 \[(\alpha \times \left\{ 0 \right\}) \cup (\alpha \times \left\{ 1 \right\}) = \alpha \times 2 \] 로의 일대일 함수가 존재한다. 따라서 \[\alpha \cdot \beta \leq \alpha \cdot \alpha ,\quad \alpha + \beta \leq \alpha \cdot \alpha\] 이다. 한편 \(\beta \neq 0\)일 때 명백히 \[\alpha \leq \alpha + \beta ,\quad \alpha \leq \alpha \cdot \beta\] 이다. 그러므로 (3)으로부터 (1)과 (2)를 얻는다.

이제 (3)을 증명하자. \(\mathbb{N} \times \mathbb{N}\)이 가산집합이므로 \(\alpha = \aleph_0\)인 경우는 이미 증명되었다. 직관적으로 이 증명은 다음과 같은 그림으로 표현할 수 있다. \[\begin{array}{cc} (1,\,1) && (1,\,2) && (1,\,3) && (1,\,4) && (1,\,5) & \cdots \\[2pt] &\swarrow&&\swarrow&&\swarrow&&\swarrow&& \\[2pt] (2,\,1) && (2,\,2) && (2,\,3) && (2,\,4) && (2,\,5) & \cdots \\[2pt] &\swarrow&&\swarrow&&\swarrow&&\swarrow&& \\[2pt] (3,\,1) && (3,\,2) && (3,\,3) && (3,\,4) && (3,\,5) & \cdots \\[2pt] &\swarrow&&\swarrow&&\swarrow&&\swarrow&& \\[2pt] (4,\,1) && (4,\,2) && (4,\,3) && (4,\,4) && (4,\,5) & \cdots \\[2pt] &\swarrow&&\swarrow&&\swarrow&&\swarrow&& \\[2pt] (5,\,1) && (5,\,2) && (5,\,3) && (5,\,4) && (5,\,5) & \cdots \\[2pt] \vdots && \vdots && \vdots && \vdots && \vdots & \ddots \end{array}\] 다른 경우의 증명은 비슷하지만 조금 더 복잡하다. 결론에 반하여 (3)이 성립하지 않는다고 가정하자. \(\alpha < \alpha \cdot \alpha\)를 만족시키는 기수 \(\alpha\) 중 가장 작은 것을 택하고 \(P := \alpha \times \alpha\)라고 하자. \(\alpha\)는 서수이므로 \(\alpha\)의 원소 또한 모두 서수이다. \(\beta < \alpha\)인 서수 \(\beta\)에 대하여 \(P\)의 부분집합 \(P_{\beta}\)를 다음과 같이 정의하자. \[P_{\beta} := \left\{ (x,\,y) \in P \,\vert\, x+y = \beta \right\} .\] 위 식에서 \(x+y\)는 서수합이다. 직관적으로, 등식 \(x+y = \beta\)는 위 그림에서, 오른쪽 위로부터 왼쪽 아래로 이어지는 '대각선띠'라고 생각하면 된다.

\(\beta < \alpha\)인 \(\beta\)에 대하여 \(P_{\beta}\)가 \(P\)의 분할을 이룸을 보이자. 명백히 \(P_{\beta}\)들은 쌍마다 서로소이다. \(P_{\beta}\)들의 합집합이 \(P\)와 같음을 보이려면 \(x < \alpha ,\) \(y < \alpha\)일 때 \(x+y < \alpha\)임을 보여야 한다. 그런데 이것은 \(\alpha\)보다 작은 기수들에 대하여 정리가 참이라는 사실로부터 성립한다.

이제 각 대각선띠 \(P_{\beta}\)에 다음과 같은 순서관계를 부여하여 \(P_{\beta}\)가 정렬집합이 되도록 하자. \[(x,\,y) < (x ' ,\, y ' ) \quad \Longleftrightarrow \quad ((x < x ' ) \vee ((x = x ' ) \wedge (y < y ' )))\] 이 순서관계는 \(\alpha \times \alpha\)로부터 유도된 \(P_{\beta}\) 위의 순서관계이므로 정렬이다. 그러므로 \(P\) 위에서 \((x,\,y) < (x ' ,\, y ' )\)일 필요충분조건을 \[((x,\,y) \in P_{\beta}) \wedge ((x ',\, y ' ) \in P_{\gamma}) \,\,\text{when}\,\, \beta < \gamma\] 또는 \[(x,\,y) < (x ' ,\, y ' ) \,\,\text{within}\,\, P_{\beta}\] 인 것으로 정의하면 \(P\)는 이 순서관계에 의하여 정렬집합이 된다.

\(\theta\)가 \(P\)와 순서동형인 유일한 서수라고 하자. \(\lvert P \rvert > \alpha\)라는 가정으로부터 \(\theta > \alpha\)를 얻는다. 따라서 점 \((u,\,v) \in P\)가 존재하여 절단 \(P_{(u,\,v)}\)가 \(\alpha\)와 순서동형이 된다. \((u,\,v) \in P_{\beta}\)라고 가정하자. 즉 \(u+v = \beta\)라고 가정하자. 그러면 \((x,\,y) < (u,\,v)\)인 모든 점 \((x,\,y) \in P\)는 \(x+y \leq \beta\)를 만족시키며, \(x \leq \beta\) 그리고 \(y \leq \beta\)가 성립한다. 따라서 \(P\)의 절단은 \(s(\beta ) \times s(\beta )\)에 포함된다. 그러므로 다음을 얻는다. \[ \lvert s(\beta ) \times s(\beta ) \rvert \geq \alpha > \lvert s(\beta ) \rvert .\] 그런데 \(s(\beta ) < \alpha\)이므로 위 부등식은 모순이다. 그러므로 (3)이 성립한다.

위 정리에 의하면 \(\alpha\)가 초한기수일 때 \(\alpha\)를 \(\alpha\)개 또는 그 이하 개수 만큼 합집합하는 방법으로는 더 큰 기수를 만들 수 없다. 하지만 다음 정리에서 보는 바와 같이, 거듭제곱의 경우에는 더 큰 기수를 만들 수 있다.

정리 5.  초한기수의 거듭제곱에 관한 성질.

(a) \(X\)가 집합일 때 \(\lvert \mathcal{P} X \rvert = 2^{\lvert X \rvert} .\)

(b) \(\lvert \mathbb{R} \rvert = 2^{\aleph_{0}} .\)

증명. (a) \(\mathcal{P} X\)로부터 \(2^{X}\)로의 일대일 대응을 구성하자. \(\mathcal{P} X\)는 \(X\)의 멱집합이고, \(2^{X}\)는 \(X\)로부터 \(2 = \left\{0,\,1\right\}\)로의 모든 함수들의 모임임을 염두에 두자. \(X\)의 부분집합 \(Y\)에 대하여 특성함수는 다음과 같이 정의된 함수이다. \[\chi_{Y} (x) := \begin{cases} 1 & \quad \text{if} \,\, x\in Y \\[8pt] 0 & \quad \text{if} \,\, x\notin Y \end{cases} \] 이때 각 \(Y \in \mathcal{P} X \)를 \(\chi_{Y}^{-1}(\left\{ 1 \right\} )\)에 대응시키는 함수 \(F : X \rightarrow 2\)는 일대일 대응이다.

(b) \(\mathbb{R}\)의 기수는 열린구간 \((0,\,1)\)의 기수와 같다. 왜냐하면 \(f(x) = \tan \pi (x- \frac{1}{2} )\)로 정의된 함수 \(f\)는 두 집합 사이의 일대일 대응이기 때문이다. 또한 \(2^{\mathbb{N}}\)의 원소는 각 항이 \(0\) 또는 \(1\)인 무한수열이다. 이때 이 무한수열의 \(k\)번째 항을 소수점 이하 \(k\)번째 자리의 숫자로 생각하고, 정수부분은 \(0\)인 이진소수는 \(0\)과 \(1\) 사이의 수를 나타낸다. 이러한 대응은 \(2^{\mathbb{N}}\)으로부터 \((0,\,1)\)로의 일대일 함수이다.

반대방향으로는, \((0,\,1)\)에 속하는 각 수를 이진법으로 나타내되, 나타낸 이진소수가 유한소수인 경우에는 소수점 아래 처음으로 나타는 \(1\)을 \(0\)으로 바꾸고 그 이하 숫자는 모두 \(1\)로 바꾼다. 이 이진소수를 소수점 이하 \(k\)번째 자리 숫자를 \(k\)째 항으로 갖는 수열에 대응시키면 \((0,\,1)\)로부터 \(2^{\mathbb{N}}\)으로의 일대일 대응을 얻는다. 그러므로 Schröder–Bernstein 정리에 의하여 (b)가 성립한다.

멱집합에 대한 Cantor의 정리를 기수로 나타내면 다음과 같다.

정리 6.  Cantor의 정리.

\(\alpha\)가 기수일 때 \(2^{\alpha} > \alpha\)이다.

자연수의 거듭제곱에 대한 지수법칙과 마찬가지로 기수의 거듭제곱에 대한 지수법칙 \((\alpha^{\beta}) ^{\gamma} = \alpha^{\beta \cdot \gamma}\)가 성립한다. 이 사실로부터 다음 정리를 얻는다.

정리 7.  기수의 거듭제곱에 관한 성질.

\(\alpha\)와 \(\beta\)가 기수라고 하자. 만약 \(\alpha\)가 초한기수이고 \(2 \leq \beta \leq 2^{\alpha}\)이면 \(\beta^{\alpha} = 2^{\alpha}\)가 성립한다.

증명. 지수법칙과 Cantor의 정리에 의하여 다음이 성립한다. \[2^{\alpha} \leq \beta^{\alpha} \leq (2^{\alpha} )^{\alpha} = 2^{\alpha \cdot \alpha} = 2^{\alpha}\] 그러므로 Schröder–Bernstein 정리에 의하여 \(\beta^{\alpha} = 2^{\alpha}\)이다.

3. 연속체 가설

Cantor의 정리에 의하면 임의의 서수 \(\alpha\)에 대하여 \[2^{\aleph_{\alpha}} \ge \aleph_{s(\alpha )}\] 이다. 이 부등식에서 등호가 성립하는 경우가 있을까? 20세기 초 수학자들은 \[2^{\aleph_0} = \aleph_1\] 이라고 예측했는데, 이러한 예측을 연속체 가설(CH: Continuum Hypothesis)이라고 부른다. 연속체 가설은 1900년에 Hilbert가 20세기 해결 과제로서 제시한 미해결 문제 중 하나였다. 1940년 Gödel은 연속체 가설이 ZF 공리계ZFC 공리계에서 반증될 수 없음을 증명하였다. [즉 ZFC+CH가 무모순임을 증명하였다.] 그리고 1963년 Cohen은 강제하기(forcing)라는 방법을 통해 \(2^{\aleph_0} = \aleph_{2}\)가 성립하는 ZFC 모델을 만듦으로써, ZFC가 무모순일 때 연속체 가설이 ZFC 공리계에서 증명될 수 없음을 증명하였다. [즉 ZFC+¬CH가 무모순임을 증명하였다.] 요컨대 연속체 가설은 ZFC 공리계와는 독립적인 문장이다.

연속체 가설을 일반화하여, 임의의 서수 \(\alpha\)에 대하여 \[2^{\aleph_{\alpha}} = \aleph_{s(\alpha )}\] 가 성립할지 여부를 생각할 수 있다. 이 가설을 일반 연속체 가설(GCH: Generalized Continuum Hypothesis)이라고 부른다. 연속체 가설과 마찬가지로 일반 연속체 가설도 ZFC 공리계와는 독립적이다. 한편 Sierpiński는 ZF에 GCH를 추가한 공리계에서 선택 공리가 유도됨을 보였다. 즉 \[\text{ZF + GCH} \,\, \vdash \,\, \text{AC}\]이다.

끝으로 기수를 이용하여 표현한 Löwenheim–Skolem 정리를 소개한다.

정리 8.  위쪽 방향 Löwenheim–Skolem 정리.

\(\varSigma\)가 일계논리언어 \(\mathcal{L}\)에서의 문장들의 집합이라고 하자. 만약 \(\varSigma\)가 무한 모델을 가지면 \(\alpha \ge \lvert \mathcal{L} \rvert\)인 임의의 기수 \(\alpha\)에 대하여, 기수가 \(\alpha\)인 \(\varSigma\)의 모델이 존재한다.

증명. 일계논리에 대한 위쪽 방향 Löwenheim-Skolem 정리에 의하여 성립한다.

기수의 성질은 서수의 성질과 동일한 것도 있지만 다른 것도 많다.
거울 속 내 모습이 나와 같지만 다른 것처럼.
What a Looking-Glass!

Schreibe einen Kommentar