4.3. Term algebras
Synonymous terms
In any draft, x ≃ y (the minimal congruence relation, from 4.2) 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 D ⊔V E.
Equivalently, for any morphisms f∈MorL,V(D,F),
g∈MorL,V(E,F) to a functional draft F,
∀x∈D,
∀y∈E, x ≃ y ⇔ f(x) = g(y).
This equivalence comes from !: MorL,V(D
⊔V E, F) ⇌ MorL,V(D,F)
× MorL,V(E,F) and that, as explained in 4.2, ≃ is the
preimage of = by any variables-preserving morphism to a functional draft.
Then, ∀h∈MorL,V(D,E),
∀x,y∈D, h(x) ≃ x ∧ (x ≃ y ⇔ h(x)
≃ h(y))
because ≃⃗E ⚬ h ∈
MorL,V(D, ⤓E).
Thus ∀x,y∈D,
the meaning of x ≃ y 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(Tx
⊔V Ty, D)).
The category of all terms synonymous to a given term (i.e. terms with synonymous roots, and with
the same variables), has final objects which are the functional ones. In particular,
any two synonymous functional terms are related by a unique isomorphism.
Proof: the results from 4.2 easily imply that for any two synonymous terms D, D',
if D is functional then the natural morphism from it to the condensate of their
coproduct is an isomorphism.∎
Term algebras
For any set given set V, a V-ary term L-algebra is an L-system
equivalently described as:
- An algebraic L-draft D where VD = V;
-
An injective L-algebra D generated by V where
V ∩ Im φD = ∅ (thus D\Im φD = V);
- A final L-draft in the sense of variables-preserving morphisms MorL,V ;
- 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
s∈L 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 L∪V).
Any initial L-algebra (E,φE)
is :
- minimal : ∃f∈MorL(E, MinLE),
f ∈ EndL(E) = {IdE} ∴
MinLE = E
- injective : (F = LE ∧ φF =
LφE) ⇒
φE ⚬ LφE =
φE ⚬ φF
⇔
φE∈MorL(F,E)
∴
∃f∈ MorL(E,F),
φE⚬f ∈ EndL E = {IdE}
∴ f⚬φE =
φF⚬Lf =
L(φE⚬f) = 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 A ⊂ E, if there exists an L-term algebra with basis A
(this hypothesis can be dispensed of with more work) then 〈A〉L 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 (E,φE), the subalgebra 〈V〉L
generated by any V ⊂ E \ 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 ∼f ⊂ f⋆(≃Im f) =
≃K = 𝛿K).
Some more complicated statements can be obtained in non-ground cases by applying the above
to the language L∪V.
Particular languages
If L has no constant then ∅ is a ground term L-algebra and the
only ground L-draft.
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 will be deduced below.
Long composition
In any draft D over a language of function symbols, l∈DOD.
For any x∈D, the subsystem of H = ≤⃗(x) of D
has a structure of L-draft where the role of VH is played by {x}.
Proof. In the general case of drafts we had
<⃗(x) = R⋆ H, so that
∀y∈<⃗(x), H ∩ Im ly ≠ ∅.
With a language of function symbols, the condition
H∩ Im ly ≠ ∅ becomes ly ∈ H and equivalent
to Im ly ⊂ H, making H co-stable outside x.∎
Then, G = Tx ∪ H ⊂ D is a sub-draft with VG =
VTx.
Therefore (D = Tr) ⇒ (r ∈ H ∴ G = D).
So, the order on any term Tr over a language of function symbols is total,
and Tr is essentially the formal composite of both terms Tx and H
for any x ∈ Tr.
It is easy to conclude that Tr is functional with a single used variable; and from this,
that any two synomymous terms are related by a unique isomorphism.
Conversely, denoting S a function symbol, any functional unary {S}-draft
is totally ordered, and more precisely either a
term or a unary term algebra. The proof is essentially the same as above,
replacing the role of S by that of its transpose (it does use the injectivity of S
to ensure the needed antisymmetry of the generated preorder).
Trajectories by transformation sets
For any set of transformations L ⊂ EE, seen as a set of function
symbols interpreted in E, ∀x∈E,
〈{x}〉L = {f(x)|f∈〈L〉{Id,⚬}}
∀X⊂E, 〈X〉L =
⋃f∈〈L〉{Id,⚬} f[X]
= ⋃x∈X 〈{x}〉L
The left equality can be written A = K where A =
〈X〉L, M = 〈L〉{Id,⚬}
and K = {f(x) | (f,x)∈M×X};
the right equality is directly deducible from it (or from the fact unions preserve stability
among subsets of systems with languages of function symbols).
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 x∈X.
Proof of A ⊂ K
IdE ∈ M ∴ X⊂K
∀g∈L, ∀y∈K, ∃(f,x)∈M×X,
y = f(x) ∧ g⚬f ∈ M ∴ g(y) =
g⚬f(x) ∈ K
K
∈ SubL E
Proof of K ⊂ A
L ⊂ {f∈EE| A ∈
Sub{f}E} = End{A}E
∈ Sub{Id,⚬}EE
M ⊂ End{A}E
∀f∈M,
X ⊂ A ∈ Sub{f}E
∴ f[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 (as seen in 3.11) 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 s∈L with its copy sM(e)
∈ M.
By the representation
theorem, any monoid N is isomorphic to a
transformation monoid N ⊂ XX (by taking X
= N and reading composition as left action).
Any u∈NL 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,•} = {s•e | s∈〈L〉{e,•}}
= {g(e) | g∈〈{sM|s∈L}〉{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, using L as a language of function symbols.
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
∀x∈E, 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.
Intuitively, free monoids are made of all finite strings (i.e. tuples) of symbols
from a given set, with concatenation
in the role of composition. We shall formalize this in the next section (4.4).
(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
5. Second-order foundations
6. Foundations of Geometry