コンパクト性定理

1930年にゲーデルが可算集合の場合について証明した。非可算の場合については、Anatoly Maltsevが1936年に証明を与えた^[1][2]。

コンパクト性定理はモデル理論を含む様々な分野において多くの応用を持つ。例として、以下の定理や命題がコンパクト性定理を用いて証明される。

• 上方レーヴェンハイム-スコーレムの定理
• 実数や自然数の超準モデルの存在
• ロビンソンの原理(一階述語論理の文 φ が任意の標数 0 の体で成り立つならば、ある自然数 k が存在して、φは標数が k 以上のすべての体で成り立つ)
• 国の数が無限である場合の四色定理^[3]
• 任意の順序集合が全順序に拡大できること ^[3]

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

この他にも、超積を用いた証明も知られている。

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