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が抜けている)。

●p122
「(11)~(13)をきちんと確かめることも」
――(13)を(14)に。

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

●p191、第4講の練習問題2の解答
「最初の節は第2の節に吸収できるので」
――正確には、「最初の節」と「第2節∨第4節」が同値ゆえ最初の節が落とせる。

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

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

鹿島『数理論理学』解答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\)とが互いの否定になる
のは、「全順序で考えている」という前提のもとなので、一般の半順序では後者の定義は正しくない。

20180527集合と位相ゼミの補足(ハミング距離)

命題\(P\)の真理値\(V(P)\)は\(1\)(真)あるいは\(0\)(偽)という値をとるものとする。すると\(P\rightarrow Q\)は\(V(P)\leq V(Q)\)と言い換えられる。また\(V(PとQの真偽が異なる)=|V(P)-V(Q)|\)である。

\(V(a\neq b)\)のことを\(d(a,b)\)と書くことにする。

等号の対称性と推移性から\(x=y\rightarrow(x=z\Leftrightarrow y=z)\)である。これにより、「\(x\neq z\)と\(y\neq z\)の真偽が異なるならば\(x\neq y\)である」ということがわかる。このことを冒頭の準備を用いて書き直すと\(|d(x,z)-d(y,z)|\leq d(x,y)\)が得られるが、これは1次元のハミング距離の三角不等式にほかならない。