順序数と基数はどこが違うのか（整列集合から無限の大小へ）

$1 + ω = ω$ なのに $ω + 1 > ω$ です^[1]。足す順番で答えが変わる。

ところが要素の個数で見ると、どちらも可算無限で同じ。順序数は並べ方を測り、基数は個数を測ります^[2]。同じ $ω$ という記号の後ろに、 $2$ つの物差しが隠れている。

整列集合

全順序集合で、空でないどの部分集合にも最小元があるとき、整列集合といいます^[3]。

$N$ は整列集合です。 $Z$ は最小元がないので違う。 $[0, 1]$ も、 $(0, 1]$ に最小元がないので整列ではありません。

整列だと、超限帰納法が使えます。順に上っていく議論が、無限の先まで届く。

順序型

整列集合には、順序を保つ全単射で移り合うかどうかで分類が入ります。

どの整列集合も、ちょうど $1$ つの順序数と順序同型になる^[1]。この順序数を順序型と呼びます。

${0, 1, 2, \dots}$ の順序型が $ω$ 。 ${0, 1, 2, \dots} \cup {\infty}$ の順序型が $ω + 1$ です。集合としては同じ濃度なのに、順序型が違う。

フォン・ノイマンの順序数

順序数そのものを集合として作る方法があります^[1,3]。推移的で、属する関係 $\in$ で整列される集合を順序数と定める。

推移的とは、要素が同時に部分集合でもあること。この定義だと、各順序数は「それより小さい順序数の全体」になります。

$0 = \emptyset, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}$

$α < β$ を $α \in β$ で定めれば、順序も要素関係だけで決まる。 $ω$ は自然数全体の集合そのものです。

後続と極限

$0$ でない順序数は、 $2$ 種類に分かれます^[3]。

直前の順序数を持つものが後続順序数で、 $S (β) = β \cup {β}$ の形。 $5$ や $ω + 1$ がそうです。

直前を持たないものが極限順序数。自分より小さいものの上限として現れます。 $ω$ が最小の極限順序数です。

$ω$ に直前はありません。どの自然数をとっても、その次がまだ $ω$ より小さい。

ω の先を数える

$ω$ の先にも順序数は続きます^[1]。

$ω, ω + 1, ω + 2, \dots$

$ω \cdot 2, ω \cdot 3, \dots, ω^{2}$

$ω^{ω}, \dots, ε_{0}$

$ε_{0}$ は $ω^{ε_{0}} = ε_{0}$ をみたす最小の順序数です。 $ω$ からベキを重ねる操作では、そこへ届かない。

どれも可算集合の順序型で、濃度はすべて $ℵ_{0}$ のまま。並べ方だけが複雑になっていきます。

足し算が交換しない

順序数の足し算は、整列集合を横につなぐ操作です。つなぐ順番で結果が変わる^[1,3]。

$1 + ω$ は、 $1$ 個の点のうしろに $ω$ の列をつなぐ形。先頭に $1$ 個足しただけなので、全体はやはり $ω$ 型です。

$ω + 1$ は、 $ω$ の列のうしろに $1$ 個をつなぐ形。この最後の点には直前がないので、 $ω$ とは別の順序型になります。

かけ算も同じ事情です。 $2 \cdot ω$ は $2$ 個の組を $ω$ 回並べたもので $ω$ 型、 $ω \cdot 2$ は $ω$ の列を $2$ 本並べたものになります^[1]。

順序数の演算

並べる順番が結果に効く。 $1 + ω \neq = ω + 1$ 、 $2 \cdot ω \neq = ω \cdot 2$

基数の演算

個数しか見ないので順番は効かない。 $1 + ℵ_{0} = ℵ_{0} + 1 = ℵ_{0}$

超限帰納法

順序数の上では、通常の数学的帰納法が延長できます^[1,3]。

$β < α$ のすべてで $P (β)$ が成り立つとき $P (α)$ も成り立つ。これが示せれば、すべての順序数で $P$ が成り立ちます。

証明は最小反例をとる形です。 $P$ が偽になる順序数があれば、その中に最小のものがある。整列性が効くところです。

再帰的な定義も同じ形でできます。 $0$ での値、後続での作り方、極限での上限。 $3$ つを決めれば関数が定まる。

すべての順序数を集めると

順序数を全部集めた $ON$ は集合になりません^[1,3]。ブラリ＝フォルティのパラドックスと呼ばれます。

もし集合なら、それ自身が推移的で $\in$ で整列されるので、順序数になってしまう。すると $ON \in ON$ となり、正則性公理に反します。

$ON$ は真クラスです。順序数はいくらでも大きくなり、上限がない。

基数

濃度を測るほうへ移ります。選択公理があれば、どの集合も整列できるので、対応する順序数がとれる^[2]。

集合 $X$ の基数を、 $X$ と全単射がある最小の順序数と定めます。この形の順序数を始順序数といいます。

$ω$ と $ω + 1$ と $ω^{2}$ はどれも可算ですが、始順序数は $ω$ だけ。だから $∣ ω + 1∣ = ∣ ω^{2} ∣ = ℵ_{0}$ になります。

アレフ

無限の始順序数を小さい順に並べたものが、アレフの列です^[2,4]。

$ℵ_{0}$ が可算無限、 $ℵ_{1}$ がその次、 $ℵ_{2}$ がさらに次。選択公理のもとでは、どの無限基数もアレフのどれかになります。

$ℵ_{1}$ は「 $ℵ_{0}$ より大きい最小の基数」として定義されます。実数の濃度がそれと一致するかどうかは、別の問題です。

基数の演算は退屈

無限基数どうしの足し算とかけ算は、大きいほうを返すだけになります^[2]。

$κ + λ = κ \cdot λ = max (κ, λ)$

$ℵ_{0} + ℵ_{0} = ℵ_{0}$ 、 $ℵ_{0} \cdot ℵ_{0} = ℵ_{0}$ 。有理数全体が可算なのは、この式の言いかえです。

順序数の演算があれほど細かく分かれたのに、基数の演算はほとんど情報を持ちません。

式	順序数として	基数として
$1 + ω$	$ω$	$ℵ_{0}$
$ω + 1$	$ω$ より大きい	$ℵ_{0}$
$2 \cdot ω$	$ω$	$ℵ_{0}$
$ω \cdot 2$	$ω$ より大きい	$ℵ_{0}$

ベキだけは伸びる

足し算とかけ算がつぶれるなかで、ベキだけが基数を大きくします^[4]。

$2^{κ} > κ$

カントールの定理です。 $X$ から $P (X)$ への全射が作れないことから出ます。

だから最大の基数はありません。 $ℵ_{0} < 2^{ℵ_{0}} < 2^{2^{ℵ_{0}}} < \dots$ といくらでも上がっていく。

$2^{ℵ_{0}}$ が実数の濃度で、連続体濃度と呼ばれます。

連続体仮説

$ℵ_{1} = 2^{ℵ_{0}}$ が成り立つか、という問いが連続体仮説です^[2,4]。

$ℵ_{0}$ と $2^{ℵ_{0}}$ のあいだに基数がない、という主張と同じことになります。

ゲーデルとコーエンの仕事によって、ZFC からは証明も反証もできないと分かっています。公理を足すかどうかの選択になる。

連続体仮説が独立でも、 $2^{ℵ_{0}}$ の値がまったく自由なわけではありません。共終数による制約が残ります。

ケーニヒの定理から $κ < κ^{cf (κ)}$ が出るので、 $2^{ℵ_{0}} \neq = ℵ_{ω}$ が言える。 $ℵ_{ω}$ の共終数が $ω$ だからです。

選択公理を外すと

選択公理がないと、整列できない集合が出てきます。そうなると「最小の順序数」で基数を定義できない^[2]。

スコットのトリックで回避できます。 $X$ と対等な集合のうち、階数が最小のものだけを集めて基数と定める。

この集め方なら真クラスにならず、集合として扱えます。選択公理なしでも濃度の言葉が使えるようになる。

ただし、どの $2$ つの基数も比較できるとはかぎりません。比較可能性は選択公理と同値です。

$ω \cdot 2$ と $ω^{2}$ について、正しいものはどれですか。

濃度が違う
順序型は違うが、濃度はどちらも $ℵ_{0}$
順序型も濃度も同じ

__RESULT__

$ω \cdot 2$ は果てのない列が $2$ 本、 $ω^{2}$ は果てのない列が果てなく並ぶ形で、順序型は違います。どちらも可算集合なので濃度は $ℵ_{0}$ です。

よくある誤り

順序数と基数を同じものだと思う。

ω + 1

と

ω

は順序数として違い、基数として同じです。

順序数の足し算が交換すると考える。

1 + ω

と

ω + 1

は別物です。

ω

に直前があると思う。極限順序数には直前がありません。

すべての順序数の集合を作る。真クラスになり、集合にはなりません。

ℵ_{1}

を実数の濃度と決めつける。それが連続体仮説で、証明も反証もできません。

基数のベキも

max

で決まると思う。ベキだけは基数を真に大きくします。

選択公理なしでも基数が全順序になると思う。比較可能性は選択公理と同値です。

順序数を聞かれているのか、基数を聞かれているのか。まずそこを分ける。 $1 + ω$ の答えが $2$ 通りあるように見える混乱は、たいていこのとり違えから出ます。

参考文献

^[1] が順序数の定義・演算・ブラリ＝フォルティのパラドックス、^[2] が基数の定義・アレフ・共終数と連続体仮説、^[3] が整列と超限帰納法の扱い、^[4] がカントールの定理と連続体濃度の位置づけです。

Ordinal number. Wikipedia（英語）.

Cardinal number. Wikipedia（英語）.

Ordinalzahl. Wikipedia（ドイツ語）.

Nombre cardinal. Wikipédia（フランス語）.

$1 + \omega = \omega$ なのに $\omega + 1$ は $\omega$ より大きい。それでも要素の個数はどちらも $\aleph_0$ です。順序数は並べ方を測り、基数は個数を測ります。フォン・ノイマンの定義では、各順序数が自分より小さい順序数の全体になる。後続と極限の区別、$\omega^2$ や $\varepsilon_0$ の並び方、足し算が交換しない理由を図で見ます。基数のほうは足し算もかけ算も $\max$ でつぶれ、ベキだけが伸びる。連続体仮説と共終数による制約、選択公理を外したときのスコットのトリックまで。