項代数

普遍代数と数理論理学において、代数という用語は、与えられた署名に対して自由に生成された代数構造を指します。^{[1] [2]}たとえば、単一の二項演算からなる署名では、変数の集合Xに対する代数という用語は、 Xによって生成された自由なマグマそのものです。この概念の他の同義語には、絶対自由代数や無政府代数などがあります。^[3]

圏論の観点からは、項代数とは、同じ署名を持つすべてのX生成代数の圏の初期オブジェクトであり、同型を除いて一意であるこのオブジェクトは初期代数と呼ばれ、準同型射影によって圏内のすべての代数を生成します。^{[4] [5]}

同様の概念に論理におけるエルブラン宇宙があり、論理プログラミングでは通常この名前で使用され、^[6]一連の節内の定数と関数記号の集合から始めて（完全に自由に）定義されます。つまり、エルブラン宇宙はすべて基底項、つまり変数を持たない項で構成されます。

原子式またはアトムは、一般的に、項の組に適用される述語として定義されます。基底アトムは、基底項のみが現れる述語です。エルブラン基底は、エルブラン宇宙の元の節と項の集合内の述語記号から形成できるすべての基底アトムの集合です。^{[7] [8]これら2つの概念は}、ジャック・エルブランにちなんで名付けられました。

項代数は、抽象データ型のセマンティクスにおいても役割を果たします。抽象データ型の宣言は、複数のソートされた代数構造のシグネチャを提供し、項代数は抽象宣言の具体的なモデルです。

型は 関数シンボルの集合であり、それぞれにアリティ（入力数）が関連付けられています。任意の非負整数 について、はアリティの関数シンボルを表します。定数はアリティ 0 の関数シンボルです。 ${\displaystyle \tau}$${\displaystyle n}$${\displaystyle \tau_{n}}$${\displaystyle \tau}$${\displaystyle n}$

を型とし、を変数シンボルを表す空でないシンボルの集合とします。(簡単にするために、と は互いに素であると仮定します。)上の型の項の集合は、 の変数シンボルと の定数および演算を使用して構築できるすべての整形式の文字列の集合です。正式には、は次の最小の集合です。 ${\displaystyle \tau}$${\displaystyle X}$${\displaystyle X}$${\displaystyle \tau}$ ${\displaystyle T(X)}$${\displaystyle \tau}$${\displaystyle X}$${\displaystyle X}$${\displaystyle \tau}$${\displaystyle T(X)}$

• ${\displaystyle X\cup \tau _{0}\subseteq T(X)}$   — の各変数記号は の項であり、 の各定数記号も の項です。${\displaystyle X}$${\displaystyle T(X)}$${\displaystyle \tau_{0}}$
• すべてのおよびすべての関数記号と項に対して、文字列 が得られます。つまり、項   が与えられた場合、それらに-ary 関数記号を適用すると、再び項が表されます。${\displaystyle n\geq 1}$${\displaystyle f\in \tau _{n}}$${\displaystyle t_{1},...,t_{n}\in T(X)}$${\displaystyle f(t_{1},...,t_{n})\in T(X)}$${\displaystyle n}$${\displaystyle t_{1},...,t_{n}}$${\displaystyle n}$${\displaystyle f}$

型代数 という用語は、要約すると、各式をその文字列表現にマッピングする型の代数です。正式には、次のように定義されます。^[9]${\displaystyle {\mathcal {T}}(X)}$${\displaystyle \tau}$${\displaystyle X}$${\displaystyle \tau}$${\displaystyle {\mathcal {T}}(X)}$

• のドメインはです。${\displaystyle {\mathcal {T}}(X)}$${\displaystyle T(X)}$
• の各ゼロ引数関数に対して、は文字列 として定義されます。${\displaystyle f}$${\displaystyle \tau_{0}}$${\displaystyle f^{{\mathcal {T}}(X)}()}$${\displaystyle f}$
• すべての および の各n 項関数、およびドメイン内の要素に対して、は文字列として定義されます。${\displaystyle n\geq 1}$${\displaystyle f}$${\displaystyle \tau}$${\displaystyle t_{1},...,t_{n}}$${\displaystyle f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})}$${\displaystyle f(t_{1},...,t_{n})}$

項代数は絶対的に自由であると言われています。なぜなら、型の任意の代数に対して、および任意の関数 に対して、一意の準同型 に拡張され、各項を対応する値 に単純に評価するからです。正式には、各 に対して: ${\displaystyle {\mathcal {A}}}$${\displaystyle \tau}$${\displaystyle g:X\to {\mathcal {A}}}$${\displaystyle g}$${\displaystyle g^{\ast }:{\mathcal {T}}(X)\to {\mathcal {A}}}$${\displaystyle t\in {\mathcal {T}}(X)}$${\displaystyle g^{\ast }(t)\in {\mathcal {A}}}$${\displaystyle t\in {\mathcal {T}}(X)}$

• もしならば。${\displaystyle t\in X}$${\displaystyle g^{\ast }(t)=g(t)}$
• もしならば。${\displaystyle t=f\in \tau _{0}}$${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}()}$
• かつであれば、 となります。${\displaystyle t=f(t_{1},...,t_{n})}$${\displaystyle f\in \tau _{n}}$${\displaystyle n\geq 1}$${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n}))}$

例として、整数演算からヒントを得た型は、各 に対して、、 、によって定義できます。 ${\displaystyle \tau_{0}=\{0,1\}}$${\displaystyle \tau_{1}=\{\}}$${\displaystyle \tau_{2}=\{+,*\}}$${\displaystyle \tau _{i}=\{\}}$${\displaystyle i>2}$

最もよく知られている 型の代数は、自然数を定義域として持ち、、、 を通常の方法で解釈します。これを と呼びます。 ${\displaystyle \tau}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle +}$${\displaystyle *}$${\displaystyle {\mathcal {A}}_{nat}}$

例の変数セット について、上の型の項代数を調べます。 ${\displaystyle X=\{x,y\}}$${\displaystyle {\mathcal {T}}(X)}$${\displaystyle \tau }$${\displaystyle X}$

まず、型overの項の集合について考えます。そのメンバーは、構文形式が一般的ではないため、認識しにくいため、 赤色で示します。例えば、${\displaystyle T(X)}$${\displaystyle \tau }$${\displaystyle X}$

• ${\displaystyle {\color {red}x}\in T(X)}$は変数シンボルなので、${\displaystyle x\in X}$
• ${\displaystyle {\color {red}1}\in T(X)}$は定数記号なので、${\displaystyle 1\in \tau _{0}}$
• ${\displaystyle {\color {red}+x1}\in T(X)}$は2項関数記号なので、${\displaystyle +}$
• ${\displaystyle {\color {red}*+x1x}\in T(X)}$since は2 項関数シンボルです。${\displaystyle *}$

より一般的には、 の各文字列は、許容される記号から構築され、ポーランド語の接頭表記法で記述された数式に対応します。たとえば、項 は通常の挿入記法の式に対応します。ポーランド語表記の曖昧さを避けるために括弧は必要ありません。たとえば、挿入式 は項 に対応します。 ${\displaystyle T(X)}$${\displaystyle {\color {red}*+x1x}}$${\displaystyle (x+1)*x}$${\displaystyle x+(1*x)}$${\displaystyle {\color {red}+x*1x}}$

反例をいくつか挙げると、例えば

• ${\displaystyle {\color {red}z}\not \in T(X)}$は変数記号としても定数記号としても認められていないため、${\displaystyle z}$
• ${\displaystyle {\color {red}3}\not \in T(X)}$同じ理由で、
• ${\displaystyle {\color {red}+1}\not \in T(X)}$は2項関数記号ですが、ここでは1つの引数項（つまり ）のみで使用されています。${\displaystyle +}$${\displaystyle {\color {red}1}}$

項集合が確立されたので、型の項代数を考察します。この代数は をその定義域として使用し、その上で加算と乗算を定義する必要があります。加算関数は2 つの項とを取り、項 を返します。同様に、乗算関数は、指定された項と を項 にマップします。たとえば、 は項 に評価されます 。非公式には、と の演算はどちらも、計算を実行するのではなく、実行する必要がある計算を記録するだけであるという点で「怠け者」です。 ${\displaystyle T(X)}$${\displaystyle {\mathcal {T}}(X)}$${\displaystyle \tau }$${\displaystyle X}$${\displaystyle T(X)}$${\displaystyle +^{{\mathcal {T}}(X)}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle {\color {red}+}pq}$${\displaystyle *^{{\mathcal {T}}(X)}}$${\displaystyle p}$${\displaystyle q}$${\displaystyle {\color {red}*}pq}$${\displaystyle *^{{\mathcal {T}}(X)}({\color {red}+x1},{\color {red}x})}$${\displaystyle {\color {red}*+x1x}}$${\displaystyle +^{{\mathcal {T}}(X)}}$${\displaystyle *^{{\mathcal {T}}(X)}}$

準同型写像の一意な拡張可能性の例として、およびによって定義される を考えてみましょう。非公式には、 は変数記号への値の割り当てを定義し、これが完了すると、 のすべての項はにおいて一意に評価できるようになります。たとえば、 ${\displaystyle g:X\to {\mathcal {A}}_{nat}}$${\displaystyle g(x)=7}$${\displaystyle g(y)=3}$${\displaystyle g}$${\displaystyle T(X)}$${\displaystyle {\mathcal {A}}_{nat}}$

${\displaystyle {\begin{array}{lll}&g^{*}({\color {red}+x1})\\=&g^{*}({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&g({\color {red}x})+g^{*}({\color {red}1})&{\text{ since }}g^{*}{\text{ coincides on }}X{\text{ with }}g\\=&7+g^{*}({\color {red}1})&{\text{ by definition of }}g\\=&7+1&{\text{ since }}g^{*}{\text{ is a homomorphism }}\\=&8&{\text{ according to the well-known arithmetical rules in }}{\mathcal {A}}_{nat}\\\end{array}}}$

同様の方法で、 が得られます。 ${\displaystyle g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56}$

言語のシグネチャ σ は、定数 O 、関数記号 F 、述語 P のアルファベットからなる三つ組 < O 、F 、 P >である。シグネチャσ のエルブラン 基底[ 10] は、 σ のすべての基底アトム、すなわち形式 R ( t 1 、 ...、 t n ) のすべての式から構成される。^ここで、t 1 、_...、  t _nは変数_を含ま ない_項(つまりエルブラン宇宙の要素) であり、Rはn項関係記号 (つまり述語)である。等式を含む論理の場合、形式t ₁  =  t ₂のすべての方程式も含まれる。ここで、t ₁とt ₂には変数が含まれない。

項代数は量指定子除去法を使って決定可能であることを示すことができる。二項構成子は単射であり、したがってペアリング関数であるため、決定問題の複雑さは非基本的なレベルである。^[11]

• 回答セットプログラミング
• クローン（代数）
• 談話領域/宇宙（数学）
• ラビンの木定理（無限完全二分木のモナド理論は決定可能である）
• 初期代数
• 抽象データ型
• 項書き換えシステム

• ジョエル・バーマン (2005)。「自由代数の構造」。オートマトン、半群、普遍代数の構造理論。シュプリンガー。pp. 47–76。MR 2210125。

• ワイスタイン、エリック・W.「ヘルブランド・ユニバース」。マスワールド。