2013年7月 2日更新

Königの定理

PDF版

順序数や濃度の基本的な性質については順序数・濃度の簡単なまとめを参照.

次の命題をKönigの定理という.

命題 { Xλ }λ∈Λ と { Yλ }λ∈Λ が集合族で,各 λ∈Λ に対して |Xλ| < |Yλ| ならば, |∪λ∈ΛXλ| < |Πλ∈ΛYλ| である.

定理 次の命題は( ZF 上)同値.

  1. 選択公理
  2. 各 λ∈Λ に対して |Xλ| < |Yλ| ならば, |∪Xλ| ≦ |ΠYλ| である.
  3. 各 λ∈Λ に対して |Xλ| < |Yλ| ならば, |∪Xλ| ≦* |ΠYλ| である.
  4. 各 λ∈Λ に対して |Xλ| < |Yλ| ならば, |ΠYλ| \not\leq* |∪Xλ| である.
  5. 各 λ∈Λ に対して |Xλ| < |Yλ| ならば, |ΠYλ| \not\leq |∪Xλ| である.

証明 (1 ⇒ 2) { Xλ }λ∈Λ, { Yλ }λ∈Λ を集合族で,各 λ∈Λ に対して |Xλ| < |Yλ| を満たすとする. λ≠μ に対して Xλ∩Xμ= ∅ としてよい.

Aλ := { <f, y>∈YλXλ×Yλ | fは単射,y ∉ Im(f) }

と置けば Aλ≠ ∅ である.よって選択公理により (<fλ, yλ>)λ∈Λ∈Πλ∈ΛAλ が存在する. μ∈Λ に対して gμ: ∪Xλ→Yμ

gμ(x) := fμ(x) (x∈Xμ のとき)
gμ(x) := yμ (x ∉ Xμ のとき)

と定める.これにより g: ∪Xλ→ΠYλ が g(x) := (gλ(x))λ∈Λ で定まる. g は単射である.

任意の a∈Xλ, b∈Xμ, a≠b を取る.

(i) λ≠μ ならば gμ(a)=yμ, gμ(b)=fμ(b) となり, yμ ∉ Im(fμ) だったから gμ(a)≠gμ(b) となる.故に g(a)≠g(b) である.

(ii) λ=μ ならば gμ(a)=fμ(a), gμ(b)=fμ(b) であるから fμ の単射性により gμ(a)≠gμ(b) となる.故に g(a)≠g(b) である.

よって |∪Xλ|≦|ΠYλ| が分かった.

(2 ⇒ 3) |X|≦|Y| ⇒ |X|≦*|Y| だから明らか.

(3 ⇒ 1) {X_λ}_{λ∈Λ} を非空集合の族とする.各 λ∈Λ に対して 1 < |Xλ| としてよい.このとき Yλ:= { ∅ } とすれば, |Yλ| = 1 < |Xλ| だから仮定2により 1 = |∪Yλ|≦*|ΠXλ| である.その為には ΠXλ≠ ∅ でなければならない.

(1 ⇒ 4)全射 f: ∪Xλ→ΠYλ が存在すると仮定する. πλ: ΠYλ→Yλ を標準全射とすれば写像 gλ := πλf|Xλ: Xλ→Yλ が得られる.このとき Cλ := Yλ\Im(gλ)≠ ∅ だから選択公理により (yλ)λ∈Λ∈Πλ∈ΛCλ⊂Πλ∈ΛYλ が存在する. f は全射だったから,ある x∈∪Xλ が存在して f(x)=(yλ)λ∈Λ となる. x∈Xμ とすれば gμ(x)=πμ(f(x))=πμ((yλ)λ∈Λ)=yμ となり yμ ∉ Im(gμ) に矛盾する.

(4 ⇒ 5) |X|\not\leq*|Y| ⇒ |X|\not\leq|Y| だから明らか.

(5 ⇒ 1) {X_λ}_{λ∈Λ} を非空集合の族とする. λ∈Λ に対して Yλ:= ∅ とすれば, |Yλ| = 0 < |Xλ| だから仮定3により |ΠXλ|\not\leq|∪Yλ| = 0 である.その為には ΠXλ≠ ∅ でなければならない.

選択公理 ⇔ Konigの定理

証明 前定理の条件2かつ条件5がKönigの定理であるから明らか.

定理 選択公理
⇔ { Xλ }λ∈Λ が集合族で,各 λ∈Λ に対して 2≦|Xλ| ならば |∪λ∈ΛXλ|≦|Πλ∈ΛXλ| .

証明 ( ⇒ ) { Xλ }λ∈Λ を各 λ∈Λ に対して 2≦|Xλ| なる集合族とする. Aλ:= { <a, b>∈Xλ2 | a≠b } と置けば Aλ≠ ∅ である.よって選択公理により (<aλ, bλ>)λ∈Λ∈Πλ∈ΛAλ が存在する. μ∈Λ に対して fμ: ∪Xλ→Xμ

fμ(x) := x (x∈Xμ のとき)
fμ(x) := aμ (x∈Xλ\{ aλ }, λ≠μ のとき)
fμ(x) := bμ (x=aλ, λ≠μ のとき).

と定める.これにより f: ∪Xλ→ΠYλ が f(x) := (fλ(x))λ∈Λ で定まる. f は単射である.よって |∪Xλ|≦|ΠXλ| が分かった.

( ⇐ ) {X_λ}_{λ∈Λ} を非空集合の族とする.各 λ∈Λ に対して 2≦|Xλ| としてよい.このとき 0 < |∪Xλ|≦|ΠXλ| である.

参考文献

コメント

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

コメントする

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