コンパクト性定理

数理論理学において、コンパクト性定理は、一階述語文の集合がモデルを持つためには、その一階述語文の有限部分集合のすべてにモデルが必要であることを述べています。この定理は、有限に矛盾しない文の集合のモデルを構築するための便利な（ただし、一般的には効果的ではない）方法を提供するため、モデル理論において重要なツールです。

命題計算のコンパクト性定理は、コンパクト空間の積はコンパクトであるというティコノフの定理をコンパクトストーン空間に適用した結果であり、^[1]定理の名前の由来となっている。同様に、コンパクト性は位相空間におけるコンパクト性の有限交差特性の特徴付けに類似している。つまり、コンパクト空間内の閉集合のコレクションは、すべての有限部分コレクションが空でない交差を持つ場合、空でない交差を持つ。

コンパクト性定理は、下向きレーヴェンハイム・スコーレム定理とともに、リンドストロームの定理で一階述語論理を特徴付けるために使用される2つの重要な性質の1つです。コンパクト性定理の非一階述語論理への一般化はいくつかありますが、非常に限られた例を除いて、コンパクト性定理自体はそれらの論理では成り立ちません。^[2]

クルト・ゲーデルは1930年に可算コンパクト性定理を証明した。 アナトリー・マルツェフは1936年に非可算ケースを証明した。^{[3] [4]}

コンパクト性定理はモデル理論において多くの応用があり、ここではいくつかの典型的な結果を示します。

コンパクト性定理は、アブラハム・ロビンソンが1949 年の論文で述べた次の結果を意味します。

ロビンソンの原理：^{[5] [6]} 1 階の文が特性0のすべての体で成り立つ場合、より大きい特性 のすべての体に対して文が成り立つような定数が存在するこれは、次のように見ることができます。 が特性 0 のすべての体で成り立つ文であるとします。 このとき、体公理および文の無限列とともに その否定は充足可能で はありません( が成り立つ特性 0 の体はなく、文の無限列により、どのモデルも特性 0 の体になることが保証されるため)。 したがって、充足不可能なこれらの文の有限部分集合が存在します。はを含んでいなければなりません。そうでなければ充足可能になってしまうからです。 に文を追加しても充足不可能性は変わらないため、 には体公理が含まれ、いくつかの について、形式の最初の文が を除くのすべての文を含むと仮定できます。より大きい特性を持つ体はすべてのモデルであり、とともに充足可能ではありません。これは、 のあらゆるモデルにおいて が成り立つ必要があることを意味し、それはまさにより大きい特性のあらゆるフィールドにおいて が成り立つことを意味します。これで証明は完了です。 ${\displaystyle p}$${\displaystyle p.}$${\displaystyle \varphi}$${\displaystyle \lnot \varphi ,}$$${\displaystyle 1+1\neq 0,\;\;1+1+1\neq 0,\;\ldots }$$${\displaystyle \lnot \varphi }$${\displaystyle A}$${\displaystyle A}$${\displaystyle \lnot \varphi }$${\displaystyle A}$${\displaystyle A}$${\displaystyle k,}$${\displaystyle k}$${\displaystyle 1+1+\cdots +1\neq 0.}$${\displaystyle B}$${\displaystyle A}$${\displaystyle \lnot \varphi .}$${\displaystyle k}$${\displaystyle B,}$${\displaystyle \lnot \varphi }$${\displaystyle B}$${\displaystyle \varphi}$${\displaystyle B,}$${\displaystyle \varphi}$${\displaystyle k.}$

転移原理の最初の例の 1 つであるレフシェッツ原理 は、この結果を拡張します。環の言語による第 1 階の文が、特性 0 の代数的閉体(たとえば複素数など)で真となるのは、 の素数が無限個存在し、 が特性 の代数的閉体で真である場合に限ります。この場合、 は十分に大きい非 0 特性のすべての代数的閉体で真となります^{[5] 1 つの結果として、} Ax–Grothendieck の定理 の次の特別な場合が挙げられます。すべての単射複素多項式は全射です^[5] (実際、その逆も多項式になることが示されます)。^[7]実際、が有限体またはそのような体の代数的閉包である任意の単射多項式に対して、全射性の結論が成り立ちます。 ^[7]${\displaystyle \varphi}$${\displaystyle p}$${\displaystyle \varphi}$${\displaystyle p,}$${\displaystyle \varphi}$${\displaystyle p.}$ ${\displaystyle \mathbb {C} ^{n}\to \mathbb {C} ^{n}}$${\displaystyle F^{n}\to F^{n}}$${\displaystyle F}$

コンパクト性定理の 2 つ目の応用は、任意に大きな有限モデル、または単一の無限モデルを持つ理論は、任意に大きな濃度のモデルを持つことを示しています(これは上向きのレーヴェンハイム-スコーレム定理)。したがって、たとえば、無数に多くの「自然数」を持つペアノ算術の非標準モデルが存在します。これを実現するには、を初期理論とし、 を任意の濃度とします。のすべての要素に対して 1 つの定数記号の言語に を追加します。次に、新しいコレクションからの任意の 2 つの異なる定数記号によって表されるオブジェクトが異なることを述べる文のコレクションに を追加します (これは文のコレクションです)。この新しい理論のすべての有限部分集合は、 の十分に大きな有限モデルまたは任意の無限モデルによって充足可能であるため、拡張された理論全体が充足可能です。ただし、拡張された理論のどのモデルも、濃度が少なくとも です。 ${\displaystyle T}$${\displaystyle \kappa}$${\displaystyle T}$${\displaystyle \kappa .}$${\displaystyle T}$${\displaystyle \kappa^{2}}$${\displaystyle T,}$${\displaystyle \kappa}$

コンパクト性定理の 3 番目の応用は、実数の非標準モデルの構築、つまり「無限小」数を含む実数理論の一貫した拡張です。これを確認するには、を実数理論の 1 階の公理化とします。言語に新しい定数記号を追加し、公理とすべての正の整数の公理に付加することによって得られる理論を考えます。 明らかに、標準の実数はこれらの公理のすべての有限部分集合のモデルです。なぜなら、実数は のすべてを満たし、 を適切に選択することで、に関する公理の任意の有限部分集合を満たすようにすることができるから です。コンパクト性定理により、を満たし、また無限小要素を含むモデルが存在します。${\displaystyle \Sigma }$${\displaystyle \epsilon }$${\displaystyle \Sigma }$${\displaystyle \epsilon >0}$${\displaystyle \varepsilon <{\tfrac {1}{n}}}$${\displaystyle n.}$${\displaystyle \mathbb {R} }$${\displaystyle \Sigma }$${\displaystyle \epsilon ,}$${\displaystyle \epsilon .}$${\displaystyle {}^{*}\mathbb {R} }$${\displaystyle \Sigma }$${\displaystyle \epsilon .}$

同様の議論は、今度は公理などを付け加えたもので、無限に大きな大きさの数の存在は実数のいかなる公理化によっても排除できないことを示しています。 ^[8]${\displaystyle \omega >0,\;\omega >1,\ldots ,}$${\displaystyle \Sigma }$

超実数は 転移原理を満たすことが示せる：^[9]第一階の文が真であるのは、それが真であるときのみである。${\displaystyle {}^{*}\mathbb {R} }$${\displaystyle \mathbb {R} }$${\displaystyle {}^{*}\mathbb {R} .}$

コンパクト性定理はゲーデルの完全性定理を使って証明できる。ゲーデルの完全性定理は、文の集合が充足可能であるのは、その文から矛盾が証明されない場合のみであることを立証する。証明は常に有限であり、したがって有限個の与えられた文のみを含むため、コンパクト性定理が成り立つ。実際、コンパクト性定理はゲーデルの完全性定理と同等であり、どちらも選択公理の弱い形であるブール素イデアル定理と同等である。^[10]

ゲーデルはもともとこの方法でコンパクト性定理を証明しましたが、後にコンパクト性定理の「純粋に意味論的な」証明がいくつか見つかりました。つまり、証明可能性ではなく真理性に言及する証明です。それらの証明の 1 つは、次のように選択公理に依存する超積に依存しています。

証明: 一階言語を固定し、 が-文 のコレクションで、その-文のすべての有限部分コレクションがモデルを持つものとします。 また、が構造の直積であり、の有限部分集合のコレクションであるとします。それぞれに対して、 これらすべての集合の族は適切なフィルタを生成するため、形式 のすべての集合を含む超フィルタが存在することになります。${\displaystyle L,}$${\displaystyle \Sigma }$${\displaystyle L}$${\displaystyle L}$${\displaystyle i\subseteq \Sigma }$${\displaystyle {\mathcal {M}}_{i}.}$${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}}$${\displaystyle I}$${\displaystyle \Sigma .}$${\displaystyle i\in I,}$${\displaystyle A_{i}=\{j\in I:j\supseteq i\}.}$${\displaystyle A_{i}}$ ${\displaystyle U}$${\displaystyle A_{i}.}$

さて、${\displaystyle \varphi}$${\displaystyle \Sigma :}$

• セットは${\displaystyle A_{\{\varphi \}}}$${\displaystyle U}$
• いつでも、そして、したがって、保持する${\displaystyle j\in A_{\{\varphi \}},}$${\displaystyle \varphi \in j,}$${\displaystyle \varphi}$${\displaystyle {\mathcal {M}}_{j}}$
• が成り立つ 性質を持つすべての集合はのスーパーセットなので、 も となる。${\displaystyle j}$${\displaystyle \varphi}$${\displaystyle {\mathcal {M}}_{j}}$${\displaystyle A_{\{\varphi \}},}$${\displaystyle U}$

Łośの定理は、超積において成立することを示唆しており 、この超積は、${\displaystyle \varphi}$ ${\textstyle \prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U.}$${\displaystyle \Sigma .}$

• 棒状コンパクト性定理
• エルブランの定理 – 第一階の数学的論理から命題論理への還元フォールバックとしてウィキデータの説明を表示するページ
• ブール代数のトピックのリスト
• レーヴェンハイム・スコーレム定理 – 論理理論のモデルの存在と濃度

• ブーロス、ジョージ、ジェフリー、リチャード、バージェス、ジョン（2004）。計算可能性と論理（第4版）。ケンブリッジ大学出版局。
• Chang, CC; Keisler, H. Jerome (1989).モデル理論(第 3 版). Elsevier. ISBN 0-7204-0692-7。
• ドーソン、ジョン W. ジュニア( 1993)。「一階述語論理の簡潔性: ゲーデルからリンドストロームまで」。論理の歴史と哲学。14 : 15–37。doi :10.1080/01445349308837208。
• ホッジス、ウィルフリッド（1993）。モデル理論。ケンブリッジ大学出版局。ISBN 0-521-30442-3。
• ゴールドブラット、ロバート(1998)。『超実在論の講義』ニューヨーク: シュプリンガー出版。ISBN 0-387-98464-X。
• ガワーズ、ティモシー、バローグリーン、ジューン、リーダー、イムレ（2008年）。プリンストン数学コンパニオン。プリンストン：プリンストン大学出版局。pp. 635–646。ISBN 978-1-4008-3039-8. OCLC  659590835.
• マーカー、デイビッド（2002）。モデル理論：入門。数学大学院テキスト。第217巻。シュプリンガー。ISBN 978-0-387-98760-6. OCLC  49326991.
• Robinson, JA (1965). 「解決原理に基づくマシン指向ロジック」. Journal of the ACM . 12 (1). Association for Computing Machinery (ACM): 23–41. doi : 10.1145/321250.321253 . ISSN  0004-5411. S2CID  14389185.
• トラス、ジョン・K. (1997)。数学的解析の基礎。オックスフォード大学出版局。ISBN 0-19-853375-6。

• コンパクト性定理、インターネット哲学百科事典。