選択公理
選択公理(せんたくこうり、axiom of choice、選出公理ともいう)とは公理的集合論における公理のひとつで、どれも空でないような集合を元とする集合(すなわち、集合の集合)があったときに、それぞれの集合から一つずつ元を選び出して新しい集合を作ることができるというものである。1904年にエルンスト・ツェルメロによって初めて正確な形で述べられた。
空集合を要素に持たない任意の集合族に対して、各要素(それ自体が集合である)から一つずつその要素を選び、新しい集合を作ることができる。あるいは同じことであるが、空でない集合の空でない任意の族 \mathcal{A} に対して写像 f \colon \mathcal{A} \to \textstyle{\bigcup} \mathcal{A}:=\textstyle{\bigcup_{A \in \mathcal{A}}A であって任意の x \in \mathcal{A} に対し f(x) \in x なるものが存在する、と写像を用いて言い換えることが出来る(ここで存在が要求される写像 f を選択関数という)。これは次の命題と同値である。
{Aλ}λ∈Λ をどれも空集合でないような集合の族とすると、それらの直積も空集合ではない。記号で書けば、
\left(\forall \lambda \in \Lambda \right)\left[A_{\lambda} \neq \emptyset \right]
\implies \textstyle\prod_{\lambda \in \Lambda} A_\lambda \neq \emptyset.
以下の命題は全て選択公理と同値である。つまり、以下の命題のいずれかを仮定すると選択公理を証明することができるし、逆に選択公理を仮定すると以下の命題が全て証明できる。
整列可能定理:任意の集合は整列可能である。
ツォルンの補題:順序集合において、任意の全順序部分集合が有界ならば、極大元が存在する。(実際の数学では、この形で選択公理が使われることも多い。)
テューキーの補題:有限性を満たす空でない任意の集合族は包含関係に関する極大元を持つ。
比較可能定理:任意の集合の濃度は比較可能である。
直積定理:無限個の空集合でない集合の直積は空集合ではない。
右逆写像の存在:全射は右逆写像を有する。
ケーニッヒ(Julius König)の定理:濃度の小さい集合の直和より、濃度の大きい集合の直積のほうが濃度が大きい。
ベクトル空間における基底の存在: 全てのベクトル空間は基底を持つ(1984年にAndreas Blassによって選択公理と同値であることが証明された。ただし、正則性公理が必要になる)。
チコノフの定理:コンパクト空間の任意個の積空間はコンパクトになる。
クルルの定理:単位元をもつ環は極大イデアルを持つ。
選択公理、もしくはそれと同値な命題を適用することで、以下を示すことができる。
全ての体には代数的閉包が存在する。
集合論の創始者ゲオルク・カントールは、選択公理を自明なものとみなしていた。
実際、有限個の集合からなる集合族であれば、そのそれぞれの集合の中から順に1つずつ元を選び出し、それらを併せて集合とすればよいのであるから、このような操作ができることは自明である。
しかし、ツェルメロによる整列可能定理の証明に反論する過程で、エミーユ・ボレル、ルネ=ルイ・ベール、アンリ・ルベーグ、バートランド・ラッセルなどが選択公理の存在に気付き、新たな公理であることが認識されるようになった。確かに、無限個の集合からなる集合族の場合、上のような操作を想定しても「順に選び出す」操作は有限回で終了することはないのだから、このような操作を行えるかどうかは必ずしも明らかではない。
選択公理は、それ自身もまたその否定もほかの公理からは証明できないものであること、すなわち独立であることが示された(クルト・ゲーデル、ポール・コーエン)が、これは公理的集合論における大きな成果であろう。なお、ZF(ツェルメロ=フレンケルの公理系)に一般連続体仮説を加えると選択公理を証明できる。従って、一般連続体仮説と選択公理は何れもZFとは独立だが、前者の方がより強い主張であると言える。ZFに選択公理を加えた公理系をZFCと呼ぶ。
選択公理を仮定することによって導かれる、一見、奇怪で非直観的な結果の中でも、バナッハ=タルスキーのパラドックスは有名なもので、「有限個の部分に分割し、それらを回転・平行移動操作のみを使ってうまく組み替えることで、元の球と同じ半径の球を2つ作ることができる」と、初歩的な概念のみで表現することができる。ただ、ここでの「有限個の分割」は、通常イメージされる単純な分割(包丁でいくつかのパーツに切り分けるようなもの)ではなく、非常に特殊な分割であるため、「"奇怪な分割"をした結果、奇怪な結果(2つに増える)が生じた」にすぎないという側面もある。
なお、ステファン・バナフ(バナッハ)とタルスキは論文の冒頭で、「証明のなかに、この公理(選択公理)が果たす役割は、注目するに値する」と述べているだけであり、バナッハ=タルスキーのパラドックスによって選択公理が正しくないと明確に主張したわけではない。
選択公理とは矛盾するが、ZFCから選択公理を除いたZFとは矛盾しないような命題は数多く発見されている。たとえばロバート・ソロヴェイは強制法を用いて実数の集合が全てルベーグ可測であるようなZFのモデルを構成した。
1964年にヤン・ミシェルスキが導入した決定性公理もその一つである。これはその後、無矛盾性証明のために頻繁に用いられている。ZFに決定性公理を付け加えた公理系の無矛盾性と、ZFに選択公理と巨大基数の一種であるウッディン基数の存在を公理として付け加えた公理系の無矛盾性が同値となるというウッディンの定理は、互いに矛盾する公理を関係づける非常に重要なものである。
選択公理には様々な変種が存在する。
選択公理よりも弱い公理として、可算選択公理(countable axiom of choice,denumerable axiom of choice)というものも考えられている。全ての集合は可算集合を含むこと、可算集合の可算和が可算集合であることは、この公理により証明できる。
カントール、ラッセル、ボレル、ルベーグなどは、無意識のうちに可算選択公理を使ってしまっている。
集合族の要素を特定の有限集合に制限した公理も研究されている。即ち、
ACn : n元集合からなる任意の集合族は選択関数を持つ。
という形の公理である。
この種の公理について以下のようなことが知られている(すべてZF公理系を仮定)。
AC2 \Rightarrow AC4
n \neq 1,2,4 ならば AC2 \nRightarrow ACn
各 n \in N について ACn が成り立つ仮定の下でも、「有限集合からなる任意の集合族は選択関数を持つ」(Axiom of choice for finite sets)を証明できない。
ZFでは AC2 を証明できない。
AC2 \Rightarrow AC4を示すには、4元集合からなる集合族 F に選択関数が存在することを示せば良い。まず  \{\{a,b\}:a,b \in \bigcup F , a\neq b\} に AC2 を適用して、選択関数 g を得る。次に g を使って F の各元 \rm A から元をひとつ取りだすことを考える。集合 {\rm B} を  \{\{a,b\}:a,b \in {\rm A} , a\neq b \} とおくと、{\rm B} は _4C_2=6元集合となる。\rm A の元 a に対し、q(a) = |\{b \in B : g(b) = a \}| という関数を定め、q(a) の最小値を m とおく。集合 {\rm M} を \{a \in {\rm A} : q(a) = m\} とおくと、{\rm A} は4元集合なので {\rm M} の濃度は  1, 2, 3, 4  のいずれかであるが、|\rm M|=4と仮定すると、4q(a)=\sum_{a\in \rm A}q(a)=|\rm B|=6となり矛盾する。|\rm M| = 1 である場合は、{\rm M} の元を選択関数 f({\rm A}) の値とすればよい。|M| = 2 の場合は、f({\rm A}) = g({\rm M}) とする。最後に |M| = 3 である場合は、{\rm A} \setminus {\rm M} の元を f({\rm A}) の値とすればよい。