Term algebra

A type ${\displaystyle \tau }$ is a set of function symbols, with each having an associated arity (i.e. number of inputs). For any non-negative integer ${\displaystyle n}$, let ${\displaystyle \tau _{n}}$ denote the function symbols in ${\displaystyle \tau }$ of arity ${\displaystyle n}$. A constant is a function symbol of arity 0.

Let ${\displaystyle \tau }$ be a type, and let ${\displaystyle X}$ be a non-empty set of symbols, representing the variable symbols. (For simplicity, assume ${\displaystyle X}$ and ${\displaystyle \tau }$ are disjoint.) Then the set of terms ${\displaystyle T(X)}$ of type ${\displaystyle \tau }$ over ${\displaystyle X}$ is the set of all well-formed strings that can be constructed using the variable symbols of ${\displaystyle X}$ and the constants and operations of ${\displaystyle \tau }$. Formally, ${\displaystyle T(X)}$ is the smallest set such that:

• ${\displaystyle X\cup \tau _{0}\subseteq T(X)}$   — each variable symbol from ${\displaystyle X}$ is a term in ${\displaystyle T(X)}$, and so is each constant symbol from ${\displaystyle \tau _{0}}$.
• For all ${\displaystyle n\geq 1}$ and for all function symbols ${\displaystyle f\in \tau _{n}}$ and terms ${\displaystyle t_{1},...,t_{n}\in T(X)}$, we have the string ${\displaystyle f(t_{1},...,t_{n})\in T(X)}$   — given ${\displaystyle n}$ terms ${\displaystyle t_{1},...,t_{n}}$, the application of an ${\displaystyle n}$-ary function symbol ${\displaystyle f}$ to them represents again a term.

The term algebra ${\displaystyle {\mathcal {T}}(X)}$ of type ${\displaystyle \tau }$ over ${\displaystyle X}$ is, in summary, the algebra of type ${\displaystyle \tau }$ that maps each expression to its string representation. Formally, ${\displaystyle {\mathcal {T}}(X)}$ is defined as follows:[9]

• The domain of ${\displaystyle {\mathcal {T}}(X)}$ is ${\displaystyle T(X)}$.
• For each nullary function ${\displaystyle f}$ in ${\displaystyle \tau _{0}}$, ${\displaystyle f^{{\mathcal {T}}(X)}()}$ is defined as the string ${\displaystyle f}$.
• For all ${\displaystyle n\geq 1}$ and for each n-ary function ${\displaystyle f}$ in ${\displaystyle \tau }$ and elements ${\displaystyle t_{1},...,t_{n}}$ in the domain, ${\displaystyle f^{{\mathcal {T}}(X)}(t_{1},...,t_{n})}$ is defined as the string ${\displaystyle f(t_{1},...,t_{n})}$.

A term algebra is called absolutely free because for any algebra ${\displaystyle {\mathcal {A}}}$ of type ${\displaystyle \tau }$, and for any function ${\displaystyle g:X\to {\mathcal {A}}}$, ${\displaystyle g}$ extends to a unique homomorphism ${\displaystyle g^{\ast }:{\mathcal {T}}(X)\to {\mathcal {A}}}$, which simply evaluates each term ${\displaystyle t\in {\mathcal {T}}(X)}$ to its corresponding value ${\displaystyle g^{\ast }(t)\in {\mathcal {A}}}$. Formally, for each ${\displaystyle t\in {\mathcal {T}}(X)}$:

• If ${\displaystyle t\in X}$, then ${\displaystyle g^{\ast }(t)=g(t)}$.
• If ${\displaystyle t=f\in \tau _{0}}$, then ${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}()}$.
• If ${\displaystyle t=f(t_{1},...,t_{n})}$ where ${\displaystyle f\in \tau _{n}}$ and ${\displaystyle n\geq 1}$, then ${\displaystyle g^{\ast }(t)=f^{\mathcal {A}}(g^{\ast }(t_{1}),...,g^{\ast }(t_{n}))}$.

As an example type inspired from integer arithmetic can be defined by ${\displaystyle \tau _{0}=\{0,1\}}$, ${\displaystyle \tau _{1}=\{\}}$, ${\displaystyle \tau _{2}=\{+,*\}}$, and ${\displaystyle \tau _{i}=\{\}}$ for each ${\displaystyle i>2}$.

The best-known algebra of type ${\displaystyle \tau }$ has the natural numbers as its domain and interprets ${\displaystyle 0}$, ${\displaystyle 1}$, ${\displaystyle +}$, and ${\displaystyle *}$ in the usual way; we refer to it as ${\displaystyle {\mathcal {A}}_{nat}}$.

For the example variable set ${\displaystyle X=\{x,y\}}$, we are going to investigate the term algebra ${\displaystyle {\mathcal {T}}(X)}$ of type ${\displaystyle \tau }$ over ${\displaystyle X}$.

First, the set ${\displaystyle T(X)}$ of terms of type ${\displaystyle \tau }$ over ${\displaystyle X}$ is considered. We use red color to flag its members, which otherwise may be hard to recognize due to their uncommon syntactic form. We have e.g.

• ${\displaystyle {\color {red}x}\in T(X)}$, since ${\displaystyle x\in X}$ is a variable symbol;
• ${\displaystyle {\color {red}1}\in T(X)}$, since ${\displaystyle 1\in \tau _{0}}$ is a constant symbol; hence
• ${\displaystyle {\color {red}+x1}\in T(X)}$, since ${\displaystyle +}$ is a 2-ary function symbol; hence, in turn,
• ${\displaystyle {\color {red}*+x1x}\in T(X)}$ since ${\displaystyle *}$ is a 2-ary function symbol.

More generally, each string in ${\displaystyle T(X)}$ corresponds to a mathematical expression built from the admitted symbols and written in Polish prefix notation; for example, the term ${\displaystyle {\color {red}*+x1x}}$ corresponds to the expression ${\displaystyle (x+1)*x}$ in usual infix notation. No parentheses are needed to avoid ambiguities in Polish notation; e.g. the infix expression ${\displaystyle x+(1*x)}$ corresponds to the term ${\displaystyle {\color {red}+x*1x}}$.

To give some counter-examples, we have e.g.

• ${\displaystyle {\color {red}z}\not \in T(X)}$, since ${\displaystyle z}$ is neither an admitted variable symbol nor an admitted constant symbol;
• ${\displaystyle {\color {red}3}\not \in T(X)}$, for the same reason,
• ${\displaystyle {\color {red}+1}\not \in T(X)}$, since ${\displaystyle +}$ is a 2-ary function symbol, but is used here with only one argument term (viz. ${\displaystyle {\color {red}1}}$).

Now that the term set ${\displaystyle T(X)}$ is established, we consider the term algebra ${\displaystyle {\mathcal {T}}(X)}$ of type ${\displaystyle \tau }$ over ${\displaystyle X}$. This algebra uses ${\displaystyle T(X)}$ as its domain, on which addition and multiplication need to be defined. The addition function ${\displaystyle +^{{\mathcal {T}}(X)}}$ takes two terms ${\displaystyle p}$ and ${\displaystyle q}$ and returns the term ${\displaystyle {\color {red}+}pq}$; similarly, the multiplication function ${\displaystyle *^{{\mathcal {T}}(X)}}$ maps given terms ${\displaystyle p}$ and ${\displaystyle q}$ to the term ${\displaystyle {\color {red}*}pq}$. For example, ${\displaystyle *^{{\mathcal {T}}(X)}({\color {red}+x1},{\color {red}x})}$ evaluates to the term ${\displaystyle {\color {red}*+x1x}}$. Informally, the operations ${\displaystyle +^{{\mathcal {T}}(X)}}$ and ${\displaystyle *^{{\mathcal {T}}(X)}}$ are both "sluggards" in that they just record what computation should be done, rather than doing it.

As an example for unique extendability of a homomorphism consider ${\displaystyle g:X\to {\mathcal {A}}_{nat}}$ defined by ${\displaystyle g(x)=7}$ and ${\displaystyle g(y)=3}$. Informally, ${\displaystyle g}$ defines an assignment of values to variable symbols, and once this is done, every term from ${\displaystyle T(X)}$ can be evaluated in a unique way in ${\displaystyle {\mathcal {A}}_{nat}}$. For example,

${\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}}}$

In a similar way, one obtains ${\displaystyle g^{*}({\color {red}*+x1x})=...=8*g({\color {red}x})=...=56}$.

The signature σ of a language is a triple <O, F, P> consisting of the alphabet of constants O, function symbols F, and predicates P. The Herbrand base[10] of a signature σ consists of all ground atoms of σ: of all formulas of the form R(t₁, ..., t_n), where t₁, ..., t_n are terms containing no variables (i.e. elements of the Herbrand universe) and R is an n-ary relation symbol (i.e. predicate). In the case of logic with equality, it also contains all equations of the form t₁ = t₂, where t₁ and t₂ contain no variables.

Term algebras can be shown decidable using quantifier elimination. The complexity of the decision problem is in NONELEMENTARY because binary constructors are injective and thus pairing functions.[11]

• Answer-set programming
• Clone (algebra)
• Domain of discourse / Universe (mathematics)
• Rabin's tree theorem (the monadic theory of the infinite complete binary tree is decidable)
• Initial algebra
• Abstract data type
• Term rewriting system

• Joel Berman (2005). "The structure of free algebras". In Structural Theory of Automata, Semigroups, and Universal Algebra. Springer. pp. 47–76. MR2210125.

• Weisstein, Eric W. "Herbrand Universe". MathWorld.