今日のアニソン、「多田くんは恋をしない」から『オトモダチフィルム』 [今日のアニソン]
YouTubeには、公式のショートver.もあるので、あわせて紹介するにゃ。
第19回 選択公理と整列可能定理 [集合論入門]
第19回 選択公理と整列可能定理
§1 選択公理
Λを添字の集合とする集合系が与えられたとき、Λからへの関数fのうちで、Λのどの元λに対して
となるようなものの全体を集合系の直積といい、
で表し、各を直積因子という。
特に、とすれば、集合系の直積は、であるような組全体となり、これまでの直積の定義、つまり、
と一致する。
Nを自然数全体の集合とし、Λ=Nのとき、
で表すことがある。
集合系においてとなるものが少なくとも1つあるとき、その直積になる。この裏にあたる命題
Λ≠∅、かつ、すべてのλ∈Λに対して、
が成り立つ
を選択公理という。
直積において、すべてのが同一の集合Aであるとき、をで表す。また、は、ΛからAへの写像全体の集合に一致する。
Aを任意の空でない集合とする。とおくと、X∈ΛならばX≠∅だから、選択公理により、Λによって定まる集合系の直積は空でない。いま、この元を1つとって、それをfとすれば、fはからAへの写像であり、すべてのに対してf(X)=Xとなる。このようなfをAの上の選択関数という。
先に、任意の無限集合Aは可算な部分集合をもつことを示した。
その際、Aから元a₁を選び、次にA−{a₁}から元a₂を選び、さらにA−{a₁,a₂}から元a₃を選び、以下の操作を繰り返すことによって可算集合を得たのだが、実は、この証明において、選択公理を暗黙のうちに使用している。
このことが明確になるように示すと次のようになる。
定理 任意の無限集合は可算部分集合をもつ。
【証明】
集合Aが無限集合であるとし、fを集合Aの上の1つの選択関数とする。
まず、とおく。次に、とおく。
同様に、一般に
とおく。
すると、はAの可算部分集合である。
(証明終)
定理(濃度の大小)
A,Bを集合とする。AからBへの全射が存在すれば、|B|≦|A|である。
【証明】
を全射とする。
b∈Bに対して、
とおくと、fは全射であるので、である。
よって、選択公理より、
は空でない。
をその元とすれば、fが写像であることより、は単射。
したがって、
(証明終)
§2 整列可能定理
空でない任意の集合Aに順序を定め、整列集合にできるか、という問題がある。
選択公理を仮定すると、この問いに肯定的に答えることができる。しかし、この証明は難しいので、ここでは整列可能定理のみを紹介し、整列可能定理から選択公理を証明することにする。
整列可能定理
任意の集合は、その上にある順序を定義して整列集合にすることができる。
問題 整列可能定理を用いて、選択公理を証明せよ。
【証明】
をであるような集合系とする。
とし、整列可能定理によりAを整列する。この整列順序に関するの最小元をとすれば、はの元である。
よって、
(証明終)
また、整列可能定理を用い、次の定理を証明することもできる。
定理 (濃度の比較定理)
α、βを任意の濃度とすると、
のうちの1つだけが成立する。
【証明】
|A|=α、|B|=βである集合A、Bをとり、整列可能定理により、A、Bのそれぞれの上に整列順序を与えることができる。
すると、
のうちのいずれか1つだけが成立する。
ゆえに、
(1)の場合は|A|=|B|、(2)の場合は、(3)の場合は。
すなわち、α=βまたはα≦βまたはα≧β。
したがって、α<β、α=β、β>αのいずれか1つが成立する。
(証明終)
§3 Zornの補題
Aを空でない順序集合とする。Aの任意の空でない全順序部分集合Xに対して上限が存在するとき、Aを帰納的な順序集合という。
Zornの補題
Aが帰納的な順序集合ならば、Aは極大元を持つ。
証明はしないが、次のことが知られている。
定理
次の(1)〜(3)は同値である。
(1) 選択公理
(2) Zornの補題
(3) 整列可能定理
集合論の教科書などでは、選択公理→Zornの補題→整列可能定理の順に証明し、そして、整列可能定理から選択公理を証明し、選択公理、Zornの補題、整列可能定理の3つが同値であることが示されるのが一般的であるが、選択公理から整列可能定理を直接証明することもできる。
そして、この3つは同値なので、どれを出発点、つまり、公理に採用して、理論を展開してもよいのであった。