Ex. 1.1

本記事について

本記事は、R. Kaye, Models of Peano Arithmetic の演習問題1.1の解答です。

• 解答のまとめページ

注意

• 著作権の観点から、問題文は掲載しません。
• 定義や記法は教科書に則ります。
• 何か問題があれば、コメント等でご指摘ください。

解答

$h$が埋め込みであることは, 本文 p.11 の議論によってすでに分かっている. 故に後は, すべての$\mathcal{L}_A$論理式$\varphi(\bar{x})$ とすべての自然数$\bar{n}$について,
$$ \N \models \varphi(\bar{n}) \iff M \models \varphi(\overline{(h(n))}) \tag{1} \label{goal} $$
を示せば良い.
論理式の構成に関する帰納法で示す.

1. Base Step
   原始論理式については, 本文p.11においてすでに確かめられている.

2. Induction Step
   $\LA$論理式$\varphi(\bar{x}), \psi(\bar{x}), \theta(z, \bar{x})$について成立しているとする.

   • $\varphi(\bar{x})\land\psi(\bar{x})$
     任意の自然数$\bar{n}$について,
     \begin{align} \N \models \varphi(\bar{n})\land\psi(\bar{n}) &\iff \N \models \varphi(\bar{n}) \text{かつ} \N \models \psi(\bar{n})\\ &\overset{\text{I.H.}}{\iff} M \models \varphi(\overline{h(n)}) \text{かつ} M \models \psi(\overline{h(n)})\\ &\iff M \models \varphi(\overline{h(n)}) \land \psi(\overline{h(n)}) \end{align}
     なのでよい.
     • $\varphi(\bar{n})\lor\psi(\bar{n})$の場合も同様.
     • $\lnot\varphi(\bar{n})$
       任意の自然数$\bar{n}$について,
       \begin{align} \N \models \lnot\varphi(\bar{n}) &\iff \N \not\models \varphi(\bar{n})\\ &\overset{\text{I.H.}}{\iff} M \not\models \varphi(\overline{h(n)})\\ &\iff M \models \lnot\varphi(\overline{h(n)}) \end{align}
       なのでよい.
     • $\forall z \theta(z, \bar{x})$
       $\forall z \theta(z, \bar{\underline{n}})$が$\LA$文であることと, $M \models \Th{\N}$であることから, 任意の自然数$\bar{n}$について
       \begin{align} \N \models \forall z \theta(z, \bar{n}) &\iff \N \models \forall z \theta(z, \bar{\underline{n}})\\ &\implies M \models \forall z \theta(z, \bar{\underline{n}})\\ &\iff M \models \forall z \theta(z, \overline{h(n)}) \end{align}
       より$\N \models \forall z \theta(z, \bar{n}) \implies M \models \forall z \theta(z, \overline{h(n)})$が分かる. (この向きは帰納法の仮定を使用していない)
       逆は
       \begin{align} M \models \forall z \theta(z, \overline{h(n)}) &\implies \text{任意の}\ \underline{m}^M \in M\ \text{について}\ M \models \theta(\underline{m}^M, \overline{h(n)})\\ &\iff \text{任意の}\ m \in \N\ \text{について}\ M \models \theta(h(m), \overline{h(n)})\\ &\overset{\text{I.H.}}{\iff} \text{任意の}\ m \in \N\ \text{について}\ \N \models \theta(m, \bar{n})\\ &\iff \N \models \forall z \theta(z, \bar{n}) \end{align}
       によって分かる.
     • $\exists z\theta(z, \bar{x})$
       $\N \models \exists z\theta(z, \bar{n}) \implies M \models \exists z\theta(z, \overline{h(n)})$は$\forall$の後者の場合と同様.
       逆向きは, 対偶を考えることで$\forall$の前者の場合と同様に示せる.

以上により, 論理式の構成に関する帰納法で\eqref{goal}が示せた.

おわりに

高評価を押して頂けると励みになります。