§E19.3Boolean 代数

$P=\{p_1,\ldots,p_n\}$とし、$p_1,\ldots,p_n$は相異なるとする。写像$\mathbf2^n\to\mathbf2$の全体を$\mathcal F_n$とすると、$\mathbf2^n$は$2^n$個の元をもつので$\mathcal F_n$は$2^{2^n}$個の元をもつ。各$a\in\mathbf2^n$に対して付値$v_a:P\to\mathbf2$を$v_a(p_i)=a_i$で定める。$P=\{p_1,\ldots,p_n\}$であるから、任意の付値$v$は$a=(v(p_1),\ldots,v(p_n))$について$v=v_a$を満たす。写像$\Theta:\mathcal B(P)\to\mathcal F_n$を$\Theta([\varphi])(a)=\widehat{v_a}(\varphi)$で定める。$\varphi\equiv_{\mathrm{sem}}\psi$ならばすべての$a$について$\widehat{v_a}(\varphi)=\widehat{v_a}(\psi)$であるから、$\Theta$は代表元に依存しない。$\Theta([\varphi])=\Theta([\psi])$ならば、すべての付値はある$v_a$に等しいので、すべての付値$v$について$\widehat v(\varphi)=\widehat v(\psi)$であり、$[\varphi]=[\psi]$である。よって$\Theta$は単射である。

$\Theta$が全射であることを示す。$n\geq1$の場合、$f\in\mathcal F_n$に対して§E19.2 定理 3.2により$f$を表現する論理式$\varphi\in\operatorname{Form}(P)\subseteq\operatorname{Form}_{\bot}(P)$が存在し、$\Theta([\varphi])(a)=\widehat{v_a}(\varphi)=f(a)$であるから$\Theta([\varphi])=f$である。$n=0$の場合、$\mathcal F_0$は唯一の入力$()$を$0$へ送る写像と$1$へ送る写像の二つからなり、それぞれ$\Theta([\bot])$と$\Theta([\top])$に等しい。いずれの場合も$\Theta$は全単射であり、$\mathcal B(P)$の元の個数は$2^{2^n}$である。$n=0$の場合の結論は系 4.3とも一致する。

$b_1\wedge b_2$、$b_1\wedge\neg b_2$、$\neg b_1\wedge b_2$、$\neg b_1\wedge\neg b_2$である。

$S=\overline g(\mathcal B(P))$とおく。$\overline g$は Boolean 準同型であるから、$x,y\in\mathcal B(P)$について$\overline g(x)\wedge\overline g(y)=\overline g(x\wedge y)$、$\overline g(x)\vee\overline g(y)=\overline g(x\vee y)$、$\neg\overline g(x)=\overline g(\neg x)$はいずれも$S$に属し、$0=\overline g(0)$と$1=\overline g(1)$も$S$に属する。よって$S$は部分 Boolean 代数であり、各$p\in P$について$g(p)=\overline g([p])\in S$である。

次に、$g(P)$を含む任意の部分 Boolean 代数$S'$について$S\subseteq S'$を示す。$\mathcal B(P)$の元はすべて$[\varphi]$（$\varphi\in\operatorname{Form}_{\bot}(P)$）の形であるから、すべての$\varphi$について$\overline g([\varphi])\in S'$を構造帰納法で示せばよい。$\varphi=p$ならば、定理 4.2の$\overline g\circ\eta=g$により$\overline g([p])=g(p)\in S'$である。$\varphi=\bot$ならば、$[\bot]=0$であり$\overline g$は$0$を保つので$\overline g([\bot])=0\in S'$である。$\overline g([\alpha]),\overline g([\beta])\in S'$とする。$[\neg\alpha]=\neg[\alpha]$であり、$\alpha\to\beta$と$\neg\alpha\lor\beta$はすべての付値で同じ真理値をとるので$[\alpha\to\beta]=[\neg\alpha\lor\beta]=\neg[\alpha]\vee[\beta]$である。$\overline g$は Boolean 準同型であるから$\overline g([\neg\alpha])=\neg\overline g([\alpha])$、$\overline g([\alpha\to\beta])=\neg\overline g([\alpha])\vee\overline g([\beta])$であり、$S'$が$\neg$と$\vee$について閉じていることから、いずれも$S'$に属する。よって$S\subseteq S'$であり、$S$は$g(P)$を含む最小の部分 Boolean 代数である。

$X=\Z$、$P=\{p\}$、$g(p)=E$の場合、奇数全体の集合を$O=\Z\setminus E$とすると、集合$\{\varnothing,E,O,\Z\}$は$\varnothing$と$\Z$を含み、共通部分、合併、補集合について閉じている。実際、$E\cap O=\varnothing$、$E\cup O=\Z$であり、$\varnothing$と$\Z$との共通部分・合併は元の集合か$\varnothing$か$\Z$であり、補集合は$\varnothing$と$\Z$、$E$と$O$を入れ替える。この集合は$E$を含み、$E$を含む部分 Boolean 代数は$E$の補集合$O$と$\varnothing$、$\Z$を含むので、前段によりこれが$\overline g$の像である。すなわち$\overline g$の像は$\{\varnothing,E,O,\Z\}$であり、$\overline g([\bot])=\varnothing$、$\overline g([p])=E$、$\overline g([\neg p])=O$、$\overline g([\top])=\Z$である。