Understanding the Term Algebra

260 Views Asked by At

For fun, I was surveying a little universal algebra from Burris' and Sankappanavar's "A Course In Universal Algebra" (http://www.cs.elte.hu/~ewkiss/univ-algebra.pdf). Definition 10.1 says...

Let $X$ be a set of (distinct) objects called variables. Let $\mathscr{F}$ be a type of algebra. The set $T(X)$ of terms of type $\mathscr{F}$ over X is the smallest set such that

1) $X \cup \mathscr{F}_0 \subseteq T(X)$

2) If $p_1,...,p_n \in T(X)$ and $f \in \mathscr{F}_n$ then the "string" $f(p_1,...,p_n) \in T(X)$

The type $\mathscr{F}$ is just a nonempty set of operation symbols $f$, each with assigned arity, and the subset $\mathscr{F}_n \subseteq \mathscr{F}$ consists of the $n$-ary operation symbols.

Here's my problem. The quotes in his definition around the word string are the authors' quotes, not mine. But the authors don't use the word string anywhere in the book until that very definition, so though I have an intuitive understanding of what they mean, I have no technical definition to go off of.

As I understand it, a string is just a finite sequence in some alphabet. So I constructed my own term algebra using some equinumerous copy $\hat{X} \cong X$ that was disjoint from the type $\mathscr{F}$, creating two distinct formal parentheses $[\![\,,]\!]$ not contained in $\hat{X} \cup \mathscr{F}$, and then considering the free monoid over the alphabet

$$\hat{X} \cup \mathscr{F} \cup \{[\![\,,]\!]\}$$

and managed to get pretty far with it - even begin to talk about universal mapping properties. But I would like to know what Burris' and Sankappanavar's definition of "string" is, and how they are constructing the term algebra.