2014年12月 7日更新

Partition Principle

PDF版

次の命題をPartition Principleという.

Partition Principle |x|≦*|y| ならば |x|≦|y| である.

これは「 ~ を集合 X の同値関係とするとき |X/~|≦|X| 」と同値である.つまりPartitionを取ると集合は小さくなるという命題なのである.この命題と選択公理の関係を述べるのがこのページの目的である.

なお,定義については制限された選択公理有限集合・無限集合の定義順序数・濃度の簡単なまとめなども参照のこと.

定義 集合 x がidemmultiple ⇔ |x|+|x|=|x|

Weak Partition Principle |x|≦*|y| ならば |y| < |x| でない.

Idemmultiple Partition Principle y がidemmultipleのとき, |x|≦*|y| ならば |x|≦|y| である.

PP- f: y→x を全射として x を整列可能, y をidemmultipleとする.任意の a∈x に対して f-1(a) がDedekind無限であるならば |x|≦|y| である.

定理 選択公理 ⇒ Partition Principle

定理 Partition Principle ⇒ Weak Partition Principle

定理 Weak Partition Principle ⇒ Idemmultiple Partition Principle

証明 y をidemmultipleで |x|≦*|y| とする. |x|+|y|≦*|y|+|y|=|y| だからWeek Partition Principleにより |y| < |x|+|y| でない.故に |y|=|x|+|y| となる.従って |x|≦|y| である.

定理 Idemmultiple Partition Principle ⇒ PP-

定理 PP- ⇔ 任意の順序数 α に対して ACアレフα

証明 ⇐ は明らかであるから, ⇒ を示せばよい.

α に関する超限帰納法で示す. { Xβ }β<ωα を非空集合の族とする. γ < ωα に対して Cγ := Πβ<γXβ と置く.帰納法の仮定から Cγ≠ ∅ である. Γ をHartogs関数として, γ < ωα に関する超限帰納法で集合 Dγ と基数 λγ

λγ := max{ |Γ(∪δ<γDδ)|, supδ<γλδ+ }
Dγ := ω×Cγ×λγ

と定義し, D := ∪γ<ωαDγ , λ := supγ<ωαλγ と定める. f: D→λ を射影とすればこれは全射で,任意の μ < λ に対して f-1(μ) はDedekind無限である. PP- により単射 g: λ→D が存在する. g が単射だから,任意の β < ωα に対して,ある β < γ < ωα と μ < λ が存在して f(μ)∈ω×Cγ×λγ となる.故に g を使って { Xβ }β<ωα の選択関数を構成することができる.

「任意の順序数 α に対して ACアレフα 」から選択公理は従わないことが知られている.故に PP- は選択公理より真に弱い.一方Partition Principleが選択公理と同値かどうかは未解決問題らしい.

定理 双対Bernsteinの定理 ⇒ Weak Partition Principle

証明 |x|≦*|y| とする. |y| < |x| と仮定する. |y|≦*|x| である.故に双対Bernsteinの定理から |x|=|y| となり |y| < |x| に矛盾する.従って |y| < |x| でない.

双対Bernsteinの定理 ⇒ 任意の順序数 α に対して ACアレフα

PP' f: y→x を全射とする.任意の a∈x に対して f-1(a) が有限またはDedekind無限であるならば |x|≦|y| である.

命題 Partition Principle ⇔ PP'

証明 ⇒ は明らかであるから, ⇐ を示せばよい.

PP' が成り立つとする.明らかに PP- が成り立つ.よって可算選択公理( ACアレフ0 )が成り立つから,任意の集合は有限またはDedekind無限である.故にPartition Principleが成り立つ.

定理 { Xλ }λ∈Λ, { Yλ }λ∈Λ が互いに素な集合族で, λ∈Λ に対して |Xλ| = |Yλ| ならば |∪λ∈ΛXλ| = |∪λ∈ΛYλ| である. ⇒ Partition Principle

証明 PP' を示せばよい.

f: y→x を全射として,任意の a∈x に対して f-1(a) が有限またはDedekind無限であるとする. a∈x に対して

Xa := f-1(a)
Ya := n (|Xa| = n のとき)
Ya := Xasqcup { 0 } (Xa がDedekind無限のとき)

と定める.任意の a∈x に対して |Xa| = |Ya| だから,仮定により |∪λ∈ΛXλ| = |∪λ∈ΛYλ| である.任意の a∈x に対して 0∈Ya だから |x|≦Σa∈x|Ya| = |∪λ∈ΛYλ| = |∪λ∈ΛXλ| = |y| である.

参考文献

コメント

コメントはまだありません。

コメントする

感想、意見、質問など何でもどうぞ。
※書き込んだのに表示されない場合は、ページをリロードしてみてください。