コンパクト性定理
コンパクト性定理（英: 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