端点なしの可算稠密線形順序とは,すなわち有理数上の順序
この記事は 好きな証明 Advent Calendar 2018 - Adventar の2日目の記事です.
1日目は鯵坂もっちょさんの www.ajimatics.com でした
端点なしの可算稠密線形順序は同型を除いて一意に定まります.今回はこの定理の証明を紹介したいと思います.
用語の確認
まずは用語の確認です.
- 線形順序とは,任意の2元が比較可能な順序です.全順序とも言います.
- 稠密順序とは,任意のに対してあるがあって,となる順序です.
- 線形順序が端点を持たないとは,任意のに対して,あるがあってとなることを言います.すなわち,最大元も最小元も持たない線形順序です.
ところで,稠密線形順序(Dense Linear Order)は英語の頭文字をとってDLOと呼ばれることが多いので,以下そのように書くことにします.
具体例
では,端点なしの可算DLOとしてどんなものがあるでしょうか?
すぐに出てくる例として,有理数全体に通常の順序を入れたものが挙げられます.これが端点なしの可算DLOであることはすぐに確認できますね.
定理:端点なしの可算DLOは全て同型である
[証明] を端点なしの可算DLOとする. また,とする.
以下のようにして,をにより数え上げる.
まず,とする.
次に,とする.このとき,次のようにを定める:
であれば,となる最小のを取り,とする.
の場合,として,あとは同様である.
今度は,をの元で,による番号が最小のものとする.
このとき,の大小関係は以下の3パターンのいずれかである.
- が最小である.
- が最大である.
- はとの間に入る.
1.の場合,より小さいのうち,番号が最小のものを取りとする. 他の2パターンの場合も同様に,順序を保つようにを定める(いずれの場合も,は端点なしかつ稠密なので対応する元を取ってくることができる).
以下は同様に,に対して順序を保つようにを定め, 次にに対して順序を保つようにを定める,というのを繰り返していけば良い. はまだによって数え上げられていないもののうち,による番号が最小のものをとってきているので,による数え上げがによる数え上げを網羅しているのは明らかである. また,各に対してとが同型になるようにを定めたので, とが同型となることも直ちに従う. //
かくして,端点なしの可算DLOは全て同型であることが示されました. 具体例のところで書いた通り,有理数上の通常の順序は端点なしの可算DLOでした.したがって,「端点なしの可算稠密線形順序とは,すなわち有理数上の順序」というわけです.
往復論法
この証明のポイントは,基準となる元をから交互にとることで,が全体を数え上げている,という点です. 常に片側を基準にしていると,埋め込みを構成することはできるのですが,全射になっているかどうかはわからないというわけですね.*1
このように,の両側から交互に基準を取って同型を作る方法は,往復論法(back-and-forth)と呼ばれています.数学基礎論でよく使われる手法で,上記の例に限らず,構造同士が同型であることを示すのに役立ちます.便利な手法ということで,好きな証明方法の一つです.