term algebra

A term algebra is the algebra of pure syntax: its elements are the formal expressions you can write in a given language, before any equations are imposed, and the operations are just the act of writing a bigger expression out of smaller ones. Think of it as the set of all unsimplified formulas like ‘(x · y) · z’ and ‘x · (y · z)’, kept strictly distinct as strings even though they will later be forced equal by associativity.

Formally, fix a signature Σ and a set X of variables. The set of Σ-terms over X is defined recursively: every variable in X and every constant of Σ is a term, and if f has arity n and t_1, ..., t_n are terms then f(t_1, ..., t_n) is a term. The term algebra T_Σ(X) has this set of terms as carrier, with each symbol f acting by literal term-formation. It is the free algebra in the variety of all Σ-algebras (the one with no identities), and is sometimes called absolutely free for that reason.

Term algebras supply the raw material from which every other algebra is carved. Any function from X into a Σ-algebra A extends uniquely to a homomorphism T_Σ(X) -> A — this is just ‘evaluation’ of the formula in A. Quotienting T_Σ(X) by the congruence generated by a set of identities E yields the free algebra of the variety Mod(E); thus term algebras plus congruences reconstruct all free algebras, and identities themselves become equalities of terms.