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.