## 4.3. Term algebras

### Synonymous terms

In any draft, xy is the condition for the terms with roots x and y to be synonymous, i.e. taking the same value f(x) = f(y) for any interpretation f of the draft in a partial algebra.

Terms in different drafts D, E with the same variables, can be so compared by interpreting ≃ in their coproduct DV E. Equivalently, for any morphisms f∈MorL,V(D,F), g∈MorL,V(E,F) to a functional draft F,

xD, ∀yE, xyf(x) = g(y).

This equivalence comes from !: MorL,V(DV E, F) ⇌ MorL,V(D,F) × MorL,V(E,F). Then,

h∈MorL,V(D,E), ∀x,yD, h(x) ≃ x ∧ (xyh(x) ≃ h(y))

because ≃Eh ∈ MorL,V(D, ).
Thus ∀x,yD, the meaning of xy is the same for any sub-drafts of D which x and y are respectively considered elements of, such as the terms Tx and Ty (using h∈MorL,V(TxV Ty, D)).

### Term algebras

For any set given set V, a V-ary term L-algebra is an L-system equivalently described as:
1. An algebraic L-draft D where VD = V;
2. An injective L-algebra D generated by V where V ∩ Im φD = ∅ (thus D\Im φD = V);
3. A final L-draft in the sense of variables-preserving morphisms MorL,V ;
4. An L-algebra with basis V in the category of L-algebras.
As any draft, it is qualified as ground if V = ∅, i.e. (by definition 2.) a ground term L-algebra is an algebra both minimal and injective, and thus also bijective; 4. means it is an initial L-algebra.
Intuitively, a V-ary term L-algebra T represents the set of all V-ary operation symbols possibly defined by L-terms ; any V-ary sL has a copy sT(IdV) ∈ T.

Proof of equivalence. Already 1. ⇔ 2. ⇒ (3. ∧ 4.).
Proof of 3. ⇒ 1. : any final L-draft D is

• Functional : ∃f∈MorL,V(⤓D, D), f ⚬ ≃D ∈ MorL,V(D, D) ∴ f ⚬ ≃D = IdD ∴ Inj ≃D
• Serial : MorL,V(D∪(LD\Dom D), D) ≠∅
• VD = V because V is a draft.
Let us prove 4. ⇒ 2. after reduction to the ground case by replacing variables by constants (replacing L by LV).
Any initial L-algebra (EE) is :
• minimal : ∃f∈MorL(E, MinLE), f∈MorL(E,E) ∴ f = IdE ∴ MinLE = E
• injective : (F = LE ∧ φF = LφE) ⇒ φELφE = φE ⚬ φF ⇔ φE∈MorL(F,E)
∴ ∃f∈MorL(E,F), φEf = IdEf⚬φE = φFLf = LEf) = IdF.∎
According to the last formula of 3.4, for any f∈MorL(D,E) where D is an L-term algebra with basis V and E is an L-algebra, we have Im f = 〈f[V]〉L.
Thus for any AE, if there exists an L-term algebra with basis A (this hypothesis can be dispensed of with more work) then 〈AL is the set of values in E of all L-terms with variables in A.

### Term algebras in injective algebras

In any injective L-algebra (EE), the subalgebra 〈VL generated by any VE \ Im φE, is a term algebra. So, the existence of an injective L-algebra implies that of a ground term L-algebra.

For any f∈MorL(K,E) from a ground draft K to an injective system E, the system Im f is both injective and minimal, i.e. a ground draft. As with any morphism, if K is serial then Im f is serial; if E is functional then Im f is functional. Thus, if K is a ground term algebra and E is an injective partial algebra then Im f is a ground term algebra, and thus f is injective (by essential uniqueness of initial or final objects).

Precisely to distinguish statements and their respective ranges of validity,
• If K is a serial minimal system and E is an injective partial algebra then Im f is a ground term algebra;
• If K is a functional ground draft and E is injective then f is injective (because ∼ff(≃Im f) = ≃K = 𝛿K).
Some more complicated statements can be obtained in non-ground cases by applying the above to the language LV.

### Particular languages

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.
If L only has symbols with arity 0 or 1 then every L-term is functional (this may not be obvious ; we shall not use it later).

### Trajectories by transformation sets

For any set of transformations LEE, seen as a set of function symbols interpreted in E,

xE, 〈{x}〉L = {f(x)|f∈〈L{Id,⚬}}
XE, 〈XL = ⋃f∈〈L{Id,⚬} f[X] = ⋃xX 〈{x}〉L

Denoting A = 〈XL, M = 〈L{Id,⚬} and K = {f(x) | (f,x)∈M×X}, the claim is that A = K. As will be clarified below, both A and K mean the set of values of all composites of any number of functions in L, applied to any xX.
Proof of AK
IdEMXK
gL, ∀yK, ∃(f,x)∈M×X, y = f(x) ∧ gfMg(y) = gf(x) ∈ K
K ∈ SubL E
Proof of KA
L ⊂ {fEE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,⚬}EE
M ⊂ End{A}E
fM, XA ∈ Sub{f}Ef[X] ⊂ A. ∎

### Free monoids

A free monoid is a monoid with a basis in the category of monoids. Then its basis is generating (for the same reason as the above case of categories of algebras).

Any unary term L-algebra M (if it exists) is an egg in the category of L-algebras, thus a monoid acting on all L-algebras with MorL ⊂ MorM.

If L is a language of function symbols and M is a unary term L-algebra then L is a basis of M in the category of monoids.
Proof:

Let us confuse every sL with its copy sM(e) ∈ M.
By the representation theorem, any monoid N is isomorphic to a transformation monoid NXX (by taking X = N and reading composition as left action).
Any uNL makes X an L-algebra, thus defines an action f ∈ Mor{e,•}(M,XX) ∧ f|L = u.
Such an f is unique because L is a generating subset of the monoid M identified as a submonoid of the transformation monoid MM:
L{e,•} = {se | s∈〈L{e,•}} = {g(e) | g∈〈{sM|sL}〉{Id,⚬}} = 〈{e}〉L = M.
Finally Im f = f[〈L{e,•}] ⊂ 〈Im u{Id,⚬}N.∎
Conversely, if L is a basis of a monoid M in the category of monoids, then M is a unary term L-algebra.
Proof:
Any L-algebra structure on any set E is uniquely extensible as an M-set structure. Thus MorM ⊂ MorL, and (M, e) is an egg in the category with M-morphisms on the class of L-algebras. Thus
xE, hx ∈ MorM(M,X) ⊂ MorL(M,X) ∧ hx(e) = x.
To conclude that (M, e) is also an egg in the category of L-algebras, we deduce uniqueness from
〈{e}〉L = 〈L{Id,•} = M. ∎
Note: since 〈L{e,•} = M, we have MorL = MorM.

This view of free monoids as unary term algebras on languages of function symbols, can then be re-expressed saying they are made of all finite strings (i.e. tuples) of symbols from a given set, with concatenation in the role of composition. This can be easily understood after the definition of ℕ in 4.4, which is a particular case involved in the general construction.
The unique variables-preserving morphism from any {e,•}-draft to the free monoid with basis its set of variables, is the function of "syntactic simplification" which removes the occurrences of e and "removes all parenthesis", according respectively to the axioms of identity and associativity which define the category of monoids. Such morphisms from {e,•}-term algebras are surjective.

(Old French text)

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
4.1. Algebraic terms
4.2. Quotient systems
4.3. Term algebras
4.4. Integers and recursion
4.5. Presburger Arithmetic
4.6. Finiteness
4.7. Countability and Completeness
4.8. More recursion tools
4.9. Non-standard models of Arithmetic
4.10. Developing theories : definitions
4.11. Constructions
4.A. The Berry paradox
5. Second-order foundations
6. Foundations of Geometry