Clarification about the definition of term algebras

Question

The following definition has been given in this article.

A term algebra is an algebra $ \langle \mathcal{S}, \mathcal{G} \rangle $ where every time that $g_\alpha, g_\beta \in \mathcal{G}$ and $$ g_\alpha(x_1,x_2,\ldots , x_{n(\alpha)}) = g_\beta (y_1,y_2,\ldots, y_{n(\beta)}) $$ we have $\alpha = \beta$ and $x_\kappa = y_\kappa$ for all $\kappa = 1,2,\ldots,n(\alpha)=n(\beta)$.

Does it mean that we just ignore tha value of the functions and treat them as strings or it means that somehow the value of a function is influenced by its syntax?

Answer 1

The correct answer is the second one: functions of the algebras are influenced by the syntax, that's the special property of term algebras.

Usually term algebras are defined as algebras whose carrier are set formed by strings of a specified grammar. Usually they are build in such way:

• you start by two sets, a set of sorts $\mathcal S$ and a set of operation $\Sigma$, and a function $ar \colon \Sigma \to \mathcal S^*$, where $\mathcal S^*=\{ \langle S_1,\dots,S_k\rangle \mid n \in \mathbb N, S_i \in \mathcal S\}$ is the Kleene star of the set $\mathcal S$ and the equation $$ar(f) = \langle S_1,\dots,S_k,S\rangle$$ is usually rewritten as $$f \colon S_1,\dots,S_k \to S\ ;$$

• then for every $S \in \mathcal S$ one build a set $\bar S$ defined inductively from the following rules:

  • every $x \in S$ is an element of $\bar S$, so $x \in \bar S$;
  • if $g_\alpha \colon S_1,\dots,S_k \to S$ is an operation symbol and $t_1,\dots,t_k$ are (already defined) terms such that $t_i \in \bar S_i$ for every $i=1,\dots,k$ then the term $g_\alpha(t_1,\dots,t_k) \in \bar S$.

With this construction we have for every operation symbol $g_\alpha \colon S_1,\dots,S_k \to S$ an operation $$\bar g_\alpha \colon \bar S_1 \times \dots \times \bar S_k \to \bar S$$ defined by the equation $$\bar g_\alpha (t_1,\dots,t_k) = g_\alpha(t_1,\dots,t_k)$$ for every $t_1 \in \bar S_1,\dots,t_k \in \bar S_k$.

So by taking the pair $\langle \{ \bar S\mid S \in \mathcal S\},\{ \bar g_\alpha\}_{\alpha}\rangle$ we get an algebra whose operations actually verified the property you stated in the question $$\bar g_\alpha(x_1,x_2,…,x_{n(\alpha)})=g_\beta(y_1,y_2,…,y_{n(\beta)})$$ we have $\alpha=\beta$ and $x_k=y_k$ for all $k=1,2,…,n(α)=n(β)$.

The proof follows easily by the definition of the $\bar g_\alpha$.

The important thing is that this symbolic algebras are exactly the term algebras up to isomorphism. If you have an algebra $\langle \mathcal S, \mathcal G\rangle$ satisfying the propery above then there's a symbolic algebra $\langle T, O \rangle$ to which is isomorphic, i.e. there are bijection mapping sorts of the first algebra in sort of the second algebra and operation of the first algebra in operations of the second algebra.

Hope this helps.

Answer 2

The definition of "term algebra" given in the article is incorrect: it gives a necessary condition, but not the full condition. The missing condition is that the set of what it calls "generators" must actually generate the algebra. For more details I wrote a presentation of term algebras in http://settheory.net/terms (with other notations I found more convenient, introduced in previous pages).