Varieties, Free Algebras and Equational Logic
Term Operations and Polynomial Operations
The functions terms induce on an algebra, the polynomials obtained by allowing parameters, and the clones these families form.
Learning objectives
- Distinguish term operations from polynomial operations
- Describe the clone of an algebra
- Explain the role of polynomials in congruence generation
Term operations
For a term p(x1,…,xn) and an algebra A, the term operation pA: An → A is the function obtained by interpreting each operation symbol as its interpretation in A.
Term operations are exactly the functions that every subalgebra is closed under and every homomorphism preserves. That characterisation makes them the natural generalisation of the basic operations.
Sg(X) = {pA(a1,…,an) : p a term, ai ∈ X} — the uniform description promised when Sg was introduced.
Polynomial operations
A function obtained from a term operation by substituting fixed elements of A for some of its arguments. Formally, the polynomial operations are the term operations of the algebra A enriched with a nullary operation for each element of A.
| Term operations | Polynomial operations | |
|---|---|---|
| Parameters allowed | No | Yes — elements of A |
| Preserved by homomorphisms | Yes | No |
| Preserved by subalgebras | Yes | Only if the parameters lie in the subalgebra |
| Preserved by congruences | Yes | Yes |
| Example in a group | xy−1 | xax−1 for fixed a |
Mal'cev's description of Θ(a, b) uses unary polynomial functions, not term functions. Parameters are essential there: the chains that generate a principal congruence must be allowed to involve arbitrary elements of the algebra, not just the generators.
Clones
A set of finitary operations on a fixed set that contains all projections and is closed under composition.
The term operations of an algebra form a clone, called the clone of A. The polynomial operations form a larger clone, containing all constants.
- Two algebras are term-equivalent if they have the same clone. Term-equivalent algebras are indistinguishable by universal-algebraic methods, even if presented with different operations.
- Two algebras are polynomially equivalent if they have the same polynomial clone. This is weaker and is the notion used when characterising modules in Chapter II §13.
- Clone theory is a substantial subject in its own right; Post's classification of the clones on a two-element set is its founding result.
A Boolean algebra and its associated Boolean ring are term-equivalent: each operation of one is a term operation of the other. This is why Chapter IV can move between the two presentations freely, and it is the cleanest example of term equivalence in the source.
Idempotent and conservative operations
Two properties of term operations recur in the later chapters:
Idempotent
p(x,…,x) ≈ x. Idempotent term operations are central to the classification of varieties and to constraint satisfaction complexity.
Conservative
p(a1,…,an) ∈ {a1,…,an}. Conservative operations preserve every subset.
The discriminator function of Chapter IV §9 is both idempotent and conservative, and those two properties are much of what makes discriminator varieties so tractable.
Frequently asked questions
Is every function on a finite algebra a term operation?
Only for primal algebras — that is exactly the definition of primality. For most algebras the term operations are a small subset of all functions.
Why do polynomials fail to be preserved by homomorphisms?
Because a homomorphism need not map a parameter to a corresponding parameter in a coherent way. Conjugation by a fixed element a in a group is a polynomial operation, and a homomorphism sends it to conjugation by the image of a — a different polynomial.
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 69-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.