お勉強の記録

この記事は好きな証明 Advent Calendar 2018 - Adventar の2日目の記事です．

1日目は鯵坂もっちょさんの www.ajimatics.com でした

端点なしの可算稠密線形順序は同型を除いて一意に定まります．今回はこの定理の証明を紹介したいと思います．

用語の確認
具体例
定理：端点なしの可算DLOは全て同型である
往復論法

用語の確認

まずは用語の確認です．

線形順序とは，任意の2元が比較可能な順序です．全順序とも言います．
稠密順序とは，任意の $x\lt y$ に対してある $z$ があって， $x\lt z\lt y$ となる順序です．
線形順序が端点を持たないとは，任意の $x$ に対して，ある $y,z$ があって $y\lt x \lt z$ となることを言います．すなわち，最大元も最小元も持たない線形順序です．

ところで，稠密線形順序(Dense Linear Order)は英語の頭文字をとってDLOと呼ばれることが多いので，以下そのように書くことにします．

具体例

では，端点なしの可算DLOとしてどんなものがあるでしょうか？

すぐに出てくる例として，有理数全体に通常の順序を入れたもの $(\mathbb{Q} , \lt)$ が挙げられます．これが端点なしの可算DLOであることはすぐに確認できますね．

定理：端点なしの可算DLOは全て同型である

[証明] $(A, \lt) , (B,\lt)$ を端点なしの可算DLOとする．また， $A = \{ a_{0}, a_{1}, \ldots \} , B= \{ b_{0}, b_{1}, \ldots \}$ とする．

以下のようにして， $A,B$ を $\alpha, \beta$ により数え上げる．

まず， $\alpha_0 = a_0 \ ,\beta_0=b_0$ とする．
次に， $\alpha_1 = a_1$ とする．このとき，次のように $\beta_1$ を定める： $\alpha_0 \lt \alpha_1$ であれば， $\beta_0 \lt b_n$ となる最小の $n$ を取り， $\beta_1 = b_n$ とする． $\alpha_0 \gt \alpha_1$ の場合， $\beta_0 \gt b_n$ として，あとは同様である．
今度は， $\beta_2$ を $B \setminus \{\beta_0,\beta_1 \}$ の元で， $b$ による番号が最小のものとする．このとき， $\beta_0,\beta_1,\beta_2$ の大小関係は以下の3パターンのいずれかである．

$\beta_2$ が最小である．
$\beta_2$ が最大である．
$\beta_2$ は $\beta_0$ と $\beta_1$ の間に入る.

1.の場合， $\alpha_0,\alpha_1$ より小さい $a_n$ のうち，番号が最小のものを取り $\alpha_2 = a_n$ とする．他の2パターンの場合も同様に，順序を保つように $\alpha_2$ を定める(いずれの場合も， $A$ は端点なしかつ稠密なので対応する元を取ってくることができる)．

以下は同様に， $\alpha_{2n+1}$ に対して順序を保つように $\beta_{2n+1}$ を定め，次に $\beta_{2n+2}$ に対して順序を保つように $\alpha_{2n+2}$ を定める，というのを繰り返していけば良い． $\alpha_{2n+1},\beta_{2n+2}$ はまだ $\alpha,\beta$ によって数え上げられていないもののうち， $a,b$ による番号が最小のものをとってきているので， $\alpha,\beta$ による数え上げが $a,b$ による数え上げを網羅しているのは明らかである．また，各 $n$ に対して $\{ \alpha_i : i \lt n \}$ と $\{\beta_i : i\lt n \}$ が同型になるように $\alpha,\beta$ を定めたので， $A = \{\alpha_n : n \in \mathbb{N} \}$ と $B = \{\beta_n : n \in \mathbb{N} \}$ が同型となることも直ちに従う． //