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

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 : 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, 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 Proof of KA

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:

Conversely, if L is a basis of a monoid M in the category of monoids, then M is a unary term L-algebra.
Proof: 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