§E16.11無矛盾性と Henkin 拡大

証明.$S_\infty$が$L_\infty$において矛盾すると仮定する。すなわち、$S_\infty\vdash_{L_\infty}\chi$かつ$S_\infty\vdash_{L_\infty}\neg\chi$を満たす$\chi\in\operatorname{Form}(L_\infty)$が存在する。この二つの§E16.10 定義 1.2の意味の導出を一つずつ固定する。

導出はいずれも有限列であり、各行の論理式は有限個の記号からなる。したがって、二つの導出の全体に現れる$L_\infty$の非論理記号は有限個であり、前提として用いる$S_\infty$の文も有限個である。記号も前提も一つも現れない場合には、$I$が空でないことから$i_0\in I$を一つ取る。一つ以上ある場合には、現れる各記号についてその記号を含む$L_i$の添字を、用いる各前提についてその文を含む$S_i$の添字を、それぞれ一つずつ選ぶ。選ぶ対象が有限個なので、この選択は ZF のもとで行うことができ、選択原理を必要としない。得られた添字は$I$の有限部分集合であるから、$\preceq$に関する最大元$i_0$が存在する。単調性により、$L_{i_0}$は二つの導出に現れるすべての非論理記号を含み、$S_{i_0}$は用いたすべての前提を含む。

二つの導出に現れる論理式は、$L_{i_0}$の非論理記号と論理記号だけからなるので、いずれも$\operatorname{Form}(L_{i_0})$に属する。§E16.10 定義 1.2の四条件は、公理スキーマの置換例であること、先行行への modus ponens、および一般化の変数条件だけを要求し、これらはどの行の論理式も$\operatorname{Form}(L_{i_0})$に属するかぎり$L_{i_0}$についてそのまま成り立つ。したがって同じ二つの有限列は$S_{i_0}$からの$L_{i_0}$導出であり、$S_{i_0}\vdash_{L_{i_0}}\chi$かつ$S_{i_0}\vdash_{L_{i_0}}\neg\chi$である。これは$S_{i_0}$が$L_{i_0}$において構文的に無矛盾であることに反する。▨

証明.§E1.21 定理 2.2により、ZFC のもとでは任意の集合と等濃な基数がただ一つ存在する。§E1.22 定理 3.2と§E1.22 系 3.3により、無限基数$\kappa$について

である。第一の等式を与える全単射$p:\kappa\times\kappa\to\kappa$を一つ固定する。$e_1:\kappa\to\kappa$を恒等写像とし、全単射$e_n:\kappa^n\to\kappa$が定まったとき、

と定める。有限再帰により、すべての正の整数$n$について全単射$e_n$が定まる。この族は固定した$p$から再帰的に一意に定まるので、各$n$について写像を別々に選ぶための可算選択公理を必要としない。

$\kappa$は無限であるから$0\in\kappa$である。空列を$(0,0)$へ送り、長さ$n>0$の列$s$を$(n,e_n(s))$へ送ると、$\kappa^{<\omega}$から$\omega\times\kappa$への単射を得る。§E1.22 系 3.3により、この終域の濃度は$\kappa$である。逆に長さ一の列が$\kappa$個あるため、$\kappa^{<\omega}=\kappa$である。$A$から$\kappa$への単射を有限列へ成分ごとに適用すれば、$|A^{<\omega}|\le\kappa$が従う。

構文対象の評価へ移る。変数、非論理記号、論理記号、括弧、および構文木の節を示す有限個のタグを合わせた集合を$B$とする。$|B|\le\mu$である。各項と論理式の有限構文木を、最外構成子を先に記録する前置記法の有限列へ符号化する。各記号の項数が有限であり、記号そのものが項数の情報をもつため、この符号化は単射とすることができる。したがって項集合と論理式集合はともに$B^{<\omega}$へ単射し、濃度は高々$\mu$である。変数集合は可算無限なので$|\mathrm{Var}|=\aleph_0$であり、$\mu=\max(\aleph_0,|L|)$である。文集合は論理式集合の部分集合であるから、その濃度も高々$\max(\aleph_0,|L|)$である。▨

証明.$|L|\le\kappa$である。ある段階の言語の記号が高々$\kappa$個であると仮定すると、補題 2.1により、その言語の項と論理式は高々$\kappa$個である。したがって、論理式へ一つずつ新定数を割り当てても新定数は高々$\kappa$個である。既存の記号と新定数との直和は$\kappa\times 2$へ単射し、§E1.22 系 3.3により$|\kappa\times 2|=\kappa$であるから、新言語の記号も高々$\kappa$個である。通常の帰納法により、各段階の言語、項集合、論理式集合、および新定数集合は高々$\kappa$個である。可算個の段階の合併は$\omega\times\kappa$へ単射し、§E1.22 系 3.3により$|\omega\times\kappa|=\kappa$であるから、その濃度は高々$\kappa$である。補題 2.1を$L^H$へ適用すると、$L^H$の全項集合は高々$\kappa$個である。閉項集合は全項集合の部分集合であり、商写像は閉項集合から商集合への全射なので、商の濃度も高々$\kappa$である。

$\lambda$個の相異なる新定数を加えた言語は、新定数集合を部分集合として含むため濃度が少なくとも$\lambda$である。一方、$\lambda\ge\max(\aleph_0,|L|)$である。$|L|=0$なら元の記号を加えても濃度は$\lambda$のままであり、$|L|>0$なら§E1.22 系 3.3により、元の記号集合と新定数集合の和は$|L|+\lambda=\lambda$である。いずれの場合も濃度は高々$\lambda$である。したがって拡大言語の濃度はちょうど$\lambda$である。▨

証明. 与えられた導出は有限列である。導出に現れる変数を避けて新鮮な変数$y$を選び、必要なら導出中の束縛変数を$\alpha$同値な新鮮変数へ先に変更する。導出の各行で$c$を$y$へ一様に置き換える。$S$の各文は$c$を含まないので前提の行は変わらない。論理公理、量化公理、等号公理は一様置換後も同じ公理スキーマの例であり、modus ponens は保存される。一般化された変数は$y$と異なるように選び直してあるため、一般化条件も保存される。したがって、置換後の有限列は$S\vdash_L\psi(y)$を与える。

$S$は文だけからなるため、$y$は$S$のどの前提にも自由に現れない。一般化規則を適用して$S\vdash_L\forall y\psi(y)$を得る。▨

証明.$A=\exists x\varphi(x)$、$B=\varphi(c)$とおく。$S\cup\{A\to B\}$が矛盾すると仮定する。§E16.10 定理 5.1と§E16.10 補題 2.1が与える古典命題論理の派生則により$S\vdash\neg(A\to B)$である。同じ派生則により$\neg(A\to B)$から$A$と$\neg B$がそれぞれ導かれるので、

を得る。

補題 3.1を第2の導出へ適用すると、$S\vdash\forall y\neg\varphi(y)$となる。束縛変数を$x$へアルファ変換すると$S\vdash\forall x\neg\varphi(x)$である。§E16.5 定義 2.3により$\exists x\varphi(x)$は$\neg\forall x\neg\varphi(x)$の略記であるから、第1の導出$S\vdash\exists x\varphi(x)$は$S\vdash\neg\forall x\neg\varphi(x)$にほかならない。論理式$\forall x\neg\varphi(x)$とその否定がともに$S$から導かれるので、これは$S$の無矛盾性に反する。したがって証人公理を加えた理論は構文的に無矛盾である。▨

証明.$L_0=L$、$T_0=T$とする。$n$段階の$L_n,T_n$が構成され、$T_n$が$L_n$において無矛盾であると仮定する。$FV(\varphi)\subseteq\{x\}$を満たす$L_n$論理式と変数の組$(\varphi,x)$の集合を$I_n$とする。補題 2.1により$L_n$論理式は高々$\kappa$個であり、変数は可算個である。$I_n$は論理式集合と変数集合との直積の部分集合なので、§E1.22 系 3.3により$|I_n|\le\kappa$である。§E1.21 定理 2.2を$I_n$へ適用し、$I_n$と全単射で対応する基数$\theta_n$と全単射$q_n:\theta_n\to I_n$を固定する。したがって$\theta_n\le\kappa$である。$q_n(\xi)=(\varphi_\xi,x_\xi)$と書く。添字$\xi<\theta_n$をタグとして用いることで、$L_n$に属さず、互いに異なる新定数$c_{n,\xi}$を定めることができる。

§E1.17 定理 2.1を用いて、$\xi\le\theta_n$に対する言語と理論の対$(L_{n,\xi},T_{n,\xi})$を次の規則で構成する。

1. $(L_{n,0},T_{n,0})=(L_n,T_n)$とする。
2. $\xi<\theta_n$に対して、$L_{n,\xi+1}=L_{n,\xi}\cup\{c_{n,\xi}\}$とし、 $$T_{n,\xi+1}=T_{n,\xi}\cup \{\exists x_\xi\varphi_\xi(x_\xi)\to\varphi_\xi(c_{n,\xi})\}$$ とする。
3. $0<\delta\le\theta_n$が極限順序数なら、 $$L_{n,\delta}=\bigcup_{\xi<\delta}L_{n,\xi}, \qquad T_{n,\delta}=\bigcup_{\xi<\delta}T_{n,\xi}$$ とする。

この再帰規則は、それ以前の対から次の対をただ一つ定めるので、§E1.17 定理 2.1の仮定を満たす。さらに§E1.17 定理 1.1を適用し、各$\xi\le\theta_n$について、$T_{n,\xi}$が$L_{n,\xi}$において無矛盾であることを示す。$\xi=0$では$T_n$の無矛盾性が仮定である。後続段$\xi+1$では、$\varphi_\xi$は$L_n\subseteq L_{n,\xi}$の論理式であり、$c_{n,\xi}$は$L_{n,\xi}$に属さない。したがって補題 3.2により無矛盾性が保存される。非零極限段$\delta$では、それ以前の言語と理論の対が包含関係で増大する空でない鎖をなすので、補題 1.1により、合併した理論は合併した言語において無矛盾である。これで超限帰納法の三つの場合が閉じる。

$L_{n+1}=L_{n,\theta_n}$、$T_{n+1}=T_{n,\theta_n}$とおく。$q_n$は$I_n$への全射であるから、すべての$L_n$一自由変数論理式に対する証人公理が$T_{n+1}$に属する。また、上の超限帰納法により$T_{n+1}$は$L_{n+1}$において無矛盾である。

この操作をすべての非負整数$n$について反復し、

とおく。$(L_n,T_n)_{n<\omega}$は言語と理論がともに増大する鎖であるから、補題 1.1により$T_\omega$は$L^H$において構文的に無矛盾である。$L^H$の任意の論理式$\varphi$は有限個の記号だけを含むため、$\varphi\in\operatorname{Form}(L_n)$を満たす非負整数$n$が存在する。したがって、その一自由変数論理式に対する証人公理は$T_{n+1}$で追加される。ゆえに$T_\omega$は Henkin 理論である。

各$n$について$\theta_n\le\kappa$であるから、各段階の新定数と証人公理は高々$\kappa$個である。系 2.2により$|L^H|\le\kappa$である。$T_\omega$は$T$と、可算個の段階で加えた高々$\kappa$個ずつの証人公理との和集合である。§E1.22 系 3.3による$|\omega\times\kappa|=\kappa$と$|T|\le\kappa$から両者のタグ付き和は$\kappa\times 2$へ単射する。再び同じ系を用いると$|\kappa\times2|=\kappa$であるから、$|T_\omega|\le\kappa$も従う。▨

証明.$L$において構文的に無矛盾であり$S$を含む$L$理論の全体を、包含関係で順序付ける。この順序集合は$S$を含むので空でない。空でない鎖については、鎖の各要素に同じ言語$L$を対応させると補題 1.1の言語が一定である特別な場合にあたるので、その合併は$L$において構文的に無矛盾である。鎖の各要素が$S$を含むので合併も$S$を含む。したがって合併はこの順序集合に属し、鎖の上界である。空の鎖については$S$自身が上界である。§E1.20 定理 2.1 (3)の Zorn の補題を適用すると極大元$S^*$が存在する。$S^*$は定義どおり極大無矛盾な$L$理論である。▨

証明.$S\vdash\sigma$かつ$\sigma\notin S$とする。$S\cup\{\sigma\}$から矛盾が導かれれば、その有限導出で前提$\sigma$を用いる各箇所へ$S$からの$\sigma$の導出を代入して、$S$から矛盾を導くことができる。したがって$S\cup\{\sigma\}$は無矛盾であり、極大性に反する。ゆえに$\sigma\in S$である。逆向きは、前提は一行の導出になることから従う。

$\sigma$と$\neg\sigma$が両方属することは無矛盾性に反する。$\sigma\notin S$なら、極大性により$S\cup\{\sigma\}$は矛盾する。§E16.10 定理 5.1と§E16.10 補題 2.1が与える古典命題論理の派生則により$S\vdash\neg\sigma$であり、(1)から$\neg\sigma\in S$である。したがってちょうど一方が属する。

$\sigma\to\tau\in S$かつ$\sigma\in S$なら、modus ponens と(1)により$\tau\in S$である。したがって$\sigma\to\tau\in S$なら$\sigma\notin S$または$\tau\in S$である。逆に$\tau\in S$なら、§E16.10 定義 1.1の論理公理スキーマ (H1) の置換例$\tau\to(\sigma\to\tau)$と modus ponens から$S\vdash\sigma\to\tau$である。$\sigma\notin S$なら(2)から$\neg\sigma\in S$である。§E16.10 補題 2.1 (5)が与える$\sigma\to(\neg\sigma\to\bot_\rho)$と$\bot_\rho\to\tau$を用いると$S\cup\{\sigma\}\vdash\tau$であり、§E16.10 定理 5.1により$S\vdash\sigma\to\tau$である。(1)により、どちらの場合も$\sigma\to\tau\in S$となる。▨

証明.定理 4.2により、無矛盾な Henkin 理論$T_\omega\subseteq\operatorname{Sent}(L^H)$を得る。定理 5.2を$L^H$の中で適用し、$T_\omega$を極大無矛盾な理論$T^H$へ拡大する。証人公理はすでに$T_\omega$に属するので、$T^H$にも属する。したがって$T^H$は Henkin 理論である。

$\exists x\varphi(x)\in T^H$とする。対応する証人公理$\exists x\varphi(x)\to\varphi(c)$も$T^H$に属する。 modus ponens と補題 5.3の導出閉包により$\varphi(c)\in T^H$である。濃度評価は系 2.2と補題 2.1から従う。▨