term algebra

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

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

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

  $$f^T(t_1,\mathrm{\dots },t_n)=f(t_1,\mathrm{\dots },t_n),$$

  meaning that the evaluation of $f^T$ at $(t_1,\mathrm{\dots },t_n)$ is the term $f(t_1,\mathrm{\dots },t_n)\in T$.

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

Then $T$, together with the set of constants and $n$-ary operations defined above is an $\mathrm{\Sigma }$-structure (http://planetmath.org/Structure). Since there are no relations defined on it, $T$ is an algebraic system whose signature ${\mathrm{\Sigma }}^{\prime }$ is the subset of $\mathrm{\Sigma }$ consisting of all but the relation symbols of $\mathrm{\Sigma }$. The algebra $T$ is aptly called the term algebra of the signature $\mathrm{\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 $\mathrm{\Sigma }$ is just the set of logical connectives. For each $n$-ary logical connective $\mathrm{\#}$, there is an associated $n$-ary operation $[\mathrm{\#}]$ on $V$, given by $[\mathrm{\#}](p_1,\mathrm{\dots },p_n)=\mathrm{\#}{p}_1\mathrm{\cdots }{p}_n$.

Remark. The term algebra $T$ of a signature $\mathrm{\Sigma }$ over a set $V$ of variables can be thought of as a free structure in the following sense: if $A$ is any $\mathrm{\Sigma }$-structure, then any function $\varphi :V\to A$ can be extended to a unique structure homomorphism ${\varphi }^{\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 $\mathrm{\Sigma }$-structure with basis $V$.