可算非有界稠密全順序構造の一意性の別証明

どうもAaronです。

今日は普段やっている(というか体調不良と新生活の忙しさという口実で三日坊主中の)「算術の夢の楽園」ではなく単発です。

表題にもある通り非有界稠密全順序構造には $\aleph_0$ -categorical、即ち任意の可算モデルが(同型(当然だがここでは順序同型)を同じと見なす意味で)一意だという性質があり(これはモデル理論的にはそれなりに珍しい性質で、例えば通常「自然数の理論」といわれるPeanoの公理には、通常の自然数(標準自然数)のほかにも「超準自然数」と呼ばれるモデルがたくさんあることが知られており、実は可算モデルに限定してすら「自身が矛盾している」と主張しているかのように読めたり、ある意味で $\infty$ のように振舞ったりする奇妙な元を持った、性質の異なるモデルがあるのです)、このこと自体は古くから知られている(集合論の始まりであるCantorがもう示しているようです。この辺は単にある人とのpersonal communicationで聞いただけなので歴史的経緯について語る気はないですし、間違っててもご容赦を)のですが、通常の教科書に載っている(らしい)証明とは少し違うアプローチの別証明を思いついたので、モデル理論ができる方に査読をしてもらいたい(まあ恐らくどこかしらで既出だとは思いますが)事に加え、自分の備忘録もかねてここに書いておきます(Twitterでも同内容を書きましたが、はてブロのほうがある程度データの保管として信頼できるのと、結構訂正があってグダグダだったので清書を兼ねて)。

0.ちょっとだけ予備知識

別にモデル理論も順序集合論も(というか任意の数学の分野)詳しくないので説明できるような予備知識もないのですが、一応今回示したいことと背景だけ説明しときます。

今回示したいことは以下の(全て同値な)主張です。

ほとんど言葉遊びレベルでいろいろ言いかえてありますのでモデル理論の言葉が苦手な方は好きなステートメントで理解してください。

非有界稠密全順序構造は $\aleph_0$ -categoricalである。
可算非有界稠密全順序構造は同型を除いて一意である。
可算全順序集合の圏のうち、非有界で稠密な順序を持つ対象の為す部分圏は本質的に一点圏である。
任意の非有界稠密全順序構造の可算モデルは(通常の順序を備えた)有理数と順序同型を持つ。
任意の非有界稠密全順序構造の可算モデルは(有理数からの相対順序を備えた)2進分数と順序同型を持つ。

ちなみに今回僕が与える別証明では一番最後のステートメントを証明し、系として他の表現が従う形をとります。

さて先ほどから別証明といっているからには「普通こうやる」という証明があるわけですが、それは「往復論法」と呼ばれるものです。

Bernsteinの定理の証明を知っている人には、アレを順序の埋め込み写像に関して類似物を作ったような証明だと思ってもらえばいいかと思います。(因みに恥ずかしながら僕はこの証明一読したことがなく、「大体こんな感じ」というのだけ知らないのです。)。

この方法の利点は「任意にとってきた構造2つの間に直接同型が作れること」を示していることです。

反対に若干劣るのは2つの構造の間に作った同型が必ずしも具体的とは言えないところです。

そこで今回用いる方法は任意の可算構造から2進分数に順序同型を作る方法を具体的に与えるものなのです。

1.証明の仮定

今回の証明では1か所だけ、とあるトリックを用いています。

というのも可算非有界稠密全順序構造 $\rm (A,\preceq )$ の台集合 $\rm A$ は可算集合である限り、どのような集合でもよいので、具体的に与えるといっても中身のわからない集合に関する定義を書き下すのは困難だからです。

そこで台集合を自然数でエンコードします。これは可算性の定義からいつでも可能です。

少し気を使って書けば台集合 $\rm A$ に対して自然数全体の集合 $\omega$ から $\rm A$ への全単射 $\alpha$ (可算性とはまさにこのような $\alpha$ が存在することでした。)を一つ固定して、これによってあたかも自然数から他の集合 $\rm B$ への関数 $\rm f$ を、 $\rm A$ から $\rm B$ への写像であるかのように扱います。

本当ならば $\rm f(\alpha^{-1}(n))$ と書くべきところを、(ある種の記号の濫用により) $\rm f(n)$ と書いて済ませてしまったり、定義をするときでさえ $\rm f\circ\alpha^{-1}$ をなにか文字で措けば済むところを横着して $\rm f$ をして $\rm f:A \to B$ かと言い張るわけです。

計算論や算術に慣れている人にとっては台集合を $\omega$ に固定して、順序構造を2変数Bool値関数としてエンコードする、いつもやってるトリックだと思ってもらっても当然同じです。

但しこれには問題があり、議論の途中で $\rm A$ の順序ではなく通常の自然数の順序を使うところが多くあり(それだけでも十二分に紛らわしいのに、更には同型を飛ばす先である2進分数の空間の順序も使うのですから)、非常に分かりにくなることがあります。

そこで自然数の通常の順序には記号 $\leq$ を、 $\rm A$ の順序には $\preceq$ を、2進分数空間の順序には $\ll$ を使います。最大・最小などの記号も $\rm max_\leq,min_\leq,max_\preceq,min_\preceq,max_\ll,min_\ll$ のように書きます。

さて前置きが長くなりすぎました(もう2000字をはるかに越えている)。

次章で証明に入ります。

2.可算非有界稠密全順序構造 $\rm (A,\preceq)$ から2進整数の空間 $({\mathbb Z}/2^{\mathbb N},\ll)$ への関数 $\rm f$

この章では、ある固定された可算非有界稠密全順序構造 $\rm (A,\preceq)$ から2進整数の空間 $({\mathbb Z}/2^{\mathbb N},\ll)$ へある関数 $\rm f$ を定義します。

先に言ってしまえばこれが順序同型になっているのですが、それは次章以降で示すとしてその定義だけ先にやってしまうわけです。

その定義は再帰的に以下のようになります。

$Basis.\rm f(0)=0.\\\ \\ {\it Inductive\ Steps.} \\Let \\L_n^x:=\{f(m)|(m\leq n)\land (m\preceq x)\}\\G_n^x:=\{f(m)|(m\leq n)\land (x\preceq m)\}.\\\ \\f(n+1)=min_\ll(G_n^{n+1})-1\ (if\ L_n^{n+1}=\emptyset)\\f(n+1)=max_\ll(L_n^{n+1})+1\ (if\ G_n^{n+1}=\emptyset)\\f(n+1)=\frac{max_\ll(L_n^{n+1})+min_\ll(G_n^{n+1})}{2}\ (if\ G_n^{n+1},L_n^{n+1}\neq\emptyset)$

ここで $\rm \{m|m\leq n\}$ は有限集合だから、定義中の $\rm L_n^x,G_n^x$ もいつでも必ず有限集合で、よってその( $\ll$ に関する)最大値、最小値は必ず存在しますし、総当たり法で計算することも可能なことに注意してください。

またこれが関数を定めることは、(帰納法や帰納的定義の正当性を前提すれば)エンコーディング $\alpha$ が全単射であったことから従います。

これらにより $\rm f$ が確かに関数を定めうことが分かったのですが、次章にてこれが実は順序を保つこと、そして全単射であること即ち順序同型であることを示します。

3. $\rm f$ が広義順序を保つこと

この章では $\rm f$ が狭義順序を保つこと、論理式で書けば

$\rm\forall n\forall m.n\prec m\to f(n)\ll_s f(m)$

であることを示します。

ここで $\rm \prec,\ll_s$ は

$\rm n\prec m:\Leftrightarrow n\preceq m\land n\neq m\\n\ll_s m:\Leftrightarrow n\ll m\land n\neq m$

で定義される狭義順序と呼ばれるものです(狭義順序を使う場合、 $\preceq,\prec$ の様に元の順序(広義順序)を「狭義順序の記号と等号、もしくはそれを略した一本線を縦に重ねた記号」で表すのが普通なのですが、僕がTeXで出せる記号に限りがあったため $\ll$ の方はその流儀に従えず、小文字のs(狭義順序の英語strict orderの頭文字)を添えて表しました。分かりにくくて申し訳ないです。)。

写像が狭義順序を保つことは広義順序を保ちかつ単射(つまり順序埋め込み)であることと同値です。

さてそれでは証明に入ります。自然数の通常の順序に関する、通常の数学的帰納法により

「任意の自然数 $\rm n$ について $\rm m,l\lt n$ に対しては $\rm f$ は狭義順序を保つ。」

を示します(蛇足ながら $\lt$ は通常の自然数に関する狭義順序であることを付け加えておきます)。

Basis case、即ち $\rm n=0$ のとき、命題は自明です。

Inductive Stepsは3つの場合に分かれます。

(i) $\rm L_n^{n+1}=\emptyset$ のとき

$\rm L_n^x$ の定義から $\rm n+1$ は $\rm m\leq n$ のいずれよりも $\preceq$ の意味で小さく、また $\rm f(n+1)$ と $\rm G_n^{n+1}$ の定義から

$\rm f(n+1) \\=min_\ll(G_n^{n+1})-1\\\ll_s min_\ll(G_n^{n+1})\\\ll f(m)(\forall m\leq n)$

なので条件を満たします。

帰納法の仮定から $\rm l,m\lt n+1$ であるような $\rm l,m$ について条件が満たされることはわかっていますから、これによって命題が示されました。

(ii) $\rm G_n^{n+1}=\emptyset$ のとき

(i)と大小を逆にしただけで全く同様にして示されます。

(iii) $\rm L_n^{n+1},G_n^{n+1}\neq\emptyset$ のとき

帰納法の仮定と $\rm L_n^{n+1},G_n^{n+1}$ の定義、そして $\ll$ の推移性から

$\rm max_\ll(L_n^{n+1})\ll_s min_\ll(G_n^{n+1})$

となります。

ここで比較が狭義順序であることに注意してください。

というのも、帰納法の仮定から順序を保つことより

$\rm max_\ll(L_n^{n+1})=f(max_\preceq\{m|(m\leq n)\land(m\preceq n+1)\})\\min_\ll(G_n^{n+1})=f(min_\preceq\{m|(m\leq n)\land(n+1\preceq m)\})$

となり、しかも $\rm f$ の $m\leq n$ への制限は単射ですから、仮に等号が成り立つとすると

$\rm min_\preceq\{m|(m\leq n)\land(n+1\preceq m)\}=max_\preceq\{m|(m\leq n)\land(m\preceq n+1)\}$

となるよりなく、これは明らかに矛盾を生じるからです。

従って

$\rm (n\geq \forall m\prec n+1)\\\ \ \ \ \ f(m)\\\ll max_\ll(L_n^{n+1})\\\ll_s\frac{max_\ll(L_n^{n+1})+min_\ll(G_n^{n+1})}{2}\\\ll_s max_\ll(L_n^{n+1})\\\ll f(m)\\(n+1\prec \forall m\leq n)$

が得られます。

(i)の時同様、帰納法の仮定から $\rm l,m\lt n+1$ であるような $\rm l,m$ について条件が満たされることはわかっていますから、これによって命題が示されました。

以上より数学的帰納法によって

「任意の自然数 $\rm n$ について $\rm\forall m,l\lt n$ に対しては $\rm f$ は狭義順序を保つ。」

が示されました。

実は本当に示したいことは「 $\rm f$ が狭義順序を保つこと」だったわけですが、これは $\rm n$ が任意であったことから簡単に同値です。つまり我々は目標を達成したことになります。

さて、これで $\rm f$ が狭義順序を保つ写像であること、すなわち順序を保つ単射であること、即ち順序の埋め込みであることがわかりました。

ここでほんの少しだけ補足をしますと、順序集合の埋め込みは集合論的に単射であればそれで大丈夫で、引き戻した時の挙動を心配する必要はありません。

これは今の例では $\rm a\ll b$ に対して $\rm f^{-1}(a),f^{-1}(b)$ はそれぞれ存在すれば一意ですが、ここで両方の存在を仮定したうえで $\rm \lnot(f^{-1}(a)\preceq f^{-1}(b))$ とすると明らかに矛盾であることからわかります。

こうしてみると、わざわざ書くほどのことでもないのですが、位相空間の様に稀に集合論的に単射でも埋め込みとは言えない構造の例が存在するので、一応念押ししたまでのことです。

さて話を戻すと $\rm f$ は埋め込みだったのですから、あとは全射であることを言えば同型であることがわかります。

次章ではそれを証明します。

3. $\rm f$ の全射性

さて $\rm f$ の全射性を示したいのですが、ここでは少しトリッキーな帰納法を用います。

それは「2進分数の分母の指数に関する帰納法」です。

すなわち

(i)任意の整数に対して $\rm f$ に沿った引き戻しが存在すること。

を言い

(ii)分母が高々 $\rm 2^n$ であるような2進分数について、すべて $\rm f$ に沿った引き戻しが存在するなら分母の指数が $\rm 2^{n+1}$ であるような2進分数すべてについても引き戻しが存在すること

を言うわけです。

まず(i)を見ましょう。

定義から $\rm A$ には通常の順序と両立する $\prec$ に関する無限上昇列および無限下降列が存在します。

もしもないとしたら、ある $\rm n$ より $\prec$ の意味で大きいor小さい元が有限個しかないことになり明らかに矛盾だからです。

このことと自然数の整礎性により、固定された $\rm n$ に対して

$\rm min_\leq\{m|n\prec m\},min_\leq\{m|m\prec n\}$

は常にvalidですから2つの再帰的定義

$\rm A(0)=0\\A(m+1)=min_\leq\{x|A(m)\prec x\}\\\ \\B(0)=0\\B(m+1)=min_\leq\{x|x \prec B(m)\}$

もvalidです。

実はこの $\rm A(n),B(n)$ はそれぞれ正整数、負整数についての $\rm f$ に沿った引き戻しになっています。すなわち $\rm f(n)$ が整数ならば $\rm A(f(n))=n,B(-f(n))=n$ となります。

これを見るためにもう一度 $\rm f$ の再帰的定義を検証します。

まず

$\rm F(n):=max_\ll\{f(m)|m\leq n\}$

を考えます。

$\rm F(n)$ の値が変わるのは $\rm n$ が $\rm f$ の再帰的定義のinductive stepの(i)の条件を満たしたときかつそのときのみであり、1度この条件を満たすたびに $\rm F(n)$ の値は1だけ増えますから $\rm m$ 回目にこの条件を満たしたときの $\rm F(n)$ の値は $\rm m$ です。