ベシコヴィッチ・モンスターの構成

新井仁之『ルベーグ積分講義』(日本評論社)p190~p192の議論を書き直したもの。

\(\triangle{\rm ABC}=T\)に対して、操作(I)を施すことにより重なりの生じる部分(五角形\({\rm PQM'MR}\))を\(\Omega(T)\)とし、その面積を求める。\(\triangle{\rm QAM'}\)と \(\triangle{\rm RMB'}\)を、\({\rm QM'}\)と\({\rm RM}\)が一致するように合体させた三角形\({\rm QAM'(M)B'R}\)を考える。すると\(\triangle{\rm CAB}\sim \triangle{\rm PAB'}\sim\triangle{\rm QAM'(M)B'R}\)であり、相似比は\({\rm AB:AB':(AB'-M'M)}=1:\alpha:[\alpha-(1-\alpha)]\)となる。したがって\[\Omega(T)=\triangle{\rm PAB'}-\triangle{\rm QAM'(M)B'R}=[\alpha^2-(2\alpha-1)^2]T\]である。

操作(II)において、最初の\(\triangle{\rm ABC}\)を\(\Psi_0(=\Psi_{0,h})\)と書けば、\(\Psi_k\)から\(\Psi_{k+1}\)を得る操作を\(n\)回繰り返すことになる。1回の操作によって\(\Psi_{k,h}\)に由来する\(\Omega(\Psi_{k,h})/2^{n-k}\)の重なりが\(2^{n-k}\)個生じるので、これによって面積は\(\Omega(\Psi_{k,h})\)だけ減少する。この重なりは、その後の操作によって解消されることはないので、同部を「糊づけした」と考えてよい。いっぽう\(\Psi_{k,h}\)に由来しない部分は、新たな重なりが生じたり再び分離したりするため、その挙動は複雑である。そこで、面積の変化を見積もる際には「少なくとも、上述の糊づけされた分だけは面積が減少する」という事実を用いる。すると\(n\)回の操作によって面積は少なくとも\(\sum_{k=0}^{n-1}\Omega(\Psi_{k,h})\)だけ減少する。\(\Psi_{j+1,h}=\alpha^2\Psi_{j,h}\)より\(\Psi_{k,h}=\alpha^{2k}\Psi_{0,h}\)だから、以上の議論により\[\Psi_n\leq\left\{1-\sum_{k=0}^{n-1}[\alpha^2-(2\alpha-1)^2]\alpha^{2k}\right\}\Psi_{0,h}\]\[=\left[1-\frac{3\alpha-1}{1+\alpha}\left(1-\alpha^{2n}\right)\right]\triangle{\rm ABC}\]を得る。これは教科書p192の末尾で\(\sum\)の項数を有限のまま計算したものと一致する。
\(\Psi_n/\triangle{\rm ABC}\)を\(t(\alpha,n)\)とおき、任意の\(\epsilon > 0\)に対して、\(t(\alpha,n) < \epsilon\)となるような\(\alpha,n\)の組が\(\epsilon\)ごとにとれることを見る。小さい\(\epsilon > 0\)に対して\(\alpha_0=(4-\epsilon)/(4+\epsilon)\)とすると\(1/2 < \alpha < 1\)が成り立ち、\( (3\alpha_0-1)/(1+\alpha_0)=1-(\epsilon/2)\)である。さらに、この\(\alpha_0\)と\(\epsilon\)に対して、\({\alpha_0}^{n_0}\leq\epsilon/2\)なる自然数\(n_0\)をとることができる。このとき\(t(\alpha_0,n_0)\leq1-[1-(\epsilon/2)]^2 < \epsilon\)となる。

20181003セミナーのノート

(※内輪向けのメモ書きです。)
1. \(\Delta_0\)論理式の概念について
\(\Delta_0\)論理式自体は文字列としての論理式の「見た目」に依存する概念であって、互いに同値な論理式の一方が\(\Delta_0\)だが他方は\(\Delta_0\)でない、ということは珍しくありません。ただ絶対性を論じる際には同値であれば違いが吸収されるので、何か自分と同値な\(\Delta_0\)論理式を見つけさえすればよい、ということになると理解しています。したがって、この「違いが吸収される」という補題がどこかにあったのではないでしょうか(※まだKunen新版を入手できておらず未確認)。

2. ルベーグ不可測集合の構成の「第二段」までを書き直してみました。大きな変更点は
・\(\mathbb{R}\)の類別を考えるのではなく、初めから舞台を\( [0,1)\)に限定して類別を考えた。
・集合の要素を一斉にシフトした際に、右にはみ出した部分を左に戻す操作が煩雑なので、加減算を\(\rm modulo 1\)に変更して、演算の中に操作を組み込ませた。
の2点です。また\(\rm modulo\)に相性が良いように\( (0,1]\)を\( [0,1)\)に変えています。

集合\(I=[0,1)\)における\({\rm modulo} 1\)の加法・減法を\(\oplus,\ominus\)と書き*1、\(I\)上の2項関係\(\sim\)を\(x\ominus y\in\mathbb{Q}\)で定義する。\(x\ominus x=0,y\ominus x=\ominus(x\ominus y),x\ominus z=(x\ominus y)\oplus(y\ominus z)\)により、\(\sim\)は同値関係となる。選択公理により、各同値類から代表元をひとつずつ選んで集めた集合\(A\)を考えることができる。すると任意の\(x\in I\)の各々に対し\(x\ominus a\in\mathbb{Q}\)なる\(a\in A\)が一意に存在する。つまり、各\(x\)は\(a\in A\)および\(r\in I\cap\mathbb{Q}\)の組を用いて\(x=a\oplus r\)と一意に書かれる。そこで、このように書いたときの\(r\)の値によって\(I\)を類別することができる。すなわち、各\(r\in I\cap\mathbb{Q}\)に対し\(A_r=\{a\oplus r:a\in A\}\)と書けば、\(\{A_r:r\in I\cap\mathbb{Q}\}\)は\(I\)の類別となっている。

*1:例えば\(0.6\oplus 0.7=0.3,\ 0.1\ominus 0.2=0.9\)である。

高崎金久『学んでみよう!記号論理』ノート

高崎金久『学んでみよう!記号論理』(日本評論社)の正誤表
学んでみよう!記号論理
に未収録の誤りや補足など。

●p49、図1の(5)
――規則(f)を適用して直接得られるのは¬¬aと¬¬c。厳密にはこれに(h)を適用して初めてaとcを得るが、省略されている。p192の別解では省略されていない。

● p67、脚注1)
――2つ目の klassischer が klassicher になっている(sが抜けている)。

●p76、例6
――「立てていない仮定を落としてもよい」という大局観に立てば、仮定ψのもとで直ちにφ→ψを導いてもよい。

●p121、基本的な例
――たとえば「(1)において、yはφに自由変数として出現してはならない」など、細かな縛りがある。

●p121、式番号(2)
「∃yφ≡∃yφ[y/x]」
――左辺のyをxに。
●p122
「(11)~(13)をきちんと確かめることも」
――(13)を(14)に。

●p128、練習問題4
――「議論領域は空ではない」という前提がないと恒真性が頷けないものがあることに注意。

●p152、練習問題2
――ヒルベルト流で、自然演繹における「∨除去」と等価なことを行うには、演繹定理を用いなければ困難である。演繹定理により、仮定φ_1のもとでφが導かれるとき、無仮定でφ_1→φを導く証明が必ず存在する。そこで、φ_1∨φ_2とφ_1→φとφ_2→φから、公理H7を用いてφを導く。

●p155、証明の第n+1行の括弧内
「\(m-n\quad\neg{\rm I}\)」
――これは「mマイナスn」という意味ではなく、「mからn」という意味のハイフンであることに注意。

●p191、第4講の練習問題2の解答
「最初の節は第2の節に吸収できるので」
――一般に、論理和は「強いほう」が「弱いほう」に吸収されるので、ここは「第2の節は最初の節に吸収できるので」と言うべきである。同様に、第4節も第1節に吸収される。ただし、今回は「第2節∨第4節」が第1節と同値であるので、第1節だけを落としてもよい。

●p191、第5講の練習問題3の解答
「たとえば,2行目と3行目の適用の順序を変えれば」
――実際には2行目と3行目の適用順序が変わっただけでなく、2行目を適用して得られる枝を書き尽くしてから3行目の処理に移っているという違いもあることに注意。

●p200、第9講の練習問題6の解答
――(8)~(12)には、ハイティング代数{T,N,F}で考える限りにおいては恒真となるものも含まれるが、だからと言って直観主義論理の恒真式とは限らないことに注意。

●p202、下から10行目および下から4行目
――閉じ括弧を欠いている。

●p204、10行目
「注意されたい」
――ピリオドを欠いている。

●p205、下から6行目
「(7)~(10)も同様にNJの中で証明できる」
――(8)の「→」はNJでは証明できない。

鹿島『数理論理学』解答5.3後半

注意:以下において「論理式\(\psi\)の自由変数\(x\)に項\(t\)を代入する」とは、「\(\psi\)が\(x\)を自由変数として持つならば\(t\)を代入し、持たないならば何もしない」という意味であるとする。

閉論理式\(\varphi\)に登場するもの以外の変数を持たない、任意の論理式(\(\varphi\)もそのひとつであるが、閉論理式でなくてよい)\(\psi\)について、\(\psi\)および\(\psi^\sharp\)の自由変数に任意の\(\mathcal{D}\)拡大閉項を代入したとき(\(\psi\)の\(x_i\)と\(\psi^\sharp\)の\(x_{2i}\)には同じものを代入する)、そのつど両者の真理値が一致することを示せば、\(\mathcal{M}(\varphi)=\mathcal{M}(\varphi^\sharp)\)はその特別な場合として導かれる。

\(\varphi\)に登場する\(k\)個の変数を適当に並べて、その変数番号を\(i_1,i_2,\ldots,i_k\)とする。\(\mathcal{D}\)拡大閉項を\(k\)個並べた順序対(以下「代入リスト」という)\(L=({\sf a}_1,{\sf a}_2,\ldots,{\sf a}_k)\)を\(\psi\)に代入したもの、つまり「各\(j=1,2,\ldots,k\)について、\(\psi\)の自由変数\(x_{i_j}\)に\({\sf a}_j\)を代入したもの」を\(\psi_L\)と書く。同様に各\({\sf a}_j\)を\(\psi^\sharp\)の自由変数\(x_{2i_j}\)に代入したものを\(\psi^\sharp_L\)と書く。

\(\mathcal{M}(\psi_L)=\mathcal{M}(\psi^\sharp_L)\)が任意の代入リスト\(L\)について成り立つことを「論理式の複雑さに関する帰納法」によって示す。

\(\psi\)が原子論理式のとき:任意の代入リスト\(L\)について、\(\psi_L\)および\(\psi^\sharp_L\)の対応する項の値は等しいので(証明略)、これらを同じ述語記号で繋いだものの真理値も等しくなる。

\(\psi\)が複合論理式のとき:\(\psi\)より単純な任意の論理式\(\alpha\)について、「任意の代入リスト\(K\)に対し\(\mathcal{M}(\alpha_K)=\mathcal{M}(\alpha^\sharp_K) \)」が成り立っていると仮定する。

代入リスト\(L\)を任意にひとつ取って固定する。

・\(\psi=\neg\alpha\)のとき:\(\psi_L=\neg(\alpha_L)\)から\[\mathcal{M}(\psi_L)=真\Leftrightarrow\mathcal{M}(\alpha_L)=偽\]いっぽう\(\psi^\sharp=\neg(\alpha^\sharp)\)から\(\psi^\sharp_L=\neg(\alpha^\sharp_L)\)であるので\[\mathcal{M}(\psi^\sharp_L)=真\Leftrightarrow\mathcal{M}(\alpha^\sharp_L)=偽\]である。帰納法の仮定から両者の右辺同士は同値であるので、左辺同士も同値であり、\(\mathcal{M}(\psi_L)=\mathcal{M}(\psi^\sharp_L)\)となる。 \(\psi\)が「\(\alpha\wedge\beta\)」「\(\alpha\vee\beta\)」「\(\alpha\rightarrow\beta\)」と書かれる場合も同様にして示される。

・\(\psi=\exists x_i[\alpha]\)のとき:\(\alpha\)の\(x_i\)でない自由変数のみに\(L\)を代入したものを\(\alpha_{L^*}\)と書けば\[\mathcal{M}(\psi_L)=真\Leftrightarrow ある\mathcal{D}拡大閉項{\sf a}について\mathcal{M}(\alpha_{L^*}[{\sf a}/x_i])=真\]いっぽう\(\psi^\sharp=\exists x_{2i}[\alpha^\sharp]\)であり、\(\alpha^\sharp\)の\(x_{2i}\)でない自由変数のみに\(L\)を代入したものを\(\alpha^\sharp_{L^*}\)と書けば\[\mathcal{M}(\psi^\sharp_L)=真\Leftrightarrow ある\mathcal{D}拡大閉項{\sf a}について\mathcal{M}(\alpha^\sharp_{L^*}[{\sf a}/x_{2i}])=真\]である。いま任意の\(\mathcal{D}\)拡大閉項\({\sf c}\)について、\(\alpha_{L^*}[{\sf c}/x_i]\)と\(\alpha^\sharp_{L^*}[{\sf c}/x_{2i}]\)は、共通の代入リストを\(\alpha\)と\(\alpha^\sharp\)に代入したものにほかならないから、帰納法の仮定によりその真理値は\({\sf c}\)ごとに等しい。 したがって上記の右辺同士は同値であり、それゆえ左辺同士も同値となって\(\mathcal{M}(\psi_L)=\mathcal{M}(\psi^\sharp_L)\)を得る。\(\psi=\forall x_i[\alpha]\)と書かれる場合も同様に示される。■

キューネン基礎論定理II.7.15(1)(2)の同値性(コンパクト性定理)

\(\Sigma,\Theta\)を語彙\(\mathcal{L}\)の文の集合とする。次の(1)が任意の\(\Sigma\)で成り立つことと、(2)が任意の\(\Theta\)で成り立つことは同値。
(1)\(\Sigma\)のすべての有限部分集合がそれぞれモデルを持つとき、\(\Sigma\)もモデルを持つ。
(2)\(\Theta\models\psi\)のとき、ある有限の\(\Delta\subseteq\Theta\)について\(\Delta\models\psi\)となる。

(証明)(1)→(2)について:(1)および\(\Theta\models\psi\)を仮定する。\(\Theta\cup\{\neg\psi\}\)がモデルを持たないことから、(1)の対偶により\(\Theta\cup\{\neg\psi\}\)の有限部分集合\(\Omega\)でモデルを持たないものがとれる。\(\Delta=\Omega\cap\Theta\left(\subseteq\Theta\right)\)とおけば、これは有限集合であり、\(\Omega\subseteq\Delta\cup\{\neg\psi\}\)により、\(\Delta\cup\{\neg\psi\}\)もモデルを持たない。
(2)→(1)について:(2)の\(\psi\)として\(\perp\)を選ぶと、「\(\Theta\)がモデルを持たないとき、ある有限の\(\Delta\subseteq\Theta\)はモデルを持たない」となる。これは(1)の対偶である。■

原始的な帰納法のみでNにおける∈の無反射性を示す

\(\forall n\in\mathbb{N}[n\notin n]\)を、原始的な数学的帰納法のみを用いて示す。以下、\(n'\)は\({\rm Suc}(n)=n\cup\{n\}\)を意味する。
\(\beta(n):\forall k\in n'[k\notin k]\)と置くと、\(n\in n'\)により、各\(\beta(n)\)は\(n\notin n\)を含意する。そこで、\(\forall n\in\mathbb{N}[\beta(n)]\)を帰納法によって示せばよい。
まず\(\beta(\varnothing)\)は\(\varnothing\notin\varnothing\)により成立する。
\(\beta(n)\)を仮定し、\(k\)として\(n'\)を選べば\[n'\in n'\rightarrow n'\notin n'\]が得られるが、これは\(n'\notin n'\)のことである。したがって\(\beta(n')\)すなわち\(\beta(n)\wedge n'\notin n'\)も成立する。■

20180610集合と位相ゼミの補足(上限の定義について)

上限の定義に登場した、\[\forall y\in X[yはAの上界である\rightarrow a\leq y]\]と\[\forall x\in X[x < a\rightarrow\exists b\in A[x < b]]\]の同値性を納得しておきたい。記号を揃えるために前者の\(y\)を\(x\)と書き直す:\[\forall x\in X[xはAの上界である\rightarrow a\leq x]\]いっぽう、後者の\(\exists\)以降は「\(x\)は\(A\)の上界でない」と書ける:\[\forall x\in X[x < a\rightarrow xはAの上界でない]\]両者を見比べると互いに対偶になっている。ただし、
・「\(x\)は\(A\)の上界でない」は\(\exists b\in A[\neg b\leq x]\)だが、この\(\neg b\leq x\)を\(x < b\)と書いてよい
・\(a\leq x\)と\(x < a\)とが互いの否定になる
のは、「全順序で考えている」という前提のもとなので、一般の半順序では後者の定義は正しくない。