# term algebra

Let $\Sigma$ be a signature and $V$ a set of variables. Consider the set of all terms of $T:=T(\Sigma)$ over $V$. Define the following:

• For each constant symbol $c\in\Sigma$, $c^{T}$ is the element $c$ in $T$.

• For each $n$ and each $n$-ary function symbol $f\in\Sigma$, $f^{T}$ is an $n$-ary operation on $T$ given by

 $f^{T}(t_{1},\ldots,t_{n})=f(t_{1},\ldots,t_{n}),$

meaning that the evaluation of $f^{T}$ at $(t_{1},\ldots,t_{n})$ is the term $f(t_{1},\ldots,t_{n})\in T$.

• For each relational symbol $R\in\Sigma$, $R^{T}=\varnothing$.

Then $T$, together with the set of constants and $n$-ary operations defined above is an $\Sigma$-structure (http://planetmath.org/Structure). Since there are no relations defined on it, $T$ is an algebraic system whose signature $\Sigma^{\prime}$ is the subset of $\Sigma$ consisting of all but the relation symbols of $\Sigma$. The algebra $T$ is aptly called the term algebra of the signature $\Sigma$ (over $V$).

The prototypical example of a term algebra is the set of all well-formed formulas over a set $V$ of propositional variables in classical propositional logic. The signature $\Sigma$ is just the set of logical connectives. For each $n$-ary logical connective $\#$, there is an associated $n$-ary operation $[\#]$ on $V$, given by $[\#](p_{1},\ldots,p_{n})=\#p_{1}\cdots p_{n}$.

Remark. The term algebra $T$ of a signature $\Sigma$ over a set $V$ of variables can be thought of as a free structure in the following sense: if $A$ is any $\Sigma$-structure, then any function $\phi:V\to A$ can be extended to a unique structure homomorphism $\phi^{\prime}:T\to A$. In this regard, $V$ can be viewed as a free basis for the algebra $T$. As such, $T$ is also called the absolutely free $\Sigma$-structure with basis $V$.

Title term algebra TermAlgebra 2013-03-22 17:35:24 2013-03-22 17:35:24 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 03C99 msc 03C60 word algebra PolynomialsInAlgebraicSystems FreeAlgebra