Varieties, Free Algebras and Equational Logic
Terms and the Term Algebra T(X)
Terms as formal expressions built from variables and operation symbols, the term algebra they form, and its absolute freeness.
Learning objectives
- Define terms by recursion and describe the term algebra
- State the universal property of T(X)
- Distinguish terms from the operations they induce
Terms
Given a type and a set X of variables, the set T(X) of terms is defined recursively: every variable in X is a term; every nullary operation symbol is a term; and if p1,…,pn are terms and f is an n-ary operation symbol, then f(p1,…,pn) is a term. Nothing else is a term.
Terms are purely syntactic objects — strings, or equivalently finite labelled trees. Two terms are equal only when they are identical as expressions. The term x · (y · z) differs from (x · y) · z even in a variety where they induce the same operation.
A term is syntax. A term operation is the function it induces on a given algebra. Distinct terms often induce the same operation — that is exactly what it means for an identity to hold.
The term algebra
The operations do nothing but assemble longer expressions. No simplification occurs, no identity is imposed. T(X) is non-empty provided X is non-empty or the type has a constant.
For any algebra A of the same type and any function α: X → A, there is a unique homomorphism ᾱ: T(X) → A extending α.
The extension is defined by recursion on term structure, which is possible precisely because terms are uniquely readable: every non-variable term has exactly one decomposition as an operation symbol applied to arguments.
Terms as trees
Reading terms as finite labelled trees clarifies several arguments:
- f — root, arity 2
- g — arity 1
- x — leaf
- h — arity 2
- y — leaf
- z — leaf
- g — arity 1
- Leaves are variables and constants.
- Internal nodes are operation symbols, with as many children as their arity.
- Every tree is finite, which is the syntactic form of finitary arity.
- Structural induction on the tree is the standard proof technique for statements about all terms.
The role of the variable set
The size of X matters. T(X) for finite X of size n contains exactly the terms in n variables, and n-ary term operations correspond to its elements.
- <em>T</em>(∅)
- closed terms only; empty unless the type has constants
- <em>T</em>({<em>x</em>})
- unary terms; controls unary polynomial structure
- <em>T</em>(<em>X<sub>n</sub></em>)
- terms in n variables
- <em>T</em>(<em>X</em>) for countable <em>X</em>
- enough for all identities, since each identity uses finitely many variables
Every term is finite and so uses finitely many variables. A countably infinite variable set therefore supports every identity that can be written, which is why equational logic is normally developed over a fixed countable X.
Frequently asked questions
Is the term algebra ever finite?
Only in degenerate cases — if the type has no operations of positive arity, so no new terms can be built. Otherwise T(X) is infinite whenever it is non-empty.
Why does unique readability matter?
Because recursion on term structure requires it. If a term could be parsed in two ways, the recursive definition of the extending homomorphism would be ambiguous and absolute freeness would fail.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section II.10, book pages 68-72.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.