構造（数理論理学）

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

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

署名${\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}$-ary) 関数記号${\displaystyle c}$は定数記号と呼ばれ、その解釈は${\displaystyle I(c)}$定義域の定数要素と同一視できる。

構造（したがって解釈関数）が文脈によって与えられる場合、記号と記号の間に表記上の区別は行われない。${\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}}|.}$

標準署名$\displaystyle \sigma _{f}}$フィールドは2 つのバイナリ関数シンボルで構成されます${\displaystyle \mathbf {+} }$そして$\displaystyle \mathbf {\times } }$単項関数記号などの追加の記号を導出できる${\displaystyle \mathbf {-} }$（${\displaystyle \mathbf {+} }$）と2つの定数記号$\displaystyle \mathbf {0} }$そして${\displaystyle \mathbf {1} }$（${\displaystyle \mathbf {+} }$そして$\displaystyle \mathbf {\times } }$それぞれ）。したがって、このシグネチャの構造（代数）は要素の集合から構成される。${\displaystyle A}$2つの二項関数（単項関数で拡張可能）と2つの区別された要素とともに、しかし、それが体の公理のいずれにも適合する必要はない。有理数${\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つのケースすべてにおいて、標準署名が与えられています。 $${\displaystyle \sigma _{f}=(S_{f},\operatorname {ar} _{f})}$$^[ 8 ^]​${\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;}$

そして${\displaystyle I_{\mathcal {R}}}$そして${\displaystyle I_{\mathcal {C}}}$も同様に定義される。^{[ 8 ]}

しかし指輪は${\displaystyle \mathbb {Z} }$整数のフィールドではないものも、${\displaystyle \sigma _{f}}$-構造も同様です。実際、フィールドの公理のいずれかが成り立つという要件はありません。${\displaystyle \sigma _{f}}$-構造。

順序付きフィールドの署名には、次のような追加の二項関係が必要です。${\displaystyle \,<\,}$または${\displaystyle \,\leq ,\,}$したがって、そのようなシグネチャの構造は、通常の緩やかな意味での代数構造ではあるものの、代数ではない。

集合論の通常のシグネチャには、単一の二項関係が含まれる。${\displaystyle \in .}$ この署名の構造は、一連の要素と、その解釈から成ります。${\displaystyle \in }$これらの要素間の関係を二項関係として表す。

させて${\displaystyle \sigma =\{+,\times ,-,0,1\}}$再びフィールドの標準署名となる。${\displaystyle \sigma }$自然な形で構造化すると、有理数は実数の部分構造を形成し、実数は複素数の部分構造を形成します。有理数は、実数（または複素数）の部分構造の中で、体公理を満たす最小の部分構造です。

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

グラフを定義する最も分かりやすい方法は、シグネチャを持つ構造である。${\displaystyle \sigma }$単一の二項関係記号から構成される${\displaystyle E.}$グラフの頂点は構造のドメインを形成し、2 つの頂点については${\displaystyle a}$そして${\displaystyle b,}$${\displaystyle (a,b)\!\in {\text{E}}}$つまり${\displaystyle a}$そして${\displaystyle b}$は辺で接続されている。この符号化では、誘導部分構造の概念は部分グラフの概念よりも制限的である。例えば、${\displaystyle G}$を、辺で結ばれた2つの頂点からなるグラフとし、${\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から${\displaystyle {\mathcal {A}}}$に${\displaystyle {\mathcal {B}}}$通常は次のように表記されます。${\displaystyle h:{\mathcal {A}}\rightarrow {\mathcal {B}}}$技術的には関数hは定義域の間にあるが${\displaystyle |{\mathcal {A}}|}$、${\displaystyle |{\mathcal {B}}|}$2つの構造物のうち${\displaystyle {\mathcal {A}}}$、${\displaystyle {\mathcal {B}}}$。

すべてのシグネチャ σ に対して、σ-構造を対象とし、σ-準同型を射とする具体的な圏σ- Homが存在する。

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

• σ の任意のn項関係記号Rと任意の要素に対して${\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}).}$^{[ 9 ]}

強準同型写像は、上で定義した圏σ- 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の複雑さは有限モデル理論の方法を使用して研究できます。

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

各一次構造${\displaystyle {\mathcal {M}}=(M,\sigma ,I)}$満足度関係がある${\displaystyle {\mathcal {M}}\vDash \phi }$すべての数式に対して定義されています${\displaystyle \,\phi }$ 言語で${\displaystyle {\mathcal {M}}}$各要素の定数記号とともに${\displaystyle M,}$これは、その要素として解釈される。この関係は、タルスキのT図式を用いて帰納的に定義される。

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

1${\displaystyle n}$-項関係${\displaystyle R}$宇宙（つまり領域）において${\displaystyle M}$構造の${\displaystyle {\mathcal {M}}}$定義可能である（または明示的に定義可能である、Bethの定義可能性を参照）と言われている。${\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 \forall }$ x ${\displaystyle \forall }$y  ( x  + y = y + x ) 。その結果として、普遍代数では、モデル理論よりも符号の選択がより重要になります。たとえば、二項関数記号 × と定数記号 1 からなる符号における群のクラスは、基本クラスですが、多様体ではありません。普遍代数では、単項関数記号⁻¹を追加することでこの問題を解決します。     

体の場合、この戦略は加算にのみ有効です。乗算の場合、0 には乗法逆元がないため、この戦略は失敗します。この問題を解決するために、0 ⁻¹  =  0 と定義するという暫定的な試みが考えられます。（この定義では 0  ×  0 ⁻¹  =  1 が成り立たないため、この試みは失敗します。）したがって、部分関数、つまり定義域の部分集合でのみ定義される関数を許容することが自然と導かれます。しかし、部分構造、準同型、恒等などの概念を一般化する明白な方法がいくつかあります。

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

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

集合論や圏論の研究において、議論の領域が集合ではなく固有クラスであるような構造を考察することが有用な場合がある。このような構造は、前述の「集合モデル」と区別するために、クラスモデルと呼ばれることがある。領域が固有クラスである場合、各関数や関係記号も固有クラスで表現することができる。

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