日記 (2020 年 5 月 31 日)
5 月 29 日の続きだが、 自然数 (と言っても 0 と 1 だけだが) を使うので 6 月 1 日を先に読んだ方が良いかもしれない。
今回は、 順序数の演算を定義する。
順序数の演算を定義する方法は様々あるが、 ここでは順序集合として演算した結果に適切な整列順序を入れたものの順序型をとるという方法を採用する。
そのために、 まずは順序集合の演算を定義する。
定義 3.1.
半順序集合 X,Y に対し、
X⊔Y:=({0}×X)∪({1}×Y)
とおき、 この上の関係 ⪯ を、
(i,x)⪯(i,x):⟺i<iOR(i=iANDx⪯x)
で定める。
定義 3.2.
半順序集合 X,Y に対し、 集合としての直積 X×Y 上の関係 ⪯ を、
(x,y)⪯(x,y):⟺x≺xOR(x=xANDy⪯y)
で定める。
この関係は辞書式順序 (lexicographic order) と呼ばれる。
補題 3.3.
半順序集合 X,Y に対し、 X⊔Y,X×Y 上の上記の関係は半順序である。
さらに、 X,Y に定まる順序がともに整列順序であれば、 X⊔Y,X×Y 上の上記の関係もまた整列順序である。
以降、 特に断らなければ、 半順序集合 X,Y に対し、 X⊔Y,X×Y と書いたらそれぞれ上記の関係によって半順序集合であると見なす。
上の補題によって、 X,Y がともに整列集合であれば、 X⊔Y,X×Y もともに整列集合である。
このことを用いて、 順序数の和と積が定義される。
定義 3.4.
順序数 α,β に対し、
α+β := ord(α⊔β) α·β := ord(β×α)
と定め、 それぞれ α,β の和 (sum) と積 (product) という。
順序数の積の定義には特に注意すること。
α·β は、 α×β の順序型ではなく β×α の順序型である。
後で見るように、 順序数の積は一般に可換ではないので、 この違いは本質的である。
以降、 この演算の性質をいくつか示す。
6 月 1 日では、 順序数 α の後続数を α∪{α} として定義したが、 この後続数は右から 1 をたすことで得られる。
定理 3.5.
順序数 α に対し、
α+1=α∪{α}
が成り立つ。
証明.
演算の定義から、 順序同型
({0}×α)∪({1}×1)≅α∪{α}
が成り立つことを示せば良い。
そのためには順序同型写像を具体的に構成すれば良いが、 写像
f: ({0}×α)∪({1}×1) ⟶ α∪{α} (0,ξ) ⟼ ξ (1,0) ⟼ α
を考えると、 これが順序同型になっている。
次に、 演算の結合性と分配性を示す。
定理 3.6.
順序数 α,β,γ に対し、
(α+β)+γ = α+(β+γ) (α·β)·γ = α·(β·γ)
がともに成り立つ。
証明.
前定理の証明と同様、 順序同型写像を具体的に構成する。
1 つ目の同型については、
f: (α⊔β)⊔γ ⟶ α⊔(β⊔γ) (0,(0,ξ)) ⟼ (0,ξ) (0,(1,η)) ⟼ (1,(0,η)) (1,ζ) ⟼ (1,(1,ζ))
が順序同型を与える。
また、 2 つ目の同型については、
f: γ×(β×α) ⟶ (γ×β)×α ((ζ,η),ξ) ⟼ (ζ,(η,ξ))
が順序同型を与える。
定理 3.7.
順序数 α,β,γ に対し、
γ·(α+β)=γ·α+γ·β
がともに成り立つ。
証明.
写像
f: (α⊔β)×γ ⟶ (α×γ)⊔(β×γ) ((i,ξ),ζ) ⟼ (i,(ξ,ζ))
が順序同型を与える。
なお、 右から積に対する分配法則は一般に成り立たないことには注意すべきである。
左からの演算については、 通常の自然数の演算と同じ性質が順序数の演算についても成り立つことが多いが、 右からの演算については、 自然数で成り立っても順序数では成り立たないことがよくある。
さらに、 演算が順序を保つことを示す。
そのため、 順序数の大小関係を示すための道具となる補題を用意する。
補題 3.8.
整列集合 X の真の切片 S⊂X は、 ある元 x∈X について S=O(x) と書ける。
証明.
X∖S≠∅ であるから、 x:=min(X∖S) がとれる。
この x について S=O(x) であることを示す。
任意に y∈S をとる。
ここで、 仮に y∉O(x) であるとすると、 全順序性から y⪰x が成り立つが、 S は切片なので x∈S となる。
しかし、 定義から x∈X∖S であるから、 これは矛盾である。
したがって、 y∈O(x) が得られ、 S⊆O(x) が分かった。
逆に任意に y∈O(x) をとる。
仮に y∉S であったとすると、 y∈X∖S であるから、 x の最小性によって y⪰x がともに成り立つ。
しかし、 y∈O(x) より y≺x でもあるから、 これは矛盾である。
したがって、 y∈S が得られ、 S⊇O(x) も分かった。
補題 3.9.
順序数 α に対し、 α の任意の切片はまた順序数である。
証明.
α の任意の切片 S をとる。
S=α であれば、 α は順序数だから S も順序集である。
S≠α であれば、 補題 3.8 によって、 ある元 ξ∈α に対して S=O(ξ) と書ける。
一方、 補題 1.13 によって、 O(ξ)=ξ も成り立つ。
これにより S=ξ が得られたが、 定理 1.6 によって ξ は順序数だから、 S も順序数である。
補題 3.10.
整列集合 X 上の狭義単調増加写像 f:X→X をとる。
このとき、 任意の x∈X に対して x⪯f(x) が成り立つ。
証明.
まず、
Z:={x∈X∣x⪯f(x)}⊆X
とおく。
Z=X であることを示せばよいが、 これを超限帰納法によって示す。
任意に x∈X をとり、 O(x)⊆Z であるとする。
ここで、 f(x)∈O(x) であると仮定する。
すると、 定義から f(x)≺x であるが、 f は狭義単調増加なので f(f(x))≺f(x) が成り立つ。
一方、 O(x)⊆Z より f(x)∈Z だから、 f(f(x))⪰f(x) も成り立つことになるが、 これは矛盾である。
したがって、 f(x)∉O(x) が得られた。
ところでこれは f(x)⪰x であるという意味なので、 x∈Z が示された。
補題 3.11.
順序数 α,β について、 狭義単調増加写像 f:α→β が存在すれば α≤β が成り立つ。
証明.
仮に α≤β ではないとすると、 定理 1.9 によって α>β が成り立つ。
これはすなわち α⊃β であるということなので、 f の終域を拡張して f:α→α と見なせる。
ところで、 α>β は α∋β でもあるということなので、 補題 3.10 を適用すれば β≤f(β) を得る。
しかし、 もともと f の終域は β であったから、 f(β)∈β すなわち f(β)<β が成り立つはずである。
これは矛盾である。
以上により、 α≤β が示された。
以上の準備のもと、 以下が示せる。
定理 3.12.
順序数 α,β,γ に対し、
α<β ⟹ γ+α<γ+β α<β ⟹ α+γ≤β+γ α<βANDγ>0 ⟹ γ·α<γ·β α<β ⟹ α·γ≤β·γ
が全て成り立つ。
証明.
1 つ目の主張を示す。
α<β であるとすると α⊂β であるから、 包含写像
f:({0}×γ)∪({1}×α)→({0}×γ)∪({1}×β)
が存在する。
さて、 補題 1.17 を用いると、
γ+α ≅ ({0}×γ)∪({1}×α) ≅ f(({0}×γ)∪({1}×α))
が成り立ち、 さらに α∈β であるから、
f(({0}×γ)∪({1}×α)) = O((1,α)) ⊂ ({0}×γ)∪({1}×β) ≅ γ+β
が成り立つ。
以上の議論をまとめれば、 γ+β の真の切片 S⊂γ+β が存在して S≅γ+α が成り立つということが示せたことになる。
補題 3.9 によって S はある順序数と同型であるが、 S≅γ+α であるからその順序数とは γ+α である。
したがって、 γ+α⊂γ+β すなわち γ+α<γ+β が示された。
2 つ目の主張を示す。
α<β であるとすると α⊂β であるから、 包含写像
f:({0}×α)∪({1}×γ)→({0}×β)∪({1}×γ)
が存在する。
これは明らかに狭義単調増加写像である。
したがって、 これに適切な順序同型写像を合成することで、 狭義単調増加写像 f:α+γ→β+γ が得られるので、 補題 3.11 によって α+γ≤β+γ である。
3 つ目の主張を示す。
α<β より α⊂β であるから、 包含写像 f:α×γ→β×γ が存在する。
さらに γ>0 より γ∋0 であることを利用すれば、 この写像の像は O((α,0)) と書けるので、 1 つ目の主張を示したときと同じ議論によって γ·α<γ·β が示せる。
4 つ目の主張は、 2 つ目の主張と同様に包含写像を考えれば良い。
この定理から、 和と (0 でない) 積は広義には順序を保ち、 さらに左からの和と積については狭義にも順序を保つことが分かる。
しかし、 2 番目と 4 番目の主張において右辺の不等号を等号なしにしたものは一般に成り立たないので、 右からの和と積については狭義には順序を保たない。
追記 (2020 年 6 月 1 日)
自然数に関する記事を新しく書いたので、 このページの自然数に関する記述は削除し、 代わりに新しく書いたページを参照するよう勧める文言を追加した。
参考文献
- K. Ciesielski (1997) 『Set Theory for the Working Mathematician』 Cambridge University Press