整列集合の比較定理 整列集合の比較定理

整列集合の比較定理

定理1 Aを整列集合、fをAからAへの写像とします。 任意のx,y∈Aに対し、x<yならばf(x)<f(y)がなりたつならば、 任意のx∈Aに対し、x≦f(x)がなりたちます。 証明 対偶を示します。 「任意のx∈Aに対しx≦f(x)」がなりたたないとすると、Aは全順序集合なので、あるa∈Aがあってa>f(a)となります。 したがってB={x∈A|x>f(x)}とおくと、a∈Bですから、Bは空でないA(整列集合)の部分集合なので、最小元bをもちます。 当然b∈Bなのでb>f(b)です。 よって、f(b)はBの最小bより小さいのでf(b)∉B、つまりf(b)≦f(f(b))。 したがって、f(b)<bであるのにf(f(b))<f(b)が成立しないので、「任意のx,y∈Aに対しx<yならばf(x)<f(y)」とはならないことがわかります。 別証 ※任意のx,y∈Aに対し、x<yならばf(x)<f(y)がなりたつとします。 あるx∈Aに対しx>f(x)となるとして矛盾を導きます。 f(x)<xなので※よりf(f(x))<f(x) f(f(x))<f(x)なので※よりf(f(f(x)))<f(f(x)) 以下同様にして、無限下降列x,f(x),f(f(x)),f(f(f(x))),...が構成できるので、Aが整列集合であることと矛盾します。 定理2 整列集合Aは、Aのどの切片とも順序同型ではありません。 証明 任意にa∈Aをとり、fをAからC(a)への写像とします。 f(a)∈C(a)なので切片の定義からf(a)<aです。 したがって定理1の対偶より、x<yだがf(x)<f(y)とならない場合が存在します。 したがってfは順序同型ではありません。 定理3 Aを全順序集合とし、a,b∈Aとします。 a<bならば、C(a,A)=C(a,C(b,A))です。 証明 C(a,A) ={x∈A|x<a} (切片の定義) ={x∈A|x<aかつx<b} (a<bより) ={x∈A|x<aかつx∈C(b,A)} (x∈Aなので切片の定義による) ={x∈C(b,A)|x<a} (C(b,A)⫅Aより) =C(a,C(b)) (切片の定義) 定理4 Aを整列集合とし、a,b∈Aとします。 a≠bならば、C(a)とC(b)は順序同型ではありません。 証明 Aは全順序なので、a<bまたはb<aとなります。 どちらでも同じことなのでa<bとします。 C(a,A)={x∈A|x<a}={x∈A|x<aかつx<b}={x∈A|x<aかつx∈C(b)}={x∈C(b)|x<a}=C(a,C(b))。 定理2によってC(b)とC(a,C(b))は順序同型でないので、C(b)とC(a,A)つまりC(a)は順序同型ではありません。 定理5 AとBが順序同型な整列集合であるとします。 任意のa∈Aに対してあるb∈BがあってC(a,A)とC(b,B)が順序同型になります。 証明 順序同型写像をfとおきます。 a∈Aを任意にとったとき、b=f(a)とおきます。 このとき、fのC(a,A)への制限f'を考えると、これは当然、単射で順序を保ちます。 さらに、x∈C(a,A)とするとx<aなのでf(x)<f(a)=b、つまりf(x)∈C(b,B)となるので、f'の像はC(b,B)の中におさまっています。 最後に、y∈C(b,B)とするとy<bなので、f-1(y)<f-1(b)=a、つまりf-1(y)∈C(a,A)ですから、f(f-1(y))=yであることよりf'はC(b,B)への全射であることがわかります。 定理6 Aを整列集合、Bをその真部分集合とします。 任意のy∈Aとx∈Bに対し、y<xならばy∈Bとなるとします。 このとき、BはAのある切片と一致します。 証明 BはAの真部分集合なので、A-Bは空でないA(整列集合)の部分集合であり、最小元aが存在します。 x∈C(a)ならば切片の定義よりx<aです。 よってaがA-Bの最小元であることからx∉A-B、つまりx∈Bです。 したがってC(a)⫅Bです。 次に、x∈Bとします。 a∉Bなので、仮定の対偶よりa≧xです(Aば全順序であることに注意してください)。 x∈Bでa∉Bだから、x≠aなので、a>x、よってx∈C(a)です。 したがってB⫅C(a)です。 以上からB=C(a)がわかりました。 別証 Bがどの切片とも一致しないとして矛盾を導きます。 BはAの真部分集合なので、A-Bは元x0をもちます。 BはC(x0)と一致しないので、B-C(x0)とC(x0)-Bの少なくとも一方は空ではありません。 ここでx∈B-C(x0)とすると、x∉C(x0)なので(Aが全順序であることから)x0≦xです。 さらにx∈Bで、x0∈A-Bよりx0∉Bなのでx0≠xです。 よってx0<xですから、仮定よりx0∈Bとなり矛盾するので、B-C(x0)は空です。 したがって、C(x0)-Bは空ではなく、x1∈C(x0)-Bが存在します。 x1∈C(x0)なのでx1<x0です。 次に、BはC(x1)と一致しないので、B-C(x1)とC(x1)-Bの少なくとも一方は空ではありません。 ここでx∈B-C(x1)とすると、x∉C(x1)なので(Aが全順序であることから)x1≦xです。 さらにx∈Bで、x1∈C(x0)-Bよりx1∉Bなのでx1≠xです。 よってx1<xですから、仮定よりx1∈Bとなり矛盾するので、B-C(x1)は空です。 したがって、C(x1)-Bは空ではなく、x2∈C(x1)-Bが存在します。 x2∈C(x1)なのでx2<x1です。 以下同様にして、無限下降列x0,x1,x2,...が構成できるので、Aが整列集合であることと矛盾します。 定理7 AとBを整列集合とすると、必ず次のいずれか一つだけが成立します。 (1)AとBは順序同型 (2)Aは、Bのあるただ一つの切片と順序同型 (3)Bは、Aのあるただ一つの切片と順序同型 証明 つぎのようにおきます。 A'={x∈A|あるy∈BがあってC(x,A)とC(y,B)が順序同型} B'={y∈B|あるx∈AがあってC(y,B)とC(x,A)が順序同型} x∈A'とすると、A',B'の定義より当然C(x,A)≅C(y,B)なるy∈B'が存在します。 またy,y'∈B'に対してC(x,A)≅C(y,B)かつC(x,A)≅C(y',B)とすると、C(y,B)≅C(y',B)ですから、定理4の対偶をとって、y=y'となります。 xに対してこのyを対応させる写像をfとおきます。 つぎに、x,x'∈A',y∈B'に対してf(x)=yかつf(x')=yとします。 C(x,A)≅C(y,B)かつC(x',A)≅C(y,B)ならばC(x,A)≅C(y,B)ですから、ふたたび定理4の対偶をとってx=x'となります。 つまりfは単射です。 また、B'の定義よりあきらかにfは全射です。 さらに、x∈A, x'∈A', x<x', y'=f(x')とおくと、C(x',A)≅C(y',B)。 x<x'よりx∈C(x',A)なので、定理5よりあるy∈C(y',B)に対しC(x,C(x',A))≅C(y,C(y',B))となります。 ここで定理3よりC(x,A)≅C(x,C(x',A))、またy∈C(y',B)よりy<y'なのでやはり定理3よりC(y,B)≅C(y,C(y',B))ですから、C(x,A)≅C(y,B)です。 したがって、A',B'の定義よりx∈A',y∈B'であり、fの定義よりf(x)=yです。 x,x'∈Aなら、x∈Aなので、上の議論からf(x)=y<y'=f(x')であり、両集合が全順序であることとあわせて、fは順序同型写像であることがわかります。 また、上の議論では、x∈A, x'∈A', x<x'からx∈A'が導かれているので、A≠A'(つまりA'がAの真部分集合)ならば、定理6よりA'はAのある切片と一致します。 また、f-1に対して同様のことを考えれば、B≠B'ならば、B'はBのある切片と一致することもわかります。 (i) A=A' (ii) あるa∈AがあってA'=C(a,A) (iii) B=B' (iv) あるb∈BがあってB'=C(b,B) とおくと、「(i)または(ii)」かつ「(iii)または(iv)」がなりたつということです。 (i)かつ(iii)のとき A=A'≅B'=Bなので、本定理の(1)が成立します。 (i)かつ(iv)のとき A=A'≅B'=C(b,B)です。 また、b'∈Bに対してA≅C(b',B)とすると、C(b,B)≅C(b',B)なので、定理4の対偶よりb=b'です。 したがって本定理の(2)が成立します。 (ii)かつ(iii)のとき 同様に本定理の(3)が成立します。 (ii)かつ(iv)のとき これはおこりえません。 C(a,A)=A'≅B'=C(b,B)ということは、A'の定義よりa∈A'であり、a∈C(a,A)つまりa<aとなって矛盾します。 以上で(1)、(2)、(3)の少なくとも1つが常に成立することがわかりました。 最後にこれらのどの2つも同時に成立することがないことを示します。 (1)と(2) B≅A≅(Bのある切片)となり、定理2に反します。 (1)と(3) A≅B≅(Aのある切片)となり、定理2に反します。 (2)と(3) b∈B,a∈Aを適当にとってA≅C(b,B)、B≅C(a,A)とかけます。 A≅C(b,B)と定理5より、あるb'∈C(b,B)があってC(a,A)≅C(b',C(b,B))。 b'∈C(b,B)よりb'<bなので定理3よりC(b',C(b,B))=C(b,B)。 よってB≅C(a,A)≅C(b',C(b,B))=C(b,B)となり、定理2に反します。