小学生クラス

数理論理学の一分野であるモデル理論において、基本クラス（または公理化可能クラス）は、固定された一階述語理論を満たすすべての構造からなるクラスです。

意味

署名σの構造のクラス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クラス${\displaystyle _{\Delta}}$ およびECクラスを使用している（Hodges, 1993）。

この異なる用語法には十分な理由がある。一般モデル理論で扱われるシグネチャはしばしば無限であるのに対し、単一の一階述語文には有限個の記号しか含まれない。したがって、基本的な基本クラスは無限モデル理論では異例である。一方、有限モデル理論は、ほぼ有限シグネチャのみを扱う。任意の有限シグネチャσと、同型性の下で閉じたσ構造の任意のクラスKに対して、 KとKが全く同じ有限構造を含むようなσ構造の基本クラスが存在することは容易に理解できる。したがって、基本クラスは有限モデル理論家にとってそれほど興味深いものではない。 ${\displaystyle K'}$ ${\displaystyle K'}$

概念間の簡単な関係

明らかに、すべての基本素クラスは素クラスであり、すべての素クラスは擬似素クラスである。さらに、コンパクト性定理から容易に導かれる帰結として、σ構造のクラスが基本素クラスであるためには、それが素クラスであり、かつその補クラスも素クラスである場合に限る。

例

基礎初級クラス

σ を単項関数記号fのみからなるシグネチャとする。fが一対一であるσ 構造のクラスKは、基本的な基本クラスである。これは、次の一文のみからなる 理論Tによって証明される。

${\displaystyle \forall x\forall y((f(x)=f(y))\to (x=y))}$ 。

基本的な基本クラスではない、基本的な擬似基本クラス

σを任意のシグネチャとする。すべての無限σ構造の クラスKは基本クラスである。これを理解するには、次の文を考えてみよう。

${\displaystyle \rho _{2}={}}$ 「」、${\displaystyle \exists x_{1}\exists x_{2}(x_{1}\not =x_{2})}$

${\displaystyle \rho _{3}={}}$ 「」、${\displaystyle \exists x_{1}\exists x_{2}\exists x_{3}((x_{1}\not =x_{2})\land (x_{1}\not =x_{3})\land (x_{2}\not =x_{3}))}$

などなど。（つまり、この文は少なくともn個の要素が存在すると言っている。）無限σ構造はまさに理論のモデルである。 ${\displaystyle \rho_{n}}$

${\displaystyle T_{\infty}=\{\rho _{2},\rho _{3},\rho _{4},\dots \}}$ 。

しかし、Kは基本的な素類ではない。そうでなければ、無限σ構造は、ある一階述語文τを満たすものと正確に一致することになる。しかし、その場合、集合は 矛盾する。コンパクト性定理によれば、ある自然数nに対して、集合は矛盾する。しかし、これは不合理である。なぜなら、この理論は、 個以上の元 を持つ任意の有限σ構造によって満たされるからである。${\displaystyle \{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots \}}$ ${\displaystyle \{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots ,\rho _{n}\}}$ ${\displaystyle n+1}$

しかし、シグネチャ σ' = σ { f }には基本的な基本クラスK'が存在する。ここでfは単項関数記号であり、K はK'内の σ' 構造の σ への縮約のみから構成される。K 'は単一の文 によって公理化され、これはfが単射ではあるが単射ではないことを表す。したがって、Kは基本クラスであり、いわば基本擬基本クラスであるが、基本基本クラスではない。 ${\displaystyle \cup }$ ${\displaystyle (\forall x\forall y(f(x)=f(y)\rightarrow x=y)\land \exists y\neg \exists x(y=f(x))),}$

非初等教育の擬似初等教育クラス

最後に、単一の単項関係記号Pからなるシグネチャ σ を考える。すべての σ 構造は、P が成り立つ要素とそれ以外の要素という2つの部分集合に分割される。Kを、これら2つの部分集合が同じ濃度を持つ、すなわち両者の間に一対一の関係があるすべての σ 構造のクラスとする。このクラスは基本クラスではない。なぜなら、 Pの実現集合とその補集合の両方が可算無限である σ 構造は、一方の集合が可算無限でもう一方が不可算である σ 構造と全く同じ一階文を満たすからである。

ここで、 Pと単項関数記号fからなるシグネチャ を考えてみましょう。は、 fが一対一であり、xに対してPが成り立つ場合、かつPがf(x)に対して成り立たない場合に限り、すべての-構造のクラスであるとします。は明らかに基本クラスであるため、K は基本クラスではない擬似基本クラスの例です。 ${\displaystyle \sigma '}$ ${\displaystyle K'}$ ${\displaystyle \sigma '}$ ${\displaystyle K'}$

非擬似小学校クラス

σ を任意のシグネチャとする。すべての有限 σ-構造のクラスKは基本クラスではない。なぜなら（上に示したように）その補クラスは基本クラスではあるが、基本基本クラスではないからである。これは σ を拡張するすべてのシグネチャについても成り立つため、Kは擬似基本クラスですらない。

この例は、はるかに表現力豊かな二階述語論理と比較した場合、一階述語論理に固有の表現力の限界を示しています。しかし、二階述語論理は、完全性定理やコンパクト性定理など、一階述語論理の多くの望ましい特性を維持できていません。

参考文献

• チャン、チェン・チュン;キースラー、H.ジェローム(1990) [1973]、「モデル理論」、「論理と数学の基礎研究」（第3版）、エルゼビア、ISBN 978-0-444-88054-3
• エビングハウス、ハインツ・ディーター; Flum、Jörg (2005) [1995]、有限モデル理論、ベルリン、ニューヨーク: Springer-Verlag、p. 360、ISBN 978-3-540-28787-2
• エビングハウス、ハインツ＝ディーター。フルム、ヨルグ。 Thomas、Wolfgang (1994)、Mathematical Logic (第 2 版)、ベルリン、ニューヨーク: Springer-Verlag、ISBN 978-0-387-94258-2
• ホッジス、ウィルフリッド（1997）、『より短いモデル理論』、ケンブリッジ大学出版局、ISBN 978-0-521-58713-6
• ポイザット、ブルーノ（2000）、モデル理論講座：現代数学論理入門、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-98655-5