term algebra


Let Σ be a signaturePlanetmathPlanetmathPlanetmath and V a set of variablesMathworldPlanetmath. Consider the set of all terms of T:=T(Σ) over V. Define the following:

  • For each constant symbol cΣ, cT is the element c in T.

  • For each n and each n-ary function symbol fΣ, fT is an n-ary operationMathworldPlanetmath on T given by

    fT(t1,,tn)=f(t1,,tn),

    meaning that the evaluation of fT at (t1,,tn) is the term f(t1,,tn)T.

  • For each relational symbol RΣ, RT=.

Then T, together with the set of constants and n-ary operations defined above is an Σ-structureMathworldPlanetmath (http://planetmath.org/Structure). Since there are no relationsMathworldPlanetmathPlanetmath defined on it, T is an algebraic system whose signature Σ is the subset of Σ consisting of all but the relation symbols of Σ. The algebraMathworldPlanetmathPlanetmathPlanetmath T is aptly called the term algebra of the signature Σ (over V).

The prototypical example of a term algebra is the set of all well-formed formulas over a set V of propositional variables in classical propositional logicPlanetmathPlanetmath. The signature Σ is just the set of logical connectives. For each n-ary logical connective #, there is an associated n-ary operation [#] on V, given by [#](p1,,pn)=#p1pn.

Remark. The term algebra T of a signature Σ over a set V of variables can be thought of as a free structure in the following sense: if A is any Σ-structure, then any function ϕ:VA can be extended to a unique structure homomorphismMathworldPlanetmath ϕ:TA. In this regard, V can be viewed as a free basis for the algebra T. As such, T is also called the absolutely free Σ-structure with basis V.

Title term algebra
Canonical name TermAlgebra
Date of creation 2013-03-22 17:35:24
Last modified on 2013-03-22 17:35:24
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 03C99
Classification msc 03C60
Synonym word algebra
Related topic PolynomialsInAlgebraicSystems
Related topic FreeAlgebra