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 called 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).

The uniqueness comes from a previous proposition. Let us now prove existence.
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
hK
(CD*(LC) ∋ x↦ (xC ? h(x) : φE(hLD(x))))) ∈ K (see conditional operator)
D*(LC) ⊂ C
C=D

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 was introduced as the operation defined by a term, namely the L-term with root t, which can replace D here without modifying the interpretations of t.

These operations are preserved by all L-morphisms, thus can be added to L without changing the category of L-algebras. This is deducible in two ways from seen preservation properties in concrete categories:

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 exists an algebra where their interpretations differ.
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.

Term algebras

An L-algebra (EE) is called a term algebra if it is injective and 〈E\Im φEL = E. Thus it is also an L-draft with ΨE = φE-1. With this is usually assumed that V=VD=E\Im φE, i.e. variables of term algebras are usually used as an isolated set rather than 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 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 a final object in any category of ground L-drafts, and an initial object in any category of L-algebras. 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. The subalgebra Im f of M 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 element image of each term (operation symbol defined by a term) in the sense that two terms everywhere interpreted as the same operation have the same image.
Namely, any L-term T with root t and VTV, is represented in F by the image Im f with root f(t) of the f∈Mor(T,F) such that f|VT = IdVT.
Im f has the same interpretation as T in any L-algebra E extending any vEV because the unique g∈MorL(F,E) and h∈MorL(T,E) extending v, are related by h=gf, thus h(t)=g(f(t)).
Im f is condensed, and f is injective if and only if T is condensed.

For any subset A of an L-algebra E, the L-subalgebra 〈AL of E is the set of values of all L-terms with variables interpreted in A; it is the image of the interpretation in E, of a term algebra whose set of variables is a copy of A.

The unary term L-algebra M, essentially determined by L, represents all function symbols definable by unary L-terms. As a particular case of category of acts, its interpretations define actions of monoid preserved by morphisms across all L-algebras. Conversely if L is made of function symbols then any M-morphism is an L-morphism, because each sL plays the same role as sM(e)∈M.

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

This equivalence is deducible from the property of trajectories and the representation theorem.
The image of M by any morphism of monoid is the sub-monoid generated by the image of L.
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