集合の濃度

集合の濃度

集合の濃度 (cardinality) は集合の「大きさ」を測る指標であり、有限集合の「元の個数」を拡張するものである。有限集合 $X,Y$ が与えられたとき、以下は同値である。

1. $X$ と $Y$ の元の個数が等しい。
2. $X$ と $Y$ の間に全単射 $f\colon X\to Y$ が存在する。

また同様に以下も同値である。

1. $X$ の元の個数は $Y$ の元の個数以下である。
2. $X$ と $Y$ の間に単射 $f\colon X\to Y$ が存在する。

ナイーブには「元の個数」は有限集合に対してしか適用できないのに対し、全単射や単射の存在は無限集合に対しても考えうる。よって全単射や単射の存在によって集合 $X,Y$ の大きさを測ろうというのが、濃度の考え方といって良いだろう。

定義

集合 $X,Y$ に対して関係 $X\equiv_{\mathrm{card}} Y$ を $X$ から $Y$ への全単射が存在する、と定める。このとき以下が成り立つ。

1. 反射律　任意の集合 $X$ に対し、 $X\equiv_{\mathrm{card}} X$ である。
2. 対称律　任意の集合 $X,Y$ に対し、$X\equiv_{\mathrm{card}} Y$ ならば $Y\equiv_{\mathrm{card}} X$ である。
3. 推移律　任意の集合 $X,Y,Z$ に対し、 $X\equiv_{\mathrm{card}} Y$ かつ $Y\equiv_{\mathrm{card}} Z$ ならば $X\equiv_{\mathrm{card}} Z$ である。

これらは定義に基づき書き直せば以下のようになる。

1. 反射律　任意の集合 $X$ に対し、全単射 $f\colon X\to X$ が存在する。
2. 対称律　任意の集合 $X,Y$ に対し、全単射 $f\colon X\to Y$ が存在するならば 全単射$g\colon Y\to X$ も存在する。
3. 推移律　任意の集合 $X,Y,Z$ に対し、全単射 $f\colon X\to Y$が存在しかつ 全単射 $g\colon Y\to Z$ が存在するならば全単射 $h\colon X \to Z$ も存在する。

反射律は $f:=\mathrm{id}_X$ とすれば良く、対称律は $g:=f^{-1}$ とすれば良く推移律は $h:=g\circ f$ とすれば成り立つことがすぐ分かるであろう。

よって $\equiv_{\mathrm{card}}$ は同値関係であることが分かる。同値関係であるということは、集合全体を $\equiv_{\mathrm{card}}$ で割ることができ、$X$ の同値類 $[X]_{\equiv_{\mathrm{card}}}$ を考えることができる。この同値類 $[X]_{\equiv_{\mathrm{card}}}$ を $X$ の濃度 (cardinality) といい、$\mathrm{card}(X),\#X,|X|$ などと表す。また濃度の全体を $\mathrm{Card}$ とする。

濃度の順序

$\mathrm{Card}$ の元 $[X]_{\equiv_{\mathrm{card}}},[Y]_{\equiv_{\mathrm{card}}}$ に対して二項関係 $[X]_{\equiv_{\mathrm{card}}}\leq [Y]_{\equiv_{\mathrm{card}}}$ を単射 $f\colon X\to Y$ が存在することと定義する。これはwell-definedである、すなわち以下が成り立つ。

• $[X_0]_{\equiv_{\mathrm{card}}}=[Y_0]_{\equiv_{\mathrm{card}}}$ かつ $[X_1]_{\equiv_{\mathrm{card}}}=[Y_1]_{\equiv_{\mathrm{card}}}$ かつ $[X_0]_{\equiv_{\mathrm{card}}}\leq [X_1]_{\equiv_{\mathrm{card}}}$ ならば $[Y_0]_{\equiv_{\mathrm{card}}}\leq [Y_1]_{\equiv_{\mathrm{card}}}$ である。

これを定義に基づいて書き直せば以下の用になる。

• 全単射 $f_0\colon X_0\to Y_0$ と、全単射 $f_1\colon X_1\to Y_1$ と単射 $g_X\colon X_0\to X_1$ が存在するとき、単射 $g_Y\colon Y_0\to Y_1$ も存在する。

これは $g_Y:=f_0^{-1}\circ g_X\circ f_1$ とすれば成り立つことが分かるであろう。

また $\leq$ は $\mathrm{Card}$ 上で全順序になる。すなわち以下が成り立つ。

• 反射律　任意の $[X]_{\equiv_{\mathrm{card}}}\in\mathrm{Card}$ に対し、 $[X]_{\equiv_{\mathrm{card}}}\leq [X]_{\equiv_{\mathrm{card}}}$ である。
• 全域律　任意の $[X]_{\equiv_{\mathrm{card}}},[Y]_{\equiv_{\mathrm{card}}}\in\mathrm{Card}$ に対し、$[X]_{\equiv_{\mathrm{card}}}\leq [Y]_{\equiv_{\mathrm{card}}}$ または $[Y]_{\equiv_{\mathrm{card}}}\leq [X]_{\equiv_{\mathrm{card}}}$ である。
• 反対称律　任意の $[X]_{\equiv_{\mathrm{card}}},[Y]_{\equiv_{\mathrm{card}}}\in\mathrm{Card}$ に対し、$[X]_{\equiv_{\mathrm{card}}}\leq [Y]_{\equiv_{\mathrm{card}}}$ かつ$[Y]_{\equiv_{\mathrm{card}}}\leq [X]_{\equiv_{\mathrm{card}}}$ であるならば $[X]_{\equiv_{\mathrm{card}}}= [Y]_{\equiv_{\mathrm{card}}}$ である。
• 推移律　任意の $[X]_{\equiv_{\mathrm{card}}},[Y]_{\equiv_{\mathrm{card}}},[Z]_{\equiv_{\mathrm{card}}}\in\mathrm{Card}$ に対し、$[X]_{\equiv_{\mathrm{card}}}\leq [Y]_{\equiv_{\mathrm{card}}}$ かつ $[Y]_{\equiv_{\mathrm{card}}}\leq [Z]_{\equiv_{\mathrm{card}}}$ ならば $[X]_{\equiv_{\mathrm{card}}}\leq [Z]_{\equiv_{\mathrm{card}}}$ である。

特に濃度に対する反対称律をCantor–Bernstein–Schröderの定理という。

またもっと言えば濃度の順序は整列順序になっている。よって任意の濃度からなる集合 $X$ に対し最小元 $\min X$ が存在する。

濃度の演算

$I$ を添字集合とし $\{[X_i]_{\equiv_{\mathrm{card}}}\}_{i\in I}$ を濃度の族とする。また $\sum_{i\in I}X_i,\prod_{i\in I}X_i$ を集合の直和、直積とする。 このとき濃度の和 $\sum_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}$ と濃度の積 $\prod_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}$ を以下のように定める。

• $\sum_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}:=[\sum_{i\in I}X_i]_{\equiv_{\mathrm{card}}}$ 。
• $\prod_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}:=[\prod_{i\in I}X_i]_{\equiv_{\mathrm{card}}}$ 。

また濃度 $[X]_{\equiv_{\mathrm{card}}},[Y]_{\equiv_{\mathrm{card}}}$ に対して冪 ${[X]_{\equiv_{\mathrm{card}}}}^{[Y]_{\equiv_{\mathrm{card}}}}$ を以下のように定める。

• ${[X]_{\equiv_{\mathrm{card}}}}^{[Y]_{\equiv_{\mathrm{card}}}}:=[X^Y]_{\equiv_{\mathrm{card}}}$ 。

ここで $X^Y$ は $Y$ から $X$ への写像全体の集合である。

これらの演算は代表元の選択に依存しないためwell-definedである。

$I$ が有限集合で、ある $i$ に対して $X_i$ が無限集合であるとき $$\sum_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}=\prod_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}=\max_{i\in_I}[X_i]_{\equiv_{\mathrm{card}}}$$ が成り立つ。また全ての $i$ に対して $X_i$ が有限集合であるとき、濃度は要素の数の和、積と一致する。

以下のような不等式も知られている。

• Cantorの定理　$Y$ の濃度は $2:=\{0,1\}$ 以上とする。このとき任意の集合 $X$ に対して $[X]_{\equiv_{\mathrm{card}}}<[Y^X]_{\equiv_{\mathrm{card}}}$ である。特に $[X]_{\equiv_{\mathrm{card}}}<[\mathcal{P}(X)]_{\equiv_{\mathrm{card}}}$ である。
• Kőnigの定理 各 $i\in I$ に対し $[X_i]_{\equiv_{\mathrm{card}}}<[Y_i]_{\equiv_{\mathrm{card}}}$ とする。このとき $\sum_{i\in I}[X_i]_{\equiv_{\mathrm{card}}}<\prod_{i\in I} [Y_i]_{\equiv_{\mathrm{card}}}$ である。

具体的な濃度

• $\mathbb{N}$ の濃度を可算濃度 といい $\aleph_0$ と表す。また $\aleph_n$ より大きい最小の濃度を $\aleph_{n+1}$ とする。また可算濃度を持つ集合を可算無限集合という。
• $\mathbb{R}$ の濃度を連続体濃度 といい $\aleph$ や $\mathfrak{c}$ と表す。

可算濃度を持つ集合の例を挙げる。

• $\mathbb{Z},\mathbb{Q}$ 。
• 代数的数全体 $\bar{\mathbb{Q}}$ 。
• 自然数の有限列全体 $\mathbb{N}^{<\omega}$ 。

$\aleph_1$ を濃度として持つ集合の例を挙げる。

• たかだか可算な順序数全体。
• $\mathbb{Q}$ 上の通常の順序で整列されるような集合を $W$ とし順序同型関係を $\equiv$ としたとき $W/{\equiv}$ の濃度。
• $\mathbb{R}$ 上の通常の順序で整列されるような集合を $W$ とし順序同型関係を $\equiv$ としたとき $W/{\equiv}$ の濃度。
• 可算全順序の双埋め込み可能性による同値類。
• 可算アーベル$p$-群の双埋め込み可能性による同値類。

• 長い直線

連続体濃度を持つ集合の例を挙げる。

• 超越数 全体 $\mathbb{R}\setminus\bar{\mathbb{Q}}$ 。
• 複素数全体 $\mathbb{C}$ 。
• $\mathcal{P}(\mathbb{N})$ 。
• $\mathbb{N}^\mathbb{N}$ 。
• 実数の可算列全体 $\mathbb{R}^\mathbb{N}$ 。
• $\mathbb{R}\to\mathbb{R}$ の連続関数全体。
• Euclid空間 $\mathbb{R}^n$ の開集合全体。

$2^\aleph$ を濃度として持つ集合の例を挙げる。

• $\mathcal{P}(\mathbb{R})$ 。
• $\mathbb{R}^\mathbb{R}$ 。
• Sorgenfrey直線 $S$ に対して $S^2$ の開集合全体。

連続体仮説

さてCantorは以下の連続体仮説 (continuum hypothesis $\mathsf{CH}$) という問題を提示した。

• $\aleph_0$ と $\aleph$ の中間の濃度、すなわち $\aleph_0<\kappa<\aleph$ となるような濃度 $\kappa$ は存在しない。。

連続体仮説はGödelとCohenらによって一般的な集合論の公理系 $\mathsf{ZFC}$ では証明も反証もできないことが知られている。

濃度の正確な扱いについて

上記で述べた濃度の定義は集合論 $\mathsf{ZFC}$ に於いてはill-definedである。まず集合全体は集合ではないし、全単射が存在する二つの集合の組全体も集合ではなく、同じ濃度であるという論理式 $\equiv_\mathrm{card}$ も二項関係ではない。ill-definedであることは以下のように分かる。集合全体を $V$ とし、これが集合だとすると冪集合 $\mathcal{P}(V)$ が存在し $\mathcal{P}(V)$ の元はすべて集合であり $\mathcal{P}(V)\subseteq V$ あるわけだが、これはCantorの定理に矛盾する。また $\{(x,x)\mid x\in V\}$ は「全単射が存在する二つの集合の組全体」の部分クラスになっており $V$ からの単射が存在するので真のクラスとなる。 よって以下では濃度を正確に扱う方法をいくつか考えよう。一つ目に挙げる方法は前提知識なく理解できるであろうが、二つ目以降は順序数や累積階層、数理論理学などの知識を必要とする。

濃度を直接定義せず、間接的に扱う。

集合 $X$ に対して $\mathrm{card}(X)$ というものを定義せず、 $\mathrm{card}(X)=\mathrm{card}(Y)$ を全単射 $f\colon X\to Y$ が存在することの略記、$\mathrm{card}(X)\leq \mathrm{card}(Y)$ を単射 $f\colon X\to Y$ が存在することの略記として扱うという手法である。この手法のメリットとして使う道具立てが少なく、また他の扱い方と違い、整列可能性定理や正則性公理などに依存していない点が挙げられる。似たようなアイデアは構成主義数学などの亜集合 (setoid) などの文脈でも用いられている。

濃度をある種の順序数として定義する。

濃度は直観的には同値類として上では扱っていたが、同値類は実際には存在しない。しかし、その代表元に相当するものが実は取ることができる。順序数 $\kappa$ が基数 (cardinal) であるとは $\kappa$ 未満の順序数から $\kappa$ への全単射が存在しないことを言う。この基数が「集合全体を全単射で割った商集合の完全代表系」の役割を果たす。$X$ の濃度 $\mathrm{card}(X)$ を $X$ から全単射の存在する最小の順序数と定めよう。このような順序数の存在は $\mathsf{ZFC}$ で示せて、これは基数となる。このアプローチは公理的集合論に於いて一般的なものである。しかしこの定義は選択公理に依存する。整列可能性定理が、選択公理と同値なことを念頭に置くと、集合から順序数への全単射の存在は、集合の整列可能性を要求しているに他ならないからである。

Scottの絡繰を用いる方法

このアプローチは同値類の定義を見直すことで真のクラスに対して定義できるようにする、というアプローチである。階数 $\mathrm{rank}(x):=\sup\{\mathrm{rank}(y)+1\mid y\in x\}$ と定めて、クラスに対しその元の階数に於いて最小のもののみを集めたものを考える。 真のクラス $C$ に対し $$\hat{C}:=\{x\in C\mid (\forall y)[\mathrm{rank}(x)\leq\mathrm{rank}(y)]\}$$ は常に非空な集合となり、これをScottの絡繰 (Scott's trick) という。集合であることは、任意の $x\in C$ に対し $\mathrm{rank}(x)=\alpha$ であることと $x\in V_{\alpha+1}$ であることが同値であることによる。ここで $V_\alpha$ は累積階層 と呼ばれ、$\alpha$ に対する超限再帰で $V_\alpha:=\bigcup_{\xi<\alpha}\mathcal{P}(V_\xi)$ と定義される集合である。

真のクラス　$C$ 上の同値関係 $\equiv$ に対して、同値類 $[x]_\equiv$ を $$[x]_\equiv:=\{y\mid y\equiv x\land(\forall z\in C)[z\equiv x\to\mathrm{rank}(y)\leq\mathrm{rank}(z)]\}$$ とすればこれは集合である。。よってこの同値類の定義にて $\mathrm{card}(x):=[x]_{\equiv_{\mathrm{card}}}$ とすれば良い。このアプローチでは選択公理によらずに全ての集合に対して濃度が定義できるというメリットがある。

クラスを扱えるような集合論を用いる方法

クラスを対称として扱えるNeumann–Bernays–Gödel集合論に大域選択公理 $\mathsf{AGC}$ を加えた公理 $\mathsf{NBGC}$ などではクラス上の同値類 $[x]_{\equiv_{\mathrm{card}}}$ がそのままクラスとして存在する。よってこれを濃度の定義としてしまえば良い。また $\mathsf{NBGC}$ は $\mathsf{ZFC}$ の保存的拡大である。すなわち $\mathsf{ZFC}$ の言語で書かれた命題は、証明の際に $\mathsf{NBGC}$ にて定義される濃度を用いたとしても $\mathsf{ZFC}$ で証明可能であることが言える。つまり濃度の議論を用いて示した $\mathsf{ZFC}$ の言語での定理は $\mathsf{ZFC}$ で証明可能であることが言える。しかしこの定義だと濃度自体は $\mathsf{ZFC}$ の言語で記述できないため、濃度を含む定理が $\mathsf{NBGC}$ で証明可能だとしても、それが $\mathsf{ZFC}$ で証明可能であることをただちには導かない。$\mathsf{ZFC}$ の定理であることを導くためには $\mathsf{NBGC}$ での定義が上で挙げた他の $\mathsf{ZFC}$ に於ける定義と同値であることを証明しないとならない。

参考文献

• T. Jech Set theory. Springer Science & Business Media, 2013.
• Barwise, Jon, and Paul Eklof. "Infinitary properties of abelian torsion groups." Annals of Mathematical Logic 2.1 (1970): 25-68.
• Laver, Richard. "On Fraïssé's order type conjecture." Annals of Mathematics (1971): 89-111.

集合論の初歩

論理と命題 / 集合の基本的な用語、集合の演算 / 全称記号と存在記号 / 写像、像、逆像、写像のグラフ / 写像の合成、写像の拡大と制限 / 選択公理について / 単射、全射、全単射、逆写像 / 部分集合族、べき集合 / （ 演算と代数構造 ） / （ 関係、同値関係、商集合 ） / （ 初歩的な順序集合 ） / （ Zornの補題 ） / （ 集合の濃度 ）

関連項目

• 集合論