構造 (数理論理学)

テンプレート:Distinguish テンプレート:脚注の不足 普遍代数学およびモデル理論において、構造（こうぞう、テンプレート:Lang-en-short）とは、集合と、その上で定義された有限項の演算および関係の集まりからなるものをいう。

普遍代数学は、群・環・体・線型空間といった代数的構造を一般化した構造を研究する。普遍代数という語は、関係記号をもたない一階理論の構造に対して用いられる。モデル理論はより広い範囲を扱い、集合論のモデルのような基礎論的構造を含む、より一般的な一階理論を対象とする。

モデル理論の観点からは、構造は一階述語論理の意味論を定義するために用いられる対象である。タルスキの真理論やタルスキ流意味論も参照。

モデル理論において、与えられた理論のすべての文を充足する構造を、その理論のモデルという。論理学者は構造を「解釈」と呼ぶことがあるが、モデル理論において「解釈」という語は一般に（関連はするが）異なる意味をもつ。解釈 (モデル理論)を参照。

歴史

テンプレート:節スタブ 数理論理学の文脈において、「モデル」という語が最初に用いられたのは1940年、哲学者ウィラード・ヴァン・オーマン・クワインによるもので、集合論の発展の先駆者である数学者リヒャルト・デーデキント（1831年 - 1916年）への言及においてであった。 「モデルの理論」（theory of models）という語は、テンプレート:仮リンクの一員であったアルフレト・タルスキによって1954年に作られた。

19世紀以来、公理系の無矛盾性を証明する主要な方法の一つは、その公理系に対するモデルを与えることであった。

定義

形式的には、構造は三つ組 $𝒜=(A,\sigma ,I)$ として定義される。ここで $A$ は領域、$\sigma$ はシグネチャ、$I$ はシグネチャを領域上でどのように解釈するかを指定する解釈関数である。構造が特定のシグネチャ $\sigma$ をもつことを示すために、これを $\sigma$-構造と呼ぶことがある。

領域

テンプレート:Main 構造の領域は任意の集合であり、その構造のテンプレート:Em、（特に普遍代数学では）テンプレート:Em、（特にモデル理論では）テンプレート:Em、あるいはテンプレート:Emとも呼ばれる。古典的な一階述語論理においては、構造の定義はテンプレート:仮リンクを禁じているテンプレート:要出典。

$𝒜$ の領域を表すのに $\mathrm{dom}(𝒜)$ や $|𝒜|$ という記法が用いられることもあるが、構造とその領域とを記法上区別しないことも多い（すなわち、同じ記号 $𝒜$ が構造とその領域の両方を指す）。

シグネチャ

テンプレート:Main 構造のシグネチャ $\sigma =(S,\mathrm{ar})$ は次のものからなる。

• 関数記号と関係記号の集合 $S$
• 各記号 $s$ に自然数 $n=\mathrm{ar}(s)$ を割り当てる関数 $\mathrm{ar}:S\to {\mathbb{N}}_0$

記号 $s$ に対する自然数 $n=\mathrm{ar}(s)$ は $s$ のアリティと呼ばれる。これは $s$ の解釈のアリティだからであるテンプレート:要説明。

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

解釈関数

$𝒜$ の解釈関数 $I$ は、シグネチャの記号に関数と関係を割り当てる。アリティ $n$ の各関数記号 $f$ には、領域上の$n$ 項関数 $f^{𝒜}=I(f)$ が割り当てられる。アリティ $n$ の各関係記号 $R$ には、領域上の $n$ 項関係 $R^{𝒜}=I(R)\subseteq A^{\mathrm{ar(R)}}$ が割り当てられる。0項（$=0$ 項）の関数記号 $c$ は定数記号と呼ばれる。その解釈 $I(c)$ は領域の一つの定数元と同一視できるからである。

構造（したがって解釈関数）が文脈から明らかな場合、記号 $s$ とその解釈 $I(s)$ は記法上区別されない。例えば $f$ が $𝒜$ の二項関数記号であるとき、$f^{𝒜}:|𝒜{|}^2\to |𝒜|$ ではなく単に $f:{𝒜}^2\to 𝒜$ と書く。

例

体の標準的なシグネチャ ${\sigma }_f$ は二つの二項関数記号 $\mathbf{+}$ と $\mathbf{\times }$ からなり、そこから単項関数記号 $\mathbf{-}$（$\mathbf{+}$ によって一意に定まる）や二つの定数記号 $\mathrm{𝟎}$、$\mathrm{𝟏}$（それぞれ $\mathbf{+}$、$\mathbf{\times }$ によって一意に定まる）といった記号を導出できる。 したがってこのシグネチャに対する構造（代数）は、元の集合 $A$ と二つの二項関数（さらに単項関数を加えてもよい）および二つの指定された元からなるが、体の公理を満たすことは要求されない。有理数 $\mathbb{Q}$、実数 $ℝ$、複素数 $ℂ$ は、他の任意の体と同様、自然な仕方で $\sigma$-構造とみなすことができる。 $$\begin{array}{cc}𝒬& =(\mathbb{Q},{\sigma }_f,I_{𝒬})\\ ℛ& =(ℝ,{\sigma }_f,I_{ℛ})\\ 𝒞& =(ℂ,{\sigma }_f,I_{𝒞})\end{array}$$

いずれの場合も、標準的なシグネチャは $${\sigma }_f=(S_f,{\mathrm{ar}}_f)$$ で与えられ、$S_f=\{+,\times ,-,0,1\}$ かつ $$\begin{array}{cccc}{\mathrm{ar}}_f& (+)& & =2,\\ {\mathrm{ar}}_f& (\times )& & =2,\\ {\mathrm{ar}}_f& (-)& & =1,\\ {\mathrm{ar}}_f& (0)& & =0,\\ {\mathrm{ar}}_f& (1)& & =0.\end{array}$$ である。

解釈関数 $I_{𝒬}$ は次の通りである。

$I_{𝒬}(+):\mathbb{Q}\times \mathbb{Q}\to \mathbb{Q}$ は有理数の加法、

$I_{𝒬}(\times ):\mathbb{Q}\times \mathbb{Q}\to \mathbb{Q}$ は有理数の乗法、

$I_{𝒬}(-):\mathbb{Q}\to \mathbb{Q}$ は各有理数 $x$ を $-x$ に写す関数、

$I_{𝒬}(0)\in \mathbb{Q}$ は数 $0$、

$I_{𝒬}(1)\in \mathbb{Q}$ は数 $1$ である。

$I_{ℛ}$ と $I_{𝒞}$ も同様に定義される。

しかし体ではない整数環 $\mathbb{Z}$ もまた、同じ仕方で ${\sigma }_f$-構造である。実際、${\sigma }_f$-構造において体の公理のテンプレート:Emが成り立つことは要求されていない。

順序体のシグネチャには $<$ や $\le$ といった追加の二項関係が必要であり、したがってそのようなシグネチャに対する構造は代数ではない。もっとも、それらは通常の緩やかな意味では当然代数的構造である。

集合論の通常のシグネチャは単一の二項関係 $\in$ を含む。このシグネチャに対する構造は、元の集合と、それらの元の上の二項関係としての $\in$ の解釈からなる。

誘導部分構造と閉部分集合

$𝒜$ が $ℬ$ の（誘導）部分構造であるとは、次が成り立つことをいう。

• $𝒜$ と $ℬ$ が同じシグネチャをもつ: $\sigma (𝒜)=\sigma (ℬ)$
• $𝒜$ の領域が $ℬ$ の領域に含まれる: $|𝒜|\subseteq |ℬ|$
• すべての関数記号・関係記号の解釈が $|𝒜|$ 上で一致する

この関係の通常の記法は $𝒜\subseteq ℬ$ である。

構造 $𝒜$ の領域の部分集合 $B\subseteq |𝒜|$ が閉じているとは、$𝒜$ の関数の下で閉じていること、すなわち次の条件が満たされることをいう。任意の自然数 $n$、（$𝒜$ のシグネチャにおける）任意の $n$ 項関数記号 $f$、およびすべての元 $b_1,b_2,\dots ,b_n\in B$ に対して、$n$ 項組 $b_1{b}_2\dots b_n$ に $f$ を適用した結果が再び $B$ の元である: $f(b_1,b_2,\dots ,b_n)\in B$。

任意の部分集合 $B\subseteq |𝒜|$ に対して、$B$ を含む $|𝒜|$ の最小の閉部分集合が存在する。これは $B$ によって生成される閉部分集合、あるいは $B$ の包と呼ばれ、$⟨B⟩$ または $⟨B{⟩}_{𝒜}$ と書かれる。作用素 $⟨⟩$ は $|𝒜|$ の部分集合の集合上の有限閉包作用素である。

$𝒜=(A,\sigma ,I)$ であり $B\subseteq A$ が閉部分集合であるとき、$(B,\sigma ,I^{\prime })$ は $𝒜$ の誘導部分構造である。ここで $I^{\prime }$ は σ の各記号に、$𝒜$ におけるその解釈の $B$ への制限を割り当てる。逆に、誘導部分構造の領域は閉部分集合である。

構造の閉部分集合（あるいは誘導部分構造）は束をなす。二つの部分集合の交わりはそれらの共通部分である。二つの部分集合の結びは、それらの合併によって生成される閉部分集合である。普遍代数学は構造の部分構造のなす束を詳細に研究する。

例

再び $\sigma =\{+,\times ,-,0,1\}$ を体の標準的なシグネチャとする。自然な仕方で $\sigma$-構造とみなすとき、有理数は実数の部分構造をなし、実数は複素数の部分構造をなす。有理数は、体の公理をも満たす実数（あるいは複素数）の最小の部分構造である。

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

グラフを定義する最も自明な方法は、単一の二項関係記号 $E$ からなるシグネチャ $\sigma$ をもつ構造とすることである。グラフの頂点が構造の領域をなし、二つの頂点 $a$、$b$ に対して $(a,b)\in \text{E}$ は $a$ と $b$ が辺で結ばれていることを意味する。この符号化の下では、誘導部分構造の概念はテンプレート:仮リンクの概念よりも制限的である。例えば $G$ を辺で結ばれた二つの頂点からなるグラフ、$H$ を同じ頂点をもつが辺をもたないグラフとすると、$H$ は $G$ の部分グラフであるが誘導部分構造ではない。誘導部分構造に対応するグラフ理論の概念は誘導部分グラフである。

準同型と埋め込み

準同型

同じシグネチャ σ をもつ二つの構造 $𝒜$、$ℬ$ が与えられたとき、$𝒜$ から $ℬ$ への（σ-）準同型とは、関数と関係を保つ写像 $h:|𝒜|\to |ℬ|$ のことである。より正確には次が成り立つ。

• σ の任意の n 項関数記号 f と任意の元 $a_1,a_2,\dots ,a_n\in |𝒜|$ に対して、次の等式が成り立つ。

$h(f(a_1,a_2,\dots ,a_n))=f(h(a_1),h(a_2),\dots ,h(a_n))$

• σ の任意の n 項関係記号 R と任意の元 $a_1,a_2,\dots ,a_n\in |𝒜|$ に対して、次の含意が成り立つ。

$(a_1,a_2,\dots ,a_n)\in R^{𝒜}⟹(h(a_1),h(a_2),\dots ,h(a_n))\in R^{ℬ}$

ここで $R^{𝒜}$、$R^{ℬ}$ はそれぞれ構造 $𝒜$、$ℬ$ における関係記号 $R$ の解釈である。

$𝒜$ から $ℬ$ への準同型 h は通常 $h:𝒜\to ℬ$ と表記されるが、厳密には関数 h は二つの構造 $𝒜$、$ℬ$ の領域 $|𝒜|$、$|ℬ|$ の間の写像である。

任意のシグネチャ σ に対して、σ-構造を対象とし σ-準同型を射とするテンプレート:仮リンク σ-Hom が存在する。

準同型 $h:𝒜\to ℬ$ は、上の含意の逆も成り立つとき強準同型と呼ばれることがある。より正確には次が成り立つ。

• σ の任意の n 項関係記号 R と、$(h(a_1),h(a_2),\dots ,h(a_n))\in R^{ℬ}$ を満たす任意の元 $a_1,a_2,\dots ,a_n\in |𝒜|$ に対して、$({a_1}^{\prime },{a_2}^{\prime },\dots ,{a_n}^{\prime })\in R^{𝒜}$ かつ $h({a_1}^{\prime })=h(a_1),h({a_2}^{\prime })=h(a_2),\dots ,h({a_n}^{\prime })=h(a_n)$ となる ${a_1}^{\prime },{a_2}^{\prime },\dots ,{a_n}^{\prime }\in |𝒜|$ が存在する。

強準同型は、上で定義した圏 σ-Hom の部分圏を与える。

埋め込み

（σ-）準同型 $h:𝒜\to ℬ$ が（σ-）埋め込みであるとは、それが単射であり、かつ次を満たすことをいう。

• σ の任意の n 項関係記号 R と任意の元 $a_1,a_2,\dots ,a_n$ に対して、次の同値が成り立つ。

$(a_1,a_2,\dots ,a_n)\in R^{𝒜}⟺(h(a_1),h(a_2),\dots ,h(a_n))\in R^{ℬ}$

（ここで $R^{𝒜}$、$R^{ℬ}$ はそれぞれ構造 $𝒜$、$ℬ$ における関係記号 $R$ の解釈である。）

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

誘導部分構造は σ-Emb における部分対象に対応する。σ が関数記号のみをもつ場合、σ-Emb は σ-Hom のモノ射のなす部分圏である。この場合、誘導部分構造は σ-Hom における部分対象にも対応する。

例

上で見たように、グラフを構造として標準的に符号化する場合、誘導部分構造はちょうど誘導部分グラフである。しかしグラフ間の準同型は、グラフを符号化する二つの構造の間の準同型と同じものである。前節の例において、$G$ の部分グラフ $H$ は誘導部分グラフではないが、恒等写像 id: H → G は準同型である。この写像は実際、圏 σ-Hom におけるモノ射であり、したがって H は誘導部分構造ではない G の部分対象である。

準同型問題

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

有限関係シグネチャをもつ二つの有限構造 $𝒜$、$ℬ$ が与えられたとき、準同型 $h:𝒜\to ℬ$ を求めるか、そのような準同型が存在しないことを示せ。

すべての制約充足問題（CSP）は準同型問題へ翻訳できる。したがってCSPの計算量は有限モデル理論の手法を用いて研究できる。

もう一つの応用はデータベース理論にある。ここではデータベースの関係モデルは本質的に関係構造と同じものである。データベース上のテンプレート:仮リンクは、データベースモデルと同じシグネチャをもつ別の構造によって記述できることが知られている。関係モデルからクエリを表す構造への準同型は、そのクエリの解と同じものである。このことは、合接クエリ問題もまた準同型問題と等価であることを示している。

構造と一階述語論理

テンプレート:See also 構造は「一階構造」と呼ばれることがある。しかしこれは誤解を招く。というのも、構造の定義において構造を特定の論理と結びつけるものは何もなく、実際、構造は普遍代数学で用いられるような一階述語論理の非常に制限された断片に対しても、二階述語論理に対しても、意味論的対象として適している。一階述語論理およびモデル理論との関連では、構造はしばしばモデルと呼ばれる。「何のモデルか」という問いに明白な答えがない場合でさえそうである。

充足関係

各一階構造 $ℳ=(M,\sigma ,I)$ は充足関係 $ℳ\models \varphi$ をもつ。これは、$ℳ$ の言語に $M$ の各元に対する定数記号（その元として解釈される）を加えた言語におけるすべての論理式 $\varphi$ に対して定義される。 この関係はタルスキのT-スキーマを用いて帰納的に定義される。

構造 $ℳ$ が理論 $T$ のモデルであるとは、$ℳ$ の言語が $T$ の言語と同じであり、$T$ のすべての文が $ℳ$ によって充足されることをいう。例えば「環」とは環の言語に対する構造であって環の公理のそれぞれを満たすものであり、ZFC集合論のモデルとは集合論の言語における構造であってZFCの公理のそれぞれを満たすものである。

定義可能な関係

構造 $ℳ$ の宇宙（すなわち領域）$M$ 上の $n$ 項関係 $R$ が定義可能（あるいはテンプレート:仮リンク、$\mathrm{\varnothing }$-定義可能、$\mathrm{\varnothing }$ からのパラメータで定義可能）であるとは、次を満たす論理式 $\phi (x_1,\dots ,x_n)$ が存在することをいう。 $$R=\{(a_1,\dots ,a_n)\in M^n:ℳ\models \phi (a_1,\dots ,a_n)\}.$$ 言い換えれば、$R$ が定義可能であるのは、 $$(a_1,\dots ,a_n)\in R\iff ℳ\models \phi (a_1,\dots ,a_n)$$ が正しくなるような論理式 $\phi$ が存在するとき、かつそのときに限る。

重要な特別な場合は特定の元の定義可能性である。$M$ の元 $m$ が $ℳ$ において定義可能であるのは、次を満たす論理式 $\phi (x)$ が存在するとき、かつそのときに限る。 $$ℳ\models \mathrm{\forall }x(x=m\leftrightarrow \phi (x)).$$

パラメータ付き定義可能性

関係 $R$ がパラメータ付きで定義可能（あるいは $|ℳ|$-定義可能）であるとは、$ℳ$ からのパラメータをもつ論理式 $\phi$ が存在して、$R$ が $\phi$ を用いて定義可能であることをいうテンプレート:要説明。構造のすべての元は、その元自身をパラメータとして用いれば定義可能である。

定義可能をパラメータなしで定義可能の意味で用いる著者もいればテンプレート:要出典、パラメータ付きで定義可能の意味で用いる著者もいるテンプレート:要出典。大まかに言えば、定義可能をパラメータなしの意味とする慣習は集合論研究者の間でより一般的であり、逆の慣習はモデル理論研究者の間でより一般的である。

暗黙的定義可能性

上で述べたように、$ℳ$ の宇宙 $M$ 上の $n$ 項関係 $R$ が明示的に定義可能であるとは、次を満たす論理式 $\phi (x_1,\dots ,x_n)$ が存在することであった。 $$R=\{(a_1,\dots ,a_n)\in M^n:ℳ\models \phi (a_1,\dots ,a_n)\}.$$

ここで関係 $R$ を定義するために用いられる論理式 $\phi$ は $ℳ$ のシグネチャ上のものでなければならず、したがって $R$ は $ℳ$ のシグネチャに含まれないため、$\phi$ は $R$ 自身に言及できない。もし $ℳ$ の言語と新しい記号 $R$ を含む拡張言語における論理式 $\phi$ が存在し、$ℳ\models \phi$ となる $ℳ$ 上の関係が $R$ のみであるならば、$R$ は $ℳ$ 上で暗黙的に定義可能であるという。

テンプレート:仮リンクにより、暗黙的に定義可能なすべての関係は明示的に定義可能である。

多ソート構造

上で定義した構造は、より一般的なテンプレート:Visible anchorと区別するためにテンプレート:Visible anchorと呼ばれることがある。多ソート構造は任意個の領域をもちうる。ソートはシグネチャの一部であり、異なる領域に対する名前の役割を果たす。多ソートシグネチャはまた、多ソート構造の関数と関係がどのソート上で定義されるかをも規定する。したがって関数記号や関係記号のアリティは、自然数ではなくソートの組といったより複雑な対象でなければならない。

例えば線型空間は、次のようにして二ソート構造とみなすことができる。線型空間の二ソートシグネチャは、二つのソート V（ベクトル用）と S（スカラー用）および次の関数記号からなる。

アリティ (S, S; S) の +S と ×S アリティ (S; S) の −S アリティ (S) の 0S と 1S

アリティ (V, V; V) の +V アリティ (V; V) の −V アリティ (V) の 0V

アリティ (S, V; V) の ×

V が体 F 上の線型空間であるとき、対応する二ソート構造 $𝒱$ はベクトル領域 $|𝒱{|}_V=V$、スカラー領域 $|𝒱{|}_S=F$、およびベクトルの零元 $0_V^{𝒱}=0\in |𝒱{|}_V$、スカラーの零元 $0_S^{𝒱}=0\in |𝒱{|}_S$、スカラー倍 ${\times }^{𝒱}:|𝒱{|}_S\times |𝒱{|}_V\to |𝒱{|}_V$ といった自明な関数からなる。

多ソート構造は、少し工夫すれば避けられる場合でも便利な道具としてしばしば用いられる。しかし厳密に定義されることは稀である。一般化を明示的に遂行するのは単純かつ煩瑣で（したがって割に合わない）からである。

多くの数学的営みにおいて、ソートにはあまり注意が払われない。しかしテンプレート:仮リンクは自然に型理論へと導く。テンプレート:仮リンクの言葉を借りれば、「論理は常に型理論の上の論理である」。この強調は今度は圏論的論理学へと導く。というのも、型理論の上の論理は圏論的に、論理を捉える一つの（「全体」）圏が、型理論を捉える別の（「基底」）圏の上にテンプレート:仮リンクされているものに対応するからである。

その他の一般化

部分代数

普遍代数学とモデル理論はいずれも、シグネチャと公理の集合によって定義される（構造あるいは）代数のクラスを研究する。モデル理論の場合、これらの公理は一階の文の形をとる。普遍代数学の形式化ははるかに制限的で、本質的には項の間の全称量化された等式の形をもつ一階の文のみを許す（例: ∀ x ∀ y (x + y = y + x)）。その帰結の一つとして、シグネチャの選択は普遍代数学においてモデル理論におけるよりも重要となる。例えば、二項関数記号 × と定数記号 1 からなるシグネチャにおける群のクラスはテンプレート:仮リンクであるが、バラエティではない。普遍代数学は単項関数記号 ⁻¹ を追加することでこの問題を解決する。

体の場合、この戦略は加法に対してのみ機能する。乗法については、0 が乗法逆元をもたないために失敗する。これに対処する場当たり的な試みとして 0⁻¹ = 0 と定義することが考えられる（この試みは失敗する。本質的には、この定義の下では 0 × 0⁻¹ = 1 が成り立たないからである）。したがって自然に、部分関数、すなわち定義域の部分集合上でのみ定義される関数を許すことが導かれる。しかし部分構造・準同型・同一性といった概念を一般化する自明な方法は複数存在する。

型付き言語に対する構造

型理論においては多くのソートの変数があり、そのそれぞれが型をもつ。型は帰納的に定義される。二つの型 δ と σ が与えられると、型 σ の対象から型 δ の対象への関数を表す型 σ → δ も存在する。型付き言語に対する構造は（通常の一階の意味論において）各型の対象の集合を別々に含まなければならず、関数型については、その型の各対象が表す関数についての完全な情報をもたなければならない。

高階言語

テンプレート:Main 高階論理に対する意味論は複数ありうる。これについては二階述語論理の記事で論じられている。完全高階意味論を用いる場合、構造は型0の対象に対する宇宙のみをもてばよく、T-スキーマは、高階型上の量化子がモデルによって充足されるのは、それが引用符解除的に真であるとき、かつそのときに限るように拡張される。一階の意味論を用いる場合には、多ソート一階言語の場合と同様に、各高階型に対して追加のソートが加えられる。

真クラスである構造

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

バートランド・ラッセルの『プリンキピア・マテマティカ』においても、構造がその領域として真クラスをもつことが許されていた。

関連項目

• テンプレート:Annotated link

参考文献

• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation
• テンプレート:Citation

外部リンク

• Semantics section in Classical Logic（スタンフォード哲学百科事典の項目）