Part 3 : Algebra 1
3.1. Morphisms of relational systems and concrete
categories
For simplicity, let us focus the study on systems with only one type.
For
any number n and any set E, let E^{n}
abbreviate the product E^{Vn} = E×...×E (n times),
that is the set of ntuples of elements of E.
The sets of all nary relations and of all nary operations in E are defined as
 Rel_{E }^{(n)} = ℘(E^{n})
 Op_{E}^{(n)}
= E^{En}
Languages. A language is a set L of "symbols", with
the data of the intended arity n_{s}∈ℕ of each
symbol s∈L. It may be
 A relational language if its symbols aim to represent relations
 An algebraic language if its symbols aim to represent operations.
For any language L and any set E, let L⋆E = ∐_{s∈L}
E^{ns}
A relational language L, aims to be interpreted in a set E as a family
of relations, which belongs to
∏_{s∈L} ℘(E^{ns})
≅ ℘(L⋆E)
Let us now conceive an Lsystem as a pair (E,E) made of a
set E with an Lstructure E⊂L⋆E.
Most often, we shall only use one Lstructure on each set, so that E
can be treated as implicit, determined by E. Precisely, let us take a class of
Lsystems where each E is the intersection of L⋆E
with a fixed class of (s,x), denoted as s(x) because the
n_{s}ary relation s_{E} interpreting each symbol
s∈L in each system E is somehow independent of E:
E={(s,x)∈L⋆E  s(x)}.
s_{E} =
{x∈E^{ns}  s(x)}
= ⃗E(s)
E=∐_{s∈L} s_{E}.
Morphism. Between any 2 Lsystems E,F,
we define the set of Lmorphisms from E to F as
Mor_{L}(E,F) = {f
∈F^{E}∀s∈L,∀x∈E^{ns},
s(x)⇒ s(f০x)}
= {f ∈F^{E}∀(s,x)∈E,
(r,f০x)∈F}.
For any function f, let f_{L}
= (L⋆Domf ∋(s,x) ↦ (s,f০x)).
This gives shorter definitions for sets of morphisms
Mor_{L}(E,F) = {f
∈F^{E} f_{L}[E]⊂F} =
{f ∈F^{E} E⊂f_{L}*F}.
Concrete categories
The concept of concrete category is what remains of a kind of
systems with their morphisms, when we forget which are the
structures that the morphisms are preserving (as we saw that this
structures list can be extended without affecting the sets of
morphisms). Let us introduce a slightly different (more concrete)
version of this concept than the one usually found elsewhere: here,
a concrete category will be the data of
 A class of sets called objects
 A class of functions called morphisms. For any objects
E,F, the set Mor(E,F)⊂F^{E}
of all morphisms from E to F, is the set of all
functions from E to F which are morphisms.
satisfying the following axioms:
 Every morphism belongs to some Mor(E,F), i.e.
its domain is an object and its image is included in an object
(in practice, images of morphisms will be objects too);
 For any object E we have Id_{E} ∈ Mor(E,E)
;
 Any composite of morphisms is a morphism: for any 3 objects E,F,G
, ∀f ∈ Mor(E,F), ∀g∈Mor(F,G),
g০f ∈ Mor(E,G).
The last condition is easily verified for Lmorphisms : ∀(s,x)∈E, (s,f০x)∈F ∴
(s,g০f০x)∈G.
A relational symbol interpreted in a given concrete category is said to be preserved
if all morphisms of the category are also morphisms for this symbol. According to definitions,
each symbol in a language L is preserved in any category of Lsystems.
A category is small if its class of objects
is a set.
Rebuilding structures in a concrete category.
Starting now with any concrete category, its possible preserved families of relations (one relation
in each object) can be produced from some sorts of "smallest building blocks" as follows.
Proposition. In any concrete category, for any choice of tuple t of elements
of some object K, the relation defined in each object E as s_{E}
= {f০t  f∈ Mor(K,E)} is preserved.
Proof : ∀g∈Mor(E,F), ∀x∈s_{E},
∃f∈ Mor(K,E), (x = f০t ∧ g০f∈ Mor(K,F)) ∴
g০x = g০f০t
∈ s_{F}.∎
In a small concrete category, the preserved families of relations are precisely all choices of
unions of those : each preserved s equals the union of those with t
running over s (with K ranging over all objects).
This can be easily deduced from the fact that any union of preserved structures in a
concrete category is a preserved structure (not only finite unions but unions of families
indexed by any set). Any intersection of a family of preserved structures
is also a preserved structure.
However, the case of topology
will show that even giving "all these structures" to the objects of a given concrete category,
the resulting category of relational systems may admit more morphisms than those we started
with (like a closure).
Preservation of some defined structures
In any given category of Lsystems, any further invariant structure
whose defining formula only uses symbols in L and logical symbols
∧,∨,0,1,=,∃ is preserved (where 0, 1, ∨ and ∧ are particular
cases of unions and intersections we just mentioned).
Indeed, for any Lmorphism
f∈Mor_{L}(E,F),
 Substituting arguments of a s∈L by a map σ to n' other variables
(∀E,∀x∈E^{n'}, s'(x)⇔s(x০σ)),
works :
s'(x) ⇒ s(x০σ) ⇒
s(f০x০σ) ⇒ s'(f০x).
 ∀s,s'∈L,n_{s}=n_{s'} ⇒
∀x∈E^{ns}, (s(x)∧s'(x)) ⇒
(s(f০x)∧s'(f০x))
 ∀s,s'∈L,n_{s}=n_{s'}⇒∀x∈E^{ns}
, (s(x)∨s'(x)) ⇒ (s(f০x)∨s'(f০x))
 For 0 and 1 it is trivial
 ∀x,y∈E, x=y ⇒ f(x)=f(y)
 ∀x∈E^{ns},(∃y∈E,
s(x,y)) ⇒ (∃z=f(y)∈F,
s(f০x, z))
Thus, for any f ∈Mor_{L}(E,F),
if a ground formula with language L using the only
logical symbols (=,∧,∨,0,1,∃), is true in E, then it is also
true in F.
However morphisms may no more preserve structures defined with other
symbols (¬,⇒,∀).
Categories of typed systems
While we introduced the notion of morphism in the case of systems
with a single type, it may be extended to systems with several types as
well. Between systems E,F with a common list τ of types (and
interpretations of a common list of structure symbols), morphisms
can equivalently be conceived in the following 2 ways,
apart from having to preserve all structures:
 A tuple (or family) of functions (f_{t})_{t}_{∈}_{τ},
where ∀t∈τ, f_{t}:E_{t}→ F_{t}
where E_{t}⊂E, F_{t} ⊂F
are the interpretations of type t in E anf F
 A function f:E→ F that is a morphism
when regarding τ as a list of unary relation symbols (by the
same idea as the use of classes
instead of types in set theory); or equivalently, such
that h_{F}০f=h_{E}
where h_{E}:E→τ, h_{F}
:F→τ are the functions giving the type of each object.
3.2. Notion of algebra
Algebras. Given an algebraic language L, an Lalgebra
is a set E with an interpretation of each s∈L as an
n_{s}ary operation in E.
Again, let us assume a fixed class of Lalgebras E where each s
is interpreted as the restriction s_{E}
of an n_{s}ary operator s independent of E,
s_{E} = (E^{ns}
∋ x↦ s(x)).
These can be packed as one function
φ_{E} = ∐_{s∈L}
s_{E} = ((s,x) ↦
s(x)) : L⋆E → E.
Such a class of algebras
forms a concrete category with the following concept of morphism.
Morphisms of algebras. For any Lalgebras E,
F,
Mor_{L}(E,F) = {f∈F^{E} 
∀(s,x)∈L⋆E, s_{F}(f০x) =
f(s_{E}(x))} = {f∈F^{E}
φ_{F}০f_{L} = f০φ_{E}}.
When c∈L is a constant (i.e. n_{c}
=0), this condition on f says f(c_{E})=c_{F}.
Such categories can be seen as particular categories
of relational systems, as follows.
Let the relational language L' be a copy of L where to
each s∈L corresponds s'∈L' with increased arity
n_{s'} = n_{s}+1, so that
L'⋆E ≡ ∐_{s∈L}
E^{ns}×E ≡
(L⋆E)×E also expressible as the set of triples
(s,x,y) such that s∈L, x∈
E^{ns} and y∈E.
Each n_{s}ary
operation s_{E} defines an n_{s'}ary
relation s'_{E} ≡ Gr s_{E}.
These are packed as an L'structure
E = Gr φ_{E} ≡ ∐_{s∈L}
s'_{E}.
The resulting condition for an f ∈ F^{E} to be a
morphism is equivalent : (∀(x,y)∈E,
(f_{L}(x),f(y))∈F) ⇔
(∀x∈L⋆E, φ_{F}(f_{L}(x))=
f(φ_{E}(x))).
Subalgebras. A subset A⊂E of an Lalgebra
E will be called an Lsubalgebra of E, if
φ_{E}[L⋆A]⊂A.
Then the restriction φ_{A} of φ_{E}
to L⋆A gives it a structure of Lalgebra.
The set of all Lsubalgebras of E
will be denoted Sub_{L} E. It is nonempty
as E ∈ Sub_{L} E.
For any formula of the form (∀(variables), some formula without
any binder), its truth in E implies its truth in each A∈Sub_{L}
E.
Images of algebras. For any two Lalgebras E,F,
∀f ∈Mor_{L}(E,F), Im f ∈ Sub_{L}F.
The proof uses the finite choice theorem
with (AC 1)⇒(6):
∀(s,y)∈ L⋆Im f,
∃x∈E^{ns},
f০x = y ∴ s_{F}(y)
= f(s_{E}(x))
∈ Im f ∎
Thus trying to exend this result to algebras with infinitary operations, would
require the axiom of choice, otherwise it anyway still holds for injective morphisms.
Let us generalize the concept of algebra, to any L'systems
(E,E), where E ⊂ (L⋆E)×E
needs not be functional. They form the same kind of categories previously
defined, with a different notation (through the canonical bijection depending on the choice of
distinguished argument) by which more concepts can be introduced.
Stable subsets. The concept of subalgebra is generalized as that of stability
of a subset A of E by L :
A ∈ Sub_{L} E ⇔ (E_{*}(L⋆A)
⊂A) ⇔ (∀(s,x,y)∈E,
Im x⊂A ⇒ y∈A).
Stability is no more preserved by direct images by morphisms, but is still preserved by preimages:
Preimages of stable subsets. ∀f∈Mor_{L}(E,F),
∀B∈Sub_{L}F, f *(B) ∈ Sub_{L}
E.
Let A=f *B. Proof for Lalgebras:
∀(s,x)∈L⋆A, f০x
∈ B^{ns}∴ f(s_{E}(x))
= s_{F}(f০x) ∈B ∴
s_{E}(x)∈A.
Proof for L'systems:
∀(x,y)∈E, (f_{L}(x),f(y))∈F∴
(x∈L⋆A ⇒ f_{L}(x)∈L⋆B
⇒ f(y)∈B ⇒ y∈A).∎
Proposition. For any L'system E and any
Lalgebra F,
∀f,g∈Mor_{L}(E,F),
{x∈Ef(x)=g(x)}∈ Sub_{L}E.
Proof : ∀(s,x,y)∈E, f০x=g০x
⇒ f(y) = s(f০x) = g(y). ∎
Intersections of stable subsets. ∀X ⊂ Sub_{L}E,
∩X ∈ Sub_{L} E where ∩X ≝
{x∈E∀B∈X, x∈B}.
Proof:
∀(x,y)∈E, x∈L⋆∩X ⇒ (∀B∈X,
x∈L⋆B ∴ y∈B) ⇒ y∈∩X. ∎
Other way:
E_{*}(L⋆∩X) =
E_{*}(∩_{B∈X} L⋆B)
⊂∩_{B∈X}
E_{*}(L⋆B) ⊂∩X.
Subalgebra generated by a subset. ∀A ⊂ E, the
Lsubalgebra of E generated by A, written
〈A〉_{L,E} or more simply 〈A〉_{L},
is the smallest Lsubalgebra of E including A:
〈A〉_{L}=
∩{B∈Sub_{L}EA⊂B}=
{x∈E∀B∈Sub_{L} E, A⊂B
⇒ x∈B}∈ Sub_{L}E.
For fixed E and L, this function of A is a
closure with
image Sub_{L}E.
We say that A generates E if 〈A〉_{L}=E.
Minimal subalgebra. For any Lalgebra (or other L'system) E,
its minimal subalgebra (or minimal stable subset) is
Min_{L}E =〈⌀〉_{L,E}
= ∩Sub_{L}E ∈Sub_{L}E.
An Lalgebra E is minimal when E = Min_{L}
E, or equivalently Sub_{L}E
= {E}.
Proposition. For any Lalgebra E, ∀A∈Sub_{L}E,
 ∀B⊂A, B∈Sub_{L}E ⇔
B∈Sub_{L}A
 Min_{L}A=Min_{L}E
 A=Min_{L}E ⇔ A is minimal.
Proof: Min_{L}E ⊂ Min_{L}A because
Sub_{L} A ⊂ Sub_{L} E.
Min_{L} A ⊂ Min_{L} E
because ∀B∈Sub_{L}E,
A⋂B∈Sub_{L}A.
∎
(Among subsets of E, other minimal L'systems are included
in Min_{L} E but are not stable).
We can redefine generated subalgebras in terms of minimal
subalgebra with a different language: 〈A〉_{L,E}=
Min_{L∪A} E where A is seen as
a set of constants.
Injective, surjective algebras. An Lalgebra (E,φ_{E})
will be called injective if φ_{E} is injective, and surjective if
Im φ_{E} = E.
Proposition. For any Lalgebras E, F,
 ∀A⊂E, Im φ_{E}⊂A ⇒
A∈Sub_{L}E.
 Any minimal Lalgebra is surjective.
 Min_{L}E =
φ_{E}[L⋆Min_{L}E] ⊂ Im φ_{E}
 ∀A⊂E, 〈A〉_{L} =
A∪φ_{E}[L⋆〈A〉_{L}] ⊂
A∪Im φ_{E}.

∀f ∈Mor_{L}(E,F),
f [Min_{L}E] = Min_{L}F ; more generally
∀A⊂E, f [〈A〉_{L}] =
〈f [A]〉_{L}
Proofs:  φ_{E}[L⋆A] ⊂
Im φ_{E}⊂A ⇒ A∈Sub_{L}E
 Im φ_{E} ∈ Sub_{L}E
 Min_{L}E is surjective
 A∪φ_{E}[L⋆〈A〉_{L}] ∈ Sub_{L} 〈A〉_{L}
 ∀B ∈ Sub_{L}F, f
*(B)∈Sub_{L} E ∴ Min_{L}E
⊂ f*(B) ∴ f [Min_{L}E]⊂B.∎
Injectivity lemma. If E is a surjective algebra and
F is an injective one then ∀f ∈Mor_{L}(E,F),
 A= {x∈E  ∀y∈E, f(x) =
f(y) ⇒ x=y}
∈ Sub_{L}E.
 For each uniqueness quantifier Q (either ∃! or !),
B = {y∈F  Qx∈E, y =
f(x)} ∈ Sub_{L}F
They are essentially the same but let us write separate proofs:
 ∀(s,x)∈L⋆A, ∀y∈E,
f(s_{E}(x)) = f(y) ⇒
(∃(t,z)∈φ_{E}^{•}(y),
s_{F}(f০x)
= f(s_{E}(x)) = f(y) = f(t_{E}(z))
= t_{F}(f০z) ∴ (s=t
∧f০x=f০z) ∴ x=z)
⇒ s_{E}(x)=y.
 As φ_{F} is injective,
∀y∈φ_{F}[L⋆B],
∃!: φ_{F}^{•}(y) ⊂ L⋆B ∴
Qz∈ L⋆E, φ_{F}(f_{L}(z)) = y.
As φ_{F}০f_{L} = f০φ_{E} and
φ_{E} is surjective, we conclude Qx∈E,
y = f(x). ∎
Schröder–Bernstein theorem.
If there exist injections f: E → F and
g: F→ E then there exists a bijection between E and F.
Replacing F by the bijectively related set Im g, simplifies things to
the case F⊂E ∧ g=Id_{F}.
Then a bijection from E to F can be defined as x ↦
(x∈〈E\F〉_{{f}} ? f(x) : x).
3.3. Special morphisms
Let us introduce diverse possible qualifications for morphisms of
relational systems.
Embeddings and isomorphisms
Strong preservation. A function f ∈ F^{E} is said to
strongly preserve a relation symbol or formula r interpreted in each of E
and F, if it preserves both r and ¬r :
∀x∈
E^{nr}, x∈r_{E}
⇔ f০x∈r_{F}.
Embeddings. An f ∈Mor_{L}(E,F)
is called an Lembedding if it strongly preserves all structures :
∀r∈L,∀x∈
E^{nr}, x∈r_{E}
⇔ f০x∈r_{F}.
Isomorphism. An isomophism between algebras is a bijective embedding.
Generally, an isomorphism between objects E and F of a concrete category,
is a morphism (f ∈Mor(E,F)) that is bijective (f
: E ↔ F) and whose inverse is a morphism (f^{ 1}∈Mor(F,E)).
Two objects E, F are said to be isomorphic
if there exists an isomorphism between them.
Injective embeddings are isomorphisms to their images.
Embeddings of algebras
Every injective morphism f between algebras is an embedding
:
∀(s,x,y)∈L'⋆E, f(y)
= s_{F}(f০x) = f(s_{E}(x))
⇒ y=s_{E}(x).
Any embedding between algebras f ∈ Mor_{L}(E,F),
is injective whenever Im φ_{E} = E or some
s_{E} is injective for one of its arguments.
Bijective morphisms of algebras are isomorphisms. This can be deduced
from the fact they are embeddings, or by
f_{L}^{1} = (f^{1})_{L}
∴ φ_{E}০f_{L}^{1} = f
^{1}০f০φ_{E}০f_{L}^{1} = f
^{1}০φ_{F}০f_{L}০f_{L}^{1}
= f ^{1}০φ_{F}.
More generally for relational systems, injectivity is usually added to the definition of the
concept of embedding, as it means strongly preserving the equality relation.
Things can come down to this case by replacing equality in the concept of injectivity by a
properly defined equivalence relation, or replacing systems by their quotient by this relation,
where the canonical surjections would be noninjective embeddings.
Elementary embeddings
Embeddings still strongly preserve structures defined using the
symbols in L and the logical symbols ∧,∨,0,1,¬, and also = in
the case of injective embeddings.
Thus, they also preserve invariant structures defined
using symbols of L and ∧,∨,¬,0,1,∃ where any
occurrence of ¬ comes after (inside) any occurrence of ∃.
Now the full use of firstorder logic comes by removing this restriction on the order of use of logical symbols: an f ∈
Mor_{L}(E,F) is called an elementary embedding
(or elementary Lembedding) if it (strongly) preserves all
invariant structures (defined
by firstorder formulas with language L).
Every isomorphism is an elementary embedding.
Isomorphism ⇒ Elementary embedding ⇒ Embedding ⇒ Injective morphism
Elementary equivalence. Different systems are said to be
elementarily equivalent, if they have all the same true ground firstorder formulas. The existence
of an elementary embedding between systems implies that they are elementarily equivalent.
The most usual practice of mathematics ignores the diversity of elementarily
equivalent but nonisomorphic systems, as well as nonsurjective elementary
embeddings. However, they exist and play a special role in the foundations of
mathematics, as we shall see with Skolem's paradox and
nonstandard
models of arithmetic.
Endomorphisms
An endomorphism of an object E
in a category, is a morphism from E to itself. Their set
is written End(E)=Mor(E,E).
For any set E, ∀f∈E^{E}, ∀A⊂E,
A ∈ Sub_{{f}} E ⇔ f ∈ End_{{A}}E.
Automorphisms. An automorphism of an object E is an isomorphism
of E to itself.
So we have: Automorphism ⇔ (Endomorphism ∧ Isomorphism)
However an endomorphism of E which is an isomorphism to a strict
subset of E, is not an automorphism.
If f∈ End(E) is an invariant elementary embedding then it is an automorphism:
Im f is also invariant (defined by
∃y∈ E, f(y)=x)
∀x∈ E,
x∈Im f ⇔ f(x)∈Im f
Im f = E. ∎
For any relational language L, any Lsystem (E,E) and any
equivalence relation R on E, the quotient set E/R has a natural
Lstructure defined as ⃗R_{L}[E].
It is the smallest Lstructure on E/R such that
⃗R∈ Mor(E, E/R).
3.4. Monoids
Transformations monoids
A transformation of a set E, is a function from E
to itself. The full transformation monoid of E is the set E^{E}
of all transformations of E, seen as an {Id, ০}algebra,
with two operation symbols: the constant Id, and the binary
operation ০ of composition.
More generally, a transformation monoid G of E is an {Id, ০}algebra
G∈Sub_{{Id, ০}}E^{E}, of transformations of E:
 Id_{E} ∈ G
 ∀f,g∈G, g০f ∈ G.
These axioms were those directly subjecting the set of endomorphisms
of a fixed object in a concrete category. In particular, they are
the exact axioms subjecting (defining the concept of) a concrete
category with only one object E.
Permutation groups
A permutation of a set E is a bijective
transformation of E.
The set ⤹E ={f ∈ E^{E} Inj f ∧ Im
f=E} = {f ∈ E^{E}f:E↔E}
of all permutations of E, is a transformation monoid of E called the
symmetric group of E.
A permutation group G of a set E, is a transformation monoid of
E such that G ⊂
⤹E ∧ ∀f∈G, f^{ 1}∈ G.
It will be seen as an algebra with one more operation : the inversion function f↦f^{ 1}. So
it is a {Id,०, ^{1}}subalgebra of ⤹E.
Unlike full transformation monoids and symmetric groups, the concepts of
transformation monoid and permutation group make sense independently of the powerset, as sets of transformations
satisfying the above firstorder stability axioms, ignoring the containing sets E^{E}
or ⤹E.
Trajectories
For any set of transformations L ⊂ E^{E}, seen
as a set of function symbols interpreted in E, ∀x∈E,
〈{x}〉_{L} = {f(x)f∈〈L〉_{{Id, ০}}}.
Intuitively, this is because they mean the same : the set of all composites
of any number of functions in L, applied to x. This will be formalized later.
But here is a simple proof, denoting K={f(x)f∈〈L〉_{{Id, ০}}}:
Proof of 〈{x}〉_{L} ⊂ K
Id_{E}∈〈L〉_{{Id, ০}} ∴ x∈K
(∀f∈〈L〉_{{Id, ০}},∀g∈L, g০f∈〈L〉_{{Id, ০}} ∴
g(f(x))∈K) ∴ K∈Sub_{L}E
Proof of K ⊂ 〈{x}〉_{L}
L ⊂ {f∈E^{E} 〈{x}〉_{L} ∈
Sub_{{f}} E} = End_{{〈{x}〉L}}E
∈ Sub_{{Id, ০}}E^{E} ∴ ∀f∈ 〈L〉_{{Id, ০}},
〈{x}〉_{L} ∈ Sub_{{f}} E
∴ f(x)∈〈{x}〉_{L}. ∎
The trajectory of an element x∈E by a transformation monoid
G of E, is the set it generates
(usually called its orbit when G is a permutation group):
〈{x}〉_{G} = {f(x)f∈G} ⊂ E
As noted in the example in 2.7,
the binary relation on E defined by (y∈〈{x}〉_{G})
is a preorder; it is an equivalence relation if G is a permutation group.
Monoids
A monoid is an algebra behaving like a transformation
monoid, but without specifying a set which its elements may
transform, by which both symbols Id and ০ got their
interpretation. This abstractness can be formalized by renaming
these symbols, respectively as e and •.
Namely, the concept of monoid is the theory made of
 One type
 Two
operation symbols
 a constant symbol e of "identity";
 a binary operation • of "composition"
 Axioms
 Associativity : ∀x,y,z, x • (y • z)
= (x • y) • z so that either term can be more simply
written x • y • z.
 Identity : ∀x, x • e = x
= e • x
Both equalities in the last axiom may be considered separately,
forming two different concepts
 a left identity of a binary
operation • is an element e such that ∀x,
e • x = x
 a right identity of • is an element e' such that ∀x,
x • e' = x
If both a left identity and a right identity exist then they are
equal : e = e • e' = e' which makes
it the identity of • (the unique element satisfying each
identity condition). The existence of a right identity implies the
uniqueness of the left identity, but without right identity, several
left identities may coexist (and similarly switching left and right).
From any associative operation on a set E we can form a
monoid by adding the identity e as an extra element, E'
= E⊔{e} (its identity property defines how composition
extends to it, preserving associativity). Any identity element in E
loses its status of identity in E'.
Cancellativity
An element x is called left cancellative for an operation • if the left
composition by x is injective: ∀y,z,
x•y=x•z ⇒ y=z.
Similarly it is
right cancellative if x•z=y•z ⇒ x=y.
If a right identity e is left cancellative then it is the unique right identity :
e • e' = e = e • e ⇒ e' = e.
The operation • is called cancellative if all its elements are cancellative on both sides.
Any submonoid of a cancellative monoid is cancellative. Not all monoids are cancellative:
the monoid of addition in {0,1, several} is not cancellative as 1+several = several+several.
Submonoids and morphisms of monoids
Any {e, •}subalgebra of a monoid is a monoid, thus called a
submonoid.
From the concept of monoid, replacing the use of e as a constant by ∃e
in the axiom, would weaken or generalize the concepts of submonoids and morphism
as follows.
For any monoid (M, e, •) and any set with a binary operation
(X, ▪), if a function preserves composition f ∈
Mor_{•}(M,X) then its image is a monoid (A, a, ▪)
where A = Im f
and a = f(e)
 f is a morphism of monoid from M to this monoid A.
If the target forms a monoid (X,▪, e') then (by uniqueness of the identity in A)
a=e' ⇔
e'∈ A ⇔ A ∈ Sub_{{e, ▪}} X
but these equivalent formulas may still be false, unless a is cancellative on one side
(a▪a = a = a▪e' ⇒ a = e').
Every embedding between monoids is injective (as the identity element ensures the surjectivity of composition).
3.5. Actions of monoids
Left actions
Now let us give back to monoids their role as sets of transformations.
A left action of a monoid (M,e, •) on a set X, is an operation ⋅ from
M×X to X satisfying the axioms:
 ∀x∈X, e ⋅ x = x;
 ∀a,b∈M, ∀x∈X,
(a • b) ⋅ x = a ⋅ (b ⋅ x).
This turns X into an Malgebra (where M
is seen as a set of function symbols), called an Mset.
Effectiveness and free elements
A left action of M on X can be seen by currying as a
{e, •}morphism from M to X^{X}. A left action is said effective if this morphism is
injective:∀a, b ∈ M, (∀x∈ X,
a·x = b·x) ⇒ a=b
letting
the axioms of action be usable as definitions of e and • from the action, in the same
way the definitions of Id and ০ are reexpressible (from their initial
expressions via the axioms for function) as
determined by the function evaluator.
An element x∈X of an Mset, is free if the function it defines from M to X
is injective. The existence of a free element implies that the
action is effective:
(∃x∈X,
∀a≠b∈M, a·x≠b·x)
⇒ (∀a≠b∈M, ∃x∈X,
a·x≠b·x)
General example.
The monoid of endomorphisms of any typed system E=
∐_{i∈I} E_{i},
acts on every type E_{i} it contains, by
the morphism of monoid from End(E) to
E_{i}^{Ei}
defined by restricting to E_{i} each endomorphism
of E.
Right actions
The opposite of a monoid is the monoid with the same base set but
where composition is replaced by its transposed.
This symmetry of the concept of monoid, leads to the
similar concept of right action of a monoid M on a
set X: it is an operation ⋅ : X × M → X
such that
 ∀x∈ X, x ⋅ e = x;
 ∀a,b ∈ M, ∀ x ∈ X,
(x ⋅ a) ⋅ b = x ⋅ (a
• b)
It defines a function f : M → X^{X} which is not
a morphism but an antimorphism, i.e. a morphism from one
monoid to the opposite of the other (or equivalently viceversa):
f(e)=Id_{X}
∀a,b∈M, f(a • b) =
f(b) ০ f(a)
Commutants
The commutant of any subset A⊂E for a binary operation # in E,
is defined as
C(A) = {x∈E∀y∈A,
x#y = y#x}.
This is a Galois connection:
∀A,B⊂E, B⊂C(A) ⇔ A⊂C(B).
A binary operation # in a set E, is called
commutative when C(E) = E, i.e.
∀x,y∈E, x#y
= y#x.
Proposition. For any associative
operation # on a set E, ∀A⊂E,
 C(A) ∈ Sub_{#}F
 If A⊂C(A) and 〈A〉_{#}=E then # is commutative
Proof:
 ∀x,y∈C(A), (∀z∈A, (x#y)#z
= x#z#y = z#(x#y)) ∴ x#y∈C(A)
 A⊂C(A)∈ Sub_{#}F
⇒ E=C(A)
⇒ A⊂C(E) ∈ Sub_{#}F ⇒
C(E) = E.
Centralizers
In monoids, commutants of subsets are submonoids (as e commutes with all elements). There,
the word "centralizer" is used instead of "commutant". This concept will be later
generalized further, from this unary case (acting as sets of transformations) to clones
of operations with all arities.
The centralizer of any G ⊂ E^{E}, is its monoid
of endomorphisms End_{G} E.
The above commutativity
result works with the weakened assumption 〈A〉_{{e,•}}=E.
When 2 actions of monoids on the same set X commute with each
other, it can be formally convenient to see them acting on a
different side: the commutation
between a∈M acting on the left and b∈N acting on the right
on X is written ∀x∈X,
(ax)b = a(xb)
which formally looks like an associativity law.
Remark. Let M, X be given structures of Malgebras by any
operations • : M×M → M and ⋅ : M×X → X. Then denoting
∀x∈X, h_{x} = (M∋a ↦ a ⋅ x), we have
directly from definitions
h_{x}(e) = x ⇔ e ⋅ x = x
h_{x} ∈ Mor_{M}(M,X) ⇔ ∀a,b∈M,
(a • b) ⋅ x = a ⋅ (b ⋅ x)
h_{e} = Id_{M} ⇔
(∀a∈M, a • e = a) ⇒ ∀g∈Mor_{M}(M,X),
g=h_{g(e)}.
Let us verify that both axioms of monoid suffice to gather all
properties of transformation monoids, and even all properties of
monoids of endomorphisms.
Representation theorem. For any monoid M there exists a language
L of function symbols and an Lalgebra X
such that the monoid End_{L} X is
isomorphic to M.
Proof:
Let L and X be two copies of M.
Give L the right action on X copied from the
composition in M (whose axioms of monoid give those of
action).
Let f ∈ Mor(M, X^{X})
represent the left action of M on X also copied
from the composition in M.
Im f ⊂ End_{L} X by associativity
of the operation from which both actions on opposite sides are
copied.
f is injective because the copy k of e in X
is a free element.
End_{L} X ⊂ Im f because
∀g∈End_{L}X, ∃u∈M, g(k)=uk
∴ (∀x∈X, ∃s∈L,
ks=x ∴ g(x)=g(ks)=g(k)s=uks=ux)
∴ g=f(u) ∎
The bijections identifying L and X as copies of M,
finally do not play any special role: while they are definable from
k, this k itself may be not unique in the role its
plays here.
Trajectories by commutative monoids
Let a monoid M act on a set X, and let k∈X.
The trajectory Y of k by M is
stable by M, thus defines a morphism of monoid from M to Y^{Y}
with image a transformation monoid N of Y.
Forgetting M and X, we have a monoid N with an effective action on Y generated by k.
Now if N is commutative (which is the case if M is commutative) then
k is free for the action of N (thus Y can be seen as a copy of N).
The proof is easy and left as an exercise.
3.6. Invertibility and groups
Inverses
In a monoid (M, e, •), the formula x•y=e
is read "x is a left inverse of y", and "y
is a right inverse of x".
Seeing M as a transformation monoid by left action on itself, this x•y=e
becomes an invertibility of transformations :
∀z,t∈M, y•z = t ⇒ x•t = z
We say x is right invertible
when a right inverse y exists; similarly, y is left invertible.
As right invertible functions are surjective and left invertible functions are injective, the left invertibility of y is equivalent to the surjectivity of the right composition by y ({x•yx∈M} = M)
and implies that y is left cancellative:x•y =
e ⇒ ∀z∈M, z•x•y = z
∀z,t∈M, (y•z = y•t ∧ x•y=e) ⇒
(z = x•y•z = x•y•t
= t)
An element x both left invertible and right invertible is called invertible.
Then any left inverse y and any right inverse z must be equal,
and thus unique, simply called the inverse of x and written x^{1}.
Proof: y•x = e = x•z ⇒ y
= y•x•z = z
If a left invertible element y is also right cancellative then it is invertible: x•y=e ⇒ y•x•y
= e•y ⇒ y•x=e.
This characterization of invertible elements also makes sense for an element x of an
Mset X: saying that x is both generating and free, means that the morphism h_{x}∈ Mor_{M}(M,X) is both surjective
and injective, thus an isomorphism between the Msets M
and X. Then we can still make sense of its invertibility by saying it has an inverse
Mmorphism from X to M.
If x commutes with an invertible element y then it also commutes with its inverse z:
x•y=y•x ⇔ x=y•x•z ⇔ z•x=x•z
An element x of a monoid is called involutive
if it is its own inverse (equivalently on one or both sides): x•x=e. This qualifies an element such as a
transformation, regardless the choice of submonoid containing it (a transformation monoid).
Groups
A group is a monoid where all elements are invertible.
The set of invertible elements in any monoid, is a group :
 it is a submonoid : if x and y are invertible then x•y is invertible,
with inverse y^{1}•x^{1} (like in 2.6).
 Inverses are invertible (and by uniqueness of the inverse, inversion is an involutive transformation of any group).
As any group is cancellative, any submonoid of a group is also cancellative. This has a partial converse (not very easy to prove): any commutative cancellative monoid can be embedded into a commutative group.
We shall soon see the example of the monoid ℕ embedded in the group ℤ.
Subgroups. The concept of subgroup of a group, is equivalently defined as
 a submonoid which is a group, or
 a subalgebra for the language of groups {e, •,^{1}} extending the one {e, •} of monoids,
with the function symbol ^{1} of inversion.
The interpretation of inversion is determined from those of • and e by the axiom
(whose truth in a group implies its truth in every subgroup)
∀x, x•x^{1} =
x^{1}•x = e
The admission of inversion as a symbol, has no effect on morphisms: any morphism of monoid
f from a group G to a monoid preserves the inversion relation,
thus its image G' is a group, and f is a morphism of groups from G to G'.
Thus, an action of a group G on a set
X, can be equivalently conceived as an action of monoid, or as a group morphism from G
to the symmetric group of X.
By the representation theorem,
any group is isomorphic to some permutation groups,
among which the group of automorphisms of an algebra.
As inversion is an antimorphism,
it switches any left action ▪ of G on X into a right
action • by ∀x∈ X, ∀g∈G,
x•g = g^{1}▪x.
The subgroup of a group generated by a subset A, coincides with the
submonoid G generated by A∪A where A={x^{1}x∈A} .
Proof: to check that G is stable by inversion, notice that the definition of G is
stable by inversion (which is involutive), thus G = G.
3.7. Categories
Categories (also called abstract categories for insistence) differ from concrete
categories, by forgetting that objects
are sets (ordered by inclusion) and that morphisms are functions. The concept of monoid
was the particular case of an abstract category with only one object. The general
case of categories is similarly formalized as the data of:
 A class of "objects" of that category, regarded as pure elements (ignoring any inclusion order); the category is called small if this class is a set;
 Between any two objects A,B is given a set Mor(A,B); these are regarded
as pairwise disjoint sets of pure elements;
 To any object A is given an element 1_{A}∈Mor(A,A)
 To any 3 objects A,B,C is given a
composition operation we shall abusively denote by the same
symbol • : Mor(B,C)×Mor(A,B)→Mor(A,C)
satisfying the axioms
 For any objects A,B, ∀x∈Mor(A,B),
x•1_{A} = x = 1_{B}•x
 For any objects A,B,C,D, ∀x∈Mor(A,B),∀y∈Mor(B,C),∀z
∈Mor(C,D), (z•y)•x = z•(y•x)
Isomorphisms in abstract categories are the generalization of invertible elements : an isomorphism f from E to F is an f∈Mor(E,F) such that ∃g∈Mor(F,E), g•f= Id_{E} ∧
f•g= Id_{F} (for concrete categories, this condition is equivalent to
the one we gave).
Like in monoids, the inverse of any isomorphism (= invertible morphism) is unique.
Representation theorem. Any small category can be interpreted
as that of all morphisms in some given list of typed algebras.
Let us fix the set of types as a copy of the set of
objects : from each object X we make a type X'
(not giving to this bijective correspondence any special status).
Each object M is interpreted as a system where each type X' is
interpreted as the set Mor(X',M).
As a language, let us take all morphisms between types: the set of
function symbols from type X' to type Y' is defined as
Mor(Y',X') (with reverse order, as symbols act on the right).
The proof goes on just like with monoids.∎
Functions defined by composition
In any category, any f ∈ Mor(E,F) defines functions
by currying composition with other morphisms to or from another object X:
let us denote (almost following wikipedia but adapted to our concept of concrete category)
 Hom(X, f) = (Mor(X, Dom
f)∋g↦ f•g),
with target Mor(X,F) for any target F of f.
 Hom_{F}(f, X) = (Mor(F,
X)∋g↦ g•f), with target
Mor(E, X). Simplified as Hom(f,X) in abstract
categories where f determines F.
The former respects composition, while the latter reverses
it: for any 4 objects E,F,G,X , ∀f
∈Mor(E, F), ∀g∈Mor(F,G),
Hom(X, g) ০ Hom(X, f) =
Hom(X, g•f)
Hom_{F}(f, X) ০
Hom_{G}(g, X) =
Hom_{G}(g•f, X)
The concepts of cancellativity and invertibility are generalized to categories as follows.
Monomorphism. In a category, a morphism
f∈Mor(E,F)
is called monic, or a monomorphism, if Hom(X,f)
is injective for all objects X.
Epimorphism. In an abstract category, a morphism f∈Mor(E,F)
is called epic, or an epimorphism, if Hom(f,X)
is injective for all objects X:
∀g,h∈Mor(F,X),
g•f=h•f ⇒ g=h.
In our concept of concrete category, we must specify F: we say that
f∈Mor(E,F) is Fepic, or an Fepimorphism,
if all Hom_{F}(f,X) are injective.
In any concrete category, all injective morphisms are monic, and
any morphism with image F is Fepic.
However, the converses may not hold, and exceptions may be uneasy
to classify, especially as the condition depends on the whole
category.
Sections, retractions. When g•f=1_{E} we say that f
is a section of g, and that g is a retraction of f.
 A morphism f∈Mor(E,F) is a section
(or section in F if the category is concrete), if
1_{E}∈Im(Hom_{F}(f,E)),
i.e. ∃g∈Mor(F,E), g•f=1_{E}.
Then f is monic and for all objects X we have
Im(Hom_{F}(f,X)) = Mor(E,X). 
A morphism g∈Mor(F,E)
is a retraction (or retraction on E if the
category is concrete), if 1_{E}∈Im(Hom(E,g)),
i.e. ∃f∈Mor(E,F), g•f=1_{E}.
Then g is epic and for all objects X we have
Im(Hom(X, g)) = Mor(X, F).
Proof: if g•f=1_{E} then for all objects X,
Hom_{F}(f,X) ০ Hom_{E}(g,X)
= Hom_{E}(1_{E},X)
= Id_{Mor(E,X)}, thus
 Hom_{E}(g,X) is injective (g is epic)
 ∀h∈Mor(E,X), h =
h•g•f
= Hom_{F}(f,X)(h•g).
Similarly, Hom(X,g) ০ Hom(X,f) =
Hom(X,1_{E}) = 1_{Mor(X,E)} thus
f is monic and Im(Hom(X,g)) = Mor(X,F).∎
If f is an isomorphism then Hom(X,f) and Hom(X,g)
are bijections, inverse of each other, between Mor(X,E) and Mor(X,F).
Any epic section is an isomorphism. Any monic retraction is an isomorphism.
These dependencies between qualities of morphisms, can be mapped as follows:
Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔ (Section ∧ Epimorphism)
Retraction ⇒ Surjective morphism ⇒ Epimorphism
Section ⇒ Embedding ⇒ Injective morphism ⇒ Monomorphism
In any category, an object X is called an initial
object (resp. a final object) if for all objects Y
the set Mor(X,Y) (resp. Mor(Y,X)) is a
singleton.
Such objects have this remarkable property: when they exist, all such objects are
isomorphic, by a unique isomorphism between any two of them.
Proof: For any initial objects X and Y, ∃f∈Mor(X,Y),
∃g∈Mor(Y,X), g•f ∈Mor(X,X)
∧ f•g ∈ Mor(Y,Y).
But 1_{X} ∈ Mor(X,X) which is a
singleton, thus g•f = 1_{X}.
Similarly, f•g = 1_{Y}.
Thus f is an isomorphism, unique because Mor(X,Y)
is a singleton.∎
By this unique isomorphism, X and Y may be treated as identical to
each other. We say that an initial object is essentially unique.
Such objects exist in many categories, but are not always interesting. For
example, in any category of relational systems containing representatives
(copies) of all possible ones with a given language:
 Singletons are final objects (where all relations are
constantly true); and also in any category of algebras
with a fixed language where they are admitted as objects. In the case of multitype systems, final
objects are made of one singleton per type.
 The only initial object is the empty set (where any nullary
relation, i.e. boolean constant, is false).
Exercise. Given two fixed sets X and Y, consider the
category whose objects are all (E,φ) where E is a set and
φ: E×X→Y, and the morphisms from (E,φ) to (E',φ')
are all f : E→E' such that ∀a∈E,∀x∈X,
φ(a,x) = φ'(f(a),x).
Does it have an initial object ? a final object ?
Categories of acts
From a concrete category C, let C' be the category where
 Objects are all (X,x)
where X is an object of C and x∈X
 Mor((X,x),(Y,y)) =
{f∈Mor(X,Y)  f(x)=y}.
Then we have
 If C is the category of Msets for a monoid (M,e, •) then (M, e) is
an initial object of C' (when seen as acting on itself by •); initial objects are the (X,x)
where x is a free and generating element of X.
 Conversely, if C' has an initial object (M, e) then we can use e to define a
binary operation on M making it a monoid with neutral element e acting on all objects of
C, and all morphisms of C are
Mmorphisms between these Msets (but there may exist other Mmorphisms from objects other than M)
These are direct consequences of the remark
on monoid acts.
For 2., the composition in M is defined as the particular case of the Malgebra structure on
M satisfying axioms of Macts.
The monoid M can be seen as a transposed copy of the monoid
End(M). Indeed for all a, b∈M, h_{a}, h_{b}∈End(M) and
h_{a}(h_{b}(e))=h_{a}(b)=b•a.
The preservation of these interpreted function symbols, letting morphisms of C
remain Mmorphisms, is a particular case of preservation of
relations defined by tuples.
3.8. Algebraic terms and term algebras
Algebraic drafts
As the concept of term was only intuitively
introduced in 1.5, let us now formalize the case of terms using
a purely algebraic language (without logical symbols), called
algebraic terms, as mathematical systems in
a set theoretical framework.
For convenience, let us work with only one type (the generalization to many types is easy)
and introduce a class of systems more general than terms, that we shall call drafts.
Variables will have a special treatment, without adding them as constants
in the language.
Given an algebraic language L, an Ldraft will be an
L'system
(D,D) where D⊂ (L⋆D)×D, such that:
 The transpose ^{t}D of D is the
graph of a function Ψ_{D}: O_{D}
→ L⋆D, whose domain O_{D} = Im D
⊂D is called the set of occurrences in D, and
its complement V_{D}=D\O_{D}
is called the set of variables of D;
 〈V_{D}〉_{L}= D (wellfoundedness condition).
Let us denote ∀x∈O_{D},
Ψ_{D}(x)=(σ(x), l_{x})
∈ L⋆D where s(x)∈L and
l_{x}∈D^{nσ}^{(x)}.
We can also denote σ_{D}(x)=σ(x)
to let σ_{D} be a function with domain O_{D}.
Wellfoundedness can be equivalently written in any of these forms
∀A⊂O_{D}, (∀x∈O_{D},
Im l_{x} ⊂ A∪V_{D} ⇒ x∈A)
⇒ A=O_{D}
∀A⊂D, (V_{D}⊂A ∧
D_{*}(L⋆A) ⊂A) ⇒
A = D
∀A⊂D, V_{D}⊂A≠D
⇒ ∃x∈O_{D}\A, Im l_{x}⊂A
∀A⊂O_{D}, A≠∅ ⇒ ∃x∈A,
A⋂ Im l_{x} = ∅
The set of used variables of (D,D), those which effectively occur,
is V_{D}⋂⋃_{x∈OD}
Im l_{x}. Unused variables can be added or removed
in D while keeping D fixed (by changing
D⊃O_{D}∪(⋃_{x∈OD}
Im l_{x})), so that their presence may be irrelevant.
A ground draft is a draft with no variable, i.e. V_{D}=∅. Thus,
Ψ_{D}: D→ L⋆D and Sub_{L}D
= {D}.
More generally a draft is groundlike if it has no used variable (Dom D⊂ L⋆O_{D}).
Subdrafts and terms
Drafts do not have interesting stable subsets (by wellfoundedness), but let us introduce
another stability concept for them.
A subset A⊂D is a subdraft of D
(or a costable subset of D) if, denoting O_{A}
= A⋂O_{D} and Ψ_{A}= Ψ_{DOA},
we have (Im Ψ_{A}⊂ L⋆A), i.e. ∀x∈O_{A},
Im l_{x}⊂A.
Indeed, it remains wellfounded, as can be seen on the last formulation of wellfoundedness.
Like with stable subsets, any intersection of subdrafts is also a subdraft; the subdraft
cogenerated by a subset is the intersection of all subdrafts that include it.
A term is a draft cogenerated by a single element
which is its root.
Moreover, any union of subdrafts is also a subdraft (which was
not the case for subalgebras because an operation with arity
>1 whose arguments take values in different subalgebras may
give a result outside their union).
There is a natural order relation on each draft D defined by x
≤ y ⇔ x∈ (the term with root y). It is obviously
a preorder. Its antisymmetry is less obvious; a proof for integers will be given
in 3.6, while the general case will come from properties of wellfounded relations
in the study of Galois connections.
Categories of drafts
As particular relational systems, classes of Ldrafts form concrete categories.
Between two Ldrafts D,E,
f ∈Mor_{L}(D,E) ⇔
(f[O_{D}]⊂O_{E} ∧
Ψ_{E} ০ f_{OD}=
f_{L}০Ψ_{D})
where the equality condition can be split as
σ_{E}০f_{OD}
= σ_{D}
∀x∈O_{D},
l_{f(x)}=f০l_{x}
Another kind of category of drafts can be considered, with objects also Ldrafts
but with a common set of variables (V_{D}=V_{E}=V)
and taking smaller sets of morphisms: the variablespreserving morphisms,
i.e. moreover satisfying f_{V} = Id_{V}.
But for any element t in any draft, the term T cogenerated
by {t} has as set of variables T⋂V (which is the set of used variables of
T unless T={t}⊂V) generally smaller than V,
so the admission of terms defined as subsets cogenerated by singletons in
such a category requires this loosening of the condition. This naturally
simplifies when reformulating such categories as those of ground
(L∪V)drafts: in each draft, variable symbols are replaced (reinterpreted) by
constant symbols added to the language, so Ψ_{E} is extended by
Id_{V}, to form a ground (L∪V)draft.
Intepretations of drafts in algebras
For any Ldraft D and any Lalgebra E, an interpretation of
D in E is a morphism f∈Mor_{L}(D,E),
i.e. f_{OD}=
φ_{E}০f_{L}০Ψ_{D},
which can also be written
∀x∈O_{D}, f(x) =
σ(x)_{E}(f০l_{x})
Theorem. For any Ldraft D with set of variables V and
any Lalgebra E, any v∈E^{V}
is uniquely extensible to an interpretation of D:
∃!h∈Mor_{L}(D,E), h_{V}
= v, equivalently ∃!h∈E^{OD}, v∪h
∈Mor_{L}(D,E).
The uniqueness comes from a previous proposition.
Proof of existence.
S = {A⊂D  V⊂A∧ Im Ψ_{A}⊂
L⋆A}
v ∈ K = ⋃_{A∈}_{S}
{f∈Mor_{L}(A,E) 
f_{V} =v}
∀f,g ∈K, B = Dom f ⋂ Dom g
⇒ (f_{B}∈K ∧
g_{B}∈K)
⇒ f_{B}=g_{B}
⋃_{f∈K} Gr f = Gr h
C= Dom h = ⋃_{f∈K} Dom f
∈ S
h ∈ K
(C∪D_{*}(L⋆C) ∋ x↦ (x∈C
? h(x) : φ_{E}(h_{L}(Ψ_{D}(x)))))
∈ K (see conditional operator)
D_{*}(L⋆C) ⊂ C
C=D ∎
Operations defined by terms
A new operation symbol can be defined by any element t of an Ldraft D :
it is the Vary operation defined by the Lterm with root t, that is
cogenerated by t in D.
Its interpretation in each E is defined by ∀v∈E^{V},
t_{E}(v) = h(t)
for the unique h∈Mor_{L}(T,E)
such that h_{T⋂V}=v.
As a particular case of a relation defined by a tuple,
here (Id_{V},t), these operations are preserved by all morphisms between
Lalgebras, and can thus be added to L without changing the sets of morphisms.
Another way to see it is as a particular case of conservation
of relations defined by formulas in categories of relational systems, since any term defining an operation
can be reexpressed as a formula defining the graph of this operation, using logical symbols ∃ and ∧.
The advantage now that it is established for the general case of abstractly conceived terms no
matter their size, instead of concretely written terms on which the conservation property
must be repeatedly used for each occurrence of symbol it contains.
Term algebras
An Lalgebra (E,φ_{E}) is called a term algebra
if it is injective and 〈E\Im φ_{E}〉_{L}
= E. Thus it is also an Ldraft with Ψ_{E}
= φ_{E}^{1}. As such, it is ground if
moreover 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 Lalgebra.
If L only contains constants, then ground term Lalgebras
are the copies of L.
The existence of term algebras in other cases will be discussed in
the next section; let us
admit it for now.
Whenever present as object,
any ground term Lalgebra is a final object in any category of ground
Ldrafts, and an initial object in any category of Lalgebras.
In any variablespreserving category of Ldrafts with a fixed set V of variables
(category of ground (L∪V)drafts), any term Lalgebra
F, when present, is a final object.
Proposition. For any ground term Lalgebra K
and any injective Lalgebra M, the unique
f∈Mor_{L}(K,M) is injective.
Proof 1. By a previous result,
{x∈K  ∀y∈K,
f(x) = f(y) ⇒ x=y}
∈ Sub_{L}K, thus = K.
Proof 2. The subalgebra Im f of M is both injective and
minimal,
thus a ground term Lalgebra, so the morphism f between initial Lalgebras
K and Im f is an isomorphism.
Role of term algebras as sets of all terms
Any term algebra F plays the role of the "set of all terms"
with its list V of variable symbols, for the following reason:
Each element of F bijectively defines a term in F as the subdraft of
F it cogenerates, thus where it is the root.
For any
Lterm T with root t and variables ⊂V,
the unique f∈Mor(T,F) such that
f_{T⋂V} = Id_{T⋂V}
represents it in F as the term Imf with root f(t).
Then its interpretation in any Lalgebra E extending any
v∈E^{V}, is determined by the unique
g∈Mor_{L}(F,E) extending v,
as g০f∈Mor(T,E), with result g(f(t)).
The same for terms whose set of variables V' is interpreted in E by the
composite of a function from V' to V, with one from
V to E (instead of having V'⊂V).
For any subset A of an Lalgebra E, any term algebra
F_{A} whose set of variables is a copy of A,
represents the set of all Lterms with variables interpreted in A.
Then, the Lsubalgebra 〈A〉_{L} of E is the
image of the interpretation of F_{A} in E, i.e. the set of
all values of these terms.
The monoid of unary terms
Let M be a unary term Lalgebra (unary = with one variable; this
algebra is essentially unique for each L). Then its elements play the roles of the function
symbols defined by all possible unary Lterms, and
preserved by morphisms across all Lalgebras, including M itself. Therefore,
thanks to a previous remark,
M is natually a monoid acting on all Lalgebras.
If L is only made of function symbols then for any Lalgebra
E, the image of M in E^{E} is
the transformation monoid generated by the image of L.
3.9. Integers and recursion
The set ℕ
Any theory aiming to describe the system ℕ of natural numbers is called an Arithmetic.
There are several of them, depending on the logical framework and the choice of language.
Let us start with the set theoretical arithmetic, which is the most precise as it determines ℕ up to isomorphism,
i.e. it is a definition of an isomorphism class of systems in
a given universe.
The use of algebra in this formalization may make it look circular, as our study of algebras used
natural numbers as arities of operation symbols. But arithmetic only uses operation symbols with arity
0, 1 or 2, for which previous definitions might be as well written without reference to numbers.
Definition. ℕ is a ground term algebra with
two symbols: a constant symbol 0 ("zero"), and a unary symbol S.
This S is called the successor. Its meaning is to add one
unit (Sn=n+1) as will be seen below.
This definition can be explicited as the following list of 3 axioms on this
{0,S}algebra :
(H0) 
∀n∈ℕ, Sn ≠ 0

: 0 ∉ Im S 
(Inj) 
∀n,p∈ℕ, Sn =
Sp ⇒ n = p 
: S is injective 
(Ind) 
∀A⊂ℕ, (0∈A ∧ ∀n∈A,Sn∈A)
⇒ A=ℕ 
(induction) : ℕ is minimal. 
We can define 1=S0, 2=SS0...
The existence of a ground term {0,S}algebra is an equivalent form of the axiom of infinity, which completes
the set theory we progressively introduced from the beginning to the powerset (with optionally the
axiom of choice),
to form what is essentially the standard foundation of mathematics as practiced by most mathematicians.
It is most conveniently expressed by an insertion of arithmetic into set theory,
in the form of the constant symbols of the set ℕ, its element 0 and its
transformation S, and the above axioms (from which more symbols such as
+ and ⋅ can then be defined).
It will be seen
to imply the existence of term algebras of any language.
Fixing ℕ in its class does not cause any uncertainty thanks to the essential uniqueness of initial {0,S}algebras.
Recursively defined sequences
A sequence of elements of a set E, is a function from ℕ to E
(a family of elements of E indexed by ℕ).
In particular, a recursive sequence in E is a sequence defined as the
only u∈E^{ℕ} such that u ∈ Mor(ℕ,(E,a,f)),
where (E,a,f) is the {0,S}algebra E
interpreting 0 as a∈E and S as f∈E^{E} :
u_{0}=a
∀n∈ℕ, u_{Sn} = f(u_{n}).
As u_{n} also depends on a and f, let us write it as f^{ n}(a).
This notation is motivated as follows.
As an element of a ground term {0,S}algebra, each number n represents a term with symbols 0 and
S respectively interpreted as a and f in E. So, f^{ n}(a) abbreviates
the term with shape n using symbols a and f:
f^{ 0}(a) = a
f^{ 1}(a) = f(a)
f^{ 2}(a) = f(f(a)) 
Reinterpreting the constant 0 as a variable, makes ℕ a unary term
{S}algebra, where each number n is a unary term S^{n} with n
occurrences of S, interpreted in each {S}algebra (E,f)
as the function f^{ n}∈ E^{E}, recursively defined by
f^{ 0} = Id_{E}
∀n∈ℕ, f^{ Sn} = f০f^{ n}
In particular, f^{ 1}=f and f^{ 2} = f০f.
Generally for any f∈E^{E},
g∈E^{X}, the sequence (h_{n}) in E^{X} recursively
defined by (h_{0}=g) and
(∀n∈ℕ, h_{Sn} = f০h_{n})
is h_{n}=f^{ n}০g.
Addition
Like any unary term algebra, ℕ forms a monoid (ℕ, 0, +),
whose actions are the sequences (f^{ n}) for any transformation f.
It is commutative as it is generated by a singleton, {1} (which commutes with itself). Thus the side won't
matter, but conventions basically present it as acting on the right, defining addition as
n+p = S^{p}(n), or recursively as
n + 0 = n
∀p∈ℕ, n+S(p) = S(n+p).
Thus, n+1 = S(n+0) = Sn.
Like in the general case, the action formula ∀n,p∈ℕ, f^{ n+p} = f^{
p}০f^{ n} is deduced from
(f^{n+0}=f^{n} ∧ ∀p∈ℕ,
f^{n+Sp} = f^{S(n+p)
} = f০f^{n+p})
∴
∀a∈E, ∀f∈ E^{E}, (p↦f^{
n+p}(a))∈Mor(ℕ,(E,f^{n}(a),f)),
from which associativity comes as (a+b)+n = S^{n}(S^{b}(a)) =
S^{b}^{+}^{n}(a) =
a+(b+n).
Multiplication
Multiplication in ℕ can be defined as x⋅y =
(S^{x})^{y}(0), or recursively as
∀x∈ℕ, x⋅0 = 0
∀x,y∈ℕ, x⋅(Sy) = (x⋅y)+x
Then generally, ∀f∈E^{E}, f^{ x⋅y}
= (f^{ x})^{y}.
Inversed recursion and relative integers
By induction using commutativity (n+1 = 1+n), ∀f,g∈
E^{E}, g০f = Id_{E}
⇒ ∀n∈ℕ, g^{n}০f^{ n} = Id_{E}.
Thus if f is a permutation then f^{ n} is also a permutation, with inverse
(f^{ n})^{1} = (f^{ 1})^{n}.
Commutativity was just here to show that composing n times is insensitive to sides reversal,
as (f^{ n})^{1} has the more direct recursive definition
(f^{ Sn})^{1} =
(f^{n})^{1}০f.
The system of (relative) integers ℤ is defined as the {0,S}algebra where
 the set ℤ is defined as ℕ ∪ ℕ, where elements of ℕ (natural numbers) are
called positive, and ℕ= {nn∈ℕ} is a copy of ℕ
called the set of negative integers (where n is the opposite of n),
only intersecting ℕ at 0 = 0.
 S_{ℤ} is the permutation extending S_{ℕ} by
∀n∈ℕ, S(Sn)= n, thus letting Gr S_{ℤ} be
the union of Gr S_{ℕ} with its transposed copy in ℕ.
Proposition. ℤ is a commutative group, and for any permutation f of a set E,
there exists a unique (f^{ n})_{n∈ℤ} which is, equivalently, a {0,S}morphism
from ℤ to (E^{E}, Id_{E}, f), or an action of ℤ on E interpreting 1 as f.
Proof: the {0,S}morphism condition requires on ℕ the same n ↦ f^{ n} as above;
on ℕ, it recursively defines f^{ n} =
(f^{ 1})^{n},
namely
 f^{ 0} = Id_{E} = f^{ 0}
 ∀n∈ℕ, f^{ n} = f০f^{ Sn}, equivalently f^{ 1}০f^{ n} = f^{ Sn}
This makes (ℤ,0,S) an initial object in the category of {0,S}algebras
(E,a,f) where f is a permutation. This category is derived as described with categories of acts
from that of
{S}algebras (E,f) where f is a permutation.
Therefore, ℤ is a monoid acting by (f^{ n})_{n∈ℤ} on every set E
with a permutation f.
This monoid is commutative because it is generated by {1, 1}, which commute: (1)+1=0=1+(1).
It is a group: (n)+n = 0 = n+(n) can be deduced either from symmetry ((n)+n∈ℕ ⇔ n+(n)∈ℕ) and commutativity, or from the above result.∎
3.10. Arithmetic with addition
Firstorder theories of arithmetic
Our first formalization of ℕ
was based on the framework of set theory, where it used the powerset to characterize ℕ in an
"essentially unique" way (specify its isomorphism class). It allowed recursion,
from which we could define addition and multiplication.
Let us now consider formalizations in the framework of firstorder logic, thus
called firstorder arithmetic. As firstorder logic cannot fully express the powerset,
the (∀A⊂ℕ) in the
induction axiom must be replaced by a weaker version : it can only be expressed with
A ranging over all classes
of the theory, that is, the only subsets of ℕ defined by firstorder formulas in the given
language, with bound variables and parameters in ℕ. For this, it must take the form of
a schema of axioms, one for each formula that can define a class.
But without the set theoretical framework we used to express and justify the definiteness
of recursive definitions, the successor function no more suffices to define addition and
multiplication. This leaves us with several nonequivalent versions of firstorder arithmetic
depending on the choice of the primitive language, thus nonequivalent versions of the
axiom schema of induction whose range of expressible classes depends on this language:

Bare arithmetic, with the mere symbols 0 and S, is very poor.

Presburger
arithmetic, with addition, starts to be interesting, but still cannot define multiplication.
 Full arithmetic, with addition and multiplication, is finally
able to express all recursive definitions.
Presburger arithmetic
Presburger arithmetic has been proven by experts to be a decidable theory, i.e.
all its ground formulas are either provable or refutable from its axioms. Let us
present its shortest equivalent formalization, describing the set ℕ* of nonzero natural
numbers, with 2 primitive symbols: the constant 1 and the operation +. Axioms will be
∀x,y∈ℕ*, x + (y+1)
= (x+y)+1 
(A1) : + is associative on 1 
∀A⊂ℕ*,(1∈A ∧ ∀x,y∈A,
x+y∈A) ⇒A=ℕ* 
(Min) 
∀x,y∈ℕ*, x + y
≠ y 
(F) 
In set theory, (Min) would make ℕ* a minimal {1,+}algebra. But let us regard our present
use of set theoretical notations as mere abusive abbreviations of works in firstorder logic,
as long as we only consider subsets of ℕ* defined by firstorder formulas in this arithmetical
language. In particular, (Min) will be meant as abbreviating a schema of axioms with A
ranging over all classes in this theory.
(A1) is a particular case of
∀x,y,z∈ℕ*, x + (y+z)
= (x+y)+z 
(As) : + is associative 
Conversely, (A1 ∧ Min) ⇒ (As) :
Let A={a∈ℕ* ∀x,y ∈ℕ*,
x+(y+a) = (x+y)+a}. ∀a,b∈A,
∀x,y ∈ℕ*, x + (y+(a+b))
= x + ((y+a)+b) = (x + (y+a))+b
= ((x + y)+a)+b = (x+y)+(a+b)
∴ a+b ∈ A.
(A1) ⇔ 1∈A.
(A1 ∧ Min) ⇒ A=ℕ* ∎
(As ∧ Min) ⇒ (+ is commutative), as deduced from 1∈C({1}).
Now take ℕ = ℕ*∪{0} where 0∉ℕ*, to which + is extended as ∀n∈ℕ,
0+n = n+0 = n. This extension preserves its properties
of commutativity and associativity.
Define S as ℕ∋x↦ x+1.
These definitions directly imply (H0).
(Ind) ⇒ (Min) :
∀A⊂ℕ*, the set A_{0}= A∪{0}
satisfies 0∈A_{0} and
(1∈A ∧ (∀x,y∈A, x+y ∈A))
⇒ (S0∈A_{0} ∧ (∀x∈A, Sx=x+1
∈A⊂A_{0})) ⇒ A_{0}=ℕ.∎
(As ∧ Min) ⇒ (Ind) in set theory (ignoring our previous definition of ℕ)
Let M=Min_{{0,S}}ℕ.
∀x∈M, M∈Sub(ℕ,x,S) ∧ f_{x}=(M∋y↦x+y)∈Mor((M,0,S),(ℕ,x,S)).
Images of minimal algebras by morphisms are included in any subalgebras: Im f_{x}⊂M.
As M is stable by + and contains 1, it equals ℕ.∎
(As ∧ Min) ⇒ (Ind) in firstorder logic
Let A∈Sub_{{0,S}}ℕ, and B
= {y∈ℕ* ∀x∈A, x+y∈A}.
∀y,z∈B, (∀x∈A, x+y∈A ∴
x+y+z∈A) ∴ y+z ∈B.
(∀x∈A, x+1 ∈A) ⇔ 1∈B ⇒ ((Min)⇒
B=ℕ*).
0∈A ⇒ (∀y∈B, 0+y∈A) ⇒ B⊂A.∎
(F) ⇔ (∀x∈ℕ*, ∀y∈ℕ, x+y ≠ y)
because x+0 = x ≠ 0.
(Inj ∧ Ind ∧ A1) ⇒ (F) : ∀x∈ℕ*,
x+0 ≠ 0
∀y∈ℕ, x+y ≠ y ⇒ x+y+1
≠ y+1.∎
For the converse, we need to use the order relation.
The order relation
From the operation of addition in Presburger arithmetic, let us define binary relations ≤ and < on ℕ and
show that they form an order and its strict order (it coincides with the order
between terms in the common particular case of the set theoretical ℕ, thanks to the properties
of generated preorders) :x<y ⇔ ∃z∈ℕ*, y =
x+z
x≤y ⇔ ∃z∈ℕ, y = x+z
For this, here are successive consequences of (Ind ∧ A1) :
 < is transitive
 x≤y ⇔ (x<y ∨ x=y)
 x<y ⇔ x+1≤y
 ∀A⊂ℕ, A≠∅ ⇒ ∃x∈A, ∀y∈A,
x≤y (to be interpreted as a schema of formulas if we study Presburger arithmetic)
 ∀x,y∈ℕ, x≤y ∨ y≤x
 x<y ⇒ x+z < y+z
Proofs :
 using (As), x < y < z
⇒ (∃n,p∈ℕ*, z = y+p = x+n+p)
⇒ x <z.
 obvious from definitions;
 thanks to (Ind), ℕ is a bijective
{0,S}algebra;
 x≤y ⇒ (x+1≤y ∨ x=y)
0∈{x∈ℕ ∀y∈A, x≤y}=B
∀x∈B, x+1∈B ∨ x∈A
A⋂B=∅ ⇒ (B=ℕ ∴ A=∅)
 from 4. with A={x,y}
 y = x+n ⇒ y+z = x+z+n
∎
(for 5. it is also possible to more directly prove for A={x∈ℕ
∀y∈ℕ, x<y ∨ x=y ∨ y<x}
that 0∈A and ∀x∈A, x+1∈A)
Now, (F) means that < is irreflexive, thus a strict total order
thanks to 1. and 5.
Moreover it implies ∀x,y,z∈ℕ, (x<y
⇔ x+z < y+z) and (x =
y ⇔ x+z = y+z). The last formula
gives (Inj) as a particular case, and means cancellativity, as
sides can be switched thanks to commutativity (deduced from the same
assumptions as shown above).
Proof: the direct implications were shown above; the converses are deduced from there as
< is a strict total order : one of the 3 formulas (x<y), (x
= y), ( y<x) must be true while only one of
(x+z<y+z),
(x+z=y+z), (y+z<x+z)
can.∎
Finally, ≤ is a total order with strict order < and
every nonempty subset A of ℕ has a smallest element (unique by antisymmetry), written min A.
Arithmetic with order
It is possible to express a firstorder arithmetic with language {0,S, ≤}, stronger than {0,S}
but weaker than Presburger arithmetic, in the sense that addition cannot be defined from ≤.
Namely, it can be based on the characteristion of the order by the property:
For all n ∈ℕ, the set {x∈ℕ  n ≤ x}
is the unique A⊂ℕ such that
∀x∈ℕ, x∈A ⇔ (x = n
∨ ∃y∈A, Sy=x).
Its existence in ℘(ℕ) can be
deduced by induction on n; its uniqueness for a fixed n
is deduced by induction on x.
Trajectories of recursive sequences
A trajectory K = Im u where u= (f^{ n}(a))_{n∈ℕ}
is a copy of ℕ as soon as it is an injective {0,S}algebra.
Let us look at the rest of cases (there will turn out to be only one pair in {0,S}⋆K
mapped to a singleton).
Let y the minimal number such that ∃x<y, u_{x}= u_{y}. This x is unique because y is minimal.
The restriction of u to V_{y} is injective; its image being stable, equals K.
As Inj f_{K} ⇔ x=0 ⇔ a∈ Im f_{K} ⇔
f^{n}(a)=a ⇔ (f_{K})^{n} = Id_{K},
a trajectory K where these are true is called a cycle of f with period y; the restriction of
f to K is then a permutation of K.
Picking another element a in such a K would leave both K and y unaffected.
Now if f is a permutation then every cycle of f is also a cycle of f^{ 1} with the same period.
Set theory and foundations
of mathematics
1. First foundations of
mathematics
2. Set theory (continued)
3. Algebra 1
4. Model Theory