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 of a draft D is a sub-draft of D. Moreover, any union of sub-drafts is also a sub-draft (which did not work for sub-algebras because an operation with arity >1 with arguments in different sub-algebras may give a result outside 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 which is its root. Each element t of a draft D defines an L-term with root t, sub-draft of D co-generated by {t}.
Each draft D is naturally ordered by xy ⇔ x∈ (the term with root y). It is obviously a preorder. Its antisymmetry (thus the uniqueness of the root of a given term) can be proven as follows
For each xOD, let A={yODxy} and zOD\A such that Im lzA. Thus A∪{z} is a sub-draft. Thus x=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:

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 does not contain any constant then ∅ is a ground term L-algebra.
If L only contains constants, then ground term L-algebras are the copies of L.

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

We saw above that any draft can be seen as a set of terms. Conversely, any term algebra (final draft) F plays the role of the "set of all terms" with its list V of variable symbols.
Indeed, any L-term T with root t and VTV, is represented in F by the image Im f with root f(t) of its interpretation f∈Mor(T,F) such that f|VT = IdVT. This preserves its 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, the L-subalgebra 〈AL of E is the set of values of all L-terms with variables interpreted in A. Indeed 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