3.9. Term algebras

Condensed drafts

A draft D is condensed if, equivalently,
  1. D is functional, i.e. ΨD is injective;
  2. D has an injective interpretation in some algebra;
  3. For any two distinct elements of D there is an algebra interpreting them differently.
1.⇒2. if D≠∅ (otherwise replace D by a singleton), ∃φ∈DLD, φ০ΨD = IdOD, i.e. IdD interprets D in (D,φ).
2.⇒3.
3.⇒1. ∀x,yOD, if ΨD(x) = ΨD(y) then x,y have the same interpretation in every algebra.

If L only has symbols with arity 0 or 1 then every L-term is condensed.

Any draft D can be reduced to a condensed draft as follows. Let P the L-algebra ℘(D) where
∀(s,u)∈LP, φP(s,u) = {xOD | σ(x)=slx∈∏u}.
Then the interpretation of D in P which sends any variable x to {x}, is the curried form of the only equivalence relation on D which quotients it into a condensed draft. Let us call condensation of D this quotient of D into a condensed draft. This equivalence relation is included in that of any interpretation of D in any algebra, thus quotienting interpretations of D into interpretations of this condensed draft.

Term algebras

An L-algebra (EE) is called a term algebra if it is injective and 〈E\Im φEL = E. Thus it is also a condensed L-draft with ΨE = φE-1. Another usual assumption is that V=VD=E\Im φE, i.e. used variables of a term algebra are usually not regarded as a subset of any larger set of available variables. This term algebra is ground if V=∅, i.e. E=Im φE. So, a ground term L-algebra is an algebra both minimal and injective, and thus also bijective.

If L has no constant then ∅ is a ground term L-algebra.
If L only has constants, then ground term L-algebras are the copies of L.
From any injective L-algebra (EE) and VE \ Im φE one can form the term algebra 〈VL. In particular the existence of an injective algebra implies that of a ground term algebra.

Whenever present as object, any ground term L-algebra is an initial object in any category of L-algebras, and a final object in any category of ground L-drafts. It is thus essentially unique for the given L.
Conversely any initial L-algebra (EE) is a ground term algebra: Similarly, term L-algebras (EE) with E\Im φE=V are the final objects in any variables-preserving category of L-drafts for a given V (this is deducible from the above by replacing variables by constants).

Proposition. For any ground term L-algebra K and any injective L-algebra M, the unique f∈MorL(K,M) is injective.

Proof 1. By the injectivity lemma, {xK | ∀yK, f(x) = f(y) ⇒ x=y} ∈ SubLK, thus = K.
Proof 2. Im f ∈ SubLM is both injective and minimal, thus a ground term L-algebra, so the morphism f between initial L-algebras K and Im f is an isomorphism.

Role of term algebras as sets of all terms

As any draft can be seen as a family of terms, any term algebra (final draft) F precisely plays the more role of the "set of all terms" (with the given list V of variable symbols), as it contains exactly one representative image of each term (operation symbol defined by a term), i.e. any two "equivalent terms" (defining the same operation) have the same image. Namely, any L-term T with root t and VTV, is represented in F by the image of the f∈Mor(T,F) such that f|VT = IdVT, with root f(t).
This f plays the role of condensation (so is injective if and only if T is condensed), respecting the interpretation in any L-algebra E extending any vEV, as the unique g∈MorL(F,E) and h∈MorL(T,E) extending v, are related by h=gf, thus h(t)=g(f(t)).

For any subset A of an L-algebra E and any term algebra whose set of variables is a copy of A, the image of its interpretation in E is 〈AL.

Free monoids

If it exists, any unary term L-algebra M (essentially determined by L), is a monoid acting on all L-algebras, whose actions are preserved by all L-morphisms (MorL ⊂ MorM as they form a category of acts). It serves as set of all (function symbols defined by) unary L-terms. The set of function symbols from L is canonically injected there by j(s) = sM(e) so that in any L-algebra E, ∀xE, j(s)⋅x = sE(x).
Conversely if L is made of function symbols then essentially LM, thus MorL = MorM.
The monoid structure of M was defined from its L-structure; now let us take the monoid structure as primitive and review alternative descriptions from it, of the situation when L was made of function symbols. These function symbols can be replaced by (reinterpreted as) constant symbols, as these 2 interpretations can be defined from each other by terms using the monoid structure: the function defines the constant as s = s(e), while the constant defines the function as ∀xM, s(x) = sx.
For any set X, let us call X-monoid any (X∪{e,•})-algebra M seeing X as a set of constant symbols by some j:XM, such that (e,•) is a monoid structure on M.
Denoting X1 the copy of X seen a set of function symbols, the following statements on M are equivalent; such an M is called a free monoid on X.
  1. M is a unary term X1-algebra with variable e, interpreting the copy x'∈X1 of each xX as ∀yM, x'M(y) = j(x)•y
  2. For any X1-algebra E there is a unique left action ⋅ of M on E such that ∀xX, ∀yE, j(x)⋅y = xE(y)
  3. M is an initial object in the category of X-monoids.
1. is equivalent to: for any X1-algebra E and any xE there is a unique hx ∈ MorX1(M,E) such that hx(e)=x. That is the curried form of the action ⋅ : M×EE.

The uniqueness of the morphism to other X-monoids is expressed by 〈X{e,•} = M.
This equivalence is deducible from seen results, among which the property of trajectories and the representation theorem.
When writing terms with multiple uses of an associative operation symbol, all parenthesis may be removed. For monoids, this removal of parenthesis and also of occurrences of e seen as the empty chain of symbols, is operated by the interpretation of any V-ary {e,•}-term in the free monoid on V.


Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Algebraic terms
3.9. Term algebras
3.10. Integers and recursion
3.11. Presburger Arithmetic
4. Model Theory