Loading article…
一階述語論理において、一階理論は、ある言語で記述された一連の公理によって定義されます。本項目では、モデル理論で用いられる代表的な例とその性質をいくつか紹介します。
すべての自然な数学的構造には、 その理論の定数、関数、関係とそのアリティを列挙したシグネチャσが存在し、対象は自然にσ構造となる。シグネチャσが与えられると、 σ構造に関する一階述語論理で表現可能な事実を捉えるために使用できる、一意の一階述語論理言語 L σが存在する。
理論を具体的に示すには、一般的に2つの方法があります。
Lσ理論には以下の可能性がある。
純粋恒等理論の署名は空であり、関数、定数、関係式は含まれていない。
純粋同一性理論には（非論理的な）公理は存在しない。それは決定可能である。
純粋同一性理論の言葉で表現できる数少ない興味深い性質の一つは、無限性である。これは、少なくとも2つの要素が存在する、少なくとも3つの要素が存在する、といった無限の公理によって示される。
これらの公理は無限集合の理論を定義する。
有限であることの反対の性質は、任意の大きさの有限モデルを持つ理論に対しては、一階述語論理では表現できません。実際、コンパクト性定理により、そのような理論は無限のモデルを持つことになります。一般に、ある性質が有限個の一階述語論理の文で表現できる場合、その反対の性質も一階述語論理で表現できますが、ある性質が無限個の文を必要とする場合、その反対の性質は一階述語論理では表現できません。
純粋な同一性理論の記述は、非負整数の有限部分集合Nに対して、σ( N ) または ¬σ( N ) のいずれかと等価である。ここで、σ( N ) は要素の数がNに含まれるという記述である。この言語では、すべての可能な理論を次のように記述することもできる。任意の理論は、非負整数の有限部分集合Nに対するNに含まれるすべての濃度の集合の理論、または非負整数の有限または無限部分集合Nに対する、濃度がNに含まれないすべての集合の理論のいずれかである。（ N が整数の無限部分集合である場合、モデルが正確に濃度Nの集合である理論は存在しない。）完全な理論は、ある有限nに対する濃度nの集合の理論と、無限集合の理論である。
この特殊なケースの 1 つは、公理 ∃ x ¬ x = xで定義される矛盾理論です。これは、完全性、決定可能性、有限公理化可能性など、多くの優れた特性を持つ完全に優れた理論です。唯一の問題は、モデルがまったくないことです。ゲーデルの完全性定理により、これは (任意の言語に対して) モデルを持たない唯一の理論です。[ 1 ]これは、(モデルが空であることを許容する一階述語論理のバージョンにおける)空集合の理論とは異なります。空集合の理論には、要素を持たないモデルがちょうど 1 つあります。
ある集合I の要素iに対する単項関係P iの集合は、Iの互いに素な有限部分集合AとBに対して、 要素 x が存在し、P i ( x )がAの要素iに対しては真であり、 Bの要素iに対しては偽となる場合、独立であると呼ばれる。独立性は、一階述語論理の命題の集合によって表現できる。
可算個の独立した単項関係の理論は完全ではあるが、原子モデルは存在しない。また、これは超安定ではあるが、完全には超越的ではない理論の一例でもある。
同値関係のシグネチャは、二項中置関係記号 ~ を 1 つ含み、定数や関数は含まない。同値関係は以下の公理を満たす。
同値関係の一次的な性質には、次のようなものがある。
ちょうど 2 つの無限同値類を持つ同値関係の理論は、ω-カテゴリカルであるが、より大きな基数に対してカテゴリカルではない理論の簡単な例である。
同値関係 ~ は恒等記号 '=' と混同してはならない。x = yならばx ~ y であるが、その逆は必ずしも真ではない。同値関係の理論はそれほど難解でも興味深いものでもないが、様々な命題に対する分かりやすい例や反例を与えてくれることが多い。
以下の構成法は、特定のスペクトルを持つ理論の例を生成するために時々使用されます。実際、これらを少数の明示的な理論Tに適用すると、すべての可能な非可算スペクトルを持つ完全な可算理論の例が得られます。Tが何らかの言語の理論である場合、新しい二項関係を言語に追加し、それが同値関係であり、すべての同値クラスが T のモデルとなるような同値クラスが無限に存在することを示す公理を追加することによって、新しい理論 2 Tを定義します。この構成法は超限的に反復できます。順序数α が与えられた場合、各 β < α に対して同値関係E βを追加し、β < γ の場合、各E γ同値クラスは無限個のE β同値クラスの和集合であり、各E 0同値クラスはTのモデルであるという公理とともに、新しい理論を定義します。非公式に言えば、この理論のモデルは、高さαの無限に枝分かれした木として視覚化でき、すべての葉にTのモデルが取り付けられている。
順序のシグネチャには定数や関数はなく、1 つの二項関係記号 ≤ があります。(もちろん、基本関係として ≥、<、または>を使用することも可能で、その場合は公理に明らかな小さな変更が加わります。) x ≥ y、x < y、x > y をy ≤ x、x ≤ y ∧¬ y ≤ x、y < xの略語として定義します。
順序の一次特性の一部：
端点のない（つまり最小値や最大値のない）稠密線形順序の理論 DLO は、完全であり、ω-圏論的であるが、任意の非可算基数に対しては圏論的ではない。非常によく似た理論が他に 3 つある。稠密線形順序の理論は次のとおりである。
整列性（「空でない任意の部分集合には最小要素がある」）は一階述語論理の性質ではありません。通常の定義では、すべての部分集合について量化します。
格子は、1 つの二項関係記号≤からなるシグネチャを持つ、特殊な種類の半順序集合として、または2 つの二項演算∧と∨ からなるシグネチャを持つ代数構造として考えることができます。この 2 つのアプローチは、 a ≤ b をa ∧ b = aと定義することによって関連付けることができます 。
2つの二項演算に関して、格子の公理は次のとおりです。
一つの関係≤に対する公理は次のとおりです。
一次特性には以下が含まれます。
ハイティング代数は、特定の追加的な一階性質を持つ束として定義できる。
完全性は、格子の一次的な性質ではない。
グラフの署名には定数や関数はなく、1つの二項関係記号Rがあり、R ( x , y )は「 xからyへの辺が存在する」と読みます。
グラフ理論の公理は以下のとおりである。
ランダムグラフ理論には、各正の整数nに対して以下の追加公理がある。
ランダムグラフの理論は、ω カテゴリー的、完全かつ決定可能であり、その可算モデルはラドグラフと呼ばれます。グラフの言語で記述された命題は、 n個の頂点を持つランダムグラフがその命題をモデル化する確率が、 n が無限大に近づく極限で 1 に収束する場合に限り、この理論において真となります。
ブール代数には、いくつかの異なる署名と慣例が用いられています。
公理は以下のとおりです。
タルスキは、ブール代数の理論が決定可能であることを証明した。
x ≤ y はx ∧ y = xの略記であり、atom( x ) は ¬ x = 0 ∧ ∀ y y ≤ x → y = 0 ∨ y = xの略記であり、「 xは原子である」と読みます。つまり、0 との間に何も存在しない非ゼロ要素です。以下に、ブール代数の一次の性質をいくつか示します。
原子を持たないブール代数の理論はω-圏論的かつ完全である。
任意のブール代数Bに対して、以下のように定義されるいくつかの不変量が存在します。
すると、2つのブール代数が基本的に同値であるのは、それらの不変量l、m、nが同じである場合に限る。言い換えれば、これらの不変量の値は、ブール代数理論の可能な完全性を分類する。したがって、可能な完全理論は次のようになる。
群論の符号は、定数 1 (単位元)、t上での値がt − 1で表される1 次関数 (逆関数) 、および通常項から省略される 2 次関数から構成されます。任意の整数nに対して、t n はtのn乗を表す自明な項の略記です。
グループは公理によって定義される
一階述語論理の群の言語で定義できる群の性質には、次のようなものがある。
アーベル群の理論は決定可能である。[ 2 ]無限に分割可能なねじれのないアーベル群の理論は完全であり、指数 p の無限アーベル群の理論（pは素数）も同様である。
有限群の理論とは、群の言語で記述された、すべての有限群において真となる一階述語論理の命題の集合である（この理論には無限群モデルが多数存在する）。すべての群において真とならない命題を見つけることは、必ずしも容易ではない。例えば、「位数2の2つの元が与えられたとき、それらは共役であるか、または両方と可換な非自明な元が存在する」という命題が挙げられる。
有限性、自由性、単純性、ねじれ性といった性質は、一階述語論理の性質ではない。より正確に言えば、これらの性質のいずれかを持つすべての群の一階述語論理には、この性質を持たないモデルが存在する。
（単位付き）環の署名には、2 つの定数 0 と 1、2 つの二項関数 + と×、およびオプションで 1 つの単項否定関数−が含まれます。
リング
公理：加法は環をアーベル群にする。乗法は結合法則を満たし、単位元1を持つ。乗法は左分配法則と右分配法則を満たす。
環の公理プラス ∀ x ∀ y xy = yx。
可換環の公理に加えて、∀ x (¬ x = 0 → ∃ y xy = 1) および ¬ 1 = 0 。ここで挙げた例の多くは、普遍的または代数的な公理のみを持っています。このような理論を満たす構造のクラスは、部分構造に関して閉じているという性質を持ちます。たとえば、乗法と逆元の群作用に関して閉じている群の部分集合は、再び群になります。体のシグネチャには通常、乗法逆元と加法逆元が含まれていないため、逆元の公理は普遍的ではなく、したがって、加法と乗法に関して閉じている体の部分構造は、必ずしも体ではありません。これは、言語に単項逆元関数を追加することで解決できます。
任意の正の整数nに対して、次数nのすべての方程式が根を持つという性質は、単一の一次式で表現できる。
体に関する公理に加えて、各素数pに関する公理があり、 p 1 = 0 (つまり、体の特性がpである) ならば、すべての体要素はp乗根を持つと規定している。
標数pの代数的閉体
体の公理に加え、任意の正のnに対して次数nのすべての多項式が根を持つという公理、さらに特性を固定する公理。完全理論の古典的な例。すべての非可算基数に関して圏論的。理論ACF p は、ACF pの普遍公理を満たす すべての構造Nが十分に大きな代数的に閉じた体の部分構造である という意味で、普遍領域特性を持つ。さらに、そのような埋め込みN → M の任意の 2 つはMの自己同型を誘導します。
有限体理論とは、すべての有限体において真となるすべての一階述語論理式の集合である。このような命題の重要な例としては、例えば素体上でChevalley–Warningの定理を適用することによって得られる。この理論には無限体モデルが多数存在するため、その名称はやや誤解を招く可能性がある。Axは、この理論が決定可能であることを証明した。
体に関する公理に加えて、すべての正の整数nに対して、次の公理が成り立つ。
つまり、0は非自明な平方和ではない。
形式的に実数体に関する公理と、以下の公理：
実閉体の理論は有効かつ完全であり、したがって決定可能である（タルスキー・ザイデンベルクの定理）。指数関数や正弦関数などの関数記号を追加すると、決定可能性が変化する可能性がある。
p進体
Ax & Kochen (1965)は、 p進体の理論が決定可能であることを示し、そのための公理系を与えた。[ 3 ]
様々な幾何学体系の公理は通常、型付き言語を使用し、異なる型は点、線、円、平面など、異なる幾何学的オブジェクトに対応します。シグネチャは多くの場合、異なる型のオブジェクト間の二項関係で構成されます。例えば、点が線上にあるという関係などです。シグネチャには、より複雑な関係が含まれる場合もあります。例えば、順序付き幾何学では、3点間の三項関係「中間性」があり、これは1点が他の2点の間にあるかどうかを示します。また、2組の点間の「合同」関係もあります。
公理化された幾何学体系の例としては、順序幾何学、絶対幾何学、アフィン幾何学、ユークリッド幾何学、射影幾何学、双曲幾何学などが挙げられる。これらの幾何学それぞれについて、様々な次元に対応する、互いに異なれど等価でない多くの公理体系が存在する。これらの公理体系の中には、一階述語論理ではない「完全性」公理を含むものもある。
典型的な例として、射影幾何学の公理では、点と線という 2 種類の要素と、点と線の間の二項関係を使用します。点と線の変数を小文字と大文字で表し、Aに付随するものをaAと書くと、公理の 1 つのセットは次のようになります。
ユークリッドはユークリッド幾何学の公理をすべて明示的に述べたわけではなく、最初の完全なリストはヒルベルトが『ヒルベルトの公理』で示した。ヒルベルトの公理の一つは二階完全性公理であるため、これは一階公理化ではない。タルスキの公理はユークリッド幾何学の一階公理化である。タルスキはこの公理系を実閉体の完全かつ決定可能な理論と関連付けることで、この公理系が完全かつ決定可能であることを示した。
シグネチャは、フィールド (0, 1, +, −, ×) と単項関数 ∂ (導出) の組み合わせです。公理は、フィールドと
この理論では、特性が素数またはゼロであるpであるという条件を追加することで、特性pの微分体の理論DF pを得ることができます(以下に示す他の理論についても同様です)。
Kが微分場である場合、定数場微分完全体 の理論とは、定数体が完全であるという条件を付加した微分体の理論である。言い換えれば、各素数pに対して次の公理が成り立つ。
（体全体が完全体であるべきだと要求してもあまり意味がない。なぜなら、標数がゼロでない場合、これは微分が 0 であることを意味するからである。）量化子消去に関する技術的な理由から、公理を持つ符号に新しい記号rを追加することで定数体を完全体と強制する方が便利な場合がある。
後継関数を持つ自然数の理論は、定数0と単項関数S（「後継関数」：S（x ）はx +1と解釈される）からなる符号を持ち、以下の公理を持つ。
最後の公理（帰納法）は、以下の公理に置き換えることができます。
後継関数を持つ自然数の理論は完全かつ決定可能であり、非可算κに対してはκ-カテゴリ的であるが、可算κに対してはそうではない。
プレスバーガー算術は、定数 0、単項関数S、および二項関数 + からなる符号を持つ、加算に関する自然数の理論である。完全かつ決定可能である。公理は以下の通りである。
上述の多くの一階述語論理理論は、完全かつ再帰的に列挙可能な無矛盾な理論へと拡張できる。しかし、以下の理論のほとんどについては、もはやそうではない。これらの理論は通常、自然数の乗算と加算の両方を符号化することができ、それによって自己符号化するのに十分な能力を持つため、ゲーデルの不完全性定理が適用され、これらの理論は（無矛盾でない限り）完全かつ再帰的に列挙可能であることはもはやあり得ない。
算術理論の署名には以下が含まれる。
一部の著者は、関数Sの代わりに定数 1 を含む署名をとらえ、S をSt = 1 + tという明白な方法で 定義します。
ロビンソン算術（Qとも呼ばれる）。公理 (1) と (2) は、特別な要素 0 を規定する。(3) はSが単射であることを保証する。公理 (4) と (5) は加算の標準的な再帰的定義であり、(6) と (7) は乗算についても同様である。ロビンソン算術は、帰納法を用いないペアノ算術と考えることができる。Qは、ゲーデルの不完全性定理が成り立つ弱い理論である。公理:
I Σ nは、帰納法がΣ n式( n = 0, 1, 2, ...)に制限された一階ペアノ算術です。理論 I Σ 0は、しばしば I Δ 0と表記されます。これは、ますます強力になるペアノ算術の断片のシリーズです。n = 1の場合、原始再帰算術(PRA)とほぼ同じ強度を持ちます 。指数関数算術(EFA) は、すべてのxとyに対してx yが存在するという公理(通常の性質を持つ)を持つ I Σ 0です。
1階ペアノ算術（PA）。算術の「標準」理論。公理は上記のロビンソン算術の公理と、帰納法の公理体系を組み合わせたものである。
クルト・ゲーデルの1931年の論文は、PA（部分集合）が不完全であり、一貫した再帰的に列挙可能な補完が存在しないことを証明した。
完全算術（真の算術とも呼ばれる）は、算術の標準モデルである自然数Nの理論である。完全ではあるが、再帰的に列挙可能な公理系は持たない。
実数の場合、状況は少し異なります。加算と乗算のみを含む場合、整数を符号化することはできないため、ゲーデルの不完全性定理は適用されません。さらに関数記号（例えば、べき乗）を追加すると、複雑な問題が生じます。
2階算術は、その名称にもかかわらず、整数と整数の部分集合の2種類の変数を持つ1階理論を指すことがあります。（2階論理にも2階算術と呼ばれる算術理論があります。これは、不完全な1階論理の対応する理論とは異なり、1つのモデルしかありません。）シグネチャは通常、算術のシグネチャ0、S、+、×と、整数と部分集合間のメンバーシップ関係∈を組み合わせたものになります（ただし、多くの細かなバリエーションがあります）。公理は、ロビンソン算術の公理と、帰納法および内包法の公理体系を組み合わせたものです。
2階算術には、帰納法と内包法のスキームで許容される式が異なるさまざまなサブ理論が存在する。強さの順に、最も一般的な5つのシステムは以下のとおりである。
これらは、 2次算術と逆算術に関する記事で詳細に定義されています。
集合論の通常のシグネチャは、1つの二項関係∈を持ち、定数や関数は含まれません。以下の理論の中には、「クラス理論」と呼ばれるものがあり、これは集合とクラスの2種類のオブジェクトを持ちます。一階述語論理では、これを扱う一般的な方法が3つあります。
一次集合論には以下のようなものがある。
これらの公理系（通常はZF公理系）に追加できる追加の一階述語論理公理には、以下のようなものがある。
