第１８回 整列集合

第１８回　整列集合

 

（半）順序集合（A,≦）は、Aの部分集合がかならず最小元（最初の元）をもつとき、整列集合という。また、整列集合は全順序集合である。

整列集合の部分集合および整列集合と順序同型な順序集合は整列集合である。

 

例１　自然数全体の集合をNとするとき、

　　

は整列集合である。

 

例２　有限順序集合は整列集合である。

 

例３　通常の順序（大小関係）において、整数全体の集合Z、有理数全体の集合Q、実数全体の集合Rは、最小元（最初の元）を持たないので、整列集合ではない。

 

例４　は整列集合である。

 

問１　整列集合は全順序集合であることを示せ。

【証明】

（A,≦）を整列集合とし、x、y∈Aとする。X={x,y}はAの空でない部分集合だから、Xは最小元min Xをもつ。

min X=xならばx≦yであり、min X=yならばy≦x。

したがって、任意のx、y∈Aに対して、x≦yまたはy≦xが成り立つ。よって、整列集合は全順序集合である。

（証明終）

 

定理１

（A,≦）が整列集合であり、が順序単射であれば、すべてのx∈Aに対して、

　　

である。

【証明】

が空（集合）でないと仮定する。

Xの最小元をx₀とすると、f(x₀)<x₀であり、fは順序を保つ単射だから

　　

したがって、f(x₀)∈Xであって、f(x₀)はXの最小元x₀よりも小さいので、矛盾が生じる。

したがって、Xは空集合∅である。

（証明終）

 

整列集合（A,≦）の元aに対して、集合｛x∈A｜x<a｝をAの元aによる切片といい、記号A〈a〉などであらわす。

 

例５　とするとき、

 

問２　（A,≦）を整列集合とする。Aの２つの元a、bについてb<aならば、

　　(A〈a〉)〈b〉=A〈b〉

であることを示せ。

【解】

　　(A〈a〉)〈b〉=｛x∈A｜x<aかつx<b｝

問題の条件よりb<aだから、

　　(A〈a〉)〈b〉=｛x∈A｜x<aかつx<b｝=｛x∈A｜x<b｝=A〈b〉

（解答終）

 

 

問３　Aでa∈Aならば、AからA〈a〉への順序単射は存在しないことを示せ。

【証明】

を順序単射とすると、fはAからAへの順序単射だからa≦f(a)でなければならない。

一方、f(a)∈A〈a〉だからf(a)<aとなり矛盾する。

したがって、AからA〈a〉への順序単射は存在しない。

（証明終）

 

問４　次のことを示せ。

（１）　整列集合Aから自分自身への順序同型写像はに限る。

（２）　整列集合Aから順序集合Bへの順序同型写像が存在すれば１つに限る。

（３）　Aが整列集合であって、a、b∈Aであるとき、ならばa=bである。

【証明】

（１）　を順序同型写像とすると、fはAからAへの順序単射だから、x≦f(x)。また、f⁻¹も順序単射だから、x≦f⁻¹(x)となり、f(x)≦x。したがって、f(x)=x。

 

（２）　f、gがともにAからBへの順序同型写像ならばはAからAへの順序同型写像。（１）よりとなり、g=fである。

 

（３）　a<bと仮定する。

B=A〈b〉とすれば、問２よりB〈a〉=A〈a〉。したがって、ならば、整列集合Bからその切片B〈a〉への順序単射が存在することになるが、問３よりBからB〈a〉への順序単射への順序単射は存在しないので矛盾する。

よって、ならばa=bである。

（証明終）

 

定理２　A、Bを整列集合とすれば、次の３つの場合の１つ、しかも１つだけが成立する。

（１）　AとBは同型

（２）　AはBのある切片と同型

（３）　BはAのある切片と同型

【証明】

A、Bの部分集合A₁、B₁をそれぞれ

　

によって定義する。

各元a∈A₁に対して、となるb∈Bはただ１つ存在し、b∈Y₁。

この元をb=φ(a)とおくと、写像φ：A₁→B₁が定まる。φは順序同型写像であり、となる。よって、A₁はAと一致するか、またはXのある切片と一致し、同様にB₁はBと一致するか、またはBのある切片と一致する。

もし、A₁=A〈a〉かつB₁=B〈b〉とすれば

となり、a∈A₁となる。これはa∉A₁に矛盾する。したがって、この定理が主張する（１）、（２）、（３）のいずれかが必ず成り立つことがわかった。

次に、（１）、（２）、（３）のなかの２つの場合が同時に成立しないことを示す。

（２）と（３）が同時に成り立つと仮定し、順序同型が成り立つと仮定すると、合成写像

は順序を保つ写像であり、φ(a)<aである。これは定理１に矛盾する。したがって、（２）と（３）は同時に成り立つことはない。他の場合についても、同様である。

（証明終）

 

定理３　（超限帰納法）

Aを整列集合とし、P(x)をAの元に関する命題とする。

このとき、

　　

が成り立てば、すべてのx∈Aに関してP(x)が成り立つ。

【証明】

P(x)が満たさないx∈Aがあったとして矛盾を導く。

　　

とすれば、XはAの空でない部分集合となる。Aは整列集合であるから、Xは最小元を持つ。それをaとすると、aより小さい元はXに属さないから

　　

が成り立つ。したがって、仮定よりP(a)となる。すなわち、a∉Xとなる。これはa∈Xであることに矛盾する。

（証明終）

 

自然数全体の集合Nに通常の大小関係を与えた整列集合を（N,≦）とする。よく知られた数学的帰納法は、整列集合（N,≦）に関する超限帰納法にほかならない。