コンパクト性せい定理ていり

コンパクト性せい定理ていり（英えい: Compactness theorem）とは、一いち階かい述語じゅつご論理ろんりの文ぶんの集合しゅうごうがモデルを持もつこと（充足じゅうそく可能かのうであること）と、その集合しゅうごうの任意にんいの有限ゆうげん部分ぶぶん集合しゅうごうがモデルを持もつことが同値どうちであるという定理ていりである。つまりある理論りろんの充足じゅうそく可能かのう性せいを示しめすにはその有限ゆうげん部分ぶぶんについてのみ調しらべれば良よいという非常ひじょうに有用ゆうよう性せいの高たかい定理ていりであり、モデル理論りろんにおける最もっとも基本きほん的てきかつ重要じゅうような成果せいかのひとつである。

歴史れきし

1930年ねんにゲーデルが可算かさん集合しゅうごうの場合ばあいについて証明しょうめいした。非ひ可算かさんの場合ばあいについては、Anatoly Maltsevが1936年ねんに証明しょうめいを与あたえた^[1]^[2]。

応おう用例ようれい

コンパクト性せい定理ていりはモデル理論りろんを含ふくむ様々さまざまな分野ぶんやにおいて多おおくの応用おうようを持もつ。例れいとして、以下いかの定理ていりや命題めいだいがコンパクト性せい定理ていりを用もちいて証明しょうめいされる。

上方かみがたレーヴェンハイム-スコーレムの定理ていり
実数じっすうや自然しぜん数すうの超ちょう準じゅんモデルの存在そんざい
ロビンソンの原理げんり(一いち階かい述語じゅつご論理ろんりの文ぶん φふぁいが任意にんいの標しるべ数すう 0 の体からだで成なり立たつならば、ある自然しぜん数すう k が存在そんざいして、φふぁいは標しるべ数すうが k 以上いじょうのすべての体からだで成なり立たつ)
国くにの数かずが無限むげんである場合ばあいの四よん色しょく定理ていり^[3]
任意にんいの順序じゅんじょ集合しゅうごうが全ぜん順序じゅんじょに拡大かくだいできること ^[3]

証明しょうめい

コンパクト性せい定理ていりは、ゲーデルの完全かんぜん性せい定理ていりから導みちびくことができる。実際じっさい、一いち階かい述語じゅつご論理ろんりの文ぶんの集合しゅうごうSがモデルを持もたないとすると、完全かんぜん性せい定理ていりからSは矛盾むじゅんしていることになるが、どんな証明しょうめいも長ながさは有限ゆうげんなので、矛盾むじゅんの証明しょうめいに現あらわれるSの文ぶんは高々たかだか有限ゆうげん個こである。よって、Sのある有限ゆうげん部分ぶぶんから矛盾むじゅんが導出みちびきだされること、つまりSは充足じゅうそく不可能ふかのうな部分ぶぶん集合しゅうごうを持もつことがわかる。これの対偶たいぐうがコンパクト性せい定理ていりである ^[3]。

この他ほかにも、超ちょう積せきを用もちいた証明しょうめいも知しられている。

その他たの論理ろんり体系たいけいにおけるコンパクト性せい

命題めいだい論理ろんりにおける同様どうようの結果けっかは、位相いそう空間くうかん論ろんのチコノフの定理ていりをストーン空間くうかんに適用てきようすることで得えられる^[4]。 en:Lindström's theoremは、コンパクト性せい定理ていりと(下方かほう)レーヴェンハイム-スコーレムの定理ていりが一いち階かい述語じゅつご論理ろんりを特徴とくちょうづける性質せいしつであることを示しめしている。高階たかしな述語じゅつご論理ろんりにおいてもある種しゅのコンパクト性せいは保持ほじされているが、コンパクト性せい定理ていり自体じたいは成なりたない。

脚注きゃくちゅう

[脚注きゃくちゅうの使つかい方かた]

^ Vaught, Robert L.: Alfred Tarski's work in model theory. J. Symbolic Logic 51 (1986), no. 4, 869–882
^ Robinson, A.: Non-standard analysis. North-Holland Publishing Co., Amsterdam 1966. page 48.
^ ^a ^b ^c http://www.math.tsukuba.ac.jp/~tsuboi/und/14logic3.pdf
^ Truss (1997)

参考さんこう文献ぶんけん

Boolos, George; Jeffrey, Richard; Burgess, John (2004). Computability and Logic (fourth ed.). "Cambridge University Press
Chang, C.C.; Keisler, H. Jerome (1989). Model Theory (third ed.). Elsevier. ISBN 0-7204-0692-7
Dawson, John W. junior (1993). “The compactness of first-order logic: From Gödel to Lindström”. History and Philosophy of Logic 14: 15–37. doi:10.1080/01445349308837208.
Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0-521-30442-3
Marker, David (2002). Model Theory: An Introduction. Graduate Texts in Mathematics 217. Springer. ISBN 0-387-98760-6
Truss, John K. (1997). Foundations of Mathematical Analysis. Oxford University Press. ISBN 0-19-853375-6