小数表示と実数

有理数の切断によって実数を構成したとする。任意の小数表示に対して、「それによって表される実数」が存在することを示す。一意性についての議論は省略する。

以下、切断\( (A,B)\)の下組\(A\)(最大元を持たない)を指して「切断」という。

有理数\(r\)に対して「\(r\)未満の有理数全体」という集合は\(\mathbb{Q}\)の切断となっている。これを\(\mathbb{Q}_{ < r}\)と書けば、\({\mathbb{Q}_{ < r}}^c\)(\(\mathbb{Q}_{ < r}\)の補集合、すなわち切断の上組)は最小元\(r\)を持ち、この切断を有理数\(r\)と同一視することになる。

ある小数表示が与えられたとき、その第\(n\)位までで打ち切ったものを\(a_n\)とし、\(a_n\)の第\(n\)位(末位)に\(1\)を加えたものを\(b_n\)とする。この小数表示によって表される実数が存在することを示すには、「任意の\(n\)に対し\(a_n\leq\alpha\leq b_n\)」を満たす実数\(\alpha\)が存在することを言えばよく、これは「任意の\(n\)に対し\(\mathbb{Q}_{ < a_n}\subseteq A\subseteq\mathbb{Q}_{ < b_n}\)」を満たす\(\mathbb{Q}\)の切断\(A\)が存在することにほかならない。

\(\displaystyle A=\bigcup_{k\in\mathbb{N}}\mathbb{Q}_{ < a_k}\)とおき、任意の\(n\)をとる。\(A\)の定義から\(\mathbb{Q}_{ < a_n}\subseteq A\)である。また\(b_n\)はどの\(a_k\)よりも大きいから、\(A\)の任意の要素\(x\)について、ある\(k\)によって\(x < a_k < b_n\)と書かれるので\(x\in\mathbb{Q}_{ < b_n}\)、したがって\(A\subseteq\mathbb{Q}_{ < b_n}\)である。

私がレビューに参加して、最近出版されたもの一覧

『趣味で量子力学』広江克彦 @eman1972 著、理工図書

趣味で量子力学

趣味で量子力学

数学ガールの秘密ノート 場合の数』結城浩 @hyuki 著、SBクリエイティブ

『Webサーバを作りながら学ぶ 基礎からのWebアプリケーション開発入門』前橋和弥 @kmaebashi 著、技術評論社

『ヴィジュアルガイド 物理数学~1変数の微積分と常微分方程式~』前野昌弘 @irobutsu 著、東京図書

ヴィジュアルガイド 物理数学 ~1変数の微積分と常微分方程式~

ヴィジュアルガイド 物理数学 ~1変数の微積分と常微分方程式~

『キューネン数学基礎論講義』ケネス・キューネン著、藤田博司 @tenapyon 訳、日本評論社

キューネン数学基礎論講義

キューネン数学基礎論講義

有理数の切断によって構成した実数は、確かに切断公理を満たす

【定義】「\(\mathbb{Q}\)の切断」とは、以下をすべて満たす\(B\)をいう。
・\(\varnothing\subsetneq B\subsetneq\mathbb{Q}\)
・\(B\)は最大元を持たない
・\(\forall x\in B\forall y\in B^c[x < y]\)

有理数\(r\)に対し、「\(r\)未満の有理数全体」なる集合を\(\mathbb{Q}_{ < r}\)で表す。これは\(\mathbb{Q}\)の切断になっている。

\(\mathbb{Q}\)の切断全体が成す集合\(\mathcal{C}(\mathbb{Q})\)は、\(\subsetneq\)に関して全順序集合をなしている(証明略)。

【定義】「\(\mathcal{C}(\mathbb{Q})\)の切断」とは、以下をすべて満たす\(\mathcal{A}\)をいう。ただし、\(\mathcal{A}^c\)は\(\mathcal{C}(\mathbb{Q})\backslash\mathcal{A}\)を表す。
・\(\varnothing\subsetneq\mathcal{A}\subsetneq\mathcal{C}(\mathbb{Q})\)
・\(\mathcal{A}\)は\(\subsetneq\)に関する最大元を持たない
・\(\forall X\in\mathcal{A}\forall Y\in \mathcal{A}^c[X\subsetneq Y]\)

【定理】\(\mathcal{C}(\mathbb{Q})\)の任意の切断\(\mathcal{A}\)について、\(\mathcal{A}^c\)は最小元を持つ。
(証明)\(\mathbb{Q}_{ < r}\in\mathcal{A}\)なる有理数\(r\)の集合を\(B\)とすると、\(B\)は\(\mathbb{Q}\)の切断になっている(証明略)。
任意の\(X\in\mathcal{A}\)をとり、さらに任意の有理数\(x\in X\)をとると、\(\mathbb{Q}_{ < x}\subseteq X\)より\(\mathbb{Q}_{ < x}\in\mathcal{A}\)ゆえ\(x\in B\)である。これが任意の\(x\in X\)で成り立つことから\(X\subseteq B\)、したがって\(B\)は\(\mathcal{A}\)の上界である。次に任意の\(Y\in\mathcal{A}^c\)と任意の\(y\in Y^c\)をとれば、\(Y\subseteq\mathbb{Q}_{ < y}\)より\(\mathbb{Q}_{ < y}\in\mathcal{A}^c\)ゆえ\(y\in B^c\)、これが任意の\(y\in Y^c\)で成り立つことから\(Y^c\subseteq B^c\)すなわち\(B\subseteq Y\)、したがって\(B\)は\(\mathcal{A}^c\)の下界でもある。\(\mathcal{A}\)は最大元を持たないから、\(B\)は\(\mathcal{A}^c\)の最小元となる。■

『Henle集合論』定理6.13

『Henle集合論』定理6.13の証明を書いてみた。

【定理】\( (B, < _B)\)を整列集合とする。ある順序数から\(B\)への、順序を保つ全単射が存在する。
(証明)整列集合\( (B, < _B)\)に対し、\(c\notin B\)なる\(c\)をとる。超限再帰的定義により、順序数全体のクラスを定義域とする関数クラス\(g\)を次のように定める。ただし、\(g[\alpha]\)は\(g\upharpoonright_\alpha\)の値域である。\[g(\alpha)=\begin{cases} {\rm min}(B\backslash g[\alpha]) & (B\nsubseteq g[\alpha]のとき) \\ c & (B\subseteq g[\alpha]のとき)\end{cases}\]上段では\(g(\alpha)\in B\)、下段では\(g(\alpha)\notin B\)となることに注意。
\(g(\mu)=g(\nu)\in B\)を仮定して\(\mu=\nu\)を導く。背理法により\(\mu < \nu\)とすると、\(g(\mu)\in g[\nu]\)である一方で\(g(\nu)\in B\backslash g[\nu]\)すなわち\(g(\nu)\notin g[\nu]\)となり矛盾する。\(\nu < \mu\)と仮定しても同様である。

上で示したことと置換公理から、\(\{\alpha\mid g(\alpha)\in B\}\)は集合をなすので、これを\(D\)とする。\(g\upharpoonright_D\)は置換公理により集合をなすが、これが所望の写像であることを示す。
・\(D\)が順序数であること:\(D\)は順序数のみからなるので整列順序をなしている。\(\mu < \nu\)のとき\(B\backslash g[\nu]\subseteq B\backslash g[\mu]\)だから、さらに\(\nu\in D\)であるならば左辺が非空ゆえ右辺も非空となり\(\mu\in D\)、したがって\(D\)は推移的集合である。
・\(g\upharpoonright_D\)が単射であること:すでに上で示されている。
・\(g\upharpoonright_D\)が順序を保つこと:\(\mu,\nu\)はともに\(D\)に属し\(\mu < \nu\)であると仮定する。すると\(g(\nu)\in B\backslash g[\nu]\subseteq B\backslash g[\mu]\)であり、最右辺の最小元\(g(\mu)\)は\(g(\nu)\)以下となる。これと\(g\upharpoonright_D\)の単射性から\(g(\mu) < _B g(\nu)\)を得る。
・\(g[D]=B\)であること:\(D\)の定義から\(g[D]\subseteq B\)である。また、\(D\)は順序数ゆえ\(D\notin D\)すなわち\(g(D)\notin B\)であるから\(B\subseteq g[D]\)である。■

再帰定理・改

再帰定理 - y_bonten's blogを簡明に改良した。

『数学のロジックと集合論』p77、定理2.10の証明を、自分で書き直してみた。

\(m\in\mathbb{N}\)と写像\(g:\mathbb{N}\to\mathbb{N}\)が与えられている。\(k\in\mathbb{N}\)ごとに条件\(\psi_k(h)\)を「\(h\)が以下のすべてを満たすこと」と定義する。
・\(h:\mathbb{N}\to\mathbb{N}\)は\(\{0,1,\ldots,k\}\)を定義域とする部分写像である
・\(h(0)=m\)
・\(x'\in{\rm dom}(h)\)ならば\(h(x')=g(h(x))\)

補題】各々の\(k\in\mathbb{N}\)に対し、\(\psi_k\)を満たすものが一意に存在する。

(証明)\(k\)についての帰納法による。まず\(\{\langle 0,m\rangle\}\)は\(\psi_0\)を満たしている。一意性を示すために\(\psi_0(h)\)を仮定すると、\(h(0)=m\)すなわち\(\langle 0,m\rangle\in h\)であり、\(h\)は定義域を\(\{0\}\)とする部分写像であるから、これ以外の要素を持たず、\(h=\{\langle 0,m\rangle\}\)となる。
次に\(k\in\mathbb{N}\)に対し、\(h^*_k\)が\(\psi_k\)を満たす唯一のものであると仮定し、\(\psi_{k'}\)を満たすものが一意に存在することを示す。\(h^*_k\)に\(\langle k',g(h^*_k(k))\rangle\)を付け加えたものを\(h_{k'}\)とすれば、これは\(\psi_{k'}\)を満たしている。一意性を示すために\(\psi_{k'}(h)\)を仮定し、\(h=h_{k'}\)を導く。\(h\upharpoonright_{\leq k}\)は\(\psi_k\)を満たしているから\(h^*_k\)に一致し、したがって\(h\upharpoonright_{\leq k}=h_{k'}\upharpoonright_{\leq k}\)である。特に\(h(k)=h_{k'}(k)\)が成り立つので、両辺に\(g\)を作用させると\(h(k')=h_{k'}(k')\)も得られる。■

各\(k\in\mathbb{N}\)に対し\(\psi_k\)を満たす唯一のものを\(h^*_k\)とおく。

【定理】\(f=\{\langle k,h^*_k(k)\rangle:k\in\mathbb{N}\}\)は、以下をともに満たすような唯一の全域写像\(:\mathbb{N}\to\mathbb{N}\)である。
・\(f(0)=m\)
・任意の\(n\in\mathbb{N}\)に対し、\(f(n')=g(f(n))\)

(証明)\(f\)は\(\mathbb{N}\)から\(\mathbb{N}\)への全域写像であり、\(f(n)=h^*_n(n)\)であるから、\(f(0)=h^*_0(0)=m\)である。任意の\(n\in\mathbb{N}\)をとると、\(h^*_{n'}\upharpoonright_{\leq n}\)は\(\psi_n\)を満たすゆえ\(h^*_n\)に一致するから\(h^*_{n'}(n)=h^*_{n'}\upharpoonright_{\leq n}(n)=h^*_{n}(n)\)、この最左辺と最右辺に\(g\)を作用させれば\(h^*_{n'}(n')=g(h^*_n(n))\)すなわち\(f(n')=g(f(n))\)となる。一意性を示すため、全域写像\(F:\mathbb{N}\to\mathbb{N}\)が同じ条件を満たすと仮定し、\(F=f\)を帰納法により示す。まず\(F(0)=m=f(0)\)である。\(F(k)=f(k)\)と仮定すると、両辺に\(g\)を作用させることにより\(F(k')=f(k')\)を得る。■

モストフスキ同型定理

補題1】推移的集合\(T\)において関係\(\in\)が推移律を満たすとき、\(T\)の要素はすべて推移的集合である。
(証明)\(x\in y\in z\in T\)と仮定し、\(x\in z\)を導く。\(T\)が推移的集合であることから\(y\in T\)、さらに\(x\in T\)である。すると\(T\)における二項関係\(\in\)の推移性から\(x\in z\)となる。■

【定義】整列集合\( (W, < )\)の任意の要素\(x\)の各々について、条件\(\psi_x(\pi)\)とは\(\pi\)が以下をともに満たすことであるとする。
・\(\pi\)は\( (W_{ < x}, < )\)から\( (\pi[W_{ < x}],\in)\)への同型写像である。
・\(\pi\)の値域\(\pi[W_{ < x}]\)は推移的集合である。

補題2】\(\pi\)が整列集合\( (W, < )\)から推移的集合\( (T, \in)\)への同型写像であり、\(x\in W\)のとき、\(\pi\upharpoonright_{ < x}\)は\(\psi_x\)を満たし、その値域は\(\pi(x)\)である。
(証明)整列集合の性質から、\(\pi\upharpoonright_{ < x}\)は\( (W_{ < x}, < )\)から\( (T_{\in\pi(x)},\in)\)への同型写像である。\(T\)が推移的集合であることから\(\pi(x)\subseteq T\)、したがって\(T_{\in\pi(x)}=T\cap\pi(x)=\pi(x)\)である。\( (T,\in)\)は整列集合と同型であるからそれ自身も整列集合であり、したがって関係\(\in\)は\(T\)において推移的である。よって補題1により\(\pi(x)\)は推移的集合である。■

補題3】整列集合\( (W, < )\)の任意の\(x\in W\)に対し、\(\psi_x\)を満たすものが一意に存在する。

(証明)整列集合上の超限帰納法による。任意の\(x\in W\)をとり、\(y < x\)なる任意の\(y\in W\)の各々について、\(\psi_y\)を満たすものが一意に存在すると仮定し、それらを\(\pi^*_y\)とする。\(W_{ < x}\)の各要素\(y\)に対して\(\pi^*_y\)の値域を対応させる写像クラス\(\pi_x=\{\langle y,\pi^*_y[W_{ < y}]\rangle: y < x\}\)を考えれば、置換公理のもとで\(\pi_x[W_{ < x}]\)および\(\pi_x\)は集合をなす。この\(\pi_x\)が\(\psi_x\)を満たすことを示す。以下では、「帰納法の仮定により、各\(\pi_x(y)\)は\(\psi_y\)を満たす写像の値域として唯一のものである」という事実を頻繁に用いる。
・\(\pi_x\)が単射であること:\(u,v\in W_{ < x}\)かつ\(\pi_x(u)=\pi_x(v)\)と仮定すると、\(W_{ < u}\)と\(W_{ < v}\)が同型となるから、整列集合の性質により\(u=v\)である。
・任意の\(u,v\in W_{ < x}\)について、\(u < v\Leftrightarrow\pi_x(u)\in\pi_x(v)\)であること:(→)\(u < v < x\)と仮定する。補題2により、\(\pi^*_v\upharpoonright_{ < u}\)は\(\psi_u\)を満たし、その値域は\(\pi^*_v(u)\)である。よって\(\pi_x(u)=\pi^*_v(u)\in\pi_x(v)\)である。(←)\(u,v\in W_{ < x}\)かつ\(\pi_x(u)\in\pi_x(v)\)と仮定すると、\(\pi_x(u)=\pi^*_v(w)\)なる\(w < v\)が存在する。補題2により\(\pi^*_v\upharpoonright_{ < w}\)は\(\psi_w\)を満たし、その値域は\(\pi^*_v(w)\)である。よって\(\pi_x(u)=\pi^*_v(w)=\pi_x(w)\)となり、\(\pi_x\)の単射性から\(u=w < v\)を得る。
・\(\pi_x[W_{ < x}]\)が推移的集合であること:上記の「←」の証明において\(\pi_x(u)\)を\(s\)と読み替えて同様の議論をすることにより、\(s=\pi_x(w)\in\pi[W_{ < x}]\)を得る。
最後に一意性を示すため、\(\psi_x(\pi'_x)\)を仮定して\(\pi'_x=\pi_x\)を導く。任意の\(y < x\)をとると、補題2により\(\pi'_x\upharpoonright_{ < y}\)は\(\psi_y\)を満たし、その値域は\(\pi'_x(y)\)である。したがって\(\pi'_x(y)=\pi_x(y)\)である。■

【定理】任意の整列集合\( (W, <)\)の各々について、これと同型な推移的集合が一意に存在する。
(証明)\(W\)の末尾に要素\(z\)を付け加えた整列集合\(W^+\)を考えると、\(W=W^+_{ < z}\)であるから、補題3により\(W\)と同型な推移的集合が一意に存在する。■

国際言語学オリンピックの問題

のらんぶるさん紹介の国際言語学オリンピックの問題の別解をメモしておく。自分で解きたい人は読まないでください。
上質の言語パズル!言語学の知識不要,「国際言語学オリンピック」が面白い - のらんぶろぐ X
(以下、ネタバレ注意)






















「taluは『2倍』の意味だろうか」まではのらんぶるさんと同じ推論をした。

taluは「2倍」、yepokoは「2倍して1を足す」だろう。
するとrureponga=5、malapunga=7、alapunga=13、polangipunga=15で
10=5×2、15=7×2+1、27=13×2+1、30=15×2、35=24+5×2+1、48=24×2、50=24+13×2、79=24×2+15×2+1と説明がつく。
残った式は

(ア)20=supu
(イ)21=tokapunga telu
(ウ)40=tokapu(24) malapu
(エ)97=tokapu(24) yepoko alapunga(13) telu

の4つだ(すでに見た通り69=48+21なので、69には新しい情報は無い)。
(ウ)から40=24+malapu、つまりmalapu=16と考えて、malapunga=7と比較し、-punga系統が奇数ばかりだったことも考え合わせると、
[-pu]=([-punga]+1)×2という関係があるのではないか。
あるいは、基準となるnがあって、[-pu]=2n, [-punga]=n-1と考えてもいい。
するとtokapunga=tokapu(24)÷2-1=11だ。(イ)と21=11×2-1から、teluは「2倍して1を引く」のではないか……「telu<yepoko」って、そういう意味か!
すると(エ)97=24 yepoko+13×2-1から、24 yepoko=72。あれ?ここだけyepokoは「3倍」って意味に変わっている。
もしかしてtokapuの後に来るときは24×2+1ではなく24×(2+1)と解釈するのか?そう信じることにしよう。
(ア)は孤立していて使えなさそうに見えたが、もしかしたらsupungaという語があって、その値はsupu(20)÷2-1=9かもしれない。

以上の仮定を用いて設問に解答したところ、全問とも合致を見た。