項代数

普遍代数学および数理論理学において、項代数（こうだいすう、テンプレート:Lang-en-short）は、与えられたシグネチャ上に自由に生成される代数的構造である。たとえば、1 つの二項演算のみからなるシグネチャにおいては、変数の集合 X 上の項代数は正確に、X により生成されるテンプレート:仮リンクに等しい。他の同義語として、絶対自由代数（absolutely free algebra）やアナーキー代数（anarchic algebra）が用いられる。

圏論の観点からは、項代数は、同一シグネチャをもつ X 生成代数全体からなる圏の始対象である。この対象は同型を除いて一意であり、始代数と呼ばれる。項代数は圏内のすべての代数を準同型的な射影によって生成する。

これに類似した概念として、論理におけるテンプレート:仮リンクがある。この用語は通常論理プログラミングにおいて用いられ、節の集合に含まれる定数と関数記号の集合から出発して（絶対的自由に）定義される。すなわち、エルブラン領域は、すべてのテンプレート:仮リンク――変数を全く含まない項――から構成される。

項代数は、抽象データ型の意味論にも重要な役割を果たす。すなわち、抽象データ型の宣言は多ソート代数的構造のシグネチャを与え、項代数はその抽象宣言の具体的モデルとなる。

普遍代数学における定式化

型 $\tau$ とは関数記号の集合であり、各関数記号にそれぞれアリティ（すなわち入力の個数）が付随している。任意の非負整数 $n$ に対し、$\tau$ 中のアリティ $n$ の関数記号を ${\tau }_n$ と表す。定数とはアリティ 0 の関数記号である。

$\tau$ を型とし、$X$ を変数記号を表す空でない記号の集合とする（簡単のため $X$ と $\tau$ は互いに素であるとする）。このとき、X 上の型 $\tau$ のテンプレート:仮リンクの集合 $T(X)$ は、$X$ の変数記号と $\tau$ の定数および演算を用いて構成できるすべての整形式の文字列の集合である。形式的には、$T(X)$ は次を満たす最小の集合として定義される。

• $X\cup {\tau }_0\subseteq T(X)$ — $X$ の各変数記号は $T(X)$ の項であり、${\tau }_0$ の各定数記号もまた項である。
• すべての $n\ge 1$、すべての関数記号 $f\in {\tau }_n$、および項 $t_1,\mathrm{...},t_n\in T(X)$ について、文字列 $f(t_1,\mathrm{...},t_n)\in T(X)$ — $n$ 個の項 $t_1,\mathrm{...},t_n$ が与えられれば、$n$ 項関数記号 $f$ をこれらに適用したものもまた項となる。

X 上の型 $\tau$ の項代数 $𝒯(X)$ とは、要するに、各式にその文字列表現を対応付ける型 $\tau$ の代数である。形式的には、$𝒯(X)$ は次のように定義される。

• $𝒯(X)$ の領域は $T(X)$ である。
• ${\tau }_0$ 中の各 0 項関数 $f$ について、$f^{𝒯(X)}()$ は文字列 $f$ として定義される。
• すべての $n\ge 1$ と、$\tau$ 中の各 n 項関数 $f$ および領域の元 $t_1,\mathrm{...},t_n$ について、$f^{𝒯(X)}(t_1,\mathrm{...},t_n)$ は文字列 $f(t_1,\mathrm{...},t_n)$ として定義される。

項代数が絶対自由（absolutely free）と呼ばれるのは、型 $\tau$ の任意の代数 $𝒜$ と任意の関数 $g:X\to 𝒜$ に対して、$g$ が一意な準同型 $g^{\ast }:𝒯(X)\to 𝒜$ に拡張されるためである。この準同型は、単に各項 $t\in 𝒯(X)$ を対応する値 $g^{\ast }(t)\in 𝒜$ に評価する。形式的には、各 $t\in 𝒯(X)$ について:

• もし $t\in X$ ならば $g^{\ast }(t)=g(t)$。
• もし $t=f\in {\tau }_0$ ならば $g^{\ast }(t)=f^{𝒜}()$。
• もし $t=f(t_1,\mathrm{...},t_n)$ で $f\in {\tau }_n$ かつ $n\ge 1$ ならば、$g^{\ast }(t)=f^{𝒜}(g^{\ast }(t_1),\mathrm{...},g^{\ast }(t_n))$。

例

整数演算に着想を得た型の例は、${\tau }_0=\{0,1\}$、${\tau }_1=\{\}$、${\tau }_2=\{+,\ast \}$、および各 $i>2$ に対して ${\tau }_i=\{\}$ と定義できる。

型 $\tau$ の最もよく知られた代数は自然数を領域とし、$0$、$1$、$+$、$\ast$ を通常の意味で解釈するものである。これを ${𝒜}_{nat}$ と呼ぶことにする。

変数集合の例として $X=\{x,y\}$ を取り、X 上の型 $\tau$ の項代数 $𝒯(X)$ を調べる。

まず、X 上の型 $\tau$ の項の集合 $T(X)$ を考える。通常見慣れない構文形式のため識別しづらいことがあるため、その要素をテンプレート:Colorで表す。たとえば、次が得られる:

• $x\in T(X)$（$x\in X$ は変数記号だから）
• $1\in T(X)$（$1\in {\tau }_0$ は定数記号だから）
• $+x1\in T(X)$（$+$ は 2 項関数記号だから）
• $\ast +x1x\in T(X)$（$\ast$ は 2 項関数記号だから）

より一般に、$T(X)$ 中の各文字列は、許容された記号から構築されポーランド前置記法で書かれた数式に対応する。たとえば、項 $\ast +x1x$ は通常の中置記法における式 $(x+1)\ast x$ に対応する。ポーランド記法では曖昧さを避けるための括弧は不要である。たとえば中置式 $x+(1\ast x)$ は項 $+x\ast 1x$ に対応する。

反例をいくつか挙げる:

• $z\in ̸T(X)$（$z$ は許容された変数記号でも定数記号でもないから）
• $3\in ̸T(X)$（同じ理由）
• $+1\in ̸T(X)$（$+$ は 2 項関数記号だが、ここでは項を 1 つ（$1$）しか伴っていないから）

項集合 $T(X)$ が確立されたので、次に X 上の型 $\tau$ の項代数 $𝒯(X)$ を考える。この代数は領域として $T(X)$ を用いる。この上に加算と乗算を定義する必要がある。加算関数 ${+}^{𝒯(X)}$ は 2 つの項 $p$ と $q$ を受け取り、項 $+pq$ を返す。同様に、乗算関数 ${\ast }^{𝒯(X)}$ は与えられた項 $p$ と $q$ を項 $\ast pq$ に写す。たとえば ${\ast }^{𝒯(X)}(+x1,x)$ は項 $\ast +x1x$ に評価される。非形式的にいえば、演算 ${+}^{𝒯(X)}$ と ${\ast }^{𝒯(X)}$ はいずれも「怠け者」で、実際の計算を行うのではなく、どんな計算をすべきかを記録するだけである。

準同型が一意に拡張可能な例として、$g(x)=7$、$g(y)=3$ で定義される $g:X\to {𝒜}_{nat}$ を考える。非形式的にいえば、$g$ は変数記号への値の割り当てを定めており、これが定まれば $T(X)$ の任意の項は ${𝒜}_{nat}$ において一意な方法で評価できる。たとえば、

$\begin{array}{cc}& g^{\ast }(+x1)\\ =& g^{\ast }(x)+g^{\ast }(1)\\ =& g(x)+g^{\ast }(1)\\ =& 7+g^{\ast }(1)\\ =& 7+1\\ =& 8\end{array}$

ここで、各ステップの等号は上から順に以下の理由によって成り立つ。

• $g^{\ast }$ は準同型であるため。
• $g^{\ast }$ は $X$ 上で $g$ に一致するため。
• $g$ の定義による。
• 再び、$g^{\ast }$ は準同型であるため。
• 最後に、${𝒜}_{nat}$ における周知の算術規則を適用した。

同様にして、$g^{\ast }(\ast +x1x)=\mathrm{...}=8\ast g(x)=\mathrm{...}=56$ が得られる。

エルブラン基底

テンプレート:Main 言語のシグネチャ σ は、定数のアルファベット O、関数記号 F、および述語 P からなる三つ組 <O, F, P> である。原子式（atomic formula）は通常、項のタプルに述語を適用したものとして定義され、テンプレート:仮リンクは基底項のみを引数にとる原子式として定義される。

シグネチャ σ のエルブラン基底（Herbrand base） は、σ のすべての基底原子式からなる。すなわち、R(t₁, ..., t_n) の形の式であって、t₁, ..., t_n が変数を含まない項（すなわちエルブラン領域の元）であり、R が n 項関係記号（すなわち述語）であるようなものである。等号を含む論理の場合には、t₁ = t₂ の形のすべての等式（t₁ と t₂ は変数を含まない）も含まれる。これらエルブラン領域およびエルブラン基底の概念は、いずれもジャック・エルブランにちなんで名付けられた。

決定可能性

任意の項代数の一階理論はテンプレート:仮リンクを用いて決定可能であることを示せる。決定問題の計算量はテンプレート:仮リンクに属する。これは 2 項構築子が単射で、したがって対関数となるためである。

関連項目

• テンプレート:仮リンク
• テンプレート:仮リンク
• 議論領域 / 宇宙 (数学)
• テンプレート:仮リンク（無限テンプレート:仮リンクのモナディック理論は決定可能である）
• 始代数
• 抽象データ型
• テンプレート:仮リンク

参考文献

• Joel Berman (2005). "The structure of free algebras". In Structural Theory of Automata, Semigroups, and Universal Algebra. Springer. pp. 47–76. テンプレート:MR.

外部リンク

• テンプレート:Mathworld