3.8. Algebraic terms and term algebras

Algebraic drafts

This section aims to formalize as systems in a set theoretical framework, the concept of algebraic term, particular case of terms (first intuitively introduced in 1.5), with a purely algebraic language L (no predicate, logical symbols nor binders) and a set V of variable symbols, still assuming only one type (the generalization to many types is easy).
For convenience we need to start with a wider class of systems: let us call L-draft any L'-system (D,D) where D⊂ (LDD, such that:

Let us denote ∀xOD, ΨD(x) = (σ(x), lx) ∈ LD where σ∈LOD and lxDnσ(x).
Equivalent formulations of well-foundedness are

AOD, (∀xOD, Im lxAVxA) ⇒ A=OD
AD, (VDAD*(LA) ⊂A) ⇒ A = D
AD, VDAD ⇒ ∃xOD\A, Im lxA
AOD, A≠∅ ⇒ ∃xA, A∩ Im lx = ∅

A ground draft is a draft with no variable, i.e. VD=∅. Thus, ΨD: DLD and SubLD = {D}.
Variables in a draft may be reinterpreted as constants: extending ΨD by IdVD : VDV, forms a ground (LV)-draft.

Sub-drafts and terms

Drafts do not have interesting stable subsets (by well-foundedness), but let us introduce another stability concept for them.
A subset AD is a sub-draft of D (or a co-stable subset of D) if, denoting OA = AOD and ΨA = ΨD|OA, we have (Im ΨALA), i.e. ∀xOA, Im lxA.
Indeed, it remains well-founded, as can be seen on the last formulation of well-foundedness.

Like with stable subsets, any intersection of sub-drafts is a sub-draft. Moreover, any union of sub-drafts is also a sub-draft (unlike for sub-algebras with an operation with arity >1, as from arguments in different sub-algebras the result may escape their union).

The sub-draft co-generated by a subset of a draft, is the intersection of all sub-drafts that include it. A term is a draft co-generated by a single element that is its root. Each x in a draft D defines a term Tx with root x, sub-draft of D co-generated by {x}.
Each draft D is ordered by xyxTy. It is obviously a preorder. Proof of antisymmetry (uniqueness of the root):
xOD, VDA={yD|xTy} which is a sub-draft by transitivity of ≤.
xA ∴ ∃zOD\A, Im lzA.
A∪{z} is a sub-draft, thus TzA∪{z} by definition of Tz.
zOD\AxTzx=z. Thus x is determined by A. ∎
More properties of this order will be seen for natural numbers in 3.6, and in the general case with well-founded relations in the study of Galois connections.

Categories of drafts

As particular relational systems, classes of L-drafts form concrete categories. Between two L-drafts D,E,

f ∈MorL(D,E) ⇔ (f[OD]⊂OE ∧ ΨEf|OD= fL০ΨD)

where the equality condition can be split as

σEf|OD = σD
xOD, lf(x)=flx

Another concrete category is that of drafts with variables-preserving morphisms, where V is fixed and morphisms f from a draft D are subject to f|VD = IdVD. This is equivalently expressed reinterpreting variables as constants, as the category of ground (LV)-drafts.

Intepretations of drafts in algebras

For any L-draft D and any L-algebra E, an interpretation of D in E is a morphism f∈MorL(D,E), i.e. f|OD= φEfL০ΨD, also expressible as

xOD, f(x) = σ(x)E(flx)

Any interpretation vEV of variables in an algebra E determines an interpretation of any draft D in E. To simplify formulations, restricting v to VD reduces the problem to the case VD=V.

Theorem. For any L-draft D with VD=V and any L-algebra E, any vEV is uniquely extensible to an interpretation of D:
∃!h∈MorL(D,E), h|V = v, equivalently ∃!hEOD, vh ∈MorL(D,E).

A previous result gives uniqueness : ∀g,h∈MorL(D,E), g|V = v = h|VV⊂ {xD|g(x)=h(x)} ∈ SubLDg=h.
Let us now prove existence (using conditional operator).
S = {AD | VA ∧ Im ΨALA}
vK = ⋃AS {f∈MorL(A,E) | f|V =v}
f,gK, B = Dom f ∩ Dom g ⇒ (f|BKg|BK) ⇒ f|B=g|B
fK Gr f = Gr h
C= Dom h = ⋃fK Dom fS
(CD*(LC) ∋ x↦ (xC ? h(x) : φE(hLD(x))))) ∈ K
D*(LC) ⊂ C

Operations defined by terms

Any element t of an L-draft D defines a V-ary operation symbol, interpreted in each L-algebra E by ∀vEV, tE(v) = h(t) for the unique h∈MorL(D,E) such that h|VD = v|VD. This formalizes the operation defined by a term, namely the L-term with root t in D (which can replace D here without modifying the interpretations of t).

This interpreted operation symbol being the structure defined by (IdV,t), is preserved by all L-morphisms, thus can be added to L without changing the category of L-algebras.
Symbols sL come back as the particular cases of the terms they form themselves where Ψ(t) = (s, IdV).
For the case of "small" (concretely written) terms, this preservation also has a schema of one proof for each term, by re-expressing the term as a formula defining a relation (graph of the operation) using symbols ∃ and ∧, and using the preservation of structures defined by such formulas.

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,φ).
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. In any variables-preserving category of L-drafts for a given V, any term L-algebra (EE) with E\Im φE=V, when present, is a final object.

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, and where the set of function symbols from L is canonically injected by ssM(e).
Conversely if L is made of function symbols then essentially LM, thus MorL = MorM.

A free monoid on a set X (essentially determined by X) is a unary term X-algebra seeing X as a set of function symbols; or equivalently, a monoid M such that XM and

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 and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory