紧致性せい定理ていり

紧致性せい定理ていり是これ符号ふごう逻辑和わ模型もけい论中なか的てき基本きほん事ごと实，它断言だんげん一いち阶句く子こ的てき（可能かのう无限的まと）集合しゅうごう是ぜ可か满足的てき（就是说有一いち个模型もけい），当とう且仅当とう它的所有しょゆう有限ゆうげん子こ集しゅう是ぜ可か满足的てき。

命いのち题演算えんざん的てき紧致性せい定理ていり是ぜ吉よし洪ひろし诺夫定理ていり（它声称しょう紧致空そら间的てき积是紧致的てき）应用于紧致Stone空そら间的てき结果。

应用

从这个定理ていり可か以得出で，如果某ぼう个一阶句子对于特とく征せい值为零的てき所有しょゆう域いき都と成立せいりつ，则存在そんざい着ぎ一いち个常量りょうp，使つかい得とく这个句く子こ对特征せい值大于p的てき所有しょゆう域いき都と成立せいりつ。这可以被看み作さく为如下か：假定かていS是ぜ要よう考こう虑的句く子こ。那な么它的てき否定ひてい~S，和かず域いき公理こうり与あずか句く子こ的てき无限序列じょれつ1+1 ≠ 0, 1+1+1 ≠ 0, ...一起かずき，不能ふのう被ひ假定かてい所しょ满足。所以ゆえん这些句く子こ的てき有限ゆうげん子こ集しゅう是ぜ不可ふか满足的てき，意味いみ着ぎS在ざい有ゆう足あし够大特とく征せい值的这些域いき中ちゅう成立せいりつ。

从这个定理ていり还得出で，有ゆう一个无限模型的任何理论都有任意大基数きすう的てき模型もけい。所以ゆえん，有ゆう着ぎ带有不可ふか数多あまた个自然しぜん数すう的てき皮かわ亚诺算さん术有ゆう非ひ标准模型もけい。非ひ标准分析ぶんせき是ぜ出で现无限げん个自然しぜん数すう的てき另一个例子こ，是ぜ不能ふのう被ひ任にん何なに公理こうり化か所ところ排除はいじょ的てき可能かのう事物じぶつ，也是紧致性せい定理ていり的てき一いち个推论。

证明

紧致性せい定理ていり可か以使用しよう哥德尔完备性定理ていり来らい证明，它确立りつ了りょう一组句子是可满足的，当とう且仅当とう没ぼつ有ゆう矛盾むじゅん可か以证明あきら自じ它们。事こと实上，紧致性せい定理ていり等とう价于哥得尔完备性定理ていり，并且二に者しゃ都と等とう价于超ちょう滤子引理，它是弱じゃく形式けいしき的てき选择公理こうり。因よし为证明あかり总是有限ゆうげん的てき，所以ゆえん只ただ涉わたる及有限げん多た个给定じょう句く子こ，就得出で了りょう紧致性せい定理ていり。

哥德尔最初はつ就是以这种方式しき证明紧致性せい定理ていり的てき，但ただし是ぜ后きさき来らい又また找到了りょう紧致性せい定理ていり的てき一いち些“纯语义”证明，就是说提及“真理しんり”但ただし不ふ提ひさげ及“可か证明性せい”的てき证明。这些证明倚赖于依仗选择公理こうり的てき超ちょう乘じょう积：

证明：固定こてい一个一阶语言L，并设Σしぐま为L-句く子こ的てき搜さがせ集しゅう，使つかい得とく所有しょゆうL-句く子こ的てき子こ搜さがせ集しゅうi ⊆ Σしぐま都みやこ有ゆう模型もけい${\mathcal {M}}_{i}$。还设$\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}$是ぜ这些结构的てき直接ちょくせつ乘じょう积，和わI是ぜΣしぐま的てき有限ゆうげん子こ集しゅう的てき搜さがせ集しゅう。对于I中ちゅう每まい个i设A_i := { j ∈ I : j ⊇ i}。所有しょゆう这些集合しゅうごうA_i的てき家族かぞく形成けいせい一いち个滤子こ（filter），所以ゆえん有ゆう一いち个超滤子（ultrafilter）U包含ほうがん形がた如A_i的てき所有しょゆう集合しゅうごう。

现在对于Σしぐま中ちゅう任にん何なん公式こうしきφふぁい我わが们有：

• 集合しゅうごうA_{{φふぁい}}在ざいU中なか
• 只ただ要ようj ∈ A_{{φふぁい}}，则φふぁい ∈ j，因いん此φふぁい在ざい${\mathcal {M}}_{j}$中ちゅう成立せいりつ
• 带有φふぁい在ざい${\mathcal {M}}_{j}$中ちゅう成立せいりつ的てき性せい质的所有しょゆうj的てき集合しゅうごう是ぜA_{{φふぁい}}的てき超ちょう集しゅう，因いん此也在ざいU中なか

使用しようŁoś定理ていり我わが们看到いたφふぁい在ざい超ちょう乘じょう积$\prod _{i\subseteq \Sigma }{\mathcal {M}}_{i}/U$中ちゅう成立せいりつ。所以ゆえん这个超ちょう乘じょう积满足あしΣしぐま中ちゅう所有しょゆう的てき公式こうしき。

紧致性せい定理ていり（版本はんぽん2）

紧致性せい定理ていり的てき定てい义

紧致性せい定理ていり定てい义：

1）在ざい一いち阶逻辑中，如果我わが们有一いち个公式しき集合しゅうごう（记作）$\Delta$并且$\Delta$是ぜ一いち个不ふ满足式しき的てき公式こうしき集合しゅうごう，那な么$\Delta$至いたり少しょう有ゆう一个有限个数元素的子集（记作）$\Delta ^{\prime }$（$\Delta ^{\prime }\subseteq \Delta$）并且$\Delta ^{\prime }$也是不ふ满足式しき的てき集合しゅうごう

我わが们注意ちゅうい到いた：

2)（换一いち句く话说），如果我わが们有一いち个公式しき集合しゅうごう（记作）$\Delta$并且$\Delta$是ぜ一いち个可か满足式しき的てき公式こうしき集合しゅうごう，那な么对于所有しょゆう$\Delta$有限ゆうげん个数元素げんそ的てき子こ集しゅう（记作）$\Delta ^{\prime }$ ($\Delta ^{\prime }\subseteq \Delta$) , $\Delta ^{\prime }$也是可か满足式しき的てき集合しゅうごう

3)（换一いち句く话说），前提ぜんてい假かり设我们有一いち个子句く（Clause）集合しゅうごう（记作）S，并且S中なか的てき所有しょゆう子こ句く是ぜ封ふう闭的（Clause Fermee，也就是ぜ说子句く中ちゅう不ふ含有がんゆう变量），如果S是ぜ不可ふか满足式しき的てき子こ句く集合しゅうごう，当とう且仅当とうS至いたり少しょう有ゆう一いち个子集合しゅうごうS'，S'是ぜ有限ゆうげん集合しゅうごう并且S'是ぜ不可ふか满足的てき集合しゅうごう

我わが们注意ちゅうい到いた：

在ざい3)中ちゅう我わが们把公式こうしき集合しゅうごう$\Delta$转化成子なるこ句く集合しゅうごうS，（根ね据すえ定理ていり：$\Delta SAT\Leftrightarrow Clause(\Delta )SAT$），我わが们说$\Delta$的てき可か满足性せい和わ转化成かせい的てき子こ句く集合しゅうごうS的てき可か满足性せい是ぜ等とう价的

紧致性せい定理ていり的てき证明

我わが们对1)的てき证明如下： 在ざい证明前まえ，我わが们需要よう知道ともみち如下定てい义：

a)完かん备性（Completude）定理ていり的てき定てい义：前提ぜんてい假かり设我们有一个有限个数元素的子句集合（记作）S并且S中ちゅう不ふ含有がんゆう变量（符号ふごう），如果S是ぜ不可ふか满足的てき集合しゅうごう，那な么S必定ひつじょう拥有一いち个驳斥（Refutation）

b)驳斥（Refutation）的てき定てい义：一いち个子句く集合しゅうごうS的てき驳斥是ぜ一个通过应用衍生方法产生的一系列子句$C_{1},C_{2},......C_{n}$并且最さい后きさき的てき$C_{n}$是ぜ一いち个空子こ句く，我わが们叫做S拥有（或ある接受せつじゅ）一いち个驳斥，记作$S\vdash \Box$

我わが们注意ちゅうい到いた当とうS拥有一いち个驳斥时，那な么很显然集合しゅうごうS是ぜ有限ゆうげん的てき，产生的てき子こ句く$C_{1},C_{2},......C_{n}$也是有限ゆうげん的てき，这是因いん为我们不能ふのう再さい运用衍生规则产生其它新しん的てき子こ句く

c)衍生（Derivation）的てき定てい义：从一个子句く集合しゅうごうS,通つう过应用よう解かい决规则（regle de resolution）或ある因いん式しき分解ぶんかい规则（regle de factorisation）产生得え到いた的てき一いち系列けいれつ子こ句く$C_{1},C_{2},......C_{n}$叫さけべ做衍生せい

d)正せい确性（Correction）定理ていり的てき定てい义：前提ぜんていS是ぜ一个不含变量符号的子句集合，如果子こ句くC是ぜ子こ句く集合しゅうごうS通どおり过应用よう解かい决规则或因いん式しき分解ぶんかい规则所しょ的てき到いた的てき子こ句く，那な么子句くC是ぜ子こ句く集合しゅうごうS的てき逻辑子こ序列じょれつ（Consequence Logique），记作$S\models C$，也就是ぜ说集合しゅうごうS的てき所有しょゆう模型もけい（或ある称しょう解かい释，指ゆび派は）也是子こ句くC的てき模型もけい

e)逻辑子こ序列じょれつ（Consequence Logique）的てき定てい义：一いち个公式しき（或ある公式こうしき集合しゅうごう）$\phi$是ぜ另一个公式しき（或ある公式こうしき集合しゅうごう）$\psi$的てき逻辑子こ序列じょれつ，当とう且仅当とう所有しょゆう$\psi$的てき模型もけい（或ある称しょう解かい释，指ゆび派は）是これ$\phi$的てき模型もけい，记做$\psi \models \phi$

证明：

根ね据すえ完かん备性定理ていり我わが们可以知道子みちこ句く集合しゅうごうS拥有一いち个驳斥，那な么对应的集合しゅうごう$\Delta$也拥有ゆう驳斥，那な么这两个集合しゅうごう都と是ぜ有限ゆうげん的てき，所以ゆえん一いち个S的てき子こ集合しゅうごうS'在ざい衍生驳斥中也ちゅうや是ぜ有限ゆうげん的てき，我わが们根据すえ正せい确性定理ていり可か以知道どう，通つう过应用よう衍生规则,S'也是不可ふか满足的てき，那な么很显然存在そんざい对应于S'的てき公式こうしき集合しゅうごう$\Delta ^{'}$（$\Delta ^{'}\subseteq \Delta$）来らい说，由ゆかり于$\Delta$含有がんゆう以子句く形式けいしき的てき集合しゅうごうS',那な么集合しゅうごう$\Delta ^{'}$必定ひつじょう是ぜ不可ふか满足的てき

$\Box$

参まいり见

• 布ぬの尔代数すう主しゅ题列表ひょう
• 哥德尔完备性定理ていり
• Löwenheim-Skolem定理ていり