コンパクト性定理(一階論理)(compactness theorem for first-order logic)とは、一階の文の集合について、その任意の有限部分集合にモデルがあれば全体にもモデルがあるという定理である。有限部分集合ごとのモデルを超フィルターで束ねた超積が全体のモデルになること(Łoś の定理)から直接示せ、Gödel の完全性定理からも導ける。任意に大きい有限モデルをもつ理論が無限モデルをもつこと、有限性や整列性が一階の文で書けないこと、無限グラフの彩色可能性が有限部分グラフで決まることなどが帰結である。モデルを有限構造に限ったり二階論理を使ったりすると成り立たない。
1日前に更新
Gödelの完全性定理(Gödel's completeness theorem)とは、一階述語論理において意味論的帰結と形式的証明可能性が一致すること、すなわち文集合 $\Gamma$ と文 $\varphi$ に対して $\Gamma\models\varphi$ ならば $\Gamma\vdash\varphi$ であることを述べる定理である。健全性定理と合わせると両者は同値になり、無矛盾な理論のモデル存在やコンパクト性定理が従う。証明の核心は、証人定数と項モデルを用いるHenkin構成である。
1日前に更新
Löwenheim–Skolemの定理(Löwenheim–Skolem theorem)とは、一階言語 $L$ の文の集合が無限のモデルをもてば、$\lvert L\rvert+\aleph_0$ 以上のすべての基数 $\kappa$ について濃度がちょうど $\kappa$ のモデルをもつという定理である。構造から小さな初等部分モデルを取り出す下向きの定理と、初等図式とコンパクト性定理で大きな初等拡大を作る上向きの定理からなる。帰結として、無限構造はそれが満たす文の全体でも同型を除いて決まらず、有限のモデルをもたず 1 つの濃度で範疇的な理論は完全である(Łoś–Vaught の判定法)。可算な言語で書かれた集合論も可算なモデルをもち、この現象は Skolem のパラドックスとよばれる。
1日前に更新
初等部分モデル(elementary submodel)とは、構造 $M$ の部分構造 $N$ で、$N$ の元を代入した一階の論理式の真偽が $N$ と $M$ で一致するものであり、$N\preccurlyeq M$ と書く。同じ文を満たすだけの部分構造より強い条件で、同型な部分構造でも初等的とは限らない。Tarski–Vaught の判定法により、$M$ で真な存在文の証人が $N$ の中にとれるかで判定でき、下向き Löwenheim–Skolem の定理により任意の集合 $A$ を含む濃度 $\lvert A\rvert+\lvert L\rvert+\aleph_0$ 以下の初等部分モデルが存在する。集合論では $H(\theta)$ の可算な初等部分モデルが組合せ論的議論に使われる。
1日前に更新
順序体(ordered field)とは、体 $F$ とその上の全順序 $\le$ の組であって、$a\le b$ ならば $a+c\le b+c$、$0\le a$ かつ $0\le b$ ならば $0\le ab$ を満たすものである。有理数体と実数体が代表例で、順序体では $0$ でない元の平方は正、標数は $0$ であり、有理数体が順序を保って埋め込まれる。複素数体や正の標数の体には順序体の順序が入らず、体が順序付け可能であることは $-1$ が平方の和で書けないことと同値である(Artin–Schreier)。同じ体に複数の順序が入ることがあり、有理関数体 $\mathbb{R}(t)$ にはどの自然数よりも大きい元をもつ順序が入る。そのような元をもたない Archimedes 的な順序体は、実数体に順序を保ってただ 1 通りに埋め込め、実数体の部分体と同型になる。
1日前に更新
コンパクト性定理(命題論理)(compactness theorem for propositional logic)とは、命題論理の論理式の集合 $\Sigma$ について、$\Sigma$ のどの有限部分集合も充足可能(同時に真にする付値がある)ならば $\Sigma$ 全体も充足可能である、という定理である。命題変数はいくつあってもよい。同値な形として、$\Sigma\models\varphi$ ならある有限部分集合 $\Sigma_0$ で $\Sigma_0\models\varphi$ となる。証明は、有限充足可能な集合を極大なものに広げ、そこに属する命題変数を真とする付値が全体を充足することによる。無限の対象の問題を有限の場合に帰着させる道具であり、無限の木の枝についての König の補題や、有限集合の無限族の結婚定理が従う。
1日前に更新
一階述語論理(first-order predicate logic)とは、対象の間の演算や関係を記号で表し、台集合の元について量化する形式論理である。定数・関数・関係記号から項と論理式を作り、構造がそれらの記号を解釈すると文の真偽が定まる。自由変数を持つ式は、構造と変数への値の割り当てのもとで充足を判定する。完全性定理やコンパクト性定理は一階論理の基本定理である。
1日前に更新
初等同値(elementary equivalence)とは、同じ一階言語の 2 つの構造 $\mathcal M,\mathcal N$ が、その言語のすべての文について真偽を一致させること、すなわち $\operatorname{Th}(\mathcal M)=\operatorname{Th}(\mathcal N)$ であることをいい、$\mathcal M\equiv\mathcal N$ と書く。同型な構造は初等同値であり、有限構造では逆も成り立つが、無限構造では $(\mathbb{Q},<)$ と $(\mathbb{R},<)$ のように初等同値で同型でない例が必ずある。部分同型の往復系があれば初等同値であり、初等同値は 2 つの構造を同時に初等的に埋め込める構造があることと同値である。理論が完全であることは、そのモデルがどれも初等同値であることと同値である。
1日前に更新
モデル理論(model theory)とは、一階述語論理における構造と、その構造上での論理式の充足関係を研究する数理論理学の一分野である。証明の記号操作そのものではなく、ある理論(公理の集合)を満たす構造全体、すなわちそのモデルのクラスに注目し、コンパクト性定理やLöwenheim–Skolemの定理を基本道具とする。稠密線形順序・代数的閉体・実閉体のような代数学・順序論の対象や、算術の超準モデルを統一的に扱えることが特色である。型と初等埋め込みは、モデルの局所的な性質と構造間の一階的同一性を記述する基本言語である。
1日前に更新
無限小(infinitesimal)とは、実数を含む順序体では、絶対値がすべての正の実数より小さい元をいう。実数ではゼロだけがこの条件を満たすが、超準解析などでは非零の無限小を扱い、二重数やスキームでは冪零元によって一次の変化を記録する。順序体の非零の無限小は割ることができるが、冪零の無限小は割れず、通常の実解析では微小な変化を実数の極限で表す。
1日前に更新