選択関数
概要
選択関数（choice function）とは、集合の集合 $\mathcal{A}$ の各元 $A$ にその元 $c(A)\in A$ を対応させる写像である。添字付きの族 $(A_i)_{i\in I}$ では各 $i$ に $A_i$ の元を対応させる写像で、直積 $\prod_{i\in I}A_i$ の元と同じものになる。任意の族に選択関数があるという主張が選択公理である。ZF でも、族の和集合の整列順序から最小元をとるなど規則が書ける場合には選択関数を構成でき、集合 $X$ の空でない部分集合全体が選択関数をもつことは $X$ が整列可能であることと同値である。互いに交わらない族では選択関数は代表元の集合と対応し、同値関係の射影の切断とも同じものである。
空でない集合が一つあれば、その元を一つとることはいつでもできる。空でない集合がたくさんあるとき、各集合から元を一つずつ「同時に」とった結果を一つの関数として表したものが選択関数（choice function）である。「各集合に元がある」ことと「全部の集合について一斉に元を指定する関数がある」ことは、量化の順序が違う別の主張であり、その違いを正確に扱うための言葉が選択関数である。
以下、基礎の体系は選択公理を含まない集合論 $\mathsf{ZF}$ とし、$\mathbb{N}=\{0,1,2,\dots\}$ とする。
定義
$\mathcal{A}$ を集合の集合とする。写像 $c\colon\mathcal{A}\to\bigcup\mathcal{A}$ が、すべての $A\in\mathcal{A}$ について
$$
c(A)\in A
$$
を満たすとき、$c$ を $\mathcal{A}$ の選択関数という。
添字集合 $I$ で添字づけられた集合の族 $(A_i)_{i\in I}$ については、写像 $f\colon I\to\bigcup_{i\in I}A_i$ で、すべての $i\in I$ について $f(i)\in A_i$ を満たすものを、この添字付きの族の選択関数という。
$\mathcal{A}$ が選択関数をもつなら、$\mathcal{A}$ の元はすべて空でない。空集合 $\emptyset\in\mathcal{A}$ に対して $c(\emptyset)\in\emptyset$ となる値はないからである。一方 $\mathcal{A}=\emptyset$ なら空写像がただ一つの選択関数である。
二つの書き方の違いは、同じ集合が複数の添字で現れる場合に出る。添字付きの族の選択関数は添字ごとに値を指定でき、族 $(A_i)_{i\in I}$ の選択関数の全体は直積 $\prod_{i\in I}A_i$ そのものである。
$\mathcal{A}=\{\{1,2\},\{2,3\}\}$ の選択関数は、$\{1,2\}$ での値が $2$ 通り、$\{2,3\}$ での値が $2$ 通りなので $2\times2=4$ 個ある。そのうち二つの集合に同じ値 $2$ を与えるものが一つある。選択関数は単射である必要はない。
$A=\{1,2\}$、$I=\{0,1\}$、$A_0=A_1=A$ とすると、添字付きの族 $(A_i)_{i\in I}$ の選択関数は $f(0),f(1)\in\{1,2\}$ の $4$ 個だが、集合 $\{A_0,A_1\}=\{A\}$ の選択関数は $2$ 個しかない。一般に、空でない有限集合からなる有限の族 $(A_i)_{i\in I}$ の選択関数の個数は $\prod_{i\in I}\lvert A_i\rvert$ である。
選択公理は「空でない集合だけからなる任意の集合 $\mathcal{A}$ は選択関数をもつ」という主張である。添字付きの族で述べても、直積が空でないと述べても、任意の全射が右逆写像をもつと述べても同値であり、その証明は 選択公理 の記事の命題「選択公理の同値な言い換え」にある。選択関数が大事なのは、選択公理を仮定しなくても、個々の族について「選択関数があるか」「具体的に書けるか」を問えるからである。この記事では主に後者を扱う。
直感
選択関数は「選び方の規則」である。Russell の例でいえば、無限個の靴の対からは「右の靴」という規則で一斉に選べるが、左右の区別のない靴下の対には規則がない。規則が書ける族では、その規則が選択関数を一つ定義し、$\mathsf{ZF}$ の中で存在が証明できる。規則が書けない族では、選択関数の存在は選択公理に頼るしかなく、実際に $\mathsf{ZF}$ だけでは証明できない場合がある。
規則の典型は「順序を一つ固定して最小元をとる」ことである。下の定理は、ある集合の空でない部分集合すべてにわたる選択関数と、その集合の整列順序とが、実は同じだけの情報であることを示す。
規則で書ける選択関数
- $\mathbb{N}$ の空でない部分集合 $A$ に対し $c(A):=\min A$ とおくと、$\mathbb{N}$ は整列順序なので最小元が存在し、$c$ は $\mathcal{P}(\mathbb{N})\setminus\{\emptyset\}$ の選択関数である。
- $\mathbb{Z}$ の空でない部分集合には最小元がないことがある。そこで $c(A)$ を「$A$ の元のうち絶対値が最小のもの。そのような元が $\pm m$ の二つあれば $m\ge0$ の方」と定める。絶対値の集合 $\{\lvert a\rvert\mid a\in A\}\subset\mathbb{N}$ には最小元があるので、$c$ は選択関数である。
- $\mathbb{Q}$ については、全単射 $e\colon\mathbb{N}\to\mathbb{Q}$ を一つ固定し、$c(A):=e\bigl(\min e^{-1}[A]\bigr)$ とおく。$e$ を一つとることは一つの集合から一つの元をとるだけなので選択公理は要らない。
- $\mathbb{R}$ の空でない開集合 $O$ には有理数が含まれるので、上の $e$ を使って $c(O):=e\bigl(\min e^{-1}[O\cap\mathbb{Q}]\bigr)$ とおけば、$\mathbb{R}$ の空でない開集合全体の選択関数になる。空でない閉集合についても規則が書ける（可算選択公理 の記事の命題「実数の閉集合からの選択」）。
これらの例に共通する形を命題にまとめる。
（$\mathsf{ZF}$）$\mathcal{A}$ を空でない集合だけからなる集合とする。
- $\bigcup\mathcal{A}$ 上に整列順序 $\preceq$ があれば、$c(A):=\min_{\preceq}A$ は $\mathcal{A}$ の選択関数である。
- $\mathcal{A}$ の元がすべて有限集合で、$\bigcup\mathcal{A}$ 上に全順序 $\le$ があれば、$c(A):=\min_{\le}A$ は $\mathcal{A}$ の選択関数である。
- $\mathcal{A}$ が有限集合なら、$\mathcal{A}$ は選択関数をもつ。
- 各 $A\in\mathcal{A}$ は $\bigcup\mathcal{A}$ の空でない部分集合なので、整列順序の定義により最小元をもつ。$c$ は $\preceq$ だけから式で決まるので、分出公理により $\mathcal{A}\times\bigcup\mathcal{A}$ の部分集合として定義でき、$c(A)\in A$ である。
- 全順序集合の空でない有限部分集合は最小元をもつ（元の個数についての帰納法：一元集合ではその元が最小元で、$B\cup\{b\}$ の最小元は $B$ の最小元と $b$ の小さい方である）。あとは 1 と同じである。
- $\mathcal{A}$ の元の個数についての帰納法による。これは 選択公理 の記事の例「有限族の選択関数」で証明されている。$\square$
2 の「有限」は外せない。$\mathbb{Z}$ は全順序集合だが、$\mathbb{Z}$ 自身には最小元がない。3 の「有限」も外せない（下の反例の表）。
整列順序との同値
$\mathbb{N}$ の例では、整列順序から選択関数が作れた。逆に、集合 $X$ の空でない部分集合すべてにわたる選択関数が一つあれば、そこから $X$ の整列順序が作れる。以下、$X$ の部分集合 $W$ とその上の整列順序 $<_W$ の組を単に $W$ と書き、$w\in W$ について $W_{< w}:=\{v\in W\mid v<_W w\}$ とおく。
（$\mathsf{ZF}$）集合 $X$ について、次の二つは同値である。
- $\mathcal{P}(X)\setminus\{\emptyset\}$ は選択関数をもつ。
- $X$ 上に整列順序が存在する。
2 ⇒ 1 は prop-choice-function-from-order の 1 である。1 ⇒ 2 を、順序数を使わない Zermelo の方法で示す。選択関数 $g\colon\mathcal{P}(X)\setminus\{\emptyset\}\to X$ を固定し、$X$ の部分集合 $W$ と整列順序 $<_W$ の組が
$$
w=g(X\setminus W_{< w})\qquad(\text{すべての } w\in W)
$$
を満たすとき、$W$ を $g$-列と呼ぶ。「$W$ の各元は、それより前の元を除いた残りから $g$ が選んだ元である」という意味である。$X\setminus W_{< w}$ は $w$ を含むので空でなく、右辺は定義される。
$A$、$B$ が $g$-列なら、一方は他方の始切片である。すなわち、たとえば $A\subset B$ で、$A$ 上で $<_A$ と $<_B$ が一致し、$b<_B a\in A$ なら $b\in A$ となる。
$C$ を、$x\in A\cap B$ で $A_{< x}=B_{< x}$ となり、かつこの集合の上で $<_A$ と $<_B$ が一致するもの全体とする。
段 1（$C$ は $A$ の始切片で、$C$ 上で二つの順序は一致する）．$x\in C$、$y<_A x$ とする。$y\in A_{< x}=B_{< x}$ なので $y\in B$、$y<_B x$ である。$A_{< y}$ と $B_{< y}$ の元はどちらも $A_{< x}=B_{< x}$ に含まれ、そこで二つの順序は一致するので $A_{< y}=B_{< y}$ であり、$y\in C$ となる。また $x,y\in C$、$y<_A x$ なら $y\in A_{< x}=B_{< x}$ より $y<_B x$ であり、対称性から $C$ 上で $<_A$ と $<_B$ は一致する。同じ議論で $C$ は $B$ の始切片でもある。
段 2（$C=A$ または $C=B$）．$C\neq A$ かつ $C\neq B$ と仮定する。$a:=\min_{<_A}(A\setminus C)$、$b:=\min_{<_B}(B\setminus C)$ とおく。$C$ が $A$ の始切片で $a$ が $C$ の外の最小元なので $A_{< a}=C$ であり、同様に $B_{< b}=C$ である。$g$-列の条件から
$$
a=g(X\setminus A_{< a})=g(X\setminus C)=g(X\setminus B_{< b})=b .
$$
すると $a\in A\cap B$、$A_{< a}=C=B_{< a}$ で、$C$ 上で二つの順序は一致するので $a\in C$ となり、$a\notin C$ に反する。
$C=A$ なら、段 1 により $A$ は $B$ の始切片で順序も一致する。$C=B$ なら逆である。$\square$
$g$-列の全体は $\mathcal{P}(X)\times\mathcal{P}(X\times X)$ から分出公理で得られる集合である。$W^*$ をすべての $g$-列の和集合とし、$x,y\in W^*$ について「$x$ と $y$ を含むある $g$-列 $A$ で $x<_A y$」のとき $x< y$ と定める。lem-choice-function-g-sets により、二つの $g$-列の一方は他方の始切片で順序も一致するので、$<$ は矛盾なく定まり、$W^*$ 上の全順序になる。また各 $g$-列 $A$ は $(W^*,<)$ の始切片である：$y< x\in A$ で $y$ が $g$-列 $B$ に属するなら、$A\subset B$ の場合は $y<_B x$ と始切片の性質から $y\in A$、$B\subset A$ の場合は初めから $y\in A$ である。
$<$ は整列順序である。空でない $S\subset W^*$ の元 $s$ をとり、$s$ を含む $g$-列 $A$ で $m:=\min_{<_A}(S\cap A)$ をとる。$t\in S$、$t< m$ なら、$A$ が始切片なので $t\in A$ となり $m$ の最小性に反する。よって $m$ は $S$ の最小元である。
$W^*$ は $g$-列である。$w\in W^*$ が $g$-列 $A$ に属するなら、$A$ が始切片なので $W^*_{< w}=A_{< w}$ であり、$w=g(X\setminus A_{< w})=g(X\setminus W^*_{< w})$ となる。
最後に $W^*=X$ を示す。$W^*\neq X$ なら $z:=g(X\setminus W^*)$ は $W^*$ に属さない。$W^*\cup\{z\}$ に、$W^*$ の順序の後ろに $z$ を置いた整列順序を入れると、$z$ より前の元の全体は $W^*$ なので $z=g(X\setminus W^*)$ が成り立ち、これは $g$-列である。すると $z$ は $g$-列の和集合 $W^*$ に属し、矛盾する。よって $W^*=X$ であり、$<$ は $X$ の整列順序である。$\square$
この証明の構成は、$g$ で先頭から順に元を選んで並べていく操作をまとめて一度に行ったものである。「$X$ の元を $g$ で一つずつ選び尽くす」という素朴な議論を、超限の長さの再帰を使わずに正当化している。すべての集合についての形「選択公理と整列可能定理は同値」は 選択公理 の記事の定理「整列可能定理との同値」にあり、そこでは順序数と超限再帰による証明が与えられている。
thm-choice-function-well-ordering により、$\mathcal{P}(\mathbb{R})\setminus\{\emptyset\}$ の選択関数があることと、$\mathbb{R}$ が整列可能であることは同値である。$\mathbb{R}$ が整列できない $\mathsf{ZF}$ のモデルがある（Jec73 Lemma 5.15、p. 67。この記事では証明しない）ので、$\mathsf{ZF}$ が無矛盾なら、$\mathcal{P}(\mathbb{R})\setminus\{\emptyset\}$ の選択関数の存在は $\mathsf{ZF}$ では証明できない。ex-choice-function-explicit で開集合や閉集合から選べたのは、族を位相で絞ったからである。
代表元の集合と切断
選択関数は関数としてでなく、選ばれた元の集合として表すこともできる。空でない集合からなる $\mathcal{A}$ に対し、$T\subset\bigcup\mathcal{A}$ がすべての $A\in\mathcal{A}$ とちょうど一点で交わるとき、$T$ を $\mathcal{A}$ の代表元の集合（横断集合、選択集合ともいう）という。
（$\mathsf{ZF}$）$\mathcal{A}$ を空でない集合だけからなる集合とする。
- $\mathcal{A}$ の元が互いに交わらないなら、$\mathcal{A}$ の選択関数 $c$ と代表元の集合 $T$ は、$T=c[\mathcal{A}]$ と「$c(A):=T\cap A$ のただ一つの元」によって一対一に対応する。
- 一般の $\mathcal{A}$ について、$\mathcal{A}$ が選択関数をもつことと、互いに交わらない集合の族 $\mathcal{A}':=\{\{A\}\times A\mid A\in\mathcal{A}\}$ が代表元の集合をもつことは同値である。
- $c$ を選択関数とし、$T:=c[\mathcal{A}]$ とおく。$A\in\mathcal{A}$ について $c(A)\in T\cap A$ である。$t\in T\cap A$ なら $t=c(B)$ となる $B$ があり、$t\in A\cap B$ だから互いに交わらないことより $A=B$、$t=c(A)$ である。よって $T\cap A=\{c(A)\}$。逆に $T$ が代表元の集合なら、$c(A)$ を $T\cap A$ のただ一つの元と定めれば選択関数になる。二つの対応が互いに逆であることは定義から直ちに分かる。
- $A\neq B$ なら $\{A\}\times A$ と $\{B\}\times B$ は第一成分が違うので交わらず、各 $\{A\}\times A$ は空でない。$c$ が $\mathcal{A}$ の選択関数なら $A\mapsto(A,c(A))$ は $\mathcal{A}'$ の選択関数であり、逆に $\mathcal{A}'$ の選択関数の値の第二成分をとれば $\mathcal{A}$ の選択関数になる。$\mathcal{A}\to\mathcal{A}'$、$A\mapsto\{A\}\times A$ は全単射なので、あとは 1 を $\mathcal{A}'$ に適用すればよい。$\square$
1 の「互いに交わらない」は外せない。$\mathcal{A}=\{\{0,1\},\{1,2\},\{0,2\}\}$ は選択関数（たとえば $\{0,1\}\mapsto0$、$\{1,2\}\mapsto1$、$\{0,2\}\mapsto2$）をもつが、代表元の集合をもたない。$T\subset\{0,1,2\}$ が三つの集合とそれぞれ一点で交わるとすると、三つの交わりの個数の和は $3$ だが、$\{0,1,2\}$ の各元はちょうど二つの集合に属するので、その和は $2\lvert T\rvert$ に等しく偶数になるからである。
互いに交わらない族の典型は、同値関係 $\sim$ による商集合 $X/{\sim}$ である。自然な射影 $\pi\colon X\to X/{\sim}$ について、$\pi\circ s=\mathrm{id}$ を満たす写像 $s\colon X/{\sim}\to X$ を $\pi$ の切断という（切断）。切断は各同値類 $C$ に $s(C)\in C$ を対応させるので、$X/{\sim}$ の選択関数にほかならない。1 により、次の三つは同じものの言い換えである。
$$
\text{$X/{\sim}$ の選択関数}\ \longleftrightarrow\ \text{射影 $\pi$ の切断}\ \longleftrightarrow\ \text{同値類の代表元の集合}
$$
たとえば整数の $\bmod n$ の合同では、代表元の集合 $\{0,1,\dots,n-1\}$ が規則で書ける。これに対して $\mathbb{R}$ 上の $x\sim y\iff x-y\in\mathbb{Q}$ では代表元の集合を書く規則がなく、選択公理でその存在を認めると Lebesgue 可測でない集合が得られる（選択公理 の記事の例「Vitali集合の構成」）。
反例：条件を外すと崩れること
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\mathcal{A}$ の元がすべて空でない | $\mathcal{A}=\{\emptyset,\{0\}\}$ | 選択関数の存在 |
| 和集合の整列順序（prop-choice-function-from-order の 1） | $\mathcal{P}(\mathbb{R})\setminus\{\emptyset\}$ | $\mathsf{ZF}$ での選択関数の存在 |
| 和集合の全順序（prop-choice-function-from-order の 2） | 二元集合の可算族で選択関数をもたないもの | $\mathsf{ZF}$ での選択関数の存在 |
| 族が有限（prop-choice-function-from-order の 3） | 同上（可算無限の族） | $\mathsf{ZF}$ での選択関数の存在 |
| 元が互いに交わらない（prop-choice-function-transversal の 1） | $\{\{0,1\},\{1,2\},\{0,2\}\}$ | 選択関数から代表元の集合が得られる |
1 行目では $c(\emptyset)\in\emptyset$ となる値がなく、破れている条件は「各元が空でない」ことである。2 行目は ex-choice-function-reals による。3 行目と 4 行目は、二つずつの元からなる集合の可算族 $\{P_n\mid n\in\mathbb{N}\}$ で選択関数をもたないものがある $\mathsf{ZF}$ のモデル（Jec73 Theorem 5.20、p. 71。この記事では証明しない）による（$\mathsf{ZF}$ が無矛盾なら）。そこでは各 $P_n$ は二元集合なので有限で、どの有限個の $P_n$ も選択関数をもつが、族全体は選択関数をもたない。したがって $\bigcup_nP_n$ には全順序がなく（あれば 2 により選択関数ができる）、「有限個なら選べる」から「可算個でも選べる」へは進めない。$\mathbb{R}$ の二元部分集合なら小さい方を選べばよいので、このモデルの $P_n$ は実数の集合を元とする集合の対である（Jec73 §5.4、p. 68）。5 行目は前節で確かめた。
注意
- 選択関数は一般に一つに決まらない。$\mathcal{A}$ のある元が二つ以上の元をもてば、そこでの値を取り替えた別の選択関数がある。
- 選択関数の存在を示すことと、選択関数を一つ具体的に書くことは違う。ex-choice-function-explicit と prop-choice-function-from-order は後者で、選択公理は前者だけを保証する。
- 可算個の族に限った選択を可算選択公理、前の選択に依存する可算回の選択を従属選択公理という。どちらも選択公理より弱い原理である。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
