\(R\)が\(A\)を整列順序づけすることから\[\forall x,y,z\in A[xRy\wedge yRz\rightarrow xRz]\]\[\forall x,y\in A[x=y,xRy,yRxのうちちょうどひとつが成立する]\]\[\forall Y\subseteq A\exists y\in Y\neg\exists z\in Y[zRy]\]が成り立つ。\(X\subseteq A\)のとき、上記の\(A\)を\(X\)に書き換えたものがすべて成立するから、\(R\)は\(X\)を整列順序づける。
キューネン数学基礎論p151、演習問題II.7.5
\(\mathfrak{A}\)を語彙\(\mathcal{L}\)に対する構造とし、その台集合を\(A\)とする。\(\mathcal{L}\)の項\(\tau\)に対し、「\(\tau\)に対する\(A\)への任意の割り当て\(\sigma',\sigma\)について、\(\sigma'\upharpoonright V(\tau)=\sigma\upharpoonright V(\tau)\)ならば\({\rm val}_\mathfrak{A}(\tau)[\sigma']={\rm val}_\mathfrak{A}(\tau)[\sigma]\)」という条件を\(\varphi(\tau)\)と置く。帰納法により\(\mathcal{L}\)の任意の項\(\tau\)について\(\varphi(\tau)\)が成り立つことを示す。
(1)\(\tau\in VAR\)のとき:\(\tau\)に対する\(A\)への割り当てで、\(\sigma'\upharpoonright V(\tau)=\sigma\upharpoonright V(\tau)\)を満たす任意の\(\sigma',\sigma\)をとる。\({\rm val}_\mathfrak{A}(\tau)[\sigma']=\sigma'(\tau)\)、\({\rm val}_\mathfrak{A}(\tau)[\sigma]=\sigma(\tau)\)であるが、\(\tau\in V(\tau)\)により両者は等しい。
(2)\(\tau\in\mathcal{F}_0\)のとき:(1)と同様に\(\sigma',\sigma\)をとると、\({\rm val}_\mathfrak{A}(\tau)[\sigma']\)も\({\rm val}_\mathfrak{A}(\tau)[\sigma]\)も共に\(\tau_\mathfrak{A}\)に等しい。
(3)\(n > 0\)に対し\(f\in\mathcal{F}_n\)かつ項\(\tau_0,\dots,\tau_{n-1}\)がすべて\(\varphi\)を満たすと仮定し、\(\tau=f\tau_0\ldots\tau_{n-1}\)も\(\varphi\)を満たすことを導く:(1)と同様に\(\sigma',\sigma\)をとると、これらは\(\tau_0,\dots,\tau_{n-1}\)のいずれに対しても\(A\)への割り当てとなっており、またどの\(\tau_i\)についても\(\sigma'\upharpoonright V(\tau_i)=\sigma\upharpoonright V(\tau_i)\)が成り立っているから、\(\varphi(\tau_i)\)により\({\rm val}_\mathfrak{A}(\tau_i)[\sigma']={\rm val}_\mathfrak{A}(\tau_i)[\sigma]\)である。すると\({\rm val}_\mathfrak{A}(\tau)[\sigma']\)および同\([\sigma]\)はその定義から等しくなる。■
小数表示と実数
有理数の切断によって実数を構成したとする。任意の小数表示に対して、「それによって表される実数」が存在することを示す。一意性についての議論は省略する。
以下、切断\( (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}\)である。
梵天ゆとりがレビューに参加した作品一覧
『数学ガール/ポアンカレ予想』結城浩 @hyuki 著、SBクリエイティブ
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2018/04/14
- メディア: 単行本
- この商品を含むブログ (5件) を見る
『魅了する無限~アキレスは本当にカメに追いついたのか』藤田博司 @tenapyon 著、技術評論社
魅了する無限 ~アキレスは本当にカメに追いついたのか~ (知りたい!サイエンス)
- 作者: 藤田博司
- 出版社/メーカー: 技術評論社
- 発売日: 2009/02/25
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (2件) を見る
『C言語ポインタ完全制覇』前橋和弥 @kmaebashi 著、技術評論社
- 作者: 前橋和弥
- 出版社/メーカー: 技術評論社
- 発売日: 2017/12/07
- メディア: 大型本
- この商品を含むブログを見る
『数学ガールの秘密ノート 積分を見つめて』結城浩 @hyuki 著、SBクリエイティブ
数学ガールの秘密ノート/積分を見つめて (数学ガールの秘密ノートシリーズ)
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2017/06/30
- メディア: 単行本
- この商品を含むブログ (6件) を見る
『ヴィジュアルガイド 物理数学~多変数関数と偏微分~』前野昌弘 @irobutsu 著、東京図書
- 作者: 前野昌弘
- 出版社/メーカー: 東京図書
- 発売日: 2017/07/10
- メディア: 単行本
- この商品を含むブログ (2件) を見る
『ねじ子とパン太郎のモニター心電図 改訂版』森皆ねじ子 @nejiko_net 著、エス・エム・エス
ねじ子とパン太郎のモニター心電図 改訂版 (ナース専科ポケットブックシリーズ4)
- 作者: 大上丈彦,森皆ねじ子
- 出版社/メーカー: エス・エム・エス(インプレス)
- 発売日: 2017/04/21
- メディア: 新書
- この商品を含むブログを見る
『数学ガールの秘密ノート やさしい統計』結城浩 @hyuki 著、SBクリエイティブ
数学ガールの秘密ノート/やさしい統計 (数学ガールの秘密ノートシリーズ)
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2016/10/29
- メディア: 単行本
- この商品を含むブログ (12件) を見る
『趣味で量子力学』広江克彦 @eman1972 著、理工図書
- 作者: 広江克彦
- 出版社/メーカー: 理工図書
- 発売日: 2015/12/01
- メディア: 単行本
- この商品を含むブログ (5件) を見る
『数学ガールの秘密ノート 場合の数』結城浩 @hyuki 著、SBクリエイティブ
数学ガールの秘密ノート/場合の数 (数学ガールの秘密ノートシリーズ)
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2016/04/20
- メディア: 単行本
- この商品を含むブログ (8件) を見る
『Webサーバを作りながら学ぶ 基礎からのWebアプリケーション開発入門』前橋和弥 @kmaebashi 著、技術評論社
Webサーバを作りながら学ぶ 基礎からのWebアプリケーション開発入門 (Software Design plus)
- 作者: 前橋和弥
- 出版社/メーカー: 技術評論社
- 発売日: 2016/06/07
- メディア: 大型本
- この商品を含むブログ (1件) を見る
『ヴィジュアルガイド 物理数学~1変数の微積分と常微分方程式~』前野昌弘 @irobutsu 著、東京図書
ヴィジュアルガイド 物理数学 ~1変数の微積分と常微分方程式~
- 作者: 前野昌弘
- 出版社/メーカー: 東京図書
- 発売日: 2016/06/10
- メディア: 単行本
- この商品を含むブログ (5件) を見る
『キューネン数学基礎論講義』ケネス・キューネン著、藤田博司 @tenapyon 訳、日本評論社
- 作者: ケネス・キューネン,藤田博司
- 出版社/メーカー: 日本評論社
- 発売日: 2016/07/21
- メディア: 単行本
- この商品を含むブログを見る
『数学ガールの秘密ノート ベクトルの真実』結城浩 @hyuki 著、SBクリエイティブ
数学ガールの秘密ノート/ベクトルの真実 (数学ガールの秘密ノートシリーズ)
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2015/11/18
- メディア: 単行本
- この商品を含むブログ (11件) を見る
『ワナにはまらないベクトル行列』大上丈彦 @otakehiko 著、技術評論社
- 作者: 大上丈彦,メダカカレッジ,森皆ねじ子
- 出版社/メーカー: 技術評論社
- 発売日: 2015/09/26
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (1件) を見る
『数学ガールの秘密ノート 微分を追いかけて』結城浩 @hyuki 著、SBクリエイティブ
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2015/04/18
- メディア: 単行本
- この商品を含むブログ (13件) を見る
『数学ガールの秘密ノート 数列の広場』結城浩 @hyuki 著、SBクリエイティブ
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/10/18
- メディア: 単行本
- この商品を含むブログ (13件) を見る
『数学ガールの秘密ノート 丸い三角関数』結城浩 @hyuki 著、SBクリエイティブ
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2014/04/24
- メディア: 単行本
- この商品を含むブログ (12件) を見る
『数学ガールの秘密ノート 整数で遊ぼう』結城浩 @hyuki 著、SBクリエイティブ
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2013/12/18
- メディア: 単行本
- この商品を含むブログ (17件) を見る
『数学ガールの秘密ノート 式とグラフ』結城浩 @hyuki 著、SBクリエイティブ
- 作者: 結城浩
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2013/07/13
- メディア: 単行本
- この商品を含むブログ (23件) を見る
『ワナにはまらない微分積分』大上丈彦 @otakehiko 著、技術評論社
- 作者: 大上丈彦,メダカカレッジ,森皆ねじ子
- 出版社/メーカー: 技術評論社
- 発売日: 2013/05/09
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (2件) を見る
『マンガでわかる統計学 素朴な疑問からゆる~く解説』大上丈彦 @otakehiko 著、SBクリエイティブ
マンガでわかる統計学 素朴な疑問からゆる~く解説 (サイエンス・アイ新書)
- 作者: 大上丈彦,メダカカレッジ,森皆ねじ子
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2012/01/17
- メディア: 新書
- 購入: 6人 クリック: 14回
- この商品を含むブログ (6件) を見る
『ねじ子のヒミツ手技 2nd Lesson』森皆ねじ子 @nejiko_net 著、エス・エム・エス
- 作者: 森皆ねじ子
- 出版社/メーカー: エス・エム・エス(インプレス)
- 発売日: 2010/08/10
- メディア: 単行本
- 購入: 8人 クリック: 26回
- この商品を含むブログ (2件) を見る
『ねじ子のヒミツ手技 1st Lesson』森皆ねじ子 @nejiko_net 著、エス・エム・エス
- 作者: 森皆ねじ子
- 出版社/メーカー: エス・エム・エス(インプレス)
- 発売日: 2009/06/29
- メディア: 単行本
- 購入: 7人 クリック: 75回
- この商品を含むブログ (9件) を見る
『マンガでわかる微分積分 微積ってなにをしているの?どうして教科書はわかりにくいの?』 大上丈彦 @otakehiko 著、SBクリエイティブ
マンガでわかる微分積分 微積ってなにをしているの?どうして教科書はわかりにくいの? (サイエンス・アイ新書)
- 作者: 石山たいら,大上丈彦,メダカカレッジ,森皆ねじ子
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2007/12/15
- メディア: 新書
- 購入: 29人 クリック: 139回
- この商品を含むブログ (17件) を見る
有理数の切断によって構成した実数は、確かに切断公理を満たす
【定義】「\(\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')\)を得る。■