選択関数
概要
選択関数（choice function）とは、空でない集合の族の各集合に、その集合の元を一つずつ対応させる関数である。添字付きの族 $(A_i)_{i\in I}$ では各 $i$ に $A_i$ の元を対応させる関数で、直積の元と同じものになる。任意の族に選択関数があるという主張は選択公理であり、ZF 上では任意の全射が右逆を持つという主張と同値である。自然数の非空部分集合から最小元を選ぶ場合には、この公理を使わず構成できる。
選択関数とは
選択関数（choice function）とは、空でない集合の族の各集合に、その集合の元を一つずつ対応させる関数である。個々の集合から一つの元を選べることと、族のすべての集合について同時に選ぶ関数が存在することを区別するために使う。任意の集合族に選択関数が存在するとする主張が選択公理である（Jec73 Chapter 1 §1）。
定義と二つの書き方
$\mathcal A$ を空でない集合だけからなる集合とする。関数 $c$ の定義域が $\mathcal A$ で、すべての $A\in\mathcal A$ について $c(A)\in A$ を満たすとき、$c$ を $\mathcal A$ 上の選択関数という。
添字集合 $I$ と空でない集合の族 $(A_i)_{i\in I}$ が与えられたときには、$f(i)\in A_i$ をすべての $i\in I$ について満たす関数 $f$ を、この添字付きの族の選択関数という。同じ集合が複数の添字で現れても、添字ごとに選ぶ値を指定できる。$I=\emptyset$ の場合は空関数が選択関数となる。
添字付きの族の選択関数は、直積 $\prod_{i\in I}A_i$ の元と同じものである。従って「空でない集合の任意の族の直積は空でない」という選択公理の形は、「任意の添字付きの族が選択関数を持つ」と言い換えられる。
全射の右逆
選択関数は、全射の各値に対して原像から一つの代表を選ぶことでもある。
ZF 上で次の二つの主張は同値である。
- 任意の空でない集合の添字付きの族は選択関数を持つ。
- 任意の全射 $p:X\to I$ は、$p\circ s=\operatorname{id}_I$ を満たす関数 $s:I\to X$ を持つ。
1 を仮定する。全射 $p:X\to I$ の各繊維 $p^{-1}(\{i\})$ は空でない。これらの集合を添字 $i$ ごとに選ぶと $s(i)\in p^{-1}(\{i\})$ となり、$p(s(i))=i$ である。
逆に 2 を仮定し、空でない集合の族 $(A_i)_{i\in I}$ を取る。直和集合
$$
X=\{(i,a):i\in I,\ a\in A_i\}
$$
から $I$ への射影 $p(i,a)=i$ は全射である。右逆 $s$ に対し、$s(i)=(i,f(i))$ と書けば $f(i)\in A_i$ であり、$f$ が選択関数になる。$I=\emptyset$ でも空関数で同様に成り立つ。$\square$
規則がある場合の選択
選び方を明示できる族では、選択公理を使わずに選択関数を構成できる。たとえば自然数の空でない部分集合だけからなる族では
$$
c(A)=\min A
$$
が選択関数である。より一般に、族のすべての集合が共通の整列集合の部分集合なら、それぞれの最小元を選べる。
有限個の空でない集合からも、一つずつ選ぶ操作を有限回行えば選択関数を得られる。一方、添字集合が無限で、各集合に指定された元や共通の整列順序がないとき、個々の存在主張だけから選択関数の存在を結論するには選択原理が問題になる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
