数理論理学の一分野であるモデル理論において、基本クラス(または公理化可能クラス)とは、固定された一階理論を満たすすべての構造からなるクラスのことである。
符号σの構造のクラスKは 、符号σを持つ一階述語理論Tが存在し、 KがTのすべてのモデル、すなわちTを満たすすべてのσ構造から構成される場合、基本クラスと呼ばれる。Tが単一の一階述語文からなる理論として選択できる場合、 Kは基本基本クラスと呼ばれる。
より一般的に言えば、Kが擬似初等クラスであるのは、σ を拡張するシグネチャの一次理論Tが存在し、 K がTのモデルの σ への還元であるすべての σ 構造から構成される場合である。言い換えれば、σ 構造のクラスKが擬似初等であるのは、 KがK 'の構造の σ への還元のみから構成されるような初等クラスK 'が存在する場合に限る。
当然のことながら、一階述語論理では基本クラスは公理化可能とも呼ばれ、基本的な基本クラスは有限公理化可能とも呼ばれます。これらの定義は他の論理にも同様に拡張できますが、一階述語論理が最も重要であるため、他の論理が指定されていない場合は、公理化可能という言葉は暗黙のうちにこの一階述語論理を指します。
上記は現在では「無限」モデル理論における標準的な用語となっているが、わずかに異なる以前の定義は有限モデル理論において依然として使用されており、そこでは基本クラスはΔ-基本クラスと呼ばれ、基本クラスおよび一階公理化可能クラスという用語は基本基本クラスに限定されている(Ebbinghaus et al. 1994、Ebbinghaus and Flum 2005)。Hodgesは基本クラスを公理化可能クラスと呼び、基本基本クラスを定義可能クラスと呼んでいる。彼はまた、それぞれの同義語ECも使用している。クラスとECクラス(ホッジス、1993)。
この用語の相違には正当な理由がある。一般モデル理論で考慮されるシグネチャはしばしば無限であるのに対し、単一の一階述語論理式は有限個の記号しか含まない。したがって、基本的な基本クラスは無限モデル理論では一般的ではない。一方、有限モデル理論はほぼ有限シグネチャのみを扱う。任意の有限シグネチャσと、同型写像に関して閉じているσ構造の任意のクラスKに対して、基本クラスが存在することは容易にわかる。Kとσ構造のそれらは全く同じ有限構造を含んでいる。したがって、基本クラスは有限モデル理論家にとってあまり興味深いものではない。
明らかに、すべての基本基本クラスは基本クラスであり、すべての基本クラスは擬似基本クラスである。さらに、コンパクト性定理の容易な帰結として、σ構造のクラスが基本基本であるのは、それが基本クラスであり、かつその補集合も基本クラスである場合に限る。
σ を単項関数記号fのみからなるシグネチャとする。fが一対一であるσ 構造のクラスKは基本初等クラスである。これは、単一の文のみからなる理論Tによって証明される。
σ を任意のシグネチャとする。すべての無限 σ 構造のクラスKは基本的である。これを確認するには、次の文を考えてみよう。
などなど。(つまり、文は(少なくともn個の要素が存在すると述べている。)無限σ構造はまさにその理論のモデルである。
しかし、Kは基本的な初等クラスではない。そうでなければ、無限 σ-構造は、ある一階述語 τ を満たすものと正確に一致するはずである。しかし、その集合は 矛盾が生じるだろう。コンパクト性定理により、ある自然数nに対して、集合は矛盾が生じるだろう。しかしこれは不合理だ。なぜならこの理論は、有限σ構造であればどれでも満たされるからである。またはそれ以上の要素。
しかし、シグネチャ σ' = σ には基本的な基本クラスK 'が存在する。{ f }、ここでfは単項関数記号であり、K はK 'のσ'-構造の σ への還元のみから構成される。K 'は単一の文によって公理化される。これは、fが単射ではあるが全射ではないことを示している。したがって、Kは基本関数であり、擬似基本関数と呼べるものではあるが、基本関数ではない。
最後に、単一の単項関係記号Pからなるシグネチャ σ を考えます。すべての σ 構造は、Pが成り立つ要素とそれ以外の要素の 2 つの部分集合に分割されます。Kを、これら 2 つの部分集合が同じ濃度を持つ、つまり、それらの間に全単射が存在するすべての σ 構造のクラスとします。このクラスは基本ではありません。なぜなら、 Pの実現の集合とその補集合の両方が可算無限である σ 構造は、一方の集合が可算無限で他方が非可算である σ 構造とまったく同じ一階述語論理を満たすからです。
次に署名について考えてみましょうこれは、 Pと単項関数記号fから構成される。すべてのクラスになる-fが全単射であり、P がx に対して成り立つのは、P がf(x)に対して成り立たない場合に限る、という構造。は明らかに基本クラスであり、したがってKは基本クラスではない擬似基本クラスの例である。
σ を任意のシグネチャとする。すべての有限 σ 構造のクラスKは基本クラスではない。なぜなら、(上述のように)その補集合は基本クラスではあるが、基本クラスではないからである。これは σ を拡張するすべてのシグネチャについても同様に成り立つため、Kは擬似基本クラスですらない。
この例は、表現力の限界を、はるかに表現力に優れた二階述語論理と比較して示している。しかしながら、二階述語論理は、完全性定理やコンパクト性定理など、一階述語論理の多くの望ましい特性を保持できていない。