数理論理学

記号列 $\sigma$ の左括弧の個数を $L(\sigma)$、右括弧の個数を $R(\sigma)$ と書く。論理式の構成に関する帰納法で 1 と 2 を同時に示す。
$\varphi=p_i$ のとき。括弧は現れないので $L(\varphi)=R(\varphi)=0$ であり 1 が成り立つ。$p_i$ は長さ 1 の記号列で真の始切片をもたないので、2 は確かめるべき場合がなく成り立つ。
$\varphi=(\lnot\psi)$ のとき、$\psi$ について 1 と 2 が成り立つとする。$L(\varphi)=1+L(\psi)$、$R(\varphi)=R(\psi)+1$ であり、帰納法の仮定 1 より $L(\psi)=R(\psi)$ だから $L(\varphi)=R(\varphi)$ で 1 が成り立つ。$\varphi$ の真の始切片 $\sigma$ は、$($、$(\lnot$、$(\lnot\tau$（$\tau$ は $\psi$ の真の始切片）、$(\lnot\psi$ のいずれかである。最初の 2 つでは $L(\sigma)=1>0=R(\sigma)$ である。3 つ目では帰納法の仮定 2 より $L(\tau)>R(\tau)$ なので $L(\sigma)=1+L(\tau)>R(\tau)=R(\sigma)$ である。最後では $L(\sigma)=1+L(\psi)>L(\psi)=R(\psi)=R(\sigma)$ である。よって 2 が成り立つ。
$\varphi=(\psi\ast\theta)$（$\ast$ は $\land,\lor,\to$ のいずれか）のとき、$\psi,\theta$ について 1 と 2 が成り立つとする。$L(\varphi)=1+L(\psi)+L(\theta)=1+R(\psi)+R(\theta)=R(\varphi)$ で 1 が成り立つ。真の始切片 $\sigma$ は次のいずれかである。(i) $($。(ii) $(\tau$（$\tau$ は $\psi$ の真の始切片）。(iii) $(\psi$。(iv) $(\psi\ast$。(v) $(\psi\ast\tau'$（$\tau'$ は $\theta$ の真の始切片）。(vi) $(\psi\ast\theta$。(i) では $L(\sigma)=1>0=R(\sigma)$。(ii) では $L(\sigma)=1+L(\tau)>R(\tau)=R(\sigma)$。(iii) と (iv) では $L(\sigma)=1+L(\psi)>L(\psi)=R(\psi)=R(\sigma)$。(v) では $L(\sigma)=1+L(\psi)+L(\tau')>R(\psi)+R(\tau')=R(\sigma)$。(vi) では $L(\sigma)=1+L(\psi)+L(\theta)>R(\psi)+R(\theta)=R(\sigma)$。いずれも $L(\sigma)>R(\sigma)$ であり、2 が成り立つ。$\square$

前半。def-mathematical-logic-valuation より、$v((\varphi\to\psi))=\mathrm{F}$ となるのは $v(\varphi)=\mathrm{T}$ かつ $v(\psi)=\mathrm{F}$ のときに限る。仮定より $v((\varphi\to\psi))=\mathrm{T}$ なので、この場合には当たらない。ところが $v(\varphi)=\mathrm{T}$ は仮定されているから、$v(\psi)=\mathrm{F}$ ではありえず、真理値は $\mathrm{T},\mathrm{F}$ のいずれかなので $v(\psi)=\mathrm{T}$ である。
後半。$\Sigma$ のすべての元を $\mathrm{T}$ にする真理値割り当て $v$ を任意にとる。$\Sigma\vDash\varphi$ より $v(\varphi)=\mathrm{T}$、$\Sigma\vDash(\varphi\to\psi)$ より $v((\varphi\to\psi))=\mathrm{T}$ である。前半より $v(\psi)=\mathrm{T}$ である。$v$ は任意だったので $\Sigma\vDash\psi$ である。恒真式についての主張は $\Sigma=\emptyset$（空集合）の場合であり、このとき条件「$\Sigma$ のすべての元を $\mathrm{T}$ にする」はどの真理値割り当ても満たす（空虚な真）。$\square$

$L$ に含まれない相異なる新しい定数記号 $c_i$（$i\in I$）を加えた言語を $L'$ とし、
$$\Sigma':=\Sigma\cup\{\lnot(c_i=c_j)\mid i,j\in I,\ i\neq j\}$$
とおく。$\lnot(c_i=c_j)$ は変数を含まないので、$\Sigma'$ は $L'$ の文の集合である。
$\Sigma'$ の任意の有限部分集合 $\Sigma_0$ が充足可能であることを示す。$\Sigma_0$ に現れる新しい定数記号は有限個であり、それらを $c_{i_1},\dots,c_{i_n}$（$i_1,\dots,i_n$ は相異なる）とする。$\mathfrak{A}$ の台集合 $A$ は無限集合だから、相異なる元 $a_1,\dots,a_n\in A$ を選べる（無限集合は任意の自然数 $n$ について $n$ 個の相異なる元を含む）。$\mathfrak{A}$ を、$c_{i_k}$ を $a_k$ で、それ以外の $c_i$ を $A$ の固定した一つの元で解釈することで $L'$ の構造 $\mathfrak{A}'$ に拡張する。$\Sigma$ の元は新しい定数記号を含まず、$\mathfrak{A}'$ における $L$ の記号の解釈は $\mathfrak{A}$ と同じなので、$\Sigma$ の元は $\mathfrak{A}'$ で真である。$\Sigma_0$ に含まれる $\lnot(c_{i_k}=c_{i_l})$（$k\neq l$）は、$a_k\neq a_l$ より $\mathfrak{A}'$ で真である。よって $\mathfrak{A}'$ は $\Sigma_0$ のモデルである。
thm-mathematical-logic-compactness より $\Sigma'$ はモデル $\mathfrak{B}$ をもつ。$\Sigma\subset\Sigma'$ だから $\mathfrak{B}$ は $\Sigma$ のモデルであり、新しい定数記号の解釈を忘れれば $L$ の構造とみなせる。$i\mapsto c_i^{\mathfrak{B}}$ は $I$ から $\mathfrak{B}$ の台集合への写像で、$i\neq j$ なら $\lnot(c_i=c_j)$ が $\mathfrak{B}$ で真なので $c_i^{\mathfrak{B}}\neq c_j^{\mathfrak{B}}$、すなわち単射である。$\square$