Terms, Free Algebras and Equational Logic

Terms, Term Algebras and Term Operations

The term algebra is the algebra with no accidental equalities. Everything provable from nothing holds in it, and nothing else does — which is exactly what makes it the reference object for the whole equational theory.

Engineering · Mathematics5 min readKV-MATH-0219

Learning objectives

Define terms inductively over a type and a set of variables.
Construct the term algebra and state its universal property.
Distinguish a term from the term operation it induces on an algebra.
Explain why distinct terms can induce identical operations.
Compute term operations and recognise when two terms are interchangeable.
Relate term operations to subuniverses and homomorphisms.

01Terms over a type

Fix a type F and a set X of variables. Terms are defined by the smallest closed construction: variables are terms, and applying an n-ary symbol to n terms yields a term.

ProcedureGenerating the set T(X) of terms

in: F, X → out: the set T(X) of terms of type F over X

input: type F, variable set X (assume X ∩ F = ∅)
T₀ := X ∪ { f : f ∈ F nullary }
T_{k+1} := T_k ∪ { f(t₁,…,tₙ) : f ∈ F n-ary, t₁,…,tₙ ∈ T_k }
T(X) := ⋃_{k ≥ 0} T_k
each term carries a finite parse tree; depth k terms appear by stage k

T(X) is non-empty iff X ≠ ∅ or F has a nullary symbol. Every term mentions finitely many variables — the crucial finiteness that makes the whole theory finitary. Caveat: terms are formal strings (or trees), not functions.

A term is a purely syntactic object. It has a parse tree, a set of variables occurring in it, and a depth. It does not have a value until an algebra and an assignment are supplied.

02The term algebra

T(X), the set of terms, carries an algebra structure of type F in the only way it can: an operation symbol acts by building a bigger term.

f^T(X)(t₁,…,tₙ) = f(t₁,…,tₙ)

The operation does nothing but record that it was applied. No simplification, no evaluation, no collapsing.

Key resultThe term algebra is absolutely free

For any algebra A of type F and any map α : X → A, there is exactly one homomorphism from T(X) to A extending α. Existence is structural recursion on the parse tree; uniqueness is structural induction. This is the universal mapping property, and it holds with no equations imposed — hence absolutely free.

The uniqueness half is what makes the term algebra useful. Any two homomorphisms agreeing on the variables agree everywhere, so a homomorphism out of T(X) is completely determined by where it sends the variables. Every later free construction is a quotient of this one.

03Terms versus term operations

Given an algebra A and a term p with variables among x₁,…,xₙ, the induced term operation p^A is the n-ary function on A obtained by evaluating p.

Term p

Syntax

An element of T(X). A finite tree. Two terms are equal only when they are literally the same tree.

Term operation p<sup>A</sup>

Semantics

A function Aⁿ → A. Two different terms can induce the same function on a given algebra, and usually do.

CautionDistinct terms routinely induce identical operations

In any group, the terms x·(y·z) and (x·y)·z are different syntactic objects inducing the same ternary operation. In a Boolean algebra x ∧ x and x differ as terms and agree as operations. Conflating the two levels makes the statement 'A satisfies p ≈ q' vacuous, since it says precisely that two different terms induce the same operation.

The whole content of equational logic lives in this gap. An identity p ≈ q is a claim about which pairs of syntactically distinct terms happen to induce the same operation, and a variety is the class of algebras where a prescribed set of such coincidences holds.

04Term operations and structural closure

Term operations are exactly the operations preserved by every homomorphism and every subalgebra — a characterisation that makes them intrinsic rather than merely convenient.

Subuniverses are closed under term operations
Sg(Y) is precisely the set of values p^A(y₁,…,yₙ) for terms p and elements y of Y. This gives a clean second description of the generation operator.
Homomorphisms commute with term operations
α(p^A(a⃗)) = p^B(α(a⃗)) for every term p, by induction on the parse tree from the basic-operation case.
Congruences are compatible with them
Immediately, by the same induction. This is why checking compatibility on the basic operations suffices for all derived ones.
Polynomial operations are the enlargement
Allowing constants from A gives polynomial operations, which congruences still respect but homomorphisms need not.

05The clone of term operations

The set of all term operations of A, taken over all arities, is closed under composition and contains the projections. Such a set is called a clone, and it is a complete invariant for the equational behaviour of A.

Three related function sets on an algebra
Set	Built from	Closed under	Respected by
Term operations	basic operations, variables	composition, projections	homomorphisms, subalgebras, congruences
Polynomial operations	term operations + constants from A	composition	congruences only
All operations on A	everything	composition	nothing in general

Two algebras with the same universe and the same clone of term operations satisfy exactly the same identities and have exactly the same subuniverses and congruences. They are said to be term-equivalent, and for most purposes are the same algebra wearing different signatures. Boolean algebras and Boolean rings are the standard example, treated in the Boolean stream.

06Why the term algebra is the reference object

Because it has no accidental equalities, the term algebra is where syntax can be studied without semantic interference.

Reference

Identities are congruences on T(X)

The set of identities holding in a class K, viewed as pairs of terms, is a congruence on the term algebra — and a fully invariant one.

Construction

Free algebras are quotients

F_K(X) = T(X)/θ_K(X), where θ_K(X) collects the pairs of terms that K forces to agree. Every free algebra is built this way.

Completeness

Derivability equals validity

The completeness theorem for equational logic is proved by showing the deductive closure of Σ is exactly the congruence defining the free algebra for M(Σ).

Frequently asked

Is T(X) ever finite?

Only in degenerate cases — if F has no operations of positive arity, so that terms are just variables and constants. Otherwise T(X) is countably infinite whenever X is countable and F contains at least one symbol of arity ≥ 1, since terms of unbounded depth exist.

Why require X ∩ F = ∅?

Purely to keep parsing unambiguous. If a variable could also be an operation symbol, a string would admit more than one parse tree and terms would no longer be well defined as syntactic objects. It is a hygiene condition with no mathematical content.

Can I always tell whether two terms induce the same operation?

Not in general. Deciding whether p ≈ q holds throughout a variety is the word problem for that variety's free algebra, and it is undecidable for some varieties — relation algebras and certain semigroup varieties among them. For a single finite algebra it is decidable by exhaustive evaluation, though expensive.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.