可算選択公理

同義語：axiom of countable choicecountable choice

概要

前提知識: 選択公理, 可算集合, 集合論

解析学では「各 $n$ について、条件を満たす $x_n$ をとる」と書いて点列を作ることがよくある。たとえば関数 $f$ が点 $a$ で連続でないことから、$a$ に近づくのに $f(x_n)$ が $f(a)$ に近づかない点列 $(x_n)$ を作る場面である。$n$ を 1 つ決めればそのような $x_n$ は存在するが、無限個の $n$ について同時に選んだ列 $(x_n)_{n\in\mathbb{N}}$ が 1 つの集合として存在することは、選び方の規則が書けない限り、集合論のほかの公理からは出てこない。この「可算個の同時の選択」を公理として認めるのが可算選択公理である。選択公理の弱い形の一つで、可算個の可算集合の和が可算であること、外測度の可算劣加法性、点列による連続性の判定など、解析学と位相空間論の基本的な論法の多くがこれに依存している。

定義

以下、基礎の体系は選択公理を含まない Zermelo–Fraenkel の集合論 $\mathsf{ZF}$ とし、選択公理を加えた体系を $\mathsf{ZFC}$ と書く。$\mathbb{N}=\{0,1,2,\dots\}$ とする。集合 $I$ で添字づけられた集合の族 $(X_i)_{i\in I}$ に対し、写像 $f\colon I\to\bigcup_{i\in I}X_i$ で、すべての $i\in I$ について $f(i)\in X_i$ を満たすものを族の選択関数という。「可算」は可算集合の記事の定義「有限・可算無限・高々可算」に従い、有限集合も含める。

可算選択公理

$(X_n)_{n\in\mathbb{N}}$ を、すべての $n\in\mathbb{N}$ について $X_n\neq\emptyset$ である集合の族とする。このとき写像
$$ f\colon\mathbb{N}\to\bigcup_{n\in\mathbb{N}}X_n $$
で、すべての $n\in\mathbb{N}$ について $f(n)\in X_n$ を満たすものが存在する。
この主張を可算選択公理（axiom of countable choice）といい、$\mathsf{AC}_\omega$ と書く。

選択関数 $f$ は、$x_n:=f(n)$ とおけば、各項が $x_n\in X_n$ を満たす列 $(x_n)_{n\in\mathbb{N}}$ にほかならない。直積の言葉では、可算選択公理は「空でない集合の可算個の直積 $\prod_{n\in\mathbb{N}}X_n$ は空でない」と言い換えられる。選択公理（選択公理の記事の公理「選択公理の言明」）は任意の添字集合について同じことを主張するので、選択公理から可算選択公理が従う。
添字集合を $\mathbb{N}$ にしたのは書き方の都合であり、次の命題のとおり、可算な添字集合なら何でもよく、添字を使わない形で述べてもよい。

可算選択公理の言い換え

$\mathsf{ZF}$ において、次の 3 つの主張は同値である。

可算選択公理。
空でない集合だけからなる可算集合 $\mathcal{A}$ は、選択関数 $g\colon\mathcal{A}\to\bigcup\mathcal{A}$（すべての $A\in\mathcal{A}$ について $g(A)\in A$）をもつ。
可算集合 $I$ で添字づけられた空でない集合の族 $(X_i)_{i\in I}$ は、選択関数をもつ。

(1 ⇒ 3) $I=\emptyset$ なら空写像が選択関数である。$I\neq\emptyset$ とする。$I$ は空でない可算集合なので、可算集合の記事の命題「単射・全射による特徴づけ」により全射 $e\colon\mathbb{N}\to I$ が存在する。そのような $e$ を 1 つとる（1 つの集合から 1 つの元をとるだけなので選択公理は要らない）。族 $(X_{e(n)})_{n\in\mathbb{N}}$ の各成員は空でないので、可算選択公理により $h(n)\in X_{e(n)}$ を満たす $h\colon\mathbb{N}\to\bigcup_iX_i$ がある。$i\in I$ に対し、$e$ の全射性から $\{n\in\mathbb{N}\mid e(n)=i\}$ は $\mathbb{N}$ の空でない部分集合なので最小元 $n_i$ をもち、
$$ f(i):=h(n_i) $$
と定める。$e(n_i)=i$ より $f(i)=h(n_i)\in X_{e(n_i)}=X_i$ であり、$f$ は族 $(X_i)_{i\in I}$ の選択関数である。$n_i$ は「最小元」という規則で一意に決まるので、ここでも選択は使っていない。
(3 ⇒ 2) $I:=\mathcal{A}$、$X_A:=A$（$A\in\mathcal{A}$）とおいて 3 を適用すればよい。
(2 ⇒ 1) $(X_n)_{n\in\mathbb{N}}$ を空でない集合の族とする。集合 $\{X_n\mid n\in\mathbb{N}\}$ に直接 2 を適用すると、$m\neq n$ で $X_m=X_n$ のとき 2 つの添字が 1 つの元に潰れ、得られる選択関数から $n$ ごとの値が読み取れない。そこで添字を付けて
$$ Y_n:=\{n\}\times X_n,\qquad \mathcal{A}:=\{Y_n\mid n\in\mathbb{N}\} $$
とおく。各 $Y_n$ は空でなく、$m\neq n$ なら $Y_m\cap Y_n=\emptyset$ なので $Y_m\neq Y_n$ である。$\mathcal{A}$ は写像 $n\mapsto Y_n$ による $\mathbb{N}$ の像なので、可算集合の記事の系「像と単射による可算性の伝播」により可算である。2 により選択関数 $g\colon\mathcal{A}\to\bigcup\mathcal{A}$ がとれる。$g(Y_n)\in\{n\}\times X_n$ なので、その第 2 成分を $f(n)$ とおけば $f(n)\in X_n$ であり、$f$ は $(X_n)_{n\in\mathbb{N}}$ の選択関数である。$\square$

添字を使わない形 2 は、選択公理の記事の命題「選択公理の同値な言い換え」の 2 を可算な集合族に制限したものにあたる。

直感

有限個の空でない集合から 1 つずつ元を選ぶことは、個数についての帰納法で $\mathsf{ZF}$ の中で正当化できる（選択公理の記事の例「有限族の選択関数」）。帰納法は「$n$ 個まで選べたなら $n+1$ 個目も選べる」を言うだけで、無限個の選択を 1 つの写像にまとめることはしない。可算個の選択を 1 つの列にまとめるには、次の 2 つのどちらかが要る。

各 $X_n$ から元を選ぶ規則が、$n$ によらない 1 つの式で書ける。このときは列を再帰や分出公理で定義でき、選択公理は要らない。
規則がないときは、列の存在を公理として認める。これが可算選択公理である。
Russell は、可算無限個の靴の対と可算無限個の靴下の対の違いでこれを説明した。靴の対からは「右の靴」という規則で一斉に選べるが、左右の区別のない靴下の対には規則がないので、靴下を 1 つずつ選んだ列の存在には選択公理が要る（Button21 §16.5）。

例と反例

規則で選べる族

選び方の規則が書ける可算族

次の族は、選択公理を使わずに $\mathsf{ZF}$ の中で選択関数が作れる。

$\mathbb{N}$ の空でない部分集合の族 $(S_n)_{n\in\mathbb{N}}$：$f(n):=\min S_n$ とおけばよい（選択公理の記事の例「選択規則が明示できる族」）。
空でない開区間の族 $((a_n,b_n))_{n\in\mathbb{N}}$（$a_n< b_n$）：式で書ける全射 $q\colon\mathbb{N}\to\mathbb{Q}$ を 1 つ固定し（可算集合の記事の例「有理数全体の可算性」の全射 $(p,m)\mapsto p/m$ と、可算集合の記事の命題「自然数の対の番号付け」の全単射などを合成すれば得られる）、$f(n):=q(k_n)$、ただし $k_n$ は $a_n< q(k)< b_n$ を満たす最小の $k$、とおけばよい。開区間は有理数を含むので $k_n$ は存在する。同じ規則は、$\mathbb{R}$ の空でない開集合の任意の族に使える。
靴の対の族 $(\{\ell_n,r_n\})_{n\in\mathbb{N}}$ で、左右を表す 2 つの列 $(\ell_n)$、$(r_n)$ があらかじめ与えられているもの：$f(n):=r_n$ とおけばよい。
いずれも、$n$ ごとの値が $n$ によらない 1 つの式で決まっている。

次の命題は、閉集合という位相的な条件だけから選び方の規則が得られる例である。開区間の例と違い、有理数を含むとは限らない閉集合（たとえば 1 点）にも使える。

実数の閉集合からの選択

$\mathsf{ZF}$ において、$\mathbb{R}$ の空でない閉集合からなる族 $(F_i)_{i\in I}$ は、添字集合 $I$ が何であっても選択関数をもつ。

空でない閉集合 $F\subset\mathbb{R}$ に対し、$r(F):=\inf\{\lvert x\rvert\mid x\in F\}\ge0$ とおく（上限と下限）。$r:=r(F)$ または $-r$ の少なくとも一方が $F$ に属することを示す。どちらも $F$ に属さないとすると、$\mathbb{R}\setminus F$ は開集合なので、$(r-\delta,r+\delta)$ と $(-r-\delta,-r+\delta)$ がともに $F$ と交わらない $\delta>0$ がある。$x\in F$ なら $\lvert x\rvert\ge r$ であり、もし $\lvert x\rvert< r+\delta$ なら $x$ は $(r-\delta,r+\delta)$ か $(-r-\delta,-r+\delta)$ に属して矛盾する。よってすべての $x\in F$ で $\lvert x\rvert\ge r+\delta$ となり、$r$ が下限であることに反する。
そこで $g(F):=r(F)$（$r(F)\in F$ のとき）、$g(F):=-r(F)$（そうでないとき）と定め、$f(i):=g(F_i)$ とおく。$g(F)$ は $F$ から式だけで決まるので、$f$ は分出公理によって集合として定義でき、$f(i)\in F_i$ を満たす。証明の中で存在を使ったのは、1 つの $F$ に対する $\delta$ だけであり、これは $g$ の定義には現れない。$\square$

規則がない場合と、公理を外したときに崩れること

可算個でも、各成員から選ぶ規則がなければ $\mathsf{ZF}$ だけでは選べないことがある（選択公理の記事の注意「反例：可算族なら選択できるという含意」）。可算選択公理を外したとき、あるいは可算選択公理から選択公理を期待したときに崩れることを表にまとめる。いずれも「$\mathsf{ZF}$ が無矛盾なら」という相対的な主張で、モデルの構成は文献に委ねる。

外す条件・強める結論	反例となるモデル	成り立たなくなること
可算選択公理を外す（$\mathsf{ZF}$ だけ）	実数全体と対等な集合が、可算集合の可算個の和になるモデル（Feferman–Levy）	可算個の可算集合の和は可算である／外測度の可算劣加法性
可算選択公理を外す（$\mathsf{ZF}$ だけ）	$\omega$ と比較できない集合、すなわち無限だが可算無限な部分集合をもたない集合があるモデル（Cohen）	無限集合は可算無限な部分集合をもつ
可算選択公理から選択公理を結論する	可算選択公理（さらに従属選択公理）は成り立つが選択公理は成り立たないモデル	選択公理とそれに同値な整列可能定理・Zorn の補題

1 行目と 2 行目のモデルの存在は Button21 §16.5 が Feferman–Levy と Cohen の結果として述べている。3 行目は選択公理の記事の命題「弱い形との含意関係」の一部である（従属選択公理から可算選択公理は従うが、可算選択公理から従属選択公理は $\mathsf{ZF}$ で証明できず、選択公理は従属選択公理を含意するので、可算選択公理から選択公理も証明できない）。1 行目の「外測度の可算劣加法性」は、次の例で確かめる。

反例：可算選択公理がないと外測度の可算劣加法性が破れうる

$A\subset\mathbb{R}$ の外測度を、$A$ を覆う開区間の列 $(I_k)_{k\in\mathbb{N}}$ の長さの和の下限
$$ m^*(A):=\inf\Bigl\{\sum_{k\in\mathbb{N}}\ell(I_k)\ \Big|\ A\subset\bigcup_{k\in\mathbb{N}}I_k\Bigr\} $$
で定める（$\ell$ は開区間の長さ、空の区間の長さは $0$）。$\mathsf{ZF}$ だけで次の 2 つが証明できる。

可算集合 $B$ は $m^*(B)=0$ を満たす。$B\neq\emptyset$ なら全射 $e\colon\mathbb{N}\to B$ を 1 つとり、$\varepsilon>0$ に対して $I_k:=(e(k)-\varepsilon2^{-k-2},\,e(k)+\varepsilon2^{-k-2})$ とおけば、$B\subset\bigcup_kI_k$ で長さの和は $\varepsilon$ である。選んだのは 1 つの $e$ だけである。
$m^*([0,1])=1$。Axler20 2.14 の証明（Heine–Borel の定理と有限個の区間についての帰納法）は、有限個の元をとる操作しか使わない。
Feferman–Levy のモデルでは、可算集合の列 $(A_n)_{n\in\mathbb{N}}$ と全単射 $\varphi\colon\bigcup_nA_n\to\mathbb{R}$ がある。$B_n:=\varphi(A_n)$ は可算集合で $\mathbb{R}=\bigcup_nB_n$ だから
$$ \sum_{n\in\mathbb{N}}m^*(B_n)=0<1=m^*([0,1])\le m^*(\mathbb{R})=m^*\Bigl(\bigcup_{n\in\mathbb{N}}B_n\Bigr) $$
となる（途中の $\le$ は、$\mathbb{R}$ の被覆が $[0,1]$ の被覆でもあることによる）。満たす性質：各 $B_n$ の外測度は $0$ で、外測度は単調である。満たさない性質：$m^*\bigl(\bigcup_nB_n\bigr)\le\sum_nm^*(B_n)$。破る含意：「外測度は可算劣加法的である」は $\mathsf{ZF}$ だけからは証明できない（$\mathsf{ZF}$ が無矛盾なら）。$\mathsf{ZFC}$ での可算劣加法性の証明（Axler20 2.8）は、各 $A_k$ について「長さの和が $m^*(A_k)+\varepsilon2^{-k}$ 以下の被覆」を $k$ ごとに選ぶところで可算選択公理を使っている。上のモデルでは結論が偽なので、$B_n$ たちの被覆を一斉に選ぶことはできない。

性質

点列による連続性の判定

距離空間の間の写像の連続性は、$\varepsilon$-$\delta$ でも点列でも判定できると習うことが多い。片方の向きは $\mathsf{ZF}$ で証明でき、もう片方の向きで可算選択公理を使う。

連続性と点列連続性

$(X,d_X)$、$(Y,d_Y)$ を距離空間、$f\colon X\to Y$ を写像、$a\in X$ とする。次の 2 条件を考える。

(C) 任意の $\varepsilon>0$ に対し、ある $\delta>0$ が存在して、$d_X(x,a)<\delta$ ならば $d_Y(f(x),f(a))<\varepsilon$。
(S) $a$ に収束する $X$ の任意の点列 $(x_n)_{n\in\mathbb{N}}$ について、$(f(x_n))_{n\in\mathbb{N}}$ は $f(a)$ に収束する。
このとき

$\mathsf{ZF}$ において、(C) ならば (S) である。
$\mathsf{ZF}$ に可算選択公理を加えると、(S) ならば (C) である。

(C) を仮定し、$x_n\to a$ とする。$\varepsilon>0$ に対し (C) の $\delta$ をとる。$x_n\to a$ より、ある $N$ があって $n\ge N$ なら $d_X(x_n,a)<\delta$、したがって $d_Y(f(x_n),f(a))<\varepsilon$ である。よって $f(x_n)\to f(a)$。ここでは $\varepsilon$ ごとに $\delta$ と $N$ を 1 つずつとるだけで、列を作っていない。
(C) が成り立たないとして (S) が成り立たないことを示す。(C) の否定により、ある $\varepsilon>0$ があって、どの $\delta>0$ に対しても $d_X(x,a)<\delta$ かつ $d_Y(f(x),f(a))\ge\varepsilon$ を満たす $x$ がある。この $\varepsilon$ を 1 つ固定し、$n\in\mathbb{N}$ ごとに
$$ S_n:=\Bigl\{x\in X\ \Big|\ d_X(x,a)<\frac{1}{n+1},\ d_Y(f(x),f(a))\ge\varepsilon\Bigr\} $$
とおく。$\delta=1/(n+1)$ として上の性質を使えば、各 $S_n$ は空でない。可算選択公理により、すべての $n$ で $x_n\in S_n$ となる点列 $(x_n)_{n\in\mathbb{N}}$ がとれる。$d_X(x_n,a)<1/(n+1)$ より $x_n\to a$ だが、すべての $n$ で $d_Y(f(x_n),f(a))\ge\varepsilon$ なので $f(x_n)$ は $f(a)$ に収束しない。これは (S) の否定である。$\square$

選択を使ったのは 2 の「$x_n\in S_n$ を一斉にとる」1 か所だけである。$S_n$ は $\mathbb{N}$ の部分集合でも閉集合でもないので、ex-countable-choice-explicit-rules や prop-countable-choice-closed-subsets のような規則は一般には使えない。個々の $f$ について $S_n$ から元を選ぶ規則が具体的に書けるなら、その規則で点列を定義すれば可算選択公理は要らない。位相空間での同じ型の論法（閉包の点が点列の極限になること）と、そこで可算選択公理を使う箇所は、第1可算公理の記事の定理「閉包の点列による判定」と注意「選択公理の使いどころ」にある。

可算集合と無限集合

可算選択公理が最もよく知られている使われ方は、次の 2 つの定理である。

可算個の可算集合の和は可算である（可算集合の記事の定理「可算個の可算集合の和集合」）。
無限集合は可算無限な部分集合をもつ（無限集合の記事の定理「無限集合と Dedekind 無限」の 3）。
どちらの証明でも、選択公理を使うのは 1 か所だけである。前者では各 $A_n$ への $\mathbb{N}$ からの全射 $e_n$ を一斉に選び、後者では各 $n$ について $n$ 元集合から $X$ への単射 $g_n$ を一斉に選ぶ。選んだ後の構成（$(n,k)\mapsto e_n(k)$ による全射や、「まだ使っていない最小の番号」による単射）は規則で決まる。前者の素朴な証明を「各 $A_n$ は可算だから $A_n=\{a_{n,0},a_{n,1},\dots\}$ と並べる」と書くと、この 1 行が可算個の番号付けの同時の選択である。$n$ ごとには番号付けが存在しても、その存在から 2 重添字の族 $(a_{n,k})$ が 1 つの集合として得られるわけではない。Button21 §16.5 によれば、Cantor は前者を証明なしに述べ、Dedekind は後者を可算選択公理を 2 回使う形で証明したが、どちらも選択を使っていることを明示しなかった。上の表の 1 行目と 2 行目は、どちらの定理も可算選択公理なしには証明できないことを示している。

選択公理と従属選択公理との関係

可算選択公理の位置づけを比較表にまとめる。

	有限個の選択	可算選択公理	従属選択公理	選択公理
選ぶ対象	有限個の集合から 1 つずつ	可算個の集合から 1 つずつ	前に選んだ元に応じて次を選ぶ列	任意個の集合から 1 つずつ
$\mathsf{ZF}$ で証明できるか	できる	できない	できない	できない
典型的な帰結	有限個の直積が空でない	可算個の可算集合の和が可算	依存する選択による列の再帰的構成	整列可能定理、Zorn の補題、Vitali 集合

$\mathsf{ZF}$ において
$$ \text{選択公理}\ \Longrightarrow\ \text{従属選択公理}\ \Longrightarrow\ \text{可算選択公理} $$
が成り立ち、どちらの矢印も $\mathsf{ZF}$ が無矛盾なら逆にはできない（選択公理の記事の命題「弱い形との含意関係」とその証明）。可算選択公理は各 $X_n$ があらかじめ与えられている場合の選択で、従属選択公理は「$x_n$ を選んでから、$x_n$ に応じて決まる集合から $x_{n+1}$ を選ぶ」という依存する選択を許す。解析学で「帰納的に $x_0,x_1,\dots$ を選ぶ」と書く論法は、後の集合が前の選択に依存するなら従属選択公理を使っている。

独立性

可算選択公理は $\mathsf{ZF}$ から独立である。すなわち、$\mathsf{ZF}$ が無矛盾なら、$\mathsf{ZF}$ は可算選択公理もその否定も証明しない。否定を証明しないことは、選択公理の記事の定理「Gödelによる選択公理の相対的無矛盾性」（$\mathsf{ZF}$ が無矛盾なら $\mathsf{ZFC}$ も無矛盾）と、選択公理が可算選択公理を含意することから従う。可算選択公理自身を証明しないことは、Feferman–Levy のモデル（上の表の 1 行目）で可算選択公理の帰結が偽になることから従う。

補足

解析学・位相空間論での使われ方

可算選択公理は、それと意識されずに使われてきた（Button21 §16.5）。典型的なのは次の場面である。

「各 $n$ について～となる $x_n$ をとる」と書いて点列を作るとき。thm-countable-choice-sequential-continuity の 2 がその例である。
可算個の集合それぞれについて、被覆・近傍・番号付けなどを 1 つずつ選ぶとき。外測度の可算劣加法性（ex-countable-choice-subadditivity）、第 1 可算空間で閉包の点を点列の極限として得ること（第1可算公理の記事の定理「閉包の点列による判定」の必要性の向き）など。
可算個の可算集合の和の可算性を使うとき。各集合の番号付けが 1 つの規則で一斉に与えられる場合（可算集合の記事の例「自然数の有限列の全体」）は、選択は要らない。
実数の閉集合や開集合のように、選び方の規則が位相から得られる族では選択は要らない（prop-countable-choice-closed-subsets、ex-countable-choice-explicit-rules）。証明のどこで選択を使ったかを確かめるには、「選んだ列が 1 つの式で定義できるか」を見ればよい。