基数
数学において基数(きすう、cardinal number または cardinal)とは、集合の濃度(cardinality、大きさ、サイズ)を測るために定義された自然数の一般化である。有限集合の濃度つまり有限集合の要素の個数は自然数で表される。無限集合の濃度が一つではないことはゲオルク・カントールによって示された。
基数は、集合論で活発に研究されている。また、組合せ論や抽象代数学、解析学を含めた数学の各分野の道具としても使われる。圏論では、基数は集合の圏の骨格 (圏論) を形成する。
濃度は、集合論の創始者であるゲオルク・カントールによって定式化された。濃度は、集合の一側面を比べるのに用いられる。例えば、{1, 2, 3} と {4, 5, 6} という集合は等しくない。しかし、({1→4, 2→5, 3→6}という一対一の対応の存在によって確立された)3という同じ“濃度"を持っている。
カントールは、一対一対応という概念を無限集合に適用することで濃度を定義した。自然数全体からなる集合Nとの間に一対一対応が存在する集合を可算無限集合といい、可算無限集合は同じ基数\aleph_0(アレフ・ゼロ)を持つ。カントールは、このような無限集合に対応する基数を超限基数 (transfinite cardinal) と呼んだ。
カントールは、直観に反するかもしれないが、Nのいかなる非有界部分集合もNと同じ濃度を持つということを証明した。また、Nの直積N×Nも可算無限であるということを証明した(これは有理数全体からなる集合が可算無限であることを直ちに導く)。また、後に代数的数全体からなる集合も可算無限であることも証明した。
カントールは1874年の論文 において、Nの濃度より実数全体の集合の濃度のほうが真に大きいということを示すことによって、高階の基数が存在することを示した。彼の証明は、区間縮小法を用いた複雑な論法であった。しかし、1891年の論文 では、同じことを巧妙かつ簡潔な対角線論法という方法を用いて証明した。実数全体の集合に対応する新しい基数を、連続体濃度といい、カントールは\mathfrak{c}という記号をそれに用いた。
カントールは基数の一般理論の大部分を発展させた。彼は最小の超限基数の存在を示した。また、いかなる基数についても、その次に大きい基数が存在することを示した。
彼が予想した連続体仮説は、\mathfrak{c} は \aleph_1に等しい、という命題である。連続体仮説は、公理系から証明もその否定も証明できないという意味で、集合論の通常の公理系(ツェルメロ・フレンケルの公理系)から独立であることが示されている。
有限集合の要素の個数は自然数を使って数えることが出来る。自然数の個数を数える役割も「基数」と呼ばれる(対照的に順番を数える役割は序数と呼ばれる。基数詞と序数詞を参照)。通常数学では有限集合だけではなく無限集合が現れ、特に可算濃度と非可算濃度を区別することは大きな意味を持つ。このため有限集合の場合の自然数の一般化として無限集合の濃度についてもそれを表す「指標」として基数を定義したい。
集合の濃度の概念は全単射をもちいて定義される。2つの集合が等しい濃度を持つとは、その集合の間に全単射が存在することをいう。有限集合は必ずなんらかの自然数 n にたいし {0 ... n-1} との間に全単射が作れることがわかり、有限集合の濃度の指標としては自然数を採用すればいいことが分かる。無限集合の場合は、振る舞いは複雑になってくる。例えば、有限集合の真部分集合と元の集合の濃度が等しくなり得ないのに対し、無限集合の真部分集合の濃度が元の集合の濃度と等しいということが起きる(デデキント無限も参照)。さらにカントールが示したように、無限集合の濃度には最大が存在せず、いくらでも大きな濃度を構成することが出来る。
カントールは基数を濃度が等しい集合からなる同値類として素朴に定義した。しかし(ZFCなどの標準的な集合論では)この方法では基数を集合として扱うことは出来ず、また基数からなる集合やクラスを考えることは本質的に困難である。これを回避する方法はフォン・ノイマンやデイナ・スコット によって提示された。
(カントールによって暗に、フレーゲやプリンキピア・マテマティカにおいて明確に示されていた)基数の最も古い定義は、集合全体からなるクラスを濃度による同値関係で割ったときの同値類としての定義である。つまり X の濃度 | X | は X と一対一対応であるすべての集合からなるクラスとして定義される。これは、ZFCや関連する集合論の公理系ではうまく機能しない。実際、 X を空でない集合としたとき、集合 S に {S}×X を対応させる写像を考えることによって、宇宙から | X | への単射が存在し、サイズの限界 (Limitation of size) より、| X | は真のクラスである。
フォン・ノイマンの割り当て
任意の順序数 β に対し β < α ⇒ | β | < | α | を満たす順序数 α を始順序数 (initial ordinal) という。このとき整列可能な集合 X に対して min{α∈ON :| α | = | X | } を濃度 | X | の始順序数という(ただし ON は順序数全体からなるクラス)。
整列可能な集合の濃度をその始順序数として定義することをフォン・ノイマンの割り当てという。
このとき、順序数αに対して濃度! α !の始順序数がα自身であるならば、αは基数であるという。また、濃度が! α !に等しい集合Xについて、Xの基数はαであると言い、! X !=αと書く。
整列可能定理を仮定しない場合、以下の方法を用いて整列可能とは限らない集合 X に濃度として以下の集合を割り当てる(詳しくはスコットのからくりを参照):
| X | := {A : | A | = | X | かつ、任意の集合 B にたいし「| B | = | X | → rank( A) ≤ rank( B)」}
このとき基数はある集合と濃度が等しい集合のうち階数が一番小さいもの全体からなる集合として定義される。
どのような定義を採用するにしろ2つの基数が等しいのは、それらの基数を濃度とするような集合の間に全単射が構成できるちょうどそのときである。整列可能な集合の濃度として表せる基数をアレフ数(aleph number)という。ここでは基数全体からなるクラスを \mathbb{CN} とかく。\mathbb{CN} は真のクラスである。
κ ≤ λ ⇔ 「X、Y が κ = | X | , λ = | Y | を満たすなら、X から Y への単射が存在する」
有限集合の濃度となる基数を有限基数といい、自然数 n にたいし、n 点集合の濃度を n と書く。
無限集合の濃度となる基数を無限基数という。自然数全体からなる集合の濃度を \aleph_0 と書く( \aleph_0 = |\mathbb{N}| )。実数全体からなる集合の基数を \mathfrak{c} などと書き( \mathfrak{c} = \beth_1 = |\mathbb{R}| = |2^\mathbb{N}| )連続体濃度と呼ぶ。
基数に対しての基本的な演算は、有限基数について自然数上のよく知られた演算と一致するように定義される。
以下、特に言及のないときは選択公理を仮定する。X 、Y は集合、κ 、λ 、μ 、ν は基数とする。
| X |+ := |{ α∈ON : |α|≤| X | }|
を X のハルトークス数 (Hartogs number) という(これは濃度が | X | より大きい最小の順序数と一致する)。κ+ を κ の後続という。
κ が有限の時は κ+ = κ+1 が成立。一方、無限基数のときは κ+ と κ+1 は異なる。
| X |+| Y | := | X ⊔ Y | (ただし X ⊔ Y は X と Y の直和 (X × {0})∪(Y × {1}) のこと)
を | X | と | Y | の和という。
基数の加法について以下が成り立つ。
単位元 : κ+0 = κ
結合律 : (κ+λ)+μ = κ+(λ+μ)
可換律 : κ+λ = κ+λ
順序の保存 : κ ≤ λ ⇒ κ+μ ≤ λ+μ
κ と λ のどちらかが無限基数のとき κ+λ = max{κ,λ}
無限基数 κ と基数 λ にたいし、κ > λ のとき λ+μ = κ ⇔ μ = κ。
| X |·| Y | := | X × Y | (ただし X ×Y は X と Y の直積。)
を | X | と | Y | の積という。
吸収元 : κ·0 = 0
零因子の非存在 : κ ≠ 0 , λ ≠ 0 ⇒ κ·λ ≠ 0
単位元 : κ·1 = κ
結合律 : (κ·λ)·μ = κ·(λ·μ)
可換律 : κ·λ = κ·λ
順序の保存 : κ ≤ λ ⇒ κ·μ ≤ λ·μ
分配律 : κ·(λ+·μ) = κ·λ+κ·μ、 (κ+λ)·μ = κ·μ+λ·μ
0 でない基数 κ と λ のどちらかが無限基数のとき κ·λ = max{κ,λ}
無限基数 κ と基数 λ > 0 にたいし、κ > λ のとき λ·μ = κ ⇔ μ = κ。
| X || Y | := | X Y| (ただし X Y は Y から X への写像全体。)
を | X | を底、| Y | を指数とする冪という。
指数法則 :
順序の保存 :
2 \le \kappa < \aleph_0 \Rightarrow \kappa^\lambda = 2^\lambda 、1 \le \lambda < \aleph_0 \Rightarrow \kappa^\lambda = \kappa
無限基数 λ にたいし以下が成立。
|cf(κ)| ≤ λ ⇒ κ < κλ (ただし cf(κ) は κ の始順序数の共終数を表すとする。)
さらに一般連続体仮説を仮定すると無限基数 λ にたいし以下が成立。
λ < |cf(κ)| ⇒ κλ = κ
基数 λ、κ にたいし、μλ = κ を満たす μ は存在するとも一意的とも限らない。λ が有限で κ が無限なら、μλ = κ ⇔ μ = κ 。
基数 λ、κ にたいし、λμ = κ を満たす μ は存在するとも一意的とも限らない。無限基数 κ にたいし log(κ) := inf{ λ : κ ≤ 2λ } を κ の対数という。このとき log(κ) ≤ κ 、κ ≤ 2log(κ)。
順序数 \alpha にたいし、\alpha 番目のアレフ数を \aleph_\alpha と書く。より正確には \aleph_\alpha を以下のように超限再帰により定義する。
0 : \aleph_0 = |\mathbb{N}|
後続順序数 : \aleph_{\alpha+1} := \aleph_{\alpha}^+ (後述の後続を参照)
極限順序数 : \aleph_{\gamma} := \rm{sup}\{\aleph_{\alpha} : \alpha < \gamma \}(ただし \gamma は極限順序数)
特にアレフ数の列 \{\aleph_\alpha\}_{\alpha\in\mathbb{ON} のことをアレフ数と呼ぶこともある。アレフ数は必ずなんらかの \alpha によって \aleph_\alpha と表せる。\aleph_\alpha の始順序数を \omega_\alpha と書く。
順序数 \alpha にたいし、\beth_\alpha を以下のように超限再帰により定義する。
0 : \beth_0 = \aleph_0
後続順序数 : \beth_{\alpha+1} := 2^{\beth_\alpha} (後述の後続を参照)
極限順序数 : \beth_\gamma := \rm{sup}\{\beth_\alpha : \alpha < \gamma \}(ただし \gamma は極限順序数)
列 \{\beth_\alpha\}_{\alpha\in\mathbb{ON} ないし列上の基数をベート数(beth number)と呼ぶ。
\beth_1 = \aleph_1
\alpha\in\mathbb{ON}\Rightarrow\beth_\alpha = \aleph_\alpha
を一般連続体仮説という。
この仮説はゲオルク・カントールによって予想された。ヒルベルトは彼の有名な23 の問題の第一番にこの連続体仮説を取り上げている。その後、クルト・ゲーデルは構成可能集合全体のクラス L が一般連続体仮説をみたすことを示し、「ZFC からは一般連続体仮説の否定は証明できない」ことを証明した。ポール・コーエンは強制法と呼ばれる新しい手法を用いて連続体仮説が成り立たないモデルを構成し「ZFC から連続体仮説を証明できない」ことを証明した。これらの結果から(一般)連続体仮説の ZFC からの独立性が示され、連続体仮説は一応の解決を見た。コーエンはこの業績によりフィールズ賞を受賞している。
無限基数 κ がなんらかの基数 λ を使って κ = λ+ と表せるとき κ を後続基数といい、κ = sup {λ ∈ CN : λ < κ } と表せるとき κ を(弱)極限基数という。後続基数でなければ極限基数である。極限基数 κ が λ < κ ⇒ 2λ < κ を満たすとき強極限基数という、これは log(κ) = κ と同値。
無限基数 \kappa が
|\mathcal{S}| < \kappa かつ  X\in\mathcal{S} \rightarrow |X| < \kappa ならば |\bigcup\mathcal{S}| < \kappa
を満たすとき正則基数、満たさないとき特異基数という。\aleph_\alpha が正則基数となることと \rm{cf}(\omega_\alpha) = \omega_\alpha は同値。
正則な極限基数を弱到達不可能基数、正則な強極限基数を強到達不可能基数という。