집합의 기수

5장에서 집합의 크기를 일대일대응을 통해 비교하는 방법을 살펴보았다. 이 장에서는 집합의 크기를 나타내는 기수(cardinal number)라는 개념을 도입하고, 기수의 연산과 그 성질을 살펴본다. 기수는 원소의 '개수'를 추상화한 개념으로, 유한집합뿐만 아니라 무한집합의 크기도 다룰 수 있게 해준다.

1. 집합의 대등과 기수

두 집합 \(A\)와 \(B\) 사이에 일대일대응이 존재할 때, "\(A\)와 \(B\)가 대등(equipotent)하다"라고 말하며 \(A \sim B\)로 나타낸다. 5장에서 보았듯이 대등 관계는 동치관계이다. 즉, 다음을 만족시킨다.

반사적 성질: \(A \sim A\)
대칭적 성질: \(A \sim B\)이면 \(B \sim A\)이다.
추이적 성질: \(A \sim B\)이고 \(B \sim C\)이면 \(A \sim C\)이다.

집합 \(A\)의 기수(cardinal number) 또는 농도(cardinality)는 \(A\)와 대등한 모든 집합들이 공통으로 갖는 '크기'를 나타내는 개념이다. 집합 \(A\)의 기수를 \(|A|\) 또는 \(\text{card}(A)\)로 나타낸다. \(\# A\)로 나타내기도 한다.

기수를 엄밀하게 다루기 위하여 다음과 같은 기수 공리(axiom of cardinality)를 도입한다.

기수의 모임 \(CD\)가 존재하여, 다음 두 조건을 모두 만족시킨다.

(K1) 임의의 집합 \(A\)에 대하여 \(A \sim a\)인 \(a\in CD\)가 존재한다. 이때 \(a\)를 \(A\)의 기수라고 부르고, \(|A|\)로 나타낸다.
(K2) 두 집합 \(A\)와 \(B\)가 대등할 필요충분조건은 \(|A| = |B|\)이다.

유한집합의 경우 기수는 자연수이다. 예를 들면 다음과 같다.

\(|\varnothing| = 0\)
\(|\{a\}| = 1\)
\(|\{a,\, b\}| = 2\) (단, \(a \neq b\))

그러므로 \(A\)가 유한집합일 때는 \(A\)의 기수를 \(n(A)\)로 나타내도 된다.

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

\(|\mathbb{N}| = \aleph_0\) ('알레프 널' 또는 '알레프 영'이라고 읽는다.)
\(|\mathbb{R}| = \mathfrak{c}\) 또는 \(2^{\aleph_0}\) (알파벳 c와 같은 발음으로 읽는다.)
연속체 가설을 가정하면, \(| E | = \aleph_n\)일 때 \( | \mathcal{P} (E) | = \aleph_{n+1}\)이다.

2. 기수의 대소관계

두 기수 \(\kappa\)와 \(\lambda\)에 대하여, \(|A| = \kappa\)이고 \(|B| = \lambda\)인 집합 \(A\), \(B\)를 택했을 때, \(A\)에서 \(B\)로의 일대일함수가 존재하면 \(\kappa \leq \lambda\)라고 정의한다. 이 정의는 \(A\), \(B\)의 선택과 무관하다.

\(\kappa \leq \lambda\)이고 \(\lambda \leq \kappa\)이면 \(\kappa = \lambda\)이다. (슈뢰더-베른슈타인 정리)
\(\kappa \leq \lambda\)이고 \(\lambda \leq \mu\)이면 \(\kappa \leq \mu\)이다.
임의의 두 기수 \(\kappa\), \(\lambda\)에 대하여 \(\kappa \leq \lambda\)이거나 \(\lambda \leq \kappa\)이다.[선택 공리를 가정했을 때 성립한다.]

특히 \(\kappa < \lambda\)는 \(\kappa \leq \lambda\)이고 \(\kappa \neq \lambda\)임을 의미한다.

3. 기수의 덧셈

두 기수 \(\kappa = |A|\), \(\lambda = |B|\)에 대하여, \(A \cap B = \varnothing\)라고 가정하여도 일반성을 잃지 않는다.[만약 \(A,\) \(B\)가 서로소가 아니라면 \(A ' = A\times \left\{0\right\},\) \(B ' = B\times \left\{ 1\right\}\)와 같이 서로소인 \(A '\) \(B '\)을 사용하여 \(A,\) \(B\)를 대체하면 된다.] 이때 기수의 합을 다음과 같이 정의한다. \[\kappa + \lambda = |A \cup B|\] 이 정의는 \(A\), \(B\)의 선택과 무관하다. 실제로 \(A' \sim A\), \(B' \sim B\)이고 \(A' \cap B' = \varnothing\)이면 \(A' \cup B' \sim A \cup B\)이다.

기수의 덧셈은 다음 성질을 가진다.

교환법칙: \(\kappa + \lambda = \lambda + \kappa\)이다.
결합법칙: \((\kappa + \lambda) + \mu = \kappa + (\lambda + \mu)\)
항등원: \(\kappa + 0 = \kappa\)
단조성: \(\kappa \leq \kappa'\)이고 \(\lambda \leq \lambda'\)이면 \(\kappa + \lambda \leq \kappa' + \lambda'\)

기수의 덧셈의 성질은 기수의 정의와 일대일대응의 성질을 사용하면 증명된다.

문제 7.1. 다음을 증명하시오.

\(n\)이 유한기수일 때, \(\aleph_0 + n = \aleph_0\)
\(\aleph_0 + \aleph_0 = \aleph_0\)
\(\mathfrak{c} + \aleph_0 = \mathfrak{c}\)
\(\mathfrak{c} + \mathfrak{c} = \mathfrak{c}\)

4. 기수의 곱셈

기수의 곱셈은 다음 성질을 가진다.

교환법칙: \(\kappa \cdot \lambda = \lambda \cdot \kappa\)
결합법칙: \((\kappa \cdot \lambda) \cdot \mu = \kappa \cdot (\lambda \cdot \mu)\)
항등원: \(\kappa \cdot 1 = \kappa\)
영원: \(\kappa \cdot 0 = 0\)
분배법칙: \(\kappa \cdot (\lambda + \mu) = \kappa \cdot \lambda + \kappa \cdot \mu\)
단조성: \(\kappa \leq \kappa'\)이고 \(\lambda \leq \lambda'\)이면 \(\kappa \cdot \lambda \leq \kappa' \cdot \lambda'\)이다.

5. 기수의 거듭제곱

기수의 거듭제곱은 다음과 같은 성질을 가진다.

\(\kappa^{\lambda + \mu} = \kappa^\lambda \cdot \kappa^\mu\)
\((\kappa \cdot \lambda)^\mu = \kappa^\mu \cdot \lambda^\mu\)
\((\kappa^\lambda)^\mu = \kappa^{\lambda \cdot \mu}\)
\(\kappa^0 = 1\) (단, \(\kappa \neq 0\))
\(\kappa^1 = \kappa\)
\(1^\lambda = 1\)
\(0^\lambda = 0\) (단, \(\lambda \neq 0\))

특히 중요한 사실은 \(|A| = \kappa\)일 때 \(2^{\kappa} = |\mathcal{P}(A)|\)라는 점이다. 실제로 집합 \(A\)의 부분집합은 특성함수 \(\chi: A \to \{0,\, 1\}\)과 일대일 대응된다.

문제 7.2. 다음을 증명하시오.

유한기수 \(m\), \(n\)에 대하여 기수 연산이 자연수의 연산과 일치함을 보이시오.
\(2^{\aleph_0} = \mathfrak{c}\)임을 보이시오.
\(\aleph_0^{\aleph_0} = \mathfrak{c}\)임을 보이시오.
\(\mathfrak{c}^{\aleph_0} = \mathfrak{c}\)임을 보이시오.

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

무한기수는 유한기수와 다른 특별한 성질을 가진다. 예를 들면, \(\kappa\)가 무한기수이고 \(n\)이 유한기수일 때 다음이 성립한다.

\(\kappa + \kappa = \kappa\)
\(\kappa \cdot \kappa = \kappa\)
\(\kappa + n = \kappa\)
\(\kappa \cdot n = \kappa\) (단, \(n\ne 0\))

또한, \(\kappa\)와 \(\lambda\)가 무한기수일 때 다음이 성립한다. \[\kappa + \lambda = \kappa \lambda = \operatorname{max}\left\{ \kappa ,\, \lambda \right\}.\]

7. 기수 연산의 예

기수의 연산의 성질은 집합의 크기를 다루는 여러 문제에서 활용된다.

대표적인 예로서 실함수의 개수를 세어 보자. \(\mathbb{R}\)에서 \(\mathbb{R}\)로의 모든 함수의 집합의 기수는 다음과 같다. \[|\mathbb{R}^{\mathbb{R}}| = \mathfrak{c}^{\mathfrak{c}} = (2^{\aleph_0})^{2^{\aleph_0}} = 2^{\aleph_0 \cdot 2^{\aleph_0}} = 2^{2^{\aleph_0}} = 2^{\mathfrak{c}}\] 이것은 \(\mathfrak{c}\)보다 큰 기수이다. 즉, 실함수의 개수는 실수의 개수보다 본질적으로 더 많다.

다음으로 연속함수의 개수를 세어 보자. 놀랍게도 \(\mathbb{R}\)에서 \(\mathbb{R}\)로의 연속함수의 개수는 \(\mathfrak{c}\)이다. 즉 유리수의 조밀성과 연속함수의 성질에 의하여 연속함수는 유리수에서의 값으로 완전히 결정되므로, 연속함수의 개수는 기껏해야 \(\mathfrak{c}^{\aleph_0} = \mathfrak{c}\)이다.

문제 7.3. 다음을 보이시오.

가산무한개의 가산집합의 합집합은 가산이다.
\(\mathbb{R}\)의 열린구간들의 개수는 \(\mathfrak{c}\)이다.
\(\mathbb{R}\)에서 \(\mathbb{R}\)로의 단조증가 함수의 개수는 \(\mathfrak{c}\)이다.

문제 7.4. 무한집합 \(A\)에 대하여 \(|A \times A| = |A|\)의 증명을 찾아 보자.

8. 기수와 선택공리

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

또한 무한기수 \(\kappa\)에 대하여 \(\kappa + \kappa = \kappa\)라는 성질도 선택공리를 필요로 한다. 선택공리 없이는 \(\aleph_0 + \aleph_0 = \aleph_0\)조차 증명할 수 없는 모델이 존재한다.

집합과 수리논리 첫걸음 목차 보기

명제와 논리 집합의 개념 다양한 집합의 연산 관계와 함수 유한집합과 무한집합 자연수 집합의 기수 집합의 서수 집합론의 공리 선택 공리 형식논리 명제논리의 개념 명제논리의 건전성과 완전성 일계논리의 구문론 일계논리의 의미론 일계논리의 추론규칙 일계논리의 콤팩트성 페아노 산술 불완전성 정리