集合と位相

　Heyting代数（付録８参照） B は、条件

(A2-1)  (að0)ña = 1

を満たすときBoole代数といいます。
　付録８の議論で既に示唆されていることですが、以下に述べるように、直観主義論理はHeyting代数によって、古典論理はBoole代数によって、それぞれ代数的に特徴付けることができます。

　最初にHeyting代数とBoole代数について主な性質を調べておきましょう。
　Heyting代数は、次の分配律を満たします：

(A2-2a)  añ(bòc) = (añb)ò(añc)

(A2-2b)  aò(bñc) = (aòb)ñ(aòc)

　実際、一般の束に対して、a £ añb と a £ añc により a £ (añb)ò(añc) が成り立ち、b £ añb と c £ añc から bòc £ (añb)ò(añc) が成り立つので、(A2-2a) の (左辺) £ (右辺) は常に成り立ちます。
　同様に、やはり一般の束に対して、a ³ aòb と a ³ aòc により a ³ (aòb)ñ(aòc) が成り立ち、b ³ aòb と c ³ aòc から bñc ³ (aòb)ñ(aòc) が成り立つので、(A2-2b) の (左辺) ³ (右辺) も常に成り立ちます。

　逆向きの不等号は、Heyting代数の特徴である xòa £ b と x £ aðb の同値性を用いて、次のように証明することができます。

　まず bòc £ añ(bòc) により b £ cð(añ(bòc)) が得られ、他方で aòc £ a £ añ(bòc) により a £ cð(añ(bòc)) が得られます。
　ゆえに añb £ cð(añ(bòc)) が得られますが、これは (añb)òc £ añ(bòc) と、従って c £ (añb)ð(añ(bòc)) と同値です。
　一方、明らかに (añb)òa = a £ añ(bòc) が成り立ちますが、これは a £ (añb)ð(añ(bòc)) と同値です。
　ゆえに añc £ (añb)ð(añ(bòc)) が成り立ちますが、これは (añb)ò(añc) £ añ(bòc) と同値ですから、これで (A2-2a) が証明されました。

　次に aòb £ (aòb)ñ(aòc) により b £ að((aòb)ñ(aòc)) が得られます。
　同様に、aòc £ (aòb)ñ(aòc) により c £ að((aòb)ñ(aòc)) が得られます。
　ゆえに bñc £ að((aòb)ñ(aòc)) が得られますが、これは aò(bñc) £ (aòb)ñ(aòc) と同値です。以上で (A2-2b) も証明されました。

　さて、xòa £ 0 と x £ að0 の同値性において x に að0 を代入すると、(að0)òa £ 0 すなわち (að0)òa = 0 が得られます。そこで

(A2-3)  ùa  :º  að0

と定義すると、この事実と (A2-1) は

(A2-4a)  añ(ùa) = 1

(A2-4b)  aò(ùa) = 0

と書くことができます。

　さて、束 B は、最大値 1 と最小値 0 を持ち、分配律 (A2-2) を満たし、(A2-4) を満たす演算 ù が存在すればBoole代数になります。実際、まず

(A2-5)  aðb :º (ùa)ñb

と置いて、B がHeyting代数になることを証明しましょう。
　実際、(A2-2b) と (A2-4b) により、(aðb)òa = ((ùa)ñb)òa = ((ùa)òa)ñ(bòa) = 0ñ(bòa) = bòa £ b が成り立ちます。
　また xòa £ b なら、(A2-4a) と (A2-2a) により、x £ (ùa)ñx = ((ùa)ñx)ò1 = ((ùa)ñx)ò((ùa)ña) = (ùa)ñ(xòa) £ (ùa)ñb = aðb となります。
　これらは aðb = max { xÎB | xòa £ b } が成り立つことを意味するので、確かに B はHeyting代数になることがわかりました。

　最後に að0 = (ùa)ñ0 = ùa となりますから、これと (A2-4a) により (A2-1) が成り立つことがわかり、B がBoole代数になることがわかります。

　T  を、古典論理の論理接続詞と量化記号とそれらの推論規則以外に論理接続詞、量化記号、推論規則を持たない古典論理の推論体系とし、集合 S とBoole代数 B が与えられたとき、この場合の T  のHeytingモデル（付録８参照）のことを、理論 T  のBooleモデルといいます。この場合、付録８ (A8-1) の性質：

(A2-6a)  ( f T1 ,¼, Tn )* = f*(T1*,¼, Tn*)

(A2-6b)  ( pT1 ,¼, Tn )* = p*(T1*,¼, Tn*)

(A2-6c)  ^* = 0

(A2-6d)  (P Ù Q)* = P* ò Q*

(A2-6e)  (P Ú Q)* = P* ñ Q*

(A2-6f)  (P Þ Q)* = P* ð Q*

(A2-6g)  ("xP)* = inf{ P* | x*ÎS }

(A2-6h)  ($xP)* = sup{ P* | x*ÎS }

に加えて

(A2-6i)  (Ø P)* = (P Þ ^)* = P* ð ^* = (ùP*) ñ ^* = (ùP*) ñ 0 = ùP*

が成り立つこともわかります。

　この場合も、もし B が S-完備ならば、変数 x に対する x* と、関数記号 f に対する f* と、述語記号 p に対する p* さえ与えられれば（このとき論理式の解釈が与えられたといいます）、項 T に対する T*ÎS と命題 P に対する P*ÎB を (A2-10) によって順次定義していくことによって、理論 T  のBooleモデルを構成することができることは、Heytingモデルの場合と全く同様です。

　さて、Booleモデルが与えられたとき、直観主義論理の場合の (A8-2) と同様に、古典論理で証明可能な任意のsequent A₁ ,¼, A_n ® R に対し、

(A2-7)   inf{A1* ,¼, An* } £ R*

が成り立つことが証明できます。
　実際、証明文に現れる各sequentが、どんな解釈に対しても (A2-7) を満たすことを、上から順に確かめていけばよいのですが、用いられた推論規則が排中律以外の場合は付録８で既に確かめていますから、用いた推論規則が排中律である場合のみを確かめれば十分です。
　すなわちsequent ® P Ú Ø P について (A2-7) を確かめればよく、その右辺は (A2-6e),(A2-6i),(A2-4a) により (P Ú Ø P)* = P*ñ(ùP*) = 1 となるので明らかに成り立ちます。

　さて、理論 T  でsequent ® R が証明可能であるとき、R は証明可能であるといいますが、直観主義論理の場合の (A8-2) と古典論理の場合の (A2-7) で n をゼロとすれば、inf Æ = 1 ですから R* = 1 となることがわかります。
　そこで一般に、考えているモデルにおいて R* = 1 となる閉命題を真な命題、R* = 0 となる閉命題を偽な命題とよぶことにし、（特定の性質を持つ）すべてのモデルにおいて真であるような閉命題は（その特定の性質に対して）恒真であるといいます。
　以上の結果をメタ定理の形で述べると、

直観主義論理（古典論理）の健全性 　T  を直観主義論理（古典論理）の論理接続詞と量化記号とそれらの推論規則以外に論理接続詞、量化記号、推論規則を持たない直観主義論理（古典論理）に従う任意の理論とする。このとき T  で証明可能な閉命題はすべてのHeytingモデル（Booleモデル）で恒真である。

　このように、「証明可能なら恒真である」という性質を健全性といいますが、この逆の性質、すなわち「恒真なら証明可能である」という性質を完全性とよびます（これは付録６でいう「完全性」、すなわち「すべての閉命題が証明又は反証可能」という意味とは異なります）。以下で、この完全性も成立することを証明します。

　理論 T  を、直観主義論理（古典論理）の論理接続詞と量化記号とそれらの推論規則以外に論理接続詞、量化記号、推論規則を持たない直観主義論理（古典論理）に従う任意の理論とします。
　このときHeytingモデル（Booleモデル）として集合 S とHeyting代数（Boole代数） B の組が与えられたとします。
　もし B の最小元 0 と最大元 1 が等しい、すなわち 0 = 1 ならば理論 T  が矛盾するとき、このモデルは T  と整合的であるということにします。また、集合 S が可算集合のとき、これをHeyting（Boole）可算モデルとよぶことにします。

　理論 T  の項全体から成る集合を S₀ 、T  の命題全体から成る集合を B₀ と書き、P, QÎB₀ に対して P ® Q が T  の定理であるとき P £ Q と書き、P と Q が T  で同値であるとき P = Q と書くことにします。
　このとき、推論規則 ( 仮 定 ) と ( 切 断 ) により、£ は擬順序関係であることがわかり、= は同値関係で

(A2-8)  ( P £ Q  Ù  Q £ P )  Þ  P = Q

が成り立つことがわかります。

　ところで P £ Q が成り立つ、すなわち P ® Q が定理であることと、P Þ Q が定理であることは同値です。
　実際、前者から後者は ( Þ 導入) により明らかで、逆に後者が成り立つときは、( 増 ) により P ® P Þ Q が成り立ち、( 仮 定 ) により P ® P が成り立つので ( Þ 消去) を用いれば P ® Q が得られるからです。

　以下 P , Q , R は任意の命題を表すことにします。
　まず始式 P ® P と Q ® Q から ( Ù 左) により P Ù Q ® P と P Ù Q ® Q が得られ、これは P Ù Q £ P と P Ù Q £ Q を意味します。
　逆に、R £ P と R £ Q 、すなわち R ® P と R ® Q が成り立てば、( Ù 右) により R ® P Ù Q すなわち R £ P Ù Q が得られます。ゆえに

(A2-9a)  P Ù Q  =  P ò Q

が成り立つことがわかります。
　また始式 P ® P と Q ® Q から ( Ú 右) により P ® P Ú Q と Q ® P Ú Q が得られ、これは P £ P Ú Q と Q £ P Ú Q を意味します。
　逆に、P £ R と Q £ R 、すなわち P ® R と Q ® R が成り立てば、( Ú 左) により P Ú Q ® R すなわち P Ú Q £ R が得られます。ゆえに

(A2-9b)  P Ú Q  =  P ñ Q

が成り立つことがわかります。以上で B₀ は束になっていることがわかりました。

　次に、( 仮 定 ) により ^ ® ^ は定理なので、( ^ 消去) により ^ ® P は定理であり、第３節メタ定理８、９ により P Þ Ø ^ は定理なので、これは P ® Ø ^ が定理であることを意味します。従って

(A2-10a)  ^ £ P

(A2-10b)  P £ Ø ^

が得られます。これは B₀ が最小値 ^ と最大値 Ø ^ を持つことを意味しています。

　次に、R , P ® R と R , P ® P から ( Ù 導入) により R , P ® R Ù P が得られるので、もし R Ù P ® Q が定理なら、( 切 断 ) により R , P ® Q は定理であり、従って ( Þ 導入) により R ® P Þ Q も定理です。
　逆に R ® P Þ Q が定理なら、( 増 ) により R , P ® P Þ Q は定理で、これと定理 R , P ® P から ( Þ 消去) により R , P ® Q は定理であり、これと R Ù P ® R 及び R Ù P ® P に ( 切 断 ) を用いて最後に ( 減 ) を用いれば R Ù P ® Q が得られます。
　以上により、R Ù P £ Q と R £ P Þ Q は同値であることがわかり、これは

(A2-11)  P Þ Q  =  P ð Q

が成り立つことを意味します。以上で B₀ がHeyting代数になっていることがわかりました。

　もし更に T  が古典論理に従うなら、排中律により

(A2-12)  (P Þ ^) Ú P  =  Ø ^

が成り立つので、これは (A2-1) が成り立つことを意味し、従って B₀ はBoole代数になっていることがわかります。

　以上により、B₀ はHeyting代数（Boole代数）になっていることがわかりました。しかもすべての論理式 S に対してS* を S そのものであると定義することにより、(A2-6a)~(A2-6f) （ただし古典論理の場合は更に加えて (A2-6i) ）が成り立っていることも確かめられました。そこで、更に (A2-6g),(A2-6h) が成り立っていることを確かめることにします。

　P(x) を T  の任意の命題とします。すべての TÎS₀ 、すなわちすべての項 T に対し、始式 P(T ) ® P(T ) から ( " 左) により "xP(x) ® P(T ) すなわち "xP(x) £ P(T ) が得られます。
　逆に T  の命題 R が、すべての TÎS₀ に対して R £ P(T ) を満たす、すなわち R ® P(T ) が定理になると仮定します。このとき特に R に現れない変数 z を取ると、R ® P(z) は定理になるので、( " 右) により R ® "xP(x) は定理になる、すなわち R £ "xP(x) が成り立つことがわかります。
　以上により

(A2-13a)  "xP(x) = inf{ P(T ) | TÎS0 }

が成り立つことがわかりました。
　同様に、T  の任意の命題 P(x) とすべての TÎS₀ に対し、始式 P(T ) ® P(T ) から ( $ 右) により P(T ) ® $xP(x) すなわち P(T ) £ $xP(x) が得られます。
　逆に T  の命題 R が、すべての TÎS₀ に対して P(T ) £ R を満たす、すなわち P(T ) ® R が定理になると仮定します。このとき特に R に現れない変数 z を取ると、P(z) ® R は定理になるので、( $ 左) により $xP(x) ® R は定理になる、すなわち $xP(x) £ R が成り立つことがわかります。
　以上により

(A2-13b)  $xP(x) = sup{ P(T ) | TÎS0 }

が成り立つことがわかりました。

　以上により、(A2-6g),(A2-6h) も成立していることがわかり、S₀ と B₀ の組は、T  のHeytingモデル（Booleモデル）になっていることがわかりました。
　しかも S₀ は明らかに可算集合であり、しかも 0 = 1 すなわち ^ = Ø ^ が成り立てば、Ø ^ ® ^ が定理となり、これは ® ^, ^ すなわち ^ が T  の定理、言い換えると T  が矛盾することを意味しますから、このモデルは T  と整合的です。そこで、このモデルを T  の完全モデルとよぶことにしましょう。
　完全モデルでは、P が真、すなわち P* = 1 なら、P Û Ø^ すなわち P は T  の定理であることがわかるので、以上をまとめれば、次のメタ定理が得られたことになります：

直観主義論理（古典論理）の完全性 　T  を直観主義論理（古典論理）の論理接続詞と量化記号とそれらの推論規則以外に論理接続詞、量化記号、推論規則を持たない直観主義論理（古典論理）に従う任意の理論とする。 　このとき真な閉命題はすべて T  で証明可能であるような T  の整合的なHeyting（Boole）可算モデルが存在する。従って特に、整合的なHeyting（Boole）可算モデルで恒真な閉命題はすべて証明可能である。

　この完全性定理を用いて、次のような充足可能性を示すことができます。
　A を、T  の命題からなる任意の集合とします。T  の推論規則に「A の元はすべて定理である」という推論規則を追加して得られる理論 T ' が T  に対して相対無矛盾（すなわち T ' が矛盾すれば T  も矛盾する）であるとき、A は T  で相対無矛盾であるといいます。
　また、理論 T  の閉命題からなる集合 A は、A の元をすべて真にする T  の整合的なモデルが存在するとき充足可能であるといいます。このとき次のメタ定理が成り立ちます：

充足可能定理 　T  を直観主義論理（古典論理）の論理接続詞と量化記号とそれらの推論規則以外に論理接続詞、量化記号、推論規則を持たない直観主義論理（古典論理）に従う任意の理論とする。 　このとき T の閉命題からなる集合 A が T  で相対無矛盾ならば、可算モデルの範囲内で充足可能である。逆に A が充足可能なら相対無矛盾である。

　実際、A が T  で相対無矛盾であると仮定し、理論 T ' の完全モデルを作ると、任意の AÎA は T ' の定理ですから、モデルの健全性により A はこのモデルで真ですが、更にこのモデルは T  の整合的なモデルにもなっています。
　このことを示すには、このモデルが T  のモデルになっていることは明らかですから、あとは T  と整合的であることを示せば十分です。そこで、このモデルで 0 = 1 と仮定すると、このモデルは T ' と整合的ですから、T ' は矛盾しますが、A は相対無矛盾、すなわち T ' は T  に対して相対無矛盾なので T  は矛盾します。

　逆に、A が充足可能、すなわち A の元がすべて真になるモデルが存在すると仮定し、更に上記の T ' が矛盾すると仮定します。
　このとき A₁ ,¼, A_nÎA が存在して A₁ ,¼, A_n ® が証明可能、従って (A₁ Ù A₂ Ù ¼ Ù A_n ) Þ ^ は T  の定理になります。
　ゆえにモデルの健全性により、(A₁ Ù A₂ Ù ¼ Ù A_n ) Þ ^ は真、従って A₁* òA₂* ò¼òA_n* £ 0です。ところが A の元はすべて真ですから、特に各 A_i も真、すなわち A_i* = 1です。従って 1 £ 0 すなわち 0 = 1 が得られ、このモデルが整合的であることから T  は矛盾し、A が相対無矛盾であることがわかりました。

　以上で充足可能定理は証明されました。

　さて、(A2-6) を眺めると、P と Q が 0 又は 1 という両極端の値を取るとき、(A2-6d)~(A2-6f) と (A2-6i) の左辺もやはり値 0 又は 1 を取ることがわかりますが、(A2-6g) と (A2-6h) については（ S が有限集合の場合か、あるいはメタ言語で排中律を仮定しない限り）必ずしもそのような性質は成り立ちません。
　そこで、論理記号と推論規則として Ù , Ú , Þ , Ø とそれらに関する古典論理の推論規則のみを持ち、量化記号や他の推論規則を持たない理論 P のことを命題論理とよんで、この理論 P の性質を調べてみることにしましょう。
　古典命題論理、すなわち古典論理の命題論理の場合は、Booleモデルとして一般のBooleモデルを許すのでなく、最大値 1 と最小値 0 のみからなる２値モデル B = { 0, 1 } のみを許すことにした場合でも上述の完全性定理と充足可能定理が成り立ちます。すなわち

古典命題論理の完全性 　古典論理に従う命題論理 P に対しては、２値モデルで恒真な閉命題はすべて証明可能である。

　まず証明に先立って、一般に公理 A を持つ理論 T  において、閉命題 R は、A ® R が直観主義論理で証明可能なら証明可能で、A , R ® が直観主義論理で証明可能なとき反証可能であることに注意します。
　このとき、閉命題 P と Q に対して次の結果が成り立ちます：

(A2-14a)  P と Q が共に証明可能なら P Ù Q は証明可能である。

(A2-14b)  P と Q の少なくとも一方が反証可能なら P Ù Q は反証可能である。

(A2-14c)  P と Q の少なくとも一方が証明可能なら P Ú Q は証明可能である。

(A2-14d)  P と Q が共に反証可能なら P Ú Q は反証可能である。

(A2-14e)  P が反証可能であるか、又は Q が証明可能なら P Þ Q は証明可能である。

(A2-14f)  P が証明可能で Q が反証可能なら P Þ Q は反証可能である。

(A2-14g)  P が反証可能なら Ø P は証明可能である。

(A2-14h)  P が証明可能なら Ø P は反証可能である。

　実際、(A2-14a) は、A ® P と A ® Q から (Ù 右) により A ® P Ù Q が得られるので明らかです。
　また (A2-14b) は、A , P ® からも A , Q ® からも (Ù 左) により A , P Ù Q ® が得られるので明らかです。
　また (A2-14c) は、A ® P からも A ® Q からも (Ú 右) により A ® P Ú Q が得られるので明らかです。
　また (A2-14d) は、A , P ® と A , Q ® から (Ú 左) により A , P Ú Q ® が得られるので明らかです。
　また (A2-14e) は、A , P ® からは ( 増 右 ) により、A ® Q からは ( 増 左 ) により、いずれも A , P ® Q が得られるので、これに更に (Þ 右) を適用すれば A ® P Þ Q が得られるので明らかです。
　また (A2-14f) は、A ® P と A , Q ® に (Þ 左) を適用すると A , A , P Þ Q ® が得られ、更に ( 減 左 ) により A , P Þ Q ® が得られるので明らかです。
　また (A2-14g) は、A , P ® から (Ø 右) により A ® Ø P が得られるので明らかです。
　また (A2-14h) は、A ® P から (Ø 左) により A , Ø P ® が得られるので明らかです。

　そこで、証明又は反証が可能な命題のことを決定可能な命題とよぶことにすれば、(A2-14) は

(A2-15)  P と Q が決定可能なら P Ù Q , P Ú Q , P Þ Q , Ø P はすべて決定可能である。

ということを意味していることがわかります。

　さて、メタ定理の証明に戻ります。R を２値モデルで恒真な閉命題とし、その要素となっている、相異なる原子閉命題の全体を P₁ ,¼, P_n とします。
　P に、各 i に対して P_i か Ø P_i の一方を公理に追加し、どの P_i とも異なる原子閉命題はすべて定理であるという推論規則を追加した理論を R-モデルとよぶことにしましょう。
　任意の閉命題は原子閉命題から順に論理接続詞を結合することにより得られますから、(A2-14) を繰り返し適用することにより、R-モデルではすべての閉命題が決定可能になることがわかります。これは、２つの命題が同値であるという関係を = で表すとき、すべての閉命題 P は P = ^ 又は P = Ø ^ を満たすということを意味するので、R-モデルは２値モデルになっていることがわかります。

　さて、２値モデルで恒真な閉命題 R は、定義により任意の R-モデルで証明可能です。これは、P₁ ,¼, P_n の任意の分割 A , B に対し、どの P_i とも異なる原子閉命題の列 C が存在して C , A , Ø B ® R というsequentが P で証明可能であることを意味しています。ただし Ø B は B の各命題に Ø を施して得られる命題列を表します。これは C , A ® R , B が P で証明可能ということとも同値ですが、Gentzenの基本定理により、このsequentは (LK) で ( 切 断 ) を使わずに証明できます。
　ところが C に現れる各原子命題は、A にも B にも R の構成要素にも現れないので、このsequentの ( 切 断 ) を含まない証明図には C の要素から成る始式は現れません。すなわち C の各要素は、この証明図において、すべて ( 増 ) により追加されていることがわかります。しかもこれらの要素は R の構成要素に用いられていないので、C をすべて落としたsequent A ® R , B が P で証明可能であることがわかります。
　ここで、A と B を、P₁ ,¼, P_n から重複なしに選んだ命題の列とし、両者の要素の個数の合計が k £ n であるとします。このとき A ® R , B が P で証明可能であることを、k について降順に確かめていきましょう。
　まず k = n の場合は今示したことにより明らかです。次に、ある k £ n で成り立つとし、A と B の要素の個数が k - 1 であるとします。
　このとき A にも B にも現れない P_i が少なくとも一つ存在しますが、仮定により A , P_i ® R , B と A ® R , P_i , B は P で証明可能です。
　ゆえに、これらに対して推論規則 ( 切 断 ) と ( 減 ) と ( 換 ) を何度か適用することにより、A ® R , B が P で証明可能であることがわかります。
　以上で主張は証明されたので、特に k = 0 の場合を考えれば、® R が、すなわち R が P で証明可能であることがわかります。以上で古典命題論理の完全性は証明されました。

　この古典命題論理の完全性を用いて一個の閉命題 R からなる集合の充足可能性を証明しましょう。

古典命題論理の充足可能定理 　古典命題論理 P の閉命題 R について、無矛盾であることと２値モデルで充足可能であることは同値である。

　実際、充足可能なら無矛盾であることは、既に証明した一般論により明らかなので、あとは { R } が相対無矛盾であると仮定して充足可能であることを示せば十分です。
　R の要素となっている、相異なる原子閉命題の全体を P₁ ,¼, P_n とします。
　既に示したように、P₁ ,¼, P_n のすべての分割 A , B に対して A , Ø B ® Ø R が P で証明可能なら、Ø R は P で証明可能であり、従って P は P を公理に付け加えると矛盾するので、R の相対無矛盾性により P は矛盾し、従って任意のsequentは P で証明可能です。
　ところで (A2-14) を繰り返し用いることにより、A , Ø B ® R か A , Ø B ® Ø R の少なくとも一方は証明可能ですから、今示したことから、ある分割 A , B に対して前者が証明可能であることがわかります。
　そこで、A 及び Ø B に現れるすべての命題と、P₁ ,¼, P_n 以外のすべての原子閉命題が定理であると定めた理論を M と書くと、再び (A2-14) により、M ではすべての閉命題が決定可能になります。
　しかも M が矛盾するとすれば、P₁ ,¼, P_n のいずれとも異なる原子閉命題から成る C が存在して C , A , Ø B ® が P で証明可能になり、これは C , A ® B が P で証明可能であることを意味しますが、Gentzenの基本定理により、これは ( 切 断 ) を使わずに証明できるはずですが、A , B , C はすべて相異なる原子閉命題からなるので、そのようなことはあり得ません。すなわち M は P と整合的な２値モデルであることがわかりました。
　しかも R は M で証明可能ですから、以上で古典命題論理の充足可能定理は証明されました。

　さて、上で構成した M のように、原子命題すべてに対してそれ自身又はその否定命題を公理にして得られる理論は２値モデルになり、証明可能な命題が真な命題に、反証可能な命題が偽な命題に完全に対応しています。そこで、(A2-14) の「証明可能」を「真」（記号で T ）に書き換え、「反証可能」を「偽」（記号で F ）と書き換えれば、次のような一覧表：

P Ù Q ＼ Q   P＼ T F T T F F F F

P Ú Q ＼ Q   P＼ T F T T T F T F

P Þ Q ＼ Q   P＼ T F T T F F T T

Ø P P T F F T

が得られます。これがいわゆる命題論理の真偽表とよばれているものです。
　歴史的に見れば、意味論（semantics）とよばれている議論で、まず真偽表を天下り的に導入して命題の真偽値を定め、次に構文論（syntax）として、このように定めた真偽値のもとで恒真な命題の全体が証明可能な命題の全体になるように推論規則を定めてきたわけですが、それだと真偽値の定め方の必然性がよくわからない（例えば P Þ Q に対する真偽表で P が偽の場合）ことに加え、推論規則そのものも、構文論それ自体として形式上の必然性がよくわからない（特に付録４で解説したHilbertの定式化の場合）という欠点があります。
　ところが、本稿付録２で解説したように、まず構文論によって、命題がどのように証明されているかを意味するメタ的な概念を「形式化」することによって論理接続詞とその推論規則を定め、そのような推論体系のうちで決定可能である場合において「証明可能」を「真」に、「反証可能」を「偽」と呼びかえることによって真偽表を作成する、という手順（すなわち意味論という概念を陽に用いない方法）を採用すれば、一連の概念の定義を必然の流れとして理解できることになります。

　さて、以上の結果は、量化記号 " , $ を持つ場合でも、以下に述べる意味で対象の個数が有限個しかない場合には成り立ちます。
　理論 T  は定項以外の関数記号を持たないとし、定項の全体を c₁ ,¼, c_n とします。このとき T の対象が有限個であるとは、次の推論規則：

	( 有 限 )
	R(c1 ) R(c2 ) ¼ R(cn ) ———— R(T )

が成り立つことをいいます。T  の対象が有限個なら、

(A2-16a)  "xR(x)  Û  ( R(c1 ) Ù R(c2 ) Ù ¼ Ù R(cn ) )

(A2-16b)  $xR(x)  Û  ( R(c1 ) Ú R(c2 ) Ú ¼ Ú R(cn ) )

が成り立ちます。
　実際、(A2-16a) の左辺から右辺は ( " 消去) と ( Ù 導入) により明らかです。
　逆に (A2-16a) の右辺から左辺は、( Ù 消去) と ( 有 限 ) を T が自由変数 x の場合に適用すれば R(x) が得られるので、( " 導入) により左辺が得られます。
　また (A2-16b) の右辺から左辺は、( $ 導入) と ( Ú 消去) により明らかです。
　逆に (A2-16b) の左辺から右辺を導くために、$xR(x) と仮定し、更に ( $ 消去) を用いるため、自由変数 z を選んで R(z) と仮定します。ここで命題 R(x) Þ ( R(c₁ ) Ú R(c₂ ) Ú ¼ Ú R(c_n ) ) を P(x) と書くと、明らかに P(c₁ ) , P(c₂ ) ,¼, P(c_n ) が成り立ちます。ゆえに推論規則 ( 有 限 ) を命題 P と項 z に対して適用すれば、P(z) が成り立ちますから、これと R(z) から ( Þ 消去) により (A2-16b) の右辺が得られます。

　以上で (A2-16) は証明されましたが、この (A2-16) により量化記号を含む命題は含まない命題と同値であることがわかるので、

(A2-17)  T  が対象を有限個しか持たず、すべての定項 c に対して R(c) が決定可能なら、"xR(x) も $xR(x) も決定可能である。

ということがわかります。この結果、対象が有限個しかなく、他に推論規則を持たない理論についても２値モデルに対する完全性と充足性が成り立つことがわかります。

　それでは、必ずしも“対象が有限個でない”一般の場合はどうなるでしょうか。
　そのような一般の場合でも２値モデルに対する完全性と充足性が成り立つことを主張するのがGödelの完全性定理です。
　ところがこのメタ定理は、他の超数学のメタ定理（Gentzenの基本定理、自然数論の無矛盾性、Gödel-Rosserの不完全性定理等）の場合と違って、その証明を遂行するメタ言語に排中律を使用しなければなりません。
　その様子をHenkinによる方法に従って解説していきましょう。

　最初に、理論 T  に現れない文字 0 にゼロ個以上 ' を付けたもの 0"^¼' のことを数字とよぶことにし、T  本来の項に加えて「数字は項である」と定めた理論を M₀ と書くことにします。なお、数字 0 , 0' , 0" ,¼ のことを順に 0 , 1 , 2 ,¼ と略記することにし、数字 n の ' を１個追加して得られる数字を n' と書くことにします。また２つの数字 n , m において、後者の方が ' の個数が多いとき n < m 又は m > n と書き、そうでないとき m £ n 又は n ³ m と書くことにします。

　次に、変数を高々１個しか含まない M₀ の命題の全体を（例えば付録６で解説したようなコード化を行ってその小さい順に並べるといった方法で）一列に並べたものを R_i(x_i ) ( i = 0, 1, 2 ,¼ ) とし、j £ i に対する R_j(x_j ) に現れるすべての数字と j < i に対するすべての n_j のいずれとも異なる最小の数字を n_i と書いて、理論 M_i ( i = 1, 2 ,¼ ) を次のようにして順次定義していきます。
　M_i が既に定義されているとして、この理論に「命題 $x_iR(x_i ) Þ R(n_i ) は定理である」という推論規則を追加した理論を M_i' とし、M₀ に「数字 i に対する $x_iR(x_i ) Þ R(n_i ) はすべて定理である」という推論規則を追加した理論を M と書くことにします。
　このとき、M は T  に対して相対無矛盾です。

　実際、M が矛盾すれば、その矛盾を導いた証明には有限個の i に対する $x_iR(x_i ) Þ R(n_i ) しか現れませんから、これは、ある i に対する M_i における証明になるので、M_i が矛盾することがわかります。
　そこで、一般に M_j' が M_j に対して相対無矛盾であることを証明しましょう。これができれば、まず M の M₀ 対する相対無矛盾性がわかります。

　実際、M_j' が矛盾したとします。理論 M_j' は理論 M_j に公理 $x_iR(x_i ) Þ R(n_i ) を付け加えた理論ですから、これが矛盾するということは、推論規則 (Ø 導入) により、M_j において $x_iR(x_i ) Þ R(n_i ) の否定命題、すなわち $x_iR(x_i ) Ù Ø R(n_i ) が定理であることを意味します。
　ところで定義により、n_i は j < i に対する $x_jR(x_j ) Þ R(n_j ) すなわち M_j の公理の中には出てこないので、M_j における $x_iR(x_i ) Ù Ø R(n_i ) の証明文において、数字 n_i を、一斉に、この証明文に現れない自由変数 z に置き換えたものもやはり M_j における証明文になっています。
　すなわち M_j において $x_iR(x_i ) Ù Ø R(z) は定理です。ゆえに (Ù 消去) と (" 導入) により $x_iR(x_i ) と "z( Ø R(z) ) は定理であることがわかりますが、この前者は $zR(z) とも書け、後者は第３節のメタ定理37 (a) により Ø $zR(z) と同値ですから、これは理論 M_j が矛盾することを意味します。
　以上で M_j' が M_j に対して相対無矛盾であることがわかりました。

　また、M₀ は T  に対して相対無矛盾です。
　実際、M₀ が矛盾すれば、その矛盾を導く証明文において、すべての数字をすべてその証明文に現れない相異なる変数に置き換えていけば、これは T  における証明文になります。すなわち T  も矛盾することがわかり、M₀ が T  に対して相対無矛盾であることが証明されました。
　以上で M は T  に対して相対無矛盾であることがわかりました。

　次に、M の閉命題のすべてを一列に並べて A_i ( i = 0, 1 , 2 ,¼ ) とし、M を N₀ と書き、順に A_i が N_i で証明可能なら A_i を、そうでなければ Ø A_i を公理に追加した理論を N_i' と書きます（このようなプロセスが可能であると主張するところでメタ言語に排中律を使っています）。
　次に、これらのプロセスのどこかで追加した公理をすべて M の公理に追加した理論を N と書けば、定義の仕方から明らかなように、N ではすべての閉命題が証明可能又は反証可能ですが、更に N は M に対して（従って T  に対して）相対無矛盾です。

　実際、まず N_i' は N_i で相対無矛盾であることを証明します。
　そのために、N_i' が矛盾したと仮定します。
　もし A_i が N_i で証明可能なら、N_i' の定理はすべて N_i の定理ですから N_i も矛盾します。
　また A_i が N_i で証明不可能なら、N_i' は N_i の公理に Ø A_i を追加した理論ですから、これが矛盾したということは、(帰謬法) により A_i が N_i で証明可能であることを意味し、仮定に反します。
　ゆえにメタ言語における排中律により、N_i は矛盾することがわかり、相対無矛盾性が証明されました。これで、任意の N_i が M に対して、従って T  に対して相対無矛盾であることがわかりました。
　一方、N が矛盾すれば、これはある N_i が矛盾することを意味するので、これで N が T  に対して相対無矛盾であることがわかりました。

　さて、最後に N  の閉項の全体を S とし、B を N に命題の同値性による同値関係 = を与えた集合と定義すれば、これは集合 {0, 1} と（集合の圏で）同型になり、(A2-6a)~(A2-6f) と、古典論理の場合は更に (A2-6i) が明らかに成り立ちます。あとは (A2-6g) と (A2-6h) を示せば十分です。

　まず、命題 P(x) を任意に取ります。このとき、定義により数字 i が存在して、P(x) は R_i(x) であり、x は x_i です。ゆえに $xP(x) Þ P(n_i ) は M_i' の、従って M の、従って N の定理です。これは $xP(x) ® P(n_i ) が N の定理であるということと同じことですから $xP(x) £ P(n_i ) が成り立つことを意味します。
　逆に、任意の閉項 T に対して P(T ) ® $xP(x) は N の定理ですから P(T ) £ $xP(x) が成り立ちます。よって

(A2-18a)  $xP(x) = max{ P(T ) | TÎS }

が成り立つことがわかりました。
　また、数字 j が存在して Ø P(x) は R_j(x) で、x は x_j ですから、$x(Ø P(x)) Þ Ø P(n_j ) は M_i' の、従って M の、従って N の定理です。
　ゆえにこの対偶の P(n_j ) Þ "xP(x) も N の定理ですが、これは P(n_j ) ® "xP(x) が N の定理であることを意味し、従って P(n_j ) £ "xP(x) が成り立ちます。
　逆に、任意の閉項 T に対して "xP(x) ® P(T ) は N の定理ですから "xP(x) £ P(T ) が成り立ちます。以上により

(A2-18b)  "xP(x) = min{ P(T ) | TÎS }

が成り立つことがわかりました。
　この (A2-18) により、(A2-6g) と (A2-6h) が成り立つことがわかります。
　以上がGödelによって初めて証明され、Henkinによって簡略化された「古典論理に対する整合的な２値モデルの存在定理」の証明です。

　以上の結果がひとたび得られれば、Gödelの完全性定理とよばれているメタ定理：「古典論理の論理接続詞と量化記号とそれらの推論規則以外に論理接続詞、量化記号、推論規則を持たない古典論理に従う任意の理論では、２値モデルで恒真な閉命題はすべて証明可能」は簡単に得られます。
　実際、T  をそのような理論、P を２値モデルで恒真な閉命題とし、T  に Ø P を公理に付け加えた理論を T ' と書きます。
　ここで「古典論理に対する整合的な２値モデルの存在定理」により、T ' と整合的な２値モデルが存在しますが、このモデルでは、Ø P が T ' の定理なので、モデルの健全性により Ø P は真、すなわち P は偽です。
　ところが P は２値モデルで恒真なので、このモデルでも当然真です。すなわち P はこのモデルで同時に真かつ偽となり、これは 0 = 1 を意味しますから、モデルの整合性により、理論 T ' は矛盾します。
　すなわち、理論 T  は Ø P を公理に追加したら矛盾したのですから、古典論理の推論規則 (帰謬法) により、P は T  で証明可能であることがわかります。

　さて、本節の最後に紹介した「古典論理に対する整合的な２値モデルの存在定理」とその系である「Gödelの完全性定理」は、メタ言語での推論に排中律を使う必要があるだけでなく、その証明もかなり“人工的”です。
　しかも、古典論理の代数的な特徴付けはBoole代数であるというところにあるにもかかわらず、その特別な例に過ぎない２値モデルにこだわるべき論理的必然性も特にあるようには思われません。

　歴史的には、「真か偽かが定まっているものを命題という」というのが“命題”という概念の素朴な“定義”でした。そして、論理記号についても、構文論によってではなく、真偽表によってその真偽値を定義し、その後で「恒真な命題の全体が証明可能な命題の全体に一致する」ように構文論的な概念である推論規則が定められていきました。しかも構文論についても、最初からGentzenの推論体系が“発見”されていたわけではなく、付録４で解説したような、純形式上の“根拠”もはっきりしないHilbertの推論体系のような形でしか与えられていなかったのです。
　このようないきさつを考えると、「Hilbertの体系で証明可能な命題の全体は恒真な命題の全体に一致する」ことを主張する「Gödelの完全性定理」が、Hilbertの推論体系の「妥当性」を保証する重要なメタ定理だと思われてきたのは、ある程度止むをえないことであったと思われます。
　しかしながら、その後Gentzenによる推論体系が登場すると、論理式の真の“意味”は、むしろ構文論の方で定められているという見方の方が自然であり（本稿付録２参照）、これを敢えて「意味論」によって「正当化」する意義は失われたと言えるでしょう。

　また、「真か偽かが定まっているものを命題という」という“命題”の素朴な“定義”は、モデルの言葉を用いると「２値モデル」を考えるということに他ならないわけですが、このことは、「推論規則や公理系をうまく定めれば、閉命題はすべて決定可能になるだろう」という期待に繋がります。
　ところが、この期待は「Gödelの不完全性定理」によって見事に打ち砕かれてしまいました。Gödelの不完全性定理によれば、たとえ古典論理で考えた場合でも、自然数論より強い理論であれば、本節で構成した完全モデル B₀ において、閉命題の値が 0 と 1 の間に無限個の値を取ることが明らかになってしまったのです。
　この事実は、「２値モデル」にこだわる、言い換えると「命題は真又は偽のいずれかの値を取る」と“信じる”ことが、少なくとも構文論的には何ら根拠を持たないことを意味しており、これは「２値モデル」に特別の意味を与える「Gödelの完全性定理」の「論理学の基礎付け」としての意義が実質的に失われたことを意味します。むしろこのメタ定理は、超準解析の数学的根拠付けに用いられるなど、数学内部における定理としての重要性の方が注目すべきであると思われます。