有限集合・無限集合の定義と選択公理
alg-d
http://alg-d.com/math/ac/
2016
年
1
月
24
日
次の命題の証明は順序数・濃度の簡単なまとめを参照． 命題 1. 濃度κ, λ≥ 2に対しκ + λ≤ κ · λ． 命題 2. 任意のアレフℵに対してℵ2 =ℵ． 命題 3. 濃度κ, λ, µとアレフℵがκ· ℵ ≤ λ + µを満たすとき，κ ≤ λまたはℵ ≤ µと なる． ある自然数nと全単射X −→ nが存在するとき，X を有限集合といい，有限集合で ない集合を無限集合という．このように，通常無限集合は「有限集合でない」と定義され るが，では無限集合を直接定義することはできるであろうか．そうして考えられたのが Dedekind無限集合である． 定義. Xを集合とする． 1. X がDedekind無限⇐⇒ |Y | = |X|となる真部分集合Y ⊊ X が存在する． 2. X がDedekind有限⇐⇒ X がDedekind無限でない． 明らかに Dedekind無限集合は無限集合(即ち有限集合はDedekind有限)だから，逆 に無限集合はDedekind無限(即ち Dedekind有限集合はは有限集合)であることを示し たいのだが，実はこれには選択公理を使わなければいけないことが知られている． 命題 4. 集合Xに対して次の条件は(ZF上)同値． 1. X はDedekind無限集合． 2. 全射でない単射X −→ X が存在する．3. ℵ0 ≤ |X|． 4. 単射N −→ X が存在する． 5. X は可算無限部分集合を持つ． 6. |X| = |X| + ℵ0． 7. |X| = |X| + 1． 証明. 1 ⇐⇒ 2と3 ⇐⇒ 4 ⇐⇒ 5は明らか． (2 =⇒ 4) f : X −→ X を全射でない単射とする．全射でないからx∈ X \ f(X)が取 れる．このときg : N −→ Xを g(n) := { x (n = 0のとき) f (g(n− 1)) (n > 0のとき) で定義すればこれは単射である． (5 =⇒ 6) Y ⊂ X を可算無限部分集合とする．|Y | = |Y | + ℵ0 だから |X| = |(X \ Y ) ∪ Y | = |X \ Y | + |Y | = |X \ Y | + |Y | + ℵ0 =|X| + ℵ0. (6 =⇒ 7) ℵ0 =ℵ0+ 1だから |X| = |X| + ℵ0 =|X| + ℵ0+ 1 =|X| + 1. (7 =⇒ 1) Xに含まれない元∞を一つ取る．|X| = |X|+1より全単射f : X∪{∞} −→ X が存在する．このときf (X)⊊ Xかつ|f(X)| = |X|である． 命題 5. 選択公理を仮定する．無限集合はDedekind無限である． 証明. 整列可能定理を使えば明らか． 直接示すには「選択公理 =⇒整列可能定理」の証明を真似ればよい．X を無限集合と する．選択公理によりP(X) \ {∅}の選択関数gが存在する．このときf :N −→ X を帰 納的にf (n) := g(X \ {f(0), f(1), · · · , f(n − 1)})で定義すればf は単射である． ※ Xが無限集合であるから，X \ {f(0), f(1), · · · , f(n − 1)} ̸= ∅となることに注意 する． 実はこれは可算選択公理があれば証明できる． 命題 6. 可算選択公理を仮定する．無限集合はDedekind無限である．
証明. Xを無限集合とする．命題4により可算無限部分集合Y ⊂ Xの存在を示せばよい． n≥ 0に対してXn := {⟨x0, x1,· · · , xn⟩ ∈ Xn+1 | i ̸= j ならばxi ̸= xj}と置く．X が 無限集合だからXn ̸= ∅である．そこで集合族{Xn}∞n=0 に可算選択公理を適用して選択 関数φ : N −→∪∞n=0Xnを得る．φ(n)∈ Xn ⊂ Xnだからφ(n) = ⟨x (n) 0 , x (n) 1 ,· · · , x (n) n ⟩ と書ける．Y := {x(n)i | i ≤ n}と置けば，{⟨i, n⟩ ∈ N × N | i ≤ n}は可算無限集合だか らY は高々可算集合である．しかしXn の定義から明らかにY は無限集合である．従っ てY ⊂ X は可算無限部分集合である． 命題 7. |X| < |Y |かつ|Y | ≤∗ |X|となるような無限集合X, Y は存在しない =⇒無限集合はDedekind無限集合 証明. A をDedekind有限な無限集合とする．An := {⟨a0, a1,· · · , an⟩ ∈ An+1 | i ̸= j ならば xi ̸= xj} と置いて X := ∪∞ n=0An, Y := X ∪ {∅} と置く．明らかに |X| ≤ |Y |, |Y | ≤∗ |X|である．従って|X| ̸= |Y |を示せばよい． A がDedekind有限であることからY もDedekind有限集合である．明らかに|Y | = |X| + 1で，また命題4により|Y | ̸= |Y | + 1である．よって|X| ̸= |Y |である． Dedekind有限以外にも，有限の定義は色々考えられている． 定義. Xを集合とする． 1. X がI-finite ⇐⇒任意の∅ ̸= F ⊂ P(X)が極大元を持つ． 2. X がII-finite ⇐⇒任意の部分全順序∅ ̸= C ⊂ P(X)が最大元を持つ． 3. X がIII-finite ⇐⇒ P(X)がDedekind有限． 4. X がIV-finite ⇐⇒ X がDedekind有限． 5. X がV-finite ⇐⇒ |X| = 0または2|X| > |X|． 6. X がVI-finite ⇐⇒ |X| ≤ 1または|X|2 >|X|． 7. X がVII-finite ⇐⇒ X が整列可能でないまたは|N| ≰ |X|． 定義. P (J, K)で次の命題を表す: 任意のXに対して「XがJ -finite =⇒ XがK-finite」． 命題 8. 任意のX に対して「Xが有限集合⇐⇒ XがI-finite」． 証明. (=⇒) 明らか． (⇐=) X をI-finiteとすると，Pfin(X)⊂ P(X)が極大元Y を持つ．このとき極大性か ら明らかにY = X だからX は有限集合である．
命題 9. J < KならばP (J, K)である． 証明. (I-finite =⇒ II-finite) 明らか
(II-finite =⇒ III-finite) 明らか
(III-finite =⇒ IV-finite)単射X −→ P(X)が存在するから明らか．
(IV-finite =⇒ V-finite) XがV-finiteでないとする．|X| > 0かつ2|X| = |X|だから
X はDedekind無限である，即ちIV-finiteでない．
(V-finite =⇒ VI-finite) X をV-finiteとする．|X| > 1ならば|X| < 2|X| ≤ |X|2 だ
からVI-finiteである．|X| ≤ 1ならば定義からVI-finiteである．
(VI-finite =⇒ VII-finite) X を VI-finite とする．|X| ≤ 1 ならば |N| ≰ |X| だか
ら VII-finite である．|X|2 > |X| ならば X は整列可能でない (命題 2 を参照) から
VII-finiteである．
命題 10. J < K ならばP (L, J ) =⇒ P (L, K)である． 証明. 明らか．
定理11. 選択公理=⇒ P (VII, I)である．従って選択公理の下ではI-finiteからVII-finite
までの定義は全て同値である． 証明. 明らか． 定理 12. 選択公理⇐⇒P (VII, VI) 証明. (=⇒) 明らか． (⇐=) X を無限集合とする．|XN| > 1かつ|XN|2 =|XN|だからXNはVI-finiteでな い．故にVII-finiteではないが，|N| ≤ |XN|だからXNは整列可能である．故にX も整 列可能である． 系. 次の命題は(ZF上)同値． 1. 選択公理 2. P (VII, I) 3. P (VII, II) 4. P (VII, III) 5. P (VII, IV) 6. P (VII, V)
定理 13. 選択公理⇐⇒ P (VI, V) 証明. (=⇒) 明らか． (⇐=) κを無限基数としてλ := κ· ℵ0+ (κ· ℵ0)∗とすれば2λ = λである．故に仮定か らλ2 = λとなる．従って λ = λ2 = (κ· ℵ0)2+ 2κ· ℵ0· (κ · ℵ0)∗+ ((κ· ℵ0)∗)2 ≥ κ · ℵ0· (κ · ℵ0)∗ よりκ· ℵ0· (κ · ℵ0)∗ ≤ (κ · ℵ0)∗+ κ· ℵ0 が分かる．故に命題3からκ· ℵ0 ≤ (κ · ℵ0)∗ ま たは(κ· ℵ0)∗ ≤ κ · ℵ0となる．(κ· ℵ0)∗ ≰ κ · ℵ0となるからκ≤ κ · ℵ0 ≤ (κ · ℵ0)∗ であ る． 系. 次の命題は(ZF上)同値． 1. 選択公理 2. P (VI, I) 3. P (VI, II) 4. P (VI, III) 5. P (VI, IV) 以上で得られた選択公理と同値なP (J, K)を言い換えると，次の系が得られる． 系. 次の命題は(ZF上)同値． 1. 選択公理
2. P(X)がDedekind無限ならばX は整列可能である． (P (VII, III)) 3. Dedekind無限集合は整列可能である． (P (VII, IV))
4. 2|X| = |X|ならばXは整列可能である． (P (VII, V)) 5. |X|2 =|X|ならばXは整列可能である． (P (VII, VI))
6. P(X)がDedekind無限ならば|X|2 =|X|．(P (VI, III))
7. Dedekind無限集合X に対して|X|2 =|X|．(P (VI, IV))
8. 無限集合X に対して，2|X| = |X| =⇒ |X|2 =|X|．(P (VI, V))
定義. Xを集合とする．
1. X が D-finite ⇐⇒ |X| ≤ 1 であるか，ある A, B が存在して |A| < |X| かつ
|B| < |X|かつX = A∪ B．
命題 14. P (IV, D)である．
証明. X をIV-finite，即ちDedekind有限とする．|X| ≤ 1ならばD-finiteであるから
|X| > 1とする．x∈ Xを一つ取れば，XがDedekind有限だから|X \ {x}| < |X|であ る．故に|X \ {x}| < |X|，|x| < |X|，X = (X\ {x}) ∪ {x}と書けるのでD-finiteであ る． 命題 15. P (D, VII)である． 証明. X をD-finiteとする．|X| ≤ 1ならばVII-finiteである．|X| > 1の場合は明らか にX は整列不可能であるからVII-finiteである． 命題 16. X が有限集合=⇒ X はamorphous． 証明. 明らか． 命題 17. X がamorphous =⇒ XはII-finite． 証明. X をII-finiteでない集合とすると，最大元を持たない部分全順序 ∅ ̸= C ⊂ P(X) が存在する． (i)無限集合Y ∈ C が存在する場合 このときX\ Y も無限集合でX = (X\ Y ) ∪ Y だから，Xはamorphousである． (ii)任意のY ∈ C が有限集合の場合 C は最大元を持たないからC = {Fn | n ∈ N}，n < mならばFn ⊊ Fm，と書けることが 分かる．G0 := F0，Gn+1 := Fn+1\ Fnとして A := ∪ n∈N G2n, B := ∪ n∈N G2n+1 とすればA, Bは互いに素な無限集合でX = A∪ Bである． 定理 18. 次の命題は(ZF上)同値． 1. 選択公理 2. κ· λ = κ + λ． 3. κ + λ = κまたはκ + λ = λ． 証明. 濃度の性質を参照．
証明. (=⇒) 定理18の3より明らか． (⇐=) 定理18の3を示す．κ =|X|, λ = |Y |を任意の無限濃度とすればX∪ Y が無 限集合だから|X| = |X ∪ Y |または|Y | = |X ∪ Y |となる． 定理 20. 選択公理 ⇐⇒「X が有限集合⇐⇒ |X| ≤ 1であるか，あるY が存在して|X| + |Y | < |X| · |Y |．」 証明. (=⇒) 定理18の2より明らか． (⇐=) 定理18の2を示す．κ =|X|, λ = |Y |を任意の無限濃度とすればX が無限集 合だから命題1より|X| + |Y | = |X| · |Y |となる． 最後に，命題「無限集合はDedekind無限集合である」と同値な命題を述べておく．そ の為にまず補題を一つ示す． 補題 21. 集合X に対してℵ0 ≤∗ |X| ⇐⇒ ℵ0 ≤ P(X)である． 証明. (=⇒) f : X −→ Nを全射とする．このときf−1: N −→ P(X)は単射である． (⇐=) f : N −→ P(X)を単射とする．g : N −→ P(X)を以下のように帰納的に定義す る．n≥ 0とする．0≤ m ≤ n − 1に対しg(m)が {f (k)\ ∪ m<n g(m) k ≥ n} = ∞ となるように定義されているとする．このとき n∗ := min { k ∈ N k ≥ n, f(k) \ ∪ m<n g(m)̸= ∅, (X \ f(k)) \ ∪ m<n g(m)̸= ∅ } An:= f (n∗)∪ ∪ m<n g(m) として g(n) := f (n∗)\ ∪ m<n g(m) (|{f(k) \ An | k > n∗}| = ∞のとき ) X \ ( f (n∗)\ ∪ m<n g(m) ) (それ以外のとき) と定める． このときh : X −→ Nを h(x) := { n (あるnに対してx ∈ g(n)となるとき) 0 (それ以外のとき) と定めればhは全射である．
命題 22. 次の命題は(ZF上)同値である．
1. 任意のDedekind有限集合は有限集合である(即ちP (IV, I))．
2. 任意のDedekind有限集合はamorphousである．
3. 任意のDedekind有限集合はII-finiteである(即ちP (IV, II))．
4. Dedekind有限集合の冪集合はDedekind有限集合である(即ちP (IV, III))．
5. Dedekind有限集合X とDedekind無限集合Y に対し|X| ≤ |Y |． 6. 非可算集合X と可算集合Y に対し|X ∪ Y | = |X|． 7. 非可算集合X と可算集合Y に対し|X \ Y | = |X|． 8. |X| > ℵ0かつ|Y | = ℵ0 ならば|X \ Y | > ℵ0． 9. 任意の集合X に対しℵ0 ≤ |X|または|X| ≤ ℵ0． 証明. 1=⇒2，2=⇒3，3=⇒4は明らか． (4 =⇒ 1) Dedekind有限な無限集合X が存在すると仮定する．X が無限集合だから P(X) ∋ Y 7−→ |Y | ∈ Nは全射である．即ちℵ0 ≤∗ |P(X)|となる．従って補題21によ りP(P(X))はDedekind無限集合である．一方X がDedekind有限だから仮定4によ りP(P(X))がDedekind有限集合となり矛盾する． (1 =⇒ 5) 仮定1よりDedekind有限集合は有限集合だから明らか． (5 =⇒ 1) X をDedekind有限集合とする．NはDedekind無限集合だから仮定5によ り|X| ≤ ℵ0．よってX が無限集合と仮定するとX は可算無限，即ちDedekind無限集 合となって矛盾する． (1 =⇒ 6) X を非可算集合，Y を可算集合とする．仮定よりX はDedekind無限集合 である．|Y \ X| ≤ ℵ0だから命題4の条件6と7により |X ∪ Y | = |X| + |Y \ X| = |X|. (6 =⇒ 7) X を非可算集合，Y を可算集合とするとX \ Y も非可算集合である．故に 仮定6により|X| = |(X \ Y ) ∪ Y | = |X \ Y |． (7 =⇒ 8) 明らか． (8 =⇒ 1) X を無限集合とする．X が可算無限ならば明らかに Dedekind 無限だか ら，X は非可算無限集合としてよい．このとき |X ⊔ N| > ℵ0 だから仮定 8 により |X| = |(X ⊔ N) \ N| > ℵ0となり，XはDedekind無限集合である． (1 ⇐⇒ 9) 明らか．
参考文献
[1] P. E. Howard, M. F. Yorke, Definitions of Finite, Fundamenta Mathematicae 133 (1989), 169–177, http://pldml.icm.edu.pl/pldml/element/bwmeta1. element.bwnjournal-article-fmv133i1p16bwm?q=bwmeta1.element.
bwnjournal-number-fm-1989-133-3;0&qt=CHILDREN-STATELESS [2] Horst Herrlich, Axiom of Choice，Springer, 2006
