エンダートン『論理学への数学的手引き』演習問題1.2.10

【補題】整式の集合$\Sigma_1,\Sigma_2$について、(A)「$\Sigma_1\vDash\sigma$ならば$\Sigma_2\vDash\sigma$」と(B)「$\Sigma_1\ni\sigma$ならば$\Sigma_2\vDash\sigma$」とは同値である。

（証明）$\Sigma_1\vDash\sigma$は$\Sigma_1\ni\sigma$よりも弱い仮定であるので(A)⇒(B)である。また(B)は「$\Sigma_1$の要素はすべて、$\Sigma_2$を充足するいかなる割り当てによっても真となる」、つまり「$\Sigma_2$を充足する割り当ては$\Sigma_1$をも充足する」ということを主張しているから、(B)⇒(A)も成り立つ。□

【演習10】(a)「整式の有限集合でサイズ$n$のものは、自身と同値で独立な部分集合を持つ」という命題を$\varphi(n)$とし、すべての自然数$n$に対して$\varphi(n)$が成り立つことを数学的帰納法により示す。$\varphi(0)$は、整式の空集合が独立の定義を満たすことから成立する。任意に自然数$n$をとって$\varphi(n)$を仮定し、$\varphi(n+1)$を導く。整式の有限集合でサイズ$n+1$のもの$\Sigma$を任意にとると、$\Sigma$が独立であれば自身が所期の部分集合となる。$\Sigma$が独立でないとき、$\alpha\in\Sigma$かつ$\Sigma\backslash\{\alpha\}\vDash\alpha$なる整式$\alpha$がとれる。$\Sigma\backslash\{\alpha\}
$は$\Sigma$と同値であり（上の補題に注意）、またサイズ$n$であるので、帰納法の仮定$\varphi(n)$により、同値で独立な部分集合を持つ。この集合はもとの$\Sigma$から見ても同値で独立な部分集合となる。

(b)整式の無限集合$\Sigma=\{A_1,A_1\wedge A_2,A_1\wedge A_2\wedge A_3,\ldots\}$が反例となることを示す。$\Sigma$の部分集合が独立であるのは一点集合か空集合のときだけである（さもないと「最も短い整式」が他から含意される）が、いずれにしても$\Sigma$と同値ではあり得ない。

(c)各$n\in\mathbb{N}$に対し$\sigma_0\rightarrow(\sigma_1\rightarrow(\sigma_2\rightarrow\cdots\rightarrow(\sigma_{n-1}\rightarrow\sigma_n)\cdots))$のことを$\gamma_n$と書く。$\Gamma=\{\gamma_n\mid n\in\mathbb{N}\}$からトートロジーをすべて除いたもの$\Gamma'$が所期の集合となることを示す。

・$\Sigma$との同値性：どの$\gamma_n\in\Gamma$に対しても$\Sigma\supseteq\{\sigma_n\}\vDash\gamma_n$、一方どの$\sigma_n\in\Sigma$に対しても$\Gamma\supseteq\{\gamma_0,\gamma_1,\ldots\gamma_n\}\vDash\sigma_n$であるから、$\Sigma$と$\Gamma$は同値である。さらに、トートロジーは整式のいかなる集合によっても含意されるから、$\Gamma(\supseteq\Gamma')$と$\Gamma'$も同値である。

・独立性：$\gamma_i\in\Gamma'$を任意にとり、$\Gamma'\backslash\{\gamma_i\}\not\vDash\gamma_i$を示す。$\gamma_i$はトートロジーではないため、これを偽にする真理値割り当て$v$が存在する。$\gamma_i$の定義から、$v$により$\sigma_0,\ldots,\sigma_{i-1}$はすべて真に、$\sigma_i$は偽になるので、$v$は$\Gamma'\backslash\{\gamma_i\}$を充足する。