基数

概要

定義

基数の概念は、「数を数える」という行為を「集合間の対応関係」へと抽象化することによって定義される。

等濃度と大小関係

2つの集合 $A, B$ の大きさを比較するために、以下の定義を用いる。

基数の比較

等濃度:
$A$ から $B$ への全単射（一対一対応）が存在するとき、$A$ と $B$ の基数は等しいといい、$|A| = |B|$ あるいは $\operatorname{card}(A) = \operatorname{card}(B)$ と書く。
大小関係:
$A$ から $B$ への単射が存在するとき、$|A| \le |B|$ と書く。
さらに、$|A| \le |B|$ かつ $|A| \neq |B|$ であるとき、$|A| < |B|$ と書く。

基数の定義

数学的に厳密には、各集合 $X$ に対して、それと等濃度な集合のクラスを代表する特別な対象（通常は順序数の中で最小のもの）を割り当て、それを $X$ の基数と呼ぶ。
例えば、有限集合 $\{a, b, c\}$ の基数は自然数の $3$ であり、自然数全体の集合 $\mathbb{N}$ の基数は $\aleph_0$（アレフ・ゼロ）という記号で表される。

重要な定理

基数の大小関係が、通常の数の大小関係と同様に「順序」として正しく振る舞うことは自明ではない。以下の定理がその整合性を保証している。

(Schröder-Bernsteinの定理)

任意の集合 $A, B$ について、
$$|A| \le |B| \quad \text{かつ} \quad |B| \le |A| \implies |A| = |B|$$
が成り立つ。
すなわち、互いに相手の中へ単射で埋め込めるならば、両者の間には必ず全単射が存在する。

また、無限の階層が無限に続くことを示す決定的な定理がある。

(Cantorの定理)

任意の集合 $X$ に対して、その冪集合 $\mathcal{P}(X)$ の基数は、元の集合 $X$ の基数よりも真に大きい。
$$|X| < |\mathcal{P}(X)|$$
特に、$2^{\aleph_0} > \aleph_0$ である。

証明には有名な対角線論法が用いられる。この定理により、最大の基数は存在しないことがわかる。

基数の演算

基数同士の和、積、べき乗は、集合演算を通じて定義される。$\kappa = |A|, \lambda = |B|$ （ただし $A \cap B = \emptyset$）とする。

演算規則

和: $\kappa + \lambda = |A \cup B|$
積: $\kappa \cdot \lambda = |A \times B|$ （直積集合の基数）
べき乗: $\kappa^\lambda = |A^B|$ （$B$ から $A$ への写像全体の集合の基数）

無限基数を含む演算は、有限数の直感とは大きく異なる振る舞いをする。

無限基数の吸収律

$\kappa, \lambda$ の少なくとも一方が無限基数であるとき、以下が成り立つ（選択公理を仮定）。

和と積の吸収:
$\kappa \ge \lambda$ ならば、$\kappa + \lambda = \kappa$ かつ $\kappa \cdot \lambda = \kappa$。
特に、$\aleph_0 + \aleph_0 = \aleph_0$ や $\aleph_0 \cdot \aleph_0 = \aleph_0$ が成り立つ。
べき乗の爆発:
和や積とは異なり、べき乗は基数を劇的に増大させる（Cantorの定理より $2^\kappa > \kappa$）。

具体例と階層

無限集合の基数には、よく知られた階層がある。

主な基数

$\aleph_0$（可算無限）:
自然数 $\mathbb{N}$、整数 $\mathbb{Z}$、有理数 $\mathbb{Q}$ の基数。これらはすべて等濃度である。
$$|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| = \aleph_0$$
$\mathfrak{c}$ または $2^{\aleph_0}$（連続体濃度）:
実数 $\mathbb{R}$、複素数 $\mathbb{C}$、無理数の集合、Euclid空間 $\mathbb{R}^n$ の基数。
$$|\mathbb{R}| = |\mathbb{R}^n| = |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0}$$

ここで、「$\aleph_0$ と $2^{\aleph_0}$ の間に中間の基数は存在するか？」という問いが連続体仮説 (CH) である。GödelとCohenにより、この命題は通常の数学の公理系（ZFC）からは証明も反証もできない（独立である）ことが示されている。

順序数との違い

基数とよく似た概念に順序数がある。

順序数: 要素の「並び順」まで区別して数えるもの（1番目, 2番目, ...）。
基数: 順序を忘れて、単に要素の「個数」だけを見るもの。
形式的には、基数は「その濃度を持つ最小の順序数」として定義されることが多い（初期順序数）。例えば、順序数としての $\omega$ は基数としての $\aleph_0$ と同一視される。

基数

概要