巨大数研究 Wiki
Advertisement

Math Advent Calender 2日目の記事です。

\(\textrm{ZFC}\)公理系の下で、\(\textrm{ZFC}\)公理系の無矛盾性を仮定して矛盾を導きます。(※よくあるネタです)

\(L\)を\(\textrm{ZFC}\)集合論の言語とします。つまり可算無限個の変数記号\(x_0, x_1, x_2, \ldots\)と2つの二項関係記号\(=, \in\)を持つ、\(1\)階述語論理の形式言語です。\(L\)論理式の集合である\(\textrm{ZFC}\)公理系を\(A\)と置きます。仮定より\(A\)は無矛盾となります。

\(A\)の下で\(\emptyset\)や\(\cup\)や\(\mathbb{N}\)における大小関係\(<\)といった通常の集合論で扱う諸概念を定義することができるので、それらを断りなく用います。

各自然数\(n\)に対し、\(L\)論理式\(P_n\)を以下のように再帰的に定義します:

  1. \(n = 0\)ならば、\(P_n\)は\(L\)論理式\(x_0 = \emptyset\)である。
  2. \(n > 0\)ならば、\(P_n\)は\(L\)論理式\(\forall x_{n-1}(P_{n-1} \to (x_n = x_{n-1} \cup \{x_{n-1}\}))\)である。

これは自然数のvon Neumann構成そのものですので、\(\exists x_n(P_n)\)は\(A\)の下で証明可能です。

\(L\)に定数記号\(c\)を添加した形式言語を\(\hat{L}\)と置きます。

\(\hat{L}\)論理式\(c \in \mathbb{N}\)を\(Q\)と置きます。

各自然数\(n\)に対し、\(\hat{L}\)論理式\(\forall x_n(P_n \to (n < c))\)を\(R_n\)と置きます。

\(\hat{L}\)論理式の集合である公理系\(A \cup \{\Psi\} \cup \{R_n \mid n \in \mathbb{N}\}\)を\(\hat{A}\)と置きます。

\(\hat{A}\)が有限充足可能であることを示します。

証明:
\(\Sigma \subset \hat{A}\)を有限集合とする。写像

\begin{eqnarray*} \mathbb{N} & \to & \hat{A} \\ n & \mapsto & R_n \end{eqnarray*}

の単射性から、\(S := \{n \in \mathbb{N} \mid R_n \in \Sigma\}\)は有限集合である。従って\(\min \{k \in \mathbb{N} \mid \forall n \in S, n < k\}\)が存在するので、それを\(N\)と置く。\(N\)の定義より\(\Sigma \subset A \cup \{\Psi\} \cup \{R_n \mid n \in \mathbb{N}, n < N\}\)である。
\(L\)論理式\(\forall x_0 \in \mathbb{N}, \neg(x_0 < x_0)\)は\(A\)の下で証明可能である。よって\(A\)の無矛盾性から、\(\forall x_0 \in \mathbb{N}, \neg(x_0 < x_0)\)の否定と同値である\(L\)論理式\(\exists x_0 \in \mathbb{N}, x_0 < x_0\)は\(A\)の下で証明可能でない。従って完全性定理より\(\exists x_0 \in \mathbb{N}, x_0 < x_0\)は\(A\)の下で恒真でない。すなわち、\(A\)のモデル\((M,E)\)であって\(\exists x_0 \in \mathbb{N}, x_0 < x_0\)を充足しないものが存在する。
\(A\)の下で\(\exists x_N(P_N)\)が証明可能であるので、ある\(m \in M\)が存在して\((M,m,E)\)が\(A \cup \{\Psi\} \cup \{R_n \mid n \in \mathbb{N}, n < N\}\)を充足する。以上より、\(\hat{A}\)は有限充足可能である。□

\(\hat{A}\)が有限充足可能であるので、コンパクト性定理から\(\hat{A}\)は充足可能となります。すなわち、\(\hat{A}\)のモデル\((M,m,E)\)が存在します。

\((M,m,E)\)は\(A\)を充足するので\((M,E)\)は\(A\)のモデルとなります。特に\(A\)の下で証明可能な\(L\)論理式\(\forall x_0 \in \mathbb{N}, \neg(x_0 < x_0)\)を充足します。

\((M,m,E)\)は\(Q\)を充足するので、\((M,E)\)において\(m \in \mathbb{N}\)は真です。

任意の\(n \in \mathbb{N}\)に対して\((M,m,E)\)は\(R_n\)を充足するので、\((M,E)\)において\(n < m\)は真です。特に、\((M,E)\)において\(m < m\)が真となります。

従って\((M,E)\)は\(\exists x_0 \in \mathbb{N}, x_0 < x_0\)を充足します。

以上より\((M,E)\)は\(\forall x_0 \in \mathbb{N}, \neg(x_0 < x_0)\)と\(\exists x_0 \in \mathbb{N}, x_0 < x_0\)の両方を充足してしまい、矛盾します。

Advertisement