構造（数理論理学）

Mapping of mathematical formulas to a particular meaning

普遍代数とモデル理論では、構造は集合と、その集合上で定義された有限演算と関係の集合から構成されます。

普遍代数は、群、環、体、ベクトル空間といった代数構造を一般化する構造を研究する。普遍代数という用語は、関係記号を持たない一階理論の構造を指す。^[1]モデル理論は、集合論モデルなどの基礎構造を含む、より任意の一階理論を包含する異なる範囲を持つ。

モデル理論の観点から見ると、構造は第一階述語論理の意味論を定義するために使用されるオブジェクトです。タルスキの真理理論やタルスキアン意味論も参照してください。

モデル理論における特定の理論において、ある構造がその理論のすべての文を満たす場合、その構造はモデルと呼ばれます。論理学者は構造を「解釈」と呼ぶことがありますが^{[2] 、「解釈」という用語はモデル理論において一般的に異なる（ただし関連性はあるものの）意味を持ちます。}解釈（モデル理論）を参照してください。

データベース理論では、関数を持たない構造がリレーショナルデータベースのモデルとして、リレーショナルモデルの形で研究されています。^[3]

歴史

数理論理学の文脈において、「モデル」という用語は、1940年に哲学者ウィラード・ヴァン・オーマン・クワインが、集合論の発展の先駆者である数学者リヒャルト・デデキント（1831-1916）に言及する際に初めて使用されました。^{[4] [5]} 19世紀以来、公理の集合の一貫性を証明する主な方法の1つは、そのためのモデルを提供することでした。

意味

正式には、構造は、定義域、シグネチャ、そしてシグネチャがその定義域上でどのように解釈されるかを示す解釈関数からなる三つ組として定義できます。構造が特定のシグネチャを持つことを示すために、それを -構造と呼ぶことができます。 ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ ${\displaystyle A,}$ ${\displaystyle \sigma ,}$ ${\displaystyle I}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$

ドメイン

構造の定義域は任意の集合である。構造の基礎集合、構造の担い手（特に普遍代数において）、構造の宇宙（特にモデル理論において、宇宙を参照）、あるいは構造の議論領域とも呼ばれる。古典的な一階述語論理では、構造の定義域は空の定義域を禁じている。^{[要出典] [6]}

またはという表記法がドメインを表すために使用されることもありますが、構造とそのドメインの間に表記上の区別がないことがよくあります（つまり、同じ記号が構造とそのドメインの両方を指します）。^[7] ${\displaystyle \operatorname {dom} ({\mathcal {A}})}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle {\mathcal {A}}}$

サイン

構造体のシグネチャは次のものから構成されます。 ${\displaystyle \sigma =(S,\operatorname {ar} )}$

• 関数記号と関係記号のセット、および ${\displaystyle S}$
• 各記号に自然数を割り当てる関数 ${\displaystyle \operatorname {ar} :\ S\to \mathbb {N} _{0}}$ ${\displaystyle s}$ ${\displaystyle n=\operatorname {ar} (s).}$

シンボルの自然数 は、解釈のアリティ^{[説明が必要]}であるため、アリティと呼ばれます。 ${\displaystyle n=\operatorname {ar} (s)}$ ${\displaystyle s}$ ${\displaystyle s}$ ${\displaystyle s.}$

代数において生じるシグネチャは関数記号のみを含むことが多いため、関係記号を含まないシグネチャは代数的シグネチャと呼ばれる。このようなシグネチャを持つ構造は代数とも呼ばれる。これは体上の代数の概念と混同してはならない。

解釈機能

の解釈関数 は、シグネチャのシンボルに関数と関係を割り当てます。アリティの各関数シンボルには、定義域上の-項関数が割り当てられます。アリティの各関係シンボルには、定義域上の-項関係が割り当てられます。ゼロ項（-項）関数シンボルは、その解釈が定義域の定数要素と同一視できるため、定数シンボルと呼ばれます。 ${\displaystyle I}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f^{\mathcal {A}}=I(f)}$ ${\displaystyle R}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle R^{\mathcal {A}}=I(R)\subseteq A^{\operatorname {ar(R)} }}$ ${\displaystyle =\,0}$ ${\displaystyle c}$ ${\displaystyle I(c)}$

構造（したがって解釈関数）が文脈によって与えられる場合、記号とその解釈の間に表記上の区別はありません。例えば、 1の2項関数記号が1である場合、単に次のように書くのではなく、 ${\displaystyle s}$ ${\displaystyle I(s).}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle f:{\mathcal {A}}^{2}\to {\mathcal {A}}}$ ${\displaystyle f^{\mathcal {A}}:|{\mathcal {A}}|^{2}\to |{\mathcal {A}}|.}$

例

体の標準的なシグネチャは、2つの2項関数記号とで構成されます。ここで、単項関数記号（ によって一意に決定される）や2つの定数記号と（とによってそれぞれ一意に決定される）などの追加記号を導出できます。したがって、このシグネチャの構造（代数）は、2つの2項関数（単項関数で拡張可能）と2つの区別された元を含む一連の要素で構成されますが、体の公理のいずれかを満たす必要はありません。有理数、実数、複素数は、他の体と同様に、明らかに -構造と見なすことができます。 ${\displaystyle \sigma _{f}}$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {\times } }$ ${\displaystyle \mathbf {-} }$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {0} }$ ${\displaystyle \mathbf {1} }$ ${\displaystyle \mathbf {+} }$ ${\displaystyle \mathbf {\times } }$ ${\displaystyle A}$ ${\displaystyle \mathbb {Q} ,}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {C} ,}$ ${\displaystyle \sigma }$ $${\displaystyle {\begin{alignedat}{3}{\mathcal {Q}}&=(\mathbb {Q} ,\sigma _{f},I_{\mathcal {Q}})\\{\mathcal {R}}&=(\mathbb {R} ,\sigma _{f},I_{\mathcal {R}})\\{\mathcal {C}}&=(\mathbb {C} ,\sigma _{f},I_{\mathcal {C}})\\\end{alignedat}}}$$

3つのケースすべてにおいて、標準的な署名は^[8] で与えられ、 $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$ ${\displaystyle S_{f}=\{+,\times ,-,0,1\}}$ $${\displaystyle {\begin{alignedat}{3}\operatorname {ar} _{f}&(+)&&=2,\\\operatorname {ar} _{f}&(\times )&&=2,\\\operatorname {ar} _{f}&(-)&&=1,\\\operatorname {ar} _{f}&(0)&&=0,\\\operatorname {ar} _{f}&(1)&&=0.\\\end{alignedat}}}$$

解釈機能は次のとおりです。 ${\displaystyle I_{\mathcal {Q}}}$

${\displaystyle I_{\mathcal {Q}}(+):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$有理数の加算であり、

${\displaystyle I_{\mathcal {Q}}(\times ):\mathbb {Q} \times \mathbb {Q} \to \mathbb {Q} }$有理数の乗算であり、

${\displaystyle I_{\mathcal {Q}}(-):\mathbb {Q} \to \mathbb {Q} }$は各有理数を ${\displaystyle x}$ ${\displaystyle -x,}$

${\displaystyle I_{\mathcal {Q}}(0)\in \mathbb {Q} }$数であり、 ${\displaystyle 0,}$

${\displaystyle I_{\mathcal {Q}}(1)\in \mathbb {Q} }$番号は ${\displaystyle 1;}$

およびおよびも同様に定義される。^[8] ${\displaystyle I_{\mathcal {R}}}$ ${\displaystyle I_{\mathcal {C}}}$

しかし、体ではない整数環 も同様に -構造である。実際、体公理のいずれかが-構造において成立する必要はない。 ${\displaystyle \mathbb {Z} }$ ${\displaystyle \sigma _{f}}$ ${\displaystyle \sigma _{f}}$

順序付き体のシグネチャには、またはなどの追加の二項関係が必要です。したがって、そのようなシグネチャの構造は、通常の緩い意味での代数構造であっても、代数ではありません。 ${\displaystyle \,<\,}$ ${\displaystyle \,\leq ,\,}$

集合論の通常のシグネチャには、単一の二項関係が含まれます。 このシグネチャの構造は、要素のセットと、これらの要素上の二項関係としての関係の解釈で構成されます。 ${\displaystyle \in .}$ ${\displaystyle \in }$

誘導された部分構造と閉部分集合

${\displaystyle {\mathcal {A}}}$は、（誘導）部分構造と呼ばれます。 ${\displaystyle {\mathcal {B}}}$

• ${\displaystyle {\mathcal {A}}}$同じ署名を持つ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle \sigma ({\mathcal {A}})=\sigma ({\mathcal {B}});}$
• のドメインはのドメインに含まれ、 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}:}$ ${\displaystyle |{\mathcal {A}}|\subseteq |{\mathcal {B}}|;}$
• すべての機能と関係の記号の解釈は一致する ${\displaystyle |{\mathcal {A}}|.}$

この関係の通常の表記は ${\displaystyle {\mathcal {A}}\subseteq {\mathcal {B}}.}$

構造の定義域の部分集合は、関数の下で閉じている場合、つまり、次の条件が満たされる場合、閉じていると呼ばれます。すべての自然数に対して、すべての-項関数記号（のシグネチャ内）とすべての要素を-組に適用した結果は、再び の要素になります。 ${\displaystyle B\subseteq |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle n,}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle b_{1},b_{2},\dots ,b_{n}\in B,}$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle b_{1}b_{2}\dots b_{n}}$ ${\displaystyle B:}$ ${\displaystyle f(b_{1},b_{2},\dots ,b_{n})\in B.}$

任意の部分集合に対して、を含む最小の閉部分集合が存在する。これはによって生成される閉部分集合、またはの包と呼ばれ、または で表される。演算子はの部分集合の集合上の有限閉包演算子である。 ${\displaystyle B\subseteq |{\mathcal {A}}|}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle B.}$ ${\displaystyle B,}$ ${\displaystyle B,}$ ${\displaystyle \langle B\rangle }$ ${\displaystyle \langle B\rangle _{\mathcal {A}}}$ ${\displaystyle \langle \rangle }$ ${\displaystyle |{\mathcal {A}}|}$

およびが閉部分集合である場合、 はの誘導部分構造であり、は σ のすべての記号ににおけるその解釈の への制約を割り当てます。逆に、誘導部分構造のドメインは閉部分集合です。 ${\displaystyle {\mathcal {A}}=(A,\sigma ,I)}$ ${\displaystyle B\subseteq A}$ ${\displaystyle (B,\sigma ,I')}$ ${\displaystyle {\mathcal {A}},}$ ${\displaystyle I'}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {A}}.}$

構造の閉部分集合（または誘導部分構造）は格子を形成します。2つの部分集合の交わりはそれらの共通部分です。2つの部分集合の結合は、それらの和によって生成される閉部分集合です。普遍代数は、構造の部分構造の格子を詳細に研究します。

例

を再び体の標準的な符号とします。自然な方法で -構造として捉えると、有理数は実数の部分構造を形成し、実数は複素数の部分構造を形成します。有理数は、体の公理を満たす実数（または複素数）の最小の部分構造です。 ${\displaystyle \sigma =\{+,\times ,-,0,1\}}$ ${\displaystyle \sigma }$

整数の集合は、実数のさらに小さな部分構造を与えますが、これは体ではありません。実際、整数は、このシグネチャを用いて空集合によって生成される実数の部分構造です。抽象代数において、このシグネチャにおける体の部分構造に対応する概念は、部分体ではなく部分環です。

グラフを定義する最も明白な方法は、単一の2項関係記号 で構成されるシグネチャを持つ構造です。グラフの頂点は構造のドメインを形成し、2つの頂点 と に対して は、と が辺で接続されていることを意味します。このエンコーディングでは、誘導部分構造 の概念は部分グラフの概念よりも制限的です。たとえば、が辺で接続された2つの頂点で構成されるグラフであるとし、が同じ頂点で構成されるが辺は含まれないグラフであるとします。は のサブグラフですが、誘導部分構造ではありません。グラフ理論において誘導部分構造に対応する概念は、誘導部分グラフです。 ${\displaystyle \sigma }$ ${\displaystyle E.}$ ${\displaystyle a}$ ${\displaystyle b,}$ ${\displaystyle (a,b)\!\in {\text{E}}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G,}$

準同型写像と埋め込み

準同型

同じシグネチャσを持つ2つの構造とが与えられたとき、からへの( σ-)準同型写像は、関数と関係を保存する写像である。より正確には、 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle h:|{\mathcal {A}}|\rightarrow |{\mathcal {B}}|}$

• σ のすべてのn項関数記号fと任意の要素に対して、次の式が成り立ちます。 ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$

${\displaystyle h(f(a_{1},a_{2},\dots ,a_{n}))=f(h(a_{1}),h(a_{2}),\dots ,h(a_{n}))}$。

• σ と任意の要素のすべてのn項関係記号Rに対して、次の含意が成り立ちます。 ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\implies (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

ここで、はそれぞれ構造 内の関係記号の解釈です。 ${\displaystyle R^{\mathcal {A}}}$ ${\displaystyle R^{\mathcal {B}}}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

からへの準同型hは通常 と表されますが、技術的には関数hは2 つの構造 の領域の間です。 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$ ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle |{\mathcal {B}}|}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

すべての署名 σ に対して、 σ 構造をオブジェクトとして、σ 準同型を射として持つ具体的な カテゴリσ- Homが存在します。

準同型は、上記の逆の帰結も成り立つ場合、強準同型と呼ばれることがあります。より正確には、 ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

• σのn項関係記号Rと任意の元に対して、次が存在し、^[9] ${\displaystyle a_{1},a_{2},\dots ,a_{n}\in |{\mathcal {A}}|}$ ${\displaystyle (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$ ${\displaystyle a_{1}',a_{2}',\dots ,a_{n}'\in |{\mathcal {A}}|}$ ${\displaystyle (a_{1}',a_{2}',\dots ,a_{n}')\in R^{\mathcal {A}}}$ ${\displaystyle h(a_{1}')=h(a_{1}),\,h(a_{2}')=h(a_{2}),\,\dots ,\,h(a_{n}')=h(a_{n}).}$

強準同型は、上で定義されたカテゴリ σ- Homのサブカテゴリを生じます。

埋め込み

(σ-)準同型写像は、それが単射であり、 ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

• σと任意の要素のすべてのn項関係記号Rに対して、次の同値性が成り立ちます。 ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$

${\displaystyle (a_{1},a_{2},\dots ,a_{n})\in R^{\mathcal {A}}\iff (h(a_{1}),h(a_{2}),\dots ,h(a_{n}))\in R^{\mathcal {B}}}$

（ここで、はそれぞれ構造 内の関係記号の解釈です）。 ${\displaystyle R^{\mathcal {A}}}$ ${\displaystyle R^{\mathcal {B}}}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$

したがって、埋め込みは、単射な強準同型写像と同じものである。σ-構造とσ-埋め込みの圏σ- Embは、 σ- Homの具体的な部分圏である。

誘導された部分構造はσ- Embの部分オブジェクトに対応する。σ が関数記号のみを持つ場合、 σ- Embはσ- Homの単射の部分圏となる。この場合、誘導された部分構造も σ- Homの部分オブジェクトに対応する。

例

上で見たように、グラフを構造として符号化する標準的な手法では、誘導された部分構造はまさに誘導された部分グラフです。しかし、グラフ間の準同型性は、グラフを符号化する2つの構造間の準同型性と同じです。前の節の例では、Gの部分グラフHは誘導されていませんが、恒等写像 id:  H  →  Gは準同型です。この写像は実際にはカテゴリ σ- Homにおける単射であり、したがってHはGの部分対象ですが、誘導された部分構造ではありません。

準同型問題

次の問題は準同型問題として知られています。

2 つの有限構造と有限関係シグネチャが与えられた場合、準同型を見つけるか、そのような準同型が存在しないことを示します。 ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$

あらゆる制約充足問題（CSP）は準同型問題への翻訳が可能です。^[10]したがって、CSPの複雑さは有限モデル理論の方法を用いて研究することができます。

もう一つの応用はデータベース理論です。データベースのリレーショナルモデルは本質的にリレーショナル構造と同一です。データベースに対する連言クエリは、データベースモデルと同じシグネチャを持つ別の構造で記述できることがわかります。リレーショナルモデルからクエリを表す構造への準同型性は、クエリの解と同一です。これは、連言クエリの問題が準同型性の問題でもあることを示しています。

構造と一階述語論理

構造は「一階構造」と呼ばれることがある。これは誤解を招く。なぜなら、その定義には特定の論理に結び付けられる要素が何もなく、実際には普遍代数で使用されるような一階論理の非常に限定された断片と二階論理の両方の意味対象として適しているからである。一階論理とモデル理論との関連では、 「何のモデルか？」という問いに明確な答えがない場合でも、 構造はしばしばモデルと呼ばれる。

満足度関係

各一階構造は、 言語の式すべてに対して、その言語の式と、その要素として解釈される各要素を表す定数記号からなる満足関係を持つ。この関係は、タルスキのTスキーマを用いて帰納的に定義される。 ${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$ ${\displaystyle {\mathcal {M}}\vDash \phi }$ ${\displaystyle \,\phi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle M,}$

の言語が の言語と同じであり、 のすべての文が によって満たされる場合、その構造は理論のモデルであると言われます。したがって、たとえば、「環」は環の言語の構造であり、環の公理のそれぞれを満たし、 ZFC 集合論のモデルは集合論の言語の構造であり、ZFC 公理のそれぞれを満たします。 ${\displaystyle {\mathcal {M}}}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {M}}.}$

定義可能な関係

構造のユニバース（ドメイン）上の-項関係は、 となるような式がある場合、定義可能（または明示的に定義可能cf. Beth 定義可能性、または-定義可能、または下記 cf.のパラメータを使用して定義可能）であると言われます。 言い換えると、が正しいような式がある場合に限り、 が定義可能です。 ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \emptyset }$ ${\displaystyle \emptyset }$ ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$ $${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$ ${\displaystyle R}$ ${\displaystyle \varphi }$ $${\displaystyle (a_{1},\ldots ,a_{n})\in R\Leftrightarrow {\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})}$$

重要な特別なケースとして、特定の元が定義可能であるというものがあります。の元がで定義可能であるのは、次の式が存在する場合のみです。 ${\displaystyle m}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi (x)}$ $${\displaystyle {\mathcal {M}}\vDash \forall x(x=m\leftrightarrow \varphi (x)).}$$

パラメータによる定義可能性

関係がパラメータ付きで定義可能（または定義可能）であるとは、からパラメータ付きの式^{[説明が必要]}が存在し、 がを使用して定義可能である場合 です。構造のすべての要素は、その要素自体をパラメータとして使用して定義可能です。 ${\displaystyle R}$ ${\displaystyle |{\mathcal {M}}|}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R}$ ${\displaystyle \varphi .}$

著者によっては、 definable をパラメータなしで定義可能な意味で使用している場合があり^{[引用が必要]} 、他の著者はパラメータ付きで定義可能な意味で使用しています^{[引用が必要]}。一般的に、 definable はパラメータなしで定義可能であることを意味する という慣習は集合理論家の間ではより一般的であり、その逆の慣習はモデル理論家の間ではより一般的です。

暗黙的な定義可能性

上で述べたように、の宇宙上の-ary 関係は、次のような式が存在する場合に明示的に定義可能となる。 ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$ $${\displaystyle R=\{(a_{1},\ldots ,a_{n})\in M^{n}:{\mathcal {M}}\vDash \varphi (a_{1},\ldots ,a_{n})\}.}$$

ここで、関係を定義するために使用される式は、のシグネチャの上でなければならないので、それ自体を言及することはできない。なぜなら、はのシグネチャには含まれていないからである。拡張言語に、の言語と新しい記号を含む 式があり、関係が、その関係が、その関係が、暗黙的に定義可能である唯一の関係である場合、は、暗黙的に定義可能であると言われる。 ${\displaystyle \varphi }$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \varphi }$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}.}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle R,}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}\vDash \varphi ,}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}.}$

ベスの定理によれば、暗黙的に定義可能な関係はすべて明示的に定義可能です。

多ソート構造

上記で定義された構造は、より一般的な構造と区別するために、 1ソート構造を使用する。多ソート構造。多ソート構造は任意の数のドメインを持つことができます。ソートはシグネチャの一部であり、異なるドメインの名前の役割を果たします。多ソートシグネチャは、多ソート構造の関数と関係がどのソート上で定義されているかを指定します。したがって、関数シンボルや関係シンボルのアリティは、自然数ではなく、ソートの組などのより複雑なオブジェクトである必要があります。

例えば、ベクトル空間は、次のように2ソート構造とみなすことができます。ベクトル空間の2ソートシグネチャは、2つのソートV (ベクトル) とS (スカラー) と、以下の関数記号から構成されます。

+ Sおよび × Sのアリティ ( S、  S ;  S )。 − Sのアリティ ( S ;  S )。 0 Sと 1 Sのアリティ ( S )。

+ Vのアリティ ( V、  V ;  V )。 −アリティのV ( V ;  V )。 0 Vのarity（V）。

× のアリティ ( S、  V ;  V )。

V が体F上のベクトル空間である場合、対応する 2 つのソート構造は、ベクトル領域、スカラー領域、およびベクトル ゼロ、スカラー ゼロ、スカラー乗算などの明らかな関数から構成されます。 ${\displaystyle {\mathcal {V}}}$ ${\displaystyle |{\mathcal {V}}|_{V}=V}$ ${\displaystyle |{\mathcal {V}}|_{S}=F}$ ${\displaystyle 0_{V}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{V}}$ ${\displaystyle 0_{S}^{\mathcal {V}}=0\in |{\mathcal {V}}|_{S}}$ ${\displaystyle \times ^{\mathcal {V}}:|{\mathcal {V}}|_{S}\times |{\mathcal {V}}|_{V}\rightarrow |{\mathcal {V}}|_{V}}$

多ソート構造は、少しの努力で回避できる場合でも、便利なツールとしてしばしば用いられます。しかし、一般化を明示的に行うのは単純かつ面倒（したがって、報われない）であるため、厳密に定義されることはほとんどありません。

ほとんどの数学的試みにおいて、種類はあまり考慮されていない。しかし、多種類論理は自然に型理論へと導く。バート・ジェイコブズが述べているように、「論理は常に型理論上の論理である」。この強調は、型理論上の論理が一つの（「全体」）カテゴリーにカテゴリー的に対応し、論理を捉え、別の（「基本」）カテゴリーに繊維化され、型理論を捉えるため、範疇論理へと導く。^[11]

その他の一般化

部分代数

普遍代数とモデル理論はどちらも、署名と公理の集合によって定義される（構造または）代数のクラスを研究します。モデル理論の場合、これらの公理は一階文の形式をとります。普遍代数の形式主義ははるかに制限的で、本質的に、項間の普遍量化方程式の形式をとる一階文のみを許可します（例：x y  ( x  +  y  =  y  +  x )）。その結果、署名の選択はモデル理論よりも普遍代数の方が重要になります。たとえば、2項関数記号 × と定数記号 1 からなる署名の群のクラスは基本クラスですが、多様体ではありません。普遍代数は、単項関数記号⁻¹を追加することでこの問題を解決します。 ${\displaystyle \forall }$   ${\displaystyle \forall }$

体の場合、この戦略は加算にのみ有効です。乗算では、0 には逆元がないため、この戦略は機能しません。この問題に対処するためのアドホックな試みとしては、0 ⁻¹  = 0 と定義することが挙げられます。（この試みは、本質的にこの定義では 0 × 0 ⁻¹  = 1 が成り立たないために失敗に終わります。）したがって、部分関数、つまり定義域の部分集合上でのみ定義される関数を自然に許容することになります。しかし、部分構造、準同型、恒等写像といった概念を一般化する明白な方法はいくつかあります。

型付き言語の構造

型理論では、多くの種類の変数が存在し、それぞれが型を持ちます。型は帰納的に定義されます。例えば、2つの型δとσが与えられた場合、型σのオブジェクトから型δのオブジェクトへの関数を表す型σ → δも存在します。型付き言語（通常の一階述語意味論）の構造は、各型のオブジェクトの別々の集合を含む必要があり、関数型の場合、構造はその型の各オブジェクトによって表される関数に関する完全な情報を持つ必要があります。

高階言語

二階論理の記事で議論されているように、高階論理には複数の意味論が考えられます。完全な高階意味論を使用する場合、構造は型0のオブジェクトに対するユニバースのみを持つ必要があり、Tスキーマは、高階型に対する量指定子が非引用的に真である場合にのみモデルによって満たされるように拡張されます。一階意味論を使用する場合、複数のソートを持つ一階言語の場合と同様に、高階型ごとに追加のソートが追加されます。

適切なクラスである構造

集合論と圏論の研究では、議論の領域が集合ではなく真クラスである構造を考えることが有用な場合があります。これらの構造は、前述の「集合モデル」と区別するために、クラスモデルと呼ばれることがあります。領域が真クラスである場合、それぞれの関数と関係記号も真クラスで表現できます。

バートランド・ラッセルの『プリンキピア・マテマティカ』では、構造体もそのドメインとして適切なクラスを持つことが許されていました。

参照

• 数学的構造 – 追加の数学的対象

注記

1. 一部の著者は、関数だけでなく関係も許容するように普遍代数を一般化するときに、構造を「代数」と呼んでいます。
2. ホッジス、ウィルフリッド (2009). 「機能モデリングと数理モデル」. アンソニー・マイヤーズ編.技術と工学の哲学. 科学哲学ハンドブック. 第9巻. エルゼビア. ISBN 978-0-444-51667-1。
3. Libkin, Leonid (2004). 『有限モデル理論の要素』 . doi :10.1007/978-3-662-07003-1. ISBN 978-3-642-05948-3。
4. オックスフォード英語辞典、sv「model, n., sense I.8.b」、2023年7月。オックスフォード大学出版局。このようなクラスが伝統的な実数体系のモデルを構成するという事実は、デデキントによって指摘された。[1]
5. クワイン、ウィラード VO (1940).数理論理学. 第6巻. ノートン.
6. 空の定義域を許容する論理体系は包含論理として知られている。
7. これらの規則の結果として、表記法はドメインの基数を参照するためにも使用されることがありますが、実際にはこれによって混乱が生じることはありません。 ${\displaystyle |{\mathcal {A}}|}$ ${\displaystyle {\mathcal {A}}.}$
8. 注:左側のとは の符号 を表し、右側の は の自然数 を表し、 の単項演算マイナスを表します。 ${\displaystyle \mathbf {0} ,\mathbf {1} ,}$ ${\displaystyle \mathbf {-} }$ ${\displaystyle S_{f}.}$ ${\displaystyle 0,1,2,}$ ${\displaystyle -}$ ${\displaystyle N_{0}}$ ${\displaystyle \mathbb {Q} .}$
9. ラウテンバーグ、ヴォルフガング (2010).数理論理学簡潔入門. doi :10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6。
10. ジェイボンズ、ピーター; コーエン、デイヴィッド; ピアソン、ジャスティン (1998)、「制約と普遍代数」、数学と人工知能の年報、24 ( 1–4 ): 51–67、doi :10.1023/A:1018941030227、S2CID  15244028。
11. ジェイコブス、バート（1999）、カテゴリー論理と型理論、エルゼビア、  pp.1-4、ISBN 9780080528700

参考文献

• バリス、スタンリー・N.; サンカッパナヴァール、H.P. (1981) 『普遍代数の講座』ベルリン、ニューヨーク：シュプリンガー・フェアラーク
• チャン、チェン・チュン;キースラー、H.ジェローム(1989) [1973]、モデル理論、エルゼビア、ISBN 978-0-7204-0692-4
• Diestel, Reinhard (2005) [1997], グラフ理論, Graduate Texts in Mathematics, vol. 173 (第3版), ベルリン, ニューヨーク: Springer-Verlag , ISBN 978-3-540-26183-4
• エビングハウス、ハインツ＝ディーター。フルム、ヨルグ。 Thomas、Wolfgang (1994)、Mathematical Logic (第 2 版)、ニューヨーク: Springer、ISBN 978-0-387-94258-2
• Hinman, P. (2005)、『数学論理の基礎』、AK Peters、ISBN 978-1-56881-262-5
• ホッジス、ウィルフリッド（1993）、モデル理論、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-30442-9
• ホッジス、ウィルフリッド（1997年）、短縮モデル理論、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-58713-6
• マーカー、デイヴィッド（2002）、モデル理論入門、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-98760-6
• ポイザット、ブルーノ（2000）、モデル理論講座：現代数学論理入門、ベルリン、ニューヨーク：シュプリンガー・フェアラーク、ISBN 978-0-387-98655-5
• ラウテンバーグ、ヴォルフガング（2010）、数理論理学簡潔入門（第3版）、ニューヨーク：シュプリンガーサイエンス+ビジネスメディア、doi：10.1007 / 978-1-4419-1221-3、ISBN 978-1-4419-1220-6
• ロスマーラー、フィリップ（2000）、モデル理論入門、ロンドン：CRCプレス、ISBN 978-90-5699-313-9

外部リンク

• 古典論理学の意味論セクション（スタンフォード哲学百科事典の項目）

Retrieved from "https://en.wikipedia.org/w/index.php?title=Structure_(mathematical_logic)&oldid=1316491800"