鹿島『数理論理学』解答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次元のハミング距離の三角不等式にほかならない。

20180513集合と位相ゼミの補足

\(\mathcal{P}\)を集合\(X\)の分割とし、\(X\)上の二項関係\(x\sim y\)を\(\exists S\in\mathcal{P}[x\in S\wedge y\in S]\)と定義すると、\(\sim\)は同値関係である(証明略)。\(a\in X\)に対し同値類\(\{x\in X\mid x\sim a\}\)を\(C_a\)と略記する。

補題】\(a\in A\)を満たす任意の\(a\in X\)および\(A\in\mathcal{P}\)に対し、\(A=C_a\)が成り立つ。
(証明)\(A\subseteq C_a\)について:任意の\(x\in A\)をとると、\(a\in A\)であったので\(x\sim a\)すなわち\(x\in C_a\)を得る。
\(A\supseteq C_a\)について:任意の\(x\in C_a\)をとると、\(x\sim a\)により、\(x\in S\)かつ\(a\in S\)を満たす\(S\in\mathcal{P}\)がとれる。すると\(a\in S\cap A\neq\varnothing\)であり、\(\mathcal{P}\)が分割であること(条件3.)から\(S=A\)、したがって\(x\in A\)である。■

【本題】\(\mathcal{P}=\{C_a:\ a\in X\}\)である。
(証明)右辺を\(\mathcal{Q}\)とおく。
\(\mathcal{P}\subseteq\mathcal{Q}\)について:任意の\(A\in\mathcal{P}\)をとると、\(\mathcal{P}\)が分割であること(条件1.)から\(a\in A\)なる\(a\in X\)がとれる。すると補題により\(A=C_a\in\mathcal{Q}\)である。
\(\mathcal{P}\supseteq\mathcal{Q}\)について:任意の\(a\in X\)をとると、\(\mathcal{P}\)が分割であること(条件2.)から\(a\in A\)なる\(A\in\mathcal{P}\)がとれる。すると補題により\(C_a=A\in\mathcal{P}\)である。■

20180506集合と位相ゼミの補足

\(f\)が単射とは限らないときの、\(f[\bigcap A_i]=\bigcap f[A_i]\)の反例。

各\(A_i\)の、\(\bigcap A_i\)以外の点\(a_i\)たちから一斉に同じ点\(b\)に飛ぶ場合、像の共通部分をとっても\(b\)が「異物」として混入することがありうる。

\(f\)を\(\mathbb{N}\)から2点集合\(\{p,q\}\)(ただし\(p\neq q\))への写像とし、\[f(x)=\left\{\begin{array}{c}p\quad({\rm if}\ x=0)\\q\quad({\rm if}\ x\neq 0)\end{array}\right.\]と定義する。\(i\)は\(1,2,3,\ldots\)に渡るとして\(f[\bigcap\{0,i\}]=f[\{0\}]=\{p\}\)、いっぽう任意の\(i=1,2,3,\ldots\)に対して\(f[\{0,i\}]=\{p,q\}\)なので\(\bigcap f[\{0,i\}]=\{p,q\}\)となり、\(q\)が排除できずに残る。