집합의 기수

5장에서 집합의 크기를 일대일대응을 통해 비교하는 방법을 살펴보았다. 이 장에서는 집합의 크기를 나타내는 기수(cardinal number)를 도입하고, 기수의 대소관계와 연산을 살펴본다. 기수는 유한집합의 원소 수를 무한집합까지 확장한 개념이다.

1. 집합의 대등과 기수

5장에서 사용한 표기를 다시 쓰면, 두 집합 \(A\)와 \(B\) 사이에 일대일대응이 존재할 때 \[A\sim B\] 로 나타낸다. 대등은 동치관계이며, 문제 4.16에서 이를 확인하였다.

여기서 “대등류”라는 말은 모든 대등한 집합들을 하나의 집합으로 모은다는 뜻이 아니다. 모든 집합을 대상으로 하는 대등류는 일반적으로 집합이 아니라 고유류가 되므로, 이 장에서는 위의 동치만을 기수에 관한 기본 원리로 사용한다. 공리적 집합론에서는 기수를 실제 집합으로 표현하는 방법을 별도로 마련할 수 있다.

유한집합의 경우 기수는 자연수와 일치한다. 예를 들면 \[|\varnothing|=0,\quad |\{a\}|=1,\quad |\{a,b\}|=2\quad(a\ne b)\] 이다. 따라서 \(A\)가 유한집합일 때는 \(|A|=n(A)\)로 생각할 수 있다.

자주 사용하는 무한집합의 기수는 다음과 같이 나타낸다.

• \(|\mathbb N|=\aleph_0\)이다. \(\aleph_0\)는 ‘알레프 영’ 또는 ‘알레프 널’이라고 읽는다.
• \(|\mathbb R|=\mathfrak c\)이다. 문제 5.14에 의해 \[\mathfrak c=|\mathcal P(\mathbb N)|=2^{\aleph_0}\] 이다.

선택공리를 가정하면 5장에서 다룬 연속체 가설은, 서수를 이용하여 \(\aleph_1\)을 정의한 뒤에는 \(2^{\aleph_0}=\aleph_1\)로 나타낼 수 있다.

한편 연속체 가설을 일반화하여, 모든 알레프 기수에 대하여 멱집합 연산이 바로 다음 알레프 기수가 된다는 주장을 일반 연속체 가설(Generalized Continuum Hypothesis, GCH)이라고 부른다.

2. 기수의 대소관계

이 정의는 대표 집합의 선택에 의존하지 않는다. 실제로 \(A\sim A'\), \(B\sim B'\)이고 \(f\colon A\to B\)가 일대일함수이면, 일대일대응 \(u\colon A'\to A\), \(v\colon B\to B'\)를 택하여 \(v\circ f\circ u\colon A'\to B'\)를 얻는다.

임의의 두 기수 \(\kappa\), \(\lambda\)에 대하여 항상 \(\kappa\le\lambda\) 또는 \(\lambda\le\kappa\)가 성립한다는 명제를 기수의 비교가능성(cardinal comparability)이라고 한다. 이 명제는 선택공리와 동치이며, 따라서 선택공리를 사용하지 않는 ZF에서는 임의의 두 기수를 항상 비교할 수 있다고 가정해서는 안 된다.

3. 기수의 덧셈

두 집합 \(A\), \(B\)의 서로소 합을 \[A\sqcup B=(A\times\{0\})\cup(B\times\{1\})\] 로 나타내자. 두 부분은 항상 서로소이다.

\(A\sim A'\), \(B\sim B'\)이면 각 일대일대응을 두 태그 위에서 따로 적용하여 \(A\sqcup B\sim A'\sqcup B'\)를 얻으므로 이 정의는 대표 집합의 선택과 무관하다.

4. 기수의 곱셈

\(A\sim A'\), \(B\sim B'\)이면 두 일대일대응을 성분별로 적용하여 \(A\times B\sim A'\times B'\)를 얻으므로 이 정의도 대표 집합의 선택과 무관하다.

5. 기수의 거듭제곱

\(A\sim A'\), \(B\sim B'\)이면 일대일대응 \(u\colon A\to A'\), \(v\colon B'\to B\)에 대하여 \[f\longmapsto u\circ f\circ v\] 는 \(A^B\)에서 \((A')^{B'}\)로 가는 일대일대응이므로 이 정의도 잘 정의된다.

\(2=|\{0,1\}|\)로 두면 임의의 집합 \(A\)에 대하여 부분집합 \(S\subseteq A\)와 특성함수 \[ \chi_S\colon A\to\{0,\,1\},\quad \chi_S(a)= \begin{cases} 1 & (a\in S),\\[5pt] 0 & (a\notin S) \end{cases} \] 가 일대일로 대응한다. 따라서 \(|A|=\kappa\)이면 \[2^\kappa=|\mathcal P(A)|\] 이다. 정리 5.3의 칸토어의 정리에 의해 항상 \(\kappa<2^\kappa\)이다.

6. 무한기수의 특별한 성질

이 절의 일반 명제에서는 선택공리를 가정한다. 선택공리 아래에서는 모든 무한기수 \(\kappa\)와 모든 양의 유한기수 \(n\)에 대하여 \[ \kappa+\kappa=\kappa,\quad \kappa\cdot\kappa=\kappa,\quad \kappa+n=\kappa,\quad \kappa\cdot n=\kappa \] 가 성립한다. 더 일반적으로 다음 정리를 얻는다.

이 정리의 일반적인 증명에는 선택공리와 무한집합의 정렬가능성을 사용하는 논의가 필요하므로 10장에서 다시 다룬다. 다만 \(\aleph_0+\aleph_0=\aleph_0\)과 \(\aleph_0\cdot\aleph_0=\aleph_0\) 같은 특정한 등식은 선택공리 없이도 명시적인 일대일대응으로 증명할 수 있다.

7. 기수 연산의 예

기수의 연산은 함수들의 집합의 크기를 세는 데 유용하다. 먼저 \(\mathbb R\)에서 \(\mathbb R\)로 가는 모든 함수들의 집합을 생각하자. 부분집합 \(S\subseteq\mathbb R\)마다 특성함수 \(\chi_S\colon\mathbb R\to\{0,1\}\subseteq\mathbb R\)를 대응시키면 \[2^{\mathfrak c}\le|\mathbb R^{\mathbb R}|\] 이다. 반대로 함수는 그 그래프로 결정되므로 \[\mathbb R^{\mathbb R}\preccurlyeq\mathcal P(\mathbb R\times\mathbb R)\] 이고, 정리 5.2에 의해 \(\mathbb R\times\mathbb R\sim\mathbb R\)이다. 따라서 \[|\mathbb R^{\mathbb R}|=2^{\mathfrak c}.\] 칸토어의 정리에 의해 이는 \(\mathfrak c\)보다 큰 기수이다.

다음으로 연속함수들의 집합을 생각하자. 연속함수 \(f\colon\mathbb R\to\mathbb R\)는 조밀한 부분집합 \(\mathbb Q\)에서의 값에 의하여 완전히 결정된다. 따라서 문제 7.7의 (4)에 의해 연속함수의 개수는 많아야 \[|\mathbb R^{\mathbb Q}|=\mathfrak c^{\aleph_0}=\mathfrak c\] 이다. 한편 상수함수만 해도 \(\mathfrak c\)개 있으므로, 연속함수의 개수는 정확히 \(\mathfrak c\)이다.

8. 기수와 선택공리

기수의 비교가능성, 즉 임의의 두 기수 \(\kappa\), \(\lambda\)에 대하여 \(\kappa\le\lambda\)이거나 \(\lambda\le\kappa\)라는 명제는 선택공리와 동치이다. 이는 10장에서 다룰 정렬 정리와도 동치이다.

선택공리를 가정하면 정리 7.10과 같이 모든 무한기수의 합과 곱을 매우 간단하게 계산할 수 있다. 그러나 선택공리가 없으면 이러한 명제를 임의의 무한집합에 일괄적으로 적용할 수 없다. 예를 들어 ZF만으로는 “모든 무한집합 \(A\)에 대하여 \(|A\times A|=|A|\)”임을 증명할 수 없다. 또한 각 \(A_n\)이 가산집합이라는 사실만으로 \(\bigcup_{n\in\mathbb N}A_n\)이 가산이라고 결론 내리는 명제에는 가산선택공리(countable choice)의 한 형태가 관여한다. 문제 7.9의 (1)에서는 각 \(A_n\)의 단사함수 \(i_n\)을 함께 주어 이 선택 문제를 피하였다. 반면 \[\aleph_0+\aleph_0=\aleph_0,\quad \aleph_0\cdot\aleph_0=\aleph_0\] 은 자연수에 대한 명시적인 일대일대응으로 ZF에서도 증명된다.