Part 3 : Algebra 1
3.1. Morphisms of relational systems and concrete
categories
Let us formalize the concept of system, focusing for simplicity on those
with only one type. For any number n∈ℕ and any set E, let us denote
 E^{n} = E×...×E = E^{Vn},
set of all ntuples of
elements of E (nary product
or exponentiation).
 Rel_{E}^{(n)} = ℘(E^{n}),
set of all nary relations in E
 Op_{E}^{(n)}
= E^{En}, set of all nary operations in E.
We then denote the set of all operations Op_{E} = ⋃_{n∈ℕ}
Op_{E}^{(n)},
and that of all relations Rel_{E } = ∐_{n∈ℕ} ℘(E^{n}).
Languages
A language L is a set of symbols, with the data of the intended arity
n_{s}∈ℕ of each s∈L. For any set E, let
^{L}E = ∐_{s∈L}
E^{ns}
A relational language is a language L of relation symbols, where each
s∈L aims to be interpreted in any set E as an n_{s}ary relation.
These form a family called an Lstructure on E, element of
∏_{s∈L} ℘(E^{ns})
≅ ℘(^{L}E)
Relational systems
A relational system with language L, or Lsystem, is the data
(E,E) of a set E with an Lstructure E⊂^{L}E.
The case of an algebraic language, whose symbols aim to represent operations,
will be studied in 3.2.
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 imagine given a class of
Lsystems where each E is the intersection of ^{L}E
with a fixed class of (s,x), denoted as a predicate s(x) for how it is naturally
curried: each symbol s∈L is interpreted in each system E as the
n_{s}ary relation s_{E} somehow independent of E,
s_{E} =
{x∈E^{ns}  s(x)}
= ⃗E(s)
E = {(s,x)∈^{L}E  s(x)} =
∐_{s∈L} s_{E}.
For any function f : E → F, let ^{L}f :
^{L}E → ^{L}F defined by (s,x) ↦ (s,f০x).
Im ^{L}f = ^{L}Im f by finite
choice with (AC 1)⇒(6), as arities of symbols are finite (otherwise it still goes for injective f,
or using AC).
∀B⊂F, (^{L}f)*(^{L}B) =
^{L}(f*(B))
Morphism. Between any Lsystems E,F,
we define the set Mor_{L}(E,F) ⊂ F^{E}
of Lmorphisms from E to F
by ∀f∈F^{E},
f ∈ Mor_{L}(E,F) ⇔
∀(s,x)∈E, (r,f০x)∈F
⇔ (∀s∈L,∀x∈E^{ns},
s(x) ⇒ s(f০x))
⇔
^{L}f[E]⊂F ⇔ E⊂(^{L}f)*F.
Concrete categories
The concept of concrete category is what remains of a class of systems with their
morphisms, when we forget which are the structures that the morphisms are preserving
(as we will see this list of structures can be extended without affecting the sets of morphisms).
Let us formalize concrete categories as made of the following data (making this
slightly "more concrete" than the official concept of concrete category from other authors)
 a class of sets called objects ;
 a class of functions called morphisms; then for any objects
E,F, we define
Mor(E,F) = {f∈F^{E}  f is a morphism}
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, 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 s with the data of an interpretation s_{E} ⊂
E^{ns} in every object E of a given concrete
category, is said to be preserved if all morphisms of the category are also morphisms
for this symbol, i.e. ∀f∈Mor(E,F), ∀x∈s_{E},
f০x∈s_{F}. From 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.
Preservation of some defined structures
In any given category of Lsystems, or any concrete category with a given list L
of preserved interpreted symbols, any further invariant structure
whose defining formula only uses symbols in L and logical symbols
∧,∨,0,1,=,∃ is preserved.
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 (¬,⇒,∀).
The above cases of 0, 1, ∨ and ∧ are mere particular cases (the nullary and binary cases)
of the following:
 Any union of a family of preserved structures in a concrete category is a preserved structure.
 Any intersection of a family of preserved structures is also a preserved structure.
Rebuilding structures in a concrete category.
The preserved relations of any concrete category can be generated from the following
kinds of "smallest building blocks".
Proposition. In any concrete category, for any choice of ntuple t
of elements of some object K, the relation s 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}.∎
From these definitions it might happen between objects E⊂F that
s_{E} ≠ s_{F}∩E^{n} but we shall not face this
in our use.
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
ranging over s (with K ranging over all objects).
However the class of relational systems obtained by even giving in this way
"all possible structures" to the objects of an otherwise given concrete category such as
topology, may still admit more morphisms than
those we started with (like a closure).
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 and F
 A function f:E→ F that is a τmorphism
seeing τ as a list of unary relation symbols (like for the use of classes
as notions in set theory), i.e. such
that h_{F}০f=h_{E}
where h_{E}:E→τ, h_{F}
:F→τ are the functions giving the type of each element.
3.2. Notion of algebra
Given an algebraic language L, an Lalgebra is the data
(E,φ) of a set E with an Lalgebraic structure φ : ^{L}E →
E, sum of a family of interpretations of each symbol s∈L as an operation
⃗φ(s)∈Op_{E}^{(ns)}.
Again, we shall usually consider a class of Lalgebras with only one choice of algebraic
structure on each set:
s_{E} : E^{ns}
→ E
φ_{E} = ∐_{s∈L}
s_{E} : ^{L}E → E
This would be the case if the s_{E} were the restrictions of a common
n_{s}ary operator to each E, but this would not allow to
interpret constant symbols r and s in algebras E and F with
r_{E}=s_{E} but
r_{F}≠s_{F}.
These form 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}০^{L}f = 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 the
copy s'∈L' of each s∈L has increased arity
n_{s'} = n_{s}+1, so that
^{L'}E ≡ ∐_{s∈L}
E^{ns}×E ≡
(^{L}E)×E ≡ {(s,x,y)  s∈L ∧
x∈E^{ns} ∧ 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,
(^{L}f(x),f(y))∈F) ⇔
(∀x∈^{L}E, φ_{F}(^{L}f(x))=
f(φ_{E}(x))).
Subalgebras. A subset A⊂E of an Lalgebra E is
called stable by L or an Lsubalgebra of E, if
φ_{E}[^{L}A]⊂A. It is also an Lalgebra,
with structure φ_{A} restriction of φ_{E} to
^{L}A. The set of Lsubalgebras of
E is written Sub_{L} E = {A⊂E 
φ_{E}[^{L}A]⊂A}.
If a formula of the form (∀(variables), formula without
binder) is true in E, then it is true 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.
Proof : φ_{F}[^{L}Im f] = φ_{F}[Im ^{L}f] = Im (f০φ_{E}) ⊂ Im f ∎
Stable subsets of systems
The concept of subagebra is generalized to relational L'systems
(E,E) with possibly nonfunctional structure E ⊂
(^{L}E)×E, as the following condition of stability for subsets A (which no more
makes them algebras) :
A ∈ Sub_{L} E ⇔ (E_{*}(^{L}A)
⊂A) ⇔ (∀(s,x,y)∈E,
Im x⊂A ⇒ y∈A).
We have E ∈ Sub_{L} E.
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.
Proof. Let A=f *B.
For Lalgebras,
∀(s,x)∈^{L}A, f০x
∈ B^{ns}∴ f(s_{E}(x))
= s_{F}(f০x) ∈B ∴
s_{E}(x)∈A.
For L'systems, ∀(x,y)∈E,
(^{L}f(x),f(y))∈F∴
(x∈^{L}A ⇒ ^{L}f(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}(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, we denote
〈A〉_{L,E} or simply 〈A〉_{L}, the
smallest Lstable subset of E including A
(called Lsubalgebra of E generated by A if E is an algebra):
〈A〉_{L} =
{x∈E  ∀B∈Sub_{L}E, A⊂B
⇒ x∈B} =
∩{B∈Sub_{L}E  A⊂B} ∈ Sub_{L}E
For fixed E and L, the function A↦〈A〉_{L} is the
closure, with
image Sub_{L}E, from the relation ∈ between E and Sub_{L}E:
∀X⊂E, ∀Y⊂Sub_{L}E, X ⊂ ∩Y
⇔ (∀B∈Y, X⊂B) ⇔ Y ⊂ {B∈Sub_{L}E  X⊂B}.
We say that A generates E or is a generating subset of E if 〈A〉_{L}=E.
Minimal subalgebra. For any L'system E,
its minimal stable subset (or minimal subalgebra for an Lalgebra)
is defined as
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 L'system 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.
The stable subset generated by A is the minimal one for the extended language
with A seen as a set of constants:
〈A〉_{L,E}= Min_{L∪A} E.
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, ⋃_{x∈A}〈{x}〉_{L} ⊂
〈A〉_{L} =
A∪φ_{E}[^{L}〈A〉_{L}] ⊂
A∪Im φ_{E}

∀f ∈Mor_{L}(E,F),
f [Min_{L}E] = Min_{L}F ∧
∀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 ∴
Q z∈ ^{L}E, φ_{F}(^{L}f(z)) = y.
As φ_{F}০^{L}f = 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.
Proof : replacing F by the bijectively related set Im g, simplifies things to
the case F⊂E.
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 between
relational systems.
Quotient systems
For any relational language L, any Lsystems (E,E) and
(F,F) and any f : E→F we have
f∈Mor(E,F) ⇔ ^{L}f[E]⊂F.
If f : E↠F and ^{L}f[E] =
F then f will be called a projection from E to F.
The role it gives to F is that of quotient of E by ∼_{f}.
Namely, for any equivalence relation R on E, the quotient set
E/R has a natural Lstructure E/R defined as
^{L}⃗R[E].
It is the smallest Lstructure on E/R such that
⃗R∈Mor(E, E/R).
If R ⊂ ∼_{f} then (f ∈ Mor(E,F) ⇔
f/R ∈ Mor(E/R,F).
Given an algebraic language L, an equivalence relation R on E is said to be compatible with an
L'structure E if the quotient structure is a functional graph. If E is an
algebra structure then Dom(E/R) = ^{L}(E/R) so that the
compatibility condition means that the quotient is also an algebra.
For any L'systems (E,E) and (F,F), any
f : E→F, B⊂F and A= f*(B) we have
(f∈Mor(E,F) ∧ B∈Sub_{L}F) ⇒ A∈Sub_{L}E
(F⊂f_{L}[E] ∧ A∈Sub_{L}E) ⇒ B∈Sub_{L}F
^{L}f[E]=F ⇒ (B∈Sub_{L}F ⇔ A∈Sub_{L}E)
Embeddings and isomorphisms
Strong preservation. A relation symbol r interpreted as r_{E}
in E and r_{F} in F is strongly preserved by a function
f ∈ F^{E}, if both r and ¬r are preserved :
∀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 :
E = ^{L}f*(F).
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.
Isomorphism. Between objects E
and F of a concrete category, an isomorphism is a bijective morphism
(f ∈Mor(E,F) ∧ f : E ↔ F)
whose inverse is a morphism (f^{ 1}∈Mor(F,E)). In
the case of relational systems, isomophisms are the bijective embeddings;
injective embeddings are isomorphisms to their images.
Two objects E, F of a category are said to be isomorphic (to each other) if
there exists an isomorphism between them. This is an equivalence predicate, i.e. it works as an equivalence relation on the class of
objects in this category.
The isomorphism class of an object in a category, is the class of all objects
which are isomorphic to it. Then an isomorphism class of objects in a category, is a class
of objects which is the isomorphism class of some object in it (independently of the choice).
For any relational system E and any subset A⊂E, defining the structure of
A by restricting that of E to A,
 Id_{A}∈Mor(A,E), therefore Mor(A,N)
⊂ {g_{A}  g∈Mor(E,N)}
 For any system N, Mor(N,A) =
{h∈Mor(N,E)  Im h ⊂ A}
 An f∈Mor(N,E) is an isomorphism to A
if and only if it is an injective embedding
to E and Im f = A.
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
(^{L}f)^{1} = ^{L}(f^{ 1})
∴ φ_{E}০^{L}f^{ 1} =
f^{ 1}০f০φ_{E}০^{L}f^{ 1}
= f^{ 1}০φ_{F}০^{L}f০^{L}f^{ 1}
= f ^{1}০φ_{F}.
Elementary embeddings
Lembeddings still strongly preserve structures defined with symbols in L
and logical symbols ∧,∨,0,1,¬, and also = in
the case of injective embeddings.
Thus, they also preserve invariant structures whose
formula may use symbols of L and ∧,∨,¬,0,1,∃ but all occurrences
of ∃ precede those of ¬.
Now the full use of firstorder logic comes by removing this restriction on the order of use of
logical symbols: an elementary embedding (or elementary
Lembedding) is a morphism that (strongly) preserves all invariant structures
(defined by firstorder formulas with language L).
An elementary subsystem of a system E is an F⊂E
interpreting L by restriction, such that Id_{F} is an elementary
embedding from F to E, i.e. any formula with parameters in F takes
the same Boolean value whether all its bound variables range in F or all range in
E.
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, automorphisms.
An endomorphism of an object E
in a category, is an element of Mor(E,E) = End(E).
It is nontrivial if it differs from Id_{E}.
An automorphism of an object E is an isomorphism
of E to itself:
Automorphism ⇔ (Endomorphism ∧ Isomorphism)
An endomorphism f∈ End(E) may be an embedding but not an automorphism : just an
isomorphism to a strict subset of E.
But any endomorphism which is an invariant elementary embedding 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. ∎
The Galois connection (End, Inv)
For any set E and any n∈ℕ, the preservation relation
(∀x∈R, f০x∈R) between f∈E^{E}
and R∈Rel_{E}^{(n)} gives
a Galois connection (End, Inv^{(n)}) between their
powersets, where Inv^{(n)}(M) is the set of nary relations
invariant by M ⊂ E^{E}. In particular,
Inv^{(1)} M = Sub_{M} :
∀M⊂E^{E}, ∀F⊂℘(E),
M ⊂ End_{F}E ⇔ (∀f∈M, ∀A∈F,
f[A] ⊂ A) ⇔ F ⊂ Sub_{M}E.
Gathering all arities forms the Galois connection (End, Inv) with Inv =
∏_{n∈ℕ} Inv^{(n)} : ℘(E^{E}) →
∏_{n∈ℕ} ℘(Rel_{E}^{(n)}) ≅
℘(Rel_{E}).
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 algebra
with two operations: the constant Id, and the binary
operation ০ of composition.
A transformation monoid of E is a set M of transformations of E forming an {Id,০}algebra,
M ∈ Sub_{{Id,০}}E^{E} :
 Id_{E} ∈ M
 ∀f,g∈M, g০f ∈ M.
The set of endomorphisms of a fixed object in a concrete category is a transformation monoid.
Any transformation monoid can be seen as a concrete category with only one object.
Monoids
A monoid is an algebra behaving like a transformation monoid, but without
specifying a set which its elements may transform. As both symbols Id and ০ lose
their natural interpretation, they are respectively renamed as e and •. So, the
concept of monoid is the theory
with only one type and
 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
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 identity element on either side).
The existence of a right identity implies the
uniqueness of any left identity, but without right identity, several
left identities may coexist (and similarly with sides reversed).
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},
to which the interpretation of • is extended as determined by the identity axioms
(preserving associativity), but where any identity element
which could exist in E loses its status of identity element in E'.
As the identity axiom ensures the surjectivity of •, every embedding
between monoids is injective.
Any {e,•}subalgebra of a monoid is a monoid, thus called a
submonoid.
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 y•x = z•x ⇒ y = z.
If a right identity e is left cancellative then it is the unique right identity :
e•e' = e = e•e ⇒ e' = e.
An operation is called cancellative if all elements are cancellative on both sides.
For example the monoid of addition in {0,1, several} is not cancellative as 1+several = several+several.
Any submonoid of a cancellative monoid is cancellative.
Commutants and centralizers
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 another Galois connection :
∀A,B⊂E, B⊂C(A) ⇔ A⊂C(B).
Such A,B are said to commute as each element of A
commutes with each element of B.
If • is associative then ∀A⊂E,
C(A) ∈ Sub_{•}F. (Proof: ∀x,y∈C(A), (∀z∈A, x•y•z
= x•z•y = z•x•y) ∴ x•y∈C(A))
Commutants in monoids are called centralizers. They are more precisely submonoids as
obviously e∈C(A).
This can be understood for transformation monoids M⊂X^{X} by the fact it
is an intersection of submonoids: ∀A⊂M,
C_{M}(A) = M ∩ End_{A} X.
This concept will be later generalized to clones
of operations with all arities.
A binary operation • in a set E, is called
commutative when C(E) = E, i.e. ∀x,y∈E, x•y
= y•x.
If A⊂C(A) and 〈A〉_{•}=E then • is
commutative
Proof: A⊂C(A)∈ Sub_{•}F
⇒ E=C(A)
⇒ A⊂C(E) ∈ Sub_{•}F ⇒
C(E) = E.∎
In the case of monoids the conditions
A⊂C(A) and 〈A〉_{{e,•}}=E suffice.
Other concepts of submonoids and morphisms
Modifying the formalization of monoid by replacing the status of e as a constant
by ∃e in the identity axiom, would weaken the concepts of submonoids
and morphism (allowing more of them) as follows.
For any monoid (M,e,•), any set X with a binary operation
▪, and any morphism of composition f ∈ Mor_{{•}}(M,X),
 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)
f ∈ Mor_{{e}}(M,X) ⇔
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').
Antimorphisms. The opposite of a monoid is the monoid
with the same base set but where composition is replaced by its transpose. An
antimorphism from (M,e,•) to (X,e',▪) is a morphism
f from one
monoid to the opposite of the other (or equivalently viceversa):
f(e) = e'
∀a,b∈M, f(a•b) =
f(b)▪f(a)
3.5. Actions of monoids
Left actions
After monoids were deprived of their role as sets of transformations,
it can be given back to them as follows.
A left action of a monoid (M,e, •) on a set X, is an operation ⋅ :
M×X → X such that
 ∀x∈X, e⋅x = x;
 ∀a,b∈M, ∀x∈X,
(a•b)⋅x = a⋅(b⋅x).
Seing M as a set of function symbols, an Malgebra (X, ⋅)
satisfying these axioms is called an Mset.
In curried view, a left action of M on X is a
{e,•}morphism from M to the full transformation monoid X^{X}.
Right actions
A right action of a monoid M on a set X, is like a left action with
sides switched: 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 amounts to a left action of the opposite monoid, and defines an antimorphism from M to X^{X}.
The commutation of 2 submonoids of X^{X} looks like an
associativity formula when written as acting by opposite sides on X:
a∈M left acting on X commutes with b∈N
right acting on X when ∀x∈X,
(a⋅x)⋅b = a⋅(x⋅b)
Effectiveness and free elements
A left action of M on X is said effective if this morphism from M
to X^{X} is injective (thus an embedding):
∀a,b∈M, (∀x∈X,
a·x = b·x) ⇒ a=b
letting e
and • be definable from (i.e. unique for) the given action, like the axioms for functions ensured the sense
of the definitions of Id and ০ from 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.
Any transformation monoid M of a set E acts by restriction on any Mstable
subset A of E, i.e. any preserved A⊂E in the concrete category M
with object E. Thus, the monoid of endomorphisms of any typed system E=
∐_{i∈I} E_{i},
acts on every type E_{i} it contains.
Acts as algebraic structures
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)}.
So in the formula ∀g∈X^{M}, ∀x∈X,
g=h_{x} ⇔
(g∈Mor_{M}(M,X) ∧ g(e)=x)
the ⇒ expresses the axioms of left action of M on X; the ⇐ is implied by
(∀a∈M, a•e = a). This last axiom of monoid (beyond those
of left action of M on itself), comes conversely as a particular case of this ⇐ when
X=M : (Id_{M} ∈
Mor_{M}(M,M) ∧ Id_{M}(e)=e)
⇒ h_{e} = Id_{M}
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,০}}}
∀X⊂E, 〈X〉_{L} =
⋃_{f∈〈L〉{Id,০}} f[X]
= ⋃_{x∈X} 〈{x}〉_{L}
Denoting A = 〈X〉_{L}, M = 〈L〉_{{Id,০}} and K = {f(x)  (f,x)∈M×X},
the claim is that A = K. As we shall formalize later, both A and K
mean the set of all composites of any number of functions in L, applied to any
x∈X.
Proof of A ⊂ K
Id_{E}∈M ∴ X⊂K
∀g∈L, ∀y∈K, ∃(f,x)∈M×X,
y=f(x) ∧ g০f∈M ∴ g(y) =
g০f(x)∈K
K
∈ Sub_{L}E
Proof of K ⊂ A
L ⊂ {f∈E^{E} A ∈
Sub_{{f}}E} = End_{{A}}E
∈ Sub_{{Id,০}}E^{E}
M ⊂ End_{{A}}E
∀f∈M,
X ⊂ A ∈ Sub_{{f}}E
∴ f[X] ⊂ A. ∎
The trajectory of an element x∈E by a transformation monoid
M of E, is the set it generates:
〈{x}〉_{M} = {f(x)f∈M} ⊂ E
For a monoid M, Inv M is made of unions of trajectories of tuples.
Other cases come down to this as ∀L⊂E^{E}, Inv L
= Inv 〈L〉_{{Id,০}}, so that closures can be written
End_{Inv(n)L} E =
{g∈E^{E} ∀x∈E^{n},
∃f∈〈L〉_{{Id,০}}, f০x=g০x}.
End_{Inv L} E =
{g∈E^{E} ∀n∈ℕ,∀x∈E^{n},
∃f∈〈L〉_{{Id,০}}, f০x=g০x}.
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
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 {Id,০, ^{1}}subalgebra
of ⤹E, i.e. a transformation monoid of E made of permutations
and stable by inversion.
While the concepts of full transformation monoid and symmetric group depend on the
powerset, those of transformation monoid
and permutation group can be defined independently of it, as firstorder theories with 2 types.
Trajectories are usually called
orbits in the case of a permutation group.
For any transformation monoid or action of a monoid M on a set E, the
relation defined by its trajectories (∐_{x∈E}
〈{x}〉_{M}) is a preorder
on E (as seen in example in 2.7).
If M is a group then this preorder is an equivalence relation,
whose partition of E is the set of orbits.
Inverses
In a monoid (M,e,•), the formula x•y = e is read
"x is a left inverse of y", or "y is a right inverse of x"; this
x is right invertible (it has a right inverse), and y is left
invertible.
Seeing M as a transformation monoid by left action on itself, this
x•y = e is interpreted as relating transformations :
∀z,t∈M, y•z = t ⇒
x•t = z
As right invertible functions are surjective
and left invertible functions are injective, the left invertibility of y means that the
right composition by y is surjective ({z•yz∈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 is called invertible if it is so both sides. Then its left and right
inverses are equal, thus unique, called the inverse of x and written x^{1}:
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.
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: x•x = e. In particular e is involutive.
Groups
The concept of group is the theory obtained by adding to that of monoid, equivalently
 The axiom that all elements are invertible, or
 The function symbol ^{1} of inversion, with the axiom
∀x, x•x^{1} = x^{1}•x = e
Indeed this latter axiom determines the interpretation of ^{1} from
those of • and e.
Permutation groups are the transformation monoids which are groups (in the first above sense).
A subgroup of a group is equivalently, a submonoid which is a group (not all are: the
submonoid ℕ of the group ℤ is not a subgroup), or a {e, •,^{1}}subalgebra.
The set of invertible elements in any monoid M, is a group:
 If x, y have inverses x^{1}, y^{1},
then x•y has inverse y^{1}•x^{1}.
 Any inverse x^{1} is invertible, with
(x^{1})^{1} = x (inversion is an
involutive transformation of any group).
Its subgroups are all the submonoids
of M which are groups, which may then be called the subgroups of M.
Between groups, a group morphism is equivalently an
{e,•,^{1}}morphism, or an {e,•}morphism, as the latter also
preserve inversion. More generally any {e,•}morphism
from a group to a monoid preserves the inversion relation
{(x,y)  x•y = e = y•x},
thus its image is a group.
In a group, the subgroup generated by a subset A, coincides with the
submonoid G generated by A∪A where A =
{x^{1}x∈A}. (To check that G is stable by
inversion, notice that the definition of G is
stable by inversion, which is involutive, thus G = G.)
Any submonoid of a group is cancellative. This has no general converse, but
some partial ones, such as: any commutative cancellative monoid has an
embedding to a commutative group (this is not very easy to prove).
Special actions
The above 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 might still say it has an inverse in the form of an Mmorphism
from X to M.
Now this can qualify actions (Msets) themselves: let us call an
action monogenic if it is a trajectory (it is generated by a single element),
and free if it is generated by the set of its free elements.
Let us call it regular
if it is both monogenic and free. Then there is a free element that generates it, i.e.
it is Misomorphic to M.
Proof: a generator being generated by the set of free elements, must be in the trajectory
of one of them, which is thus also generating. (On the other hand, a monogenic
action may have free elements without being free).
An action of a group G on a set X, is equivalently
an action of monoid, or a group morphism from G to the symmetric group of X.
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.
If an action of group is monogenic then every element is generating ; if it is free then all elements are free, so that all parts of its partition into orbits are regular.
3.7. Categories
Monoids were introduced as an abstraction of transformation monoids, which
are concrete categories with one object. Generalizing this to pluralities of
objects, a category (also called abstract category for insistence)
differs from a concrete category, by forgetting that objects
are sets and that morphisms are functions. It is made of:
 A class of "objects" of that category (which need not be sets);
the category is small if this class is a set;
 to any objects A,B is given a set Mor(A,B) of
«morphisms from A to B»; these are usually regarded
as pairwise disjoint;
 to any object A is given 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 both axioms, of identity and associativity:
 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)
Generalizing isomorphisms in
concrete categories, an isomorphism f
between objects E and F in an abstract category, is an
f∈Mor(E,F) such that ∃g∈Mor(F,E),
g•f=1_{E} ∧
f•g=1_{F}. This g is unique, called the inverse of
f and written f^{ 1}.
Again, an automorphism of an object E, is an isomorphism from E to itself.
Their set Aut(E) is the group of invertible elements of the monoid
End(E)=Mor(E,E).
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,E)∋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:
∀g,h∈Mor(X,E),
f•g = f•h ⇒ g = h.
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, saying
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}) = Id_{Mor(X,E)} thus
f is monic and Im(Hom(X,g)) = Mor(X,F).∎
A morphism f is an isomorphism if and only if Hom(X,f) :
Mor(X,E) ↔ Mor(X,F); its inverse is then
Hom(X, f^{ 1}).
In any category, Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔
(Section ∧ Epimorphism)
In concrete categories, Section ⇒ Injective morphism ⇒ Monomorphism
In categories of relational systems, Retraction ⇒ Quotient ⇒ Surjective morphism ⇒ Epimorphism
Representation theorem
Theorem. Any small category is isomorphic to that of all morphisms in a family of typed algebras.
The proof essentially repeats the formulas on acts as algebraic structures,
transposed. From the given small category, a family of typed algebras is formed as follows.
 The set T of types copies the set of objects; one type per isomorphism class suffices.
 L = ∐_{t,t'∈T} Mor(t',t) seeing
Mor(t',t) as a set of function symbols from
t to t'.
 Each object E is interpreted as a typed set ∐_{t∈T}
t_{E} where t_{E} =
Mor(t,E).
Each u ∈ Mor(E,F) acts on each type t by Hom(t,u) : t_{E} → t_{F}. These for all u and t
define f : Mor(E,F) →
F^{E}, so that the system of these for all E, F
respects identities and compositions (they form an action in a sense generalized from monoids
to small categories).
Let us prove that f : Mor(E,F) ↔ Mor_{L}(E,F).
Im f ⊂ Mor_{L}(E,F) by associativity
(f commutes with the action of L).
The existence of an isomorphism k ∈ t_{E} ensures that
f is injective (as k is epic) and
Mor_{L}(E,F) ⊂ Im f:
∀g∈Mor_{L}(E,F), u =
g(k)•k^{1} ∈ Mor(E,F)
⇒ (∀x∈E, ∃s∈L, k•s = x ∴ g(x) = g(k•s) =
g(k)•s = u•k•s = u•x)
⇒ g = f(u) ∎
In particular for any monoid M there is a language
L of function symbols and an Lalgebra X
such that End_{L} X is
isomorphic to M.
Any group is isomorphic to a permutation group, namely the group of automorphisms
of an algebra.
3.8. Initial and final objects
In any category, an object X is called an initial object if all sets
Mor(X,Y) are singletons. Of course any object isomorphic to an initial object is
also an initial object, as all isomorphic objects have the same properties. But conversely
all initial objects (if they exist) are isomorphic, by a unique isomorphism between any two of them:
For any initial objects X, Y, ∃f∈Mor(X,Y),
∃g∈Mor(Y,X), g•f ∈ Mor(X,X) ∧
1_{X} ∈ Mor(X,X) ∴ 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. Initial objects are said to be essentially unique.
Similarly, an object X is called a final object if all sets Mor(Y,X)) are
singletons.
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 where relations are constantly true, are final objects in categories
of onetype systems or algebras;
for multitype systems, final objects are made of one singleton per type.
 The empty set where Boolean constants are false is the initial object.
Exercise. Given two fixed sets K and B, consider the category where
 Objects are all (X,φ) where X is a set and φ: X×K→B ;
 Mor((X,φ),(Y,φ') = {f∈Y^{X} 
∀a∈X,∀k∈K, φ(a,k) = φ'(f(a),k)}.
Does it have an initial object ? a final object ?
Embeddings in concrete categories
In categories of relational systems, any section is an embedding, but without converse in general.
For any subset A of an object of such a category,
(There exists a section with image A) ⇔ (for any object N, Mor(A,N) =
{g_{A}  g∈Mor(E,N)})
⇒ (any embedding with image A is a section).
For images A of embeddings which are not sections, that formula for
Mor(A,N) would not generally fit the concept of morphisms for any relational structure
on A. Also in some categories of systems, not all subsets A of systems E are
images of embeddings, because they do not fit as objects, particularly if the restricted structure
on A fails at some chosen axiom. For example
categories of algebras do not accept all subsets as subalgebras.
Let us generalize the concept of embedding to any concrete category C, making
it work the same as in categories of relational systems beyond the case of sections
(but unlike sections, it will require checking the whole category).
For any subset A of an object E of C, let ToA be the category where
 Objects are all Cmorphisms f into A, conceived as
(F, f) where F is any object of C, f ∈
Mor_{C}(F,E) and Im f ⊂ A ;
 Mor_{ToA}((F, f),(G, g)) =
{h∈Mor_{C}(F,G)  f = g০h}
The injectivity of f implies the uniqueness of any ToAmorphism to
f.
Now a morphism f in C is an embedding if it is a final object of any
ToA. Then it is also a final
object of To(Im f). It is an embedding onto A if moreover A = Im f.
All such embeddings, even noninjective ones, are monic : Section ⇒ Embedding ⇒ Monomorphism.
While C may have been given with pairwise disjoint objects ("forgetting" the canonical injections between
them), any image A = Im f of an injective embedding f
may receive a role of object added to C (we may call it a subobject),
as an additional representative of an existing isomorphism class in C,
by copying to A through f (seen as an isomorphism)
the sets of morphisms involving Dom f (independently of the choice of
f because of its essential uniquess as a final object of ToA).
But for an image A of noninjective embedding, the new object must stay another set
with a surjection to A.
Products in concrete categories
For any family of objects (E_{i})_{i∈I} of a concrete category,
their product, if it exists, is defined as an object P =
∏_{i∈I} E_{i}
with sets of morphisms to it defined by
For any object F, Mor(F,P) ≅
∏_{i∈I} Mor(F,E_{i})
Here, the inclusion (Inc), or rather the canonical injection, of Mor(F,P) into
∏_{i∈I} Mor(F,E_{i}) for all F,
is equivalent to ∀i∈I, π_{i}∈Mor(P,E_{i}).
Any data of Lalgebra structures φ_{i} on each E_{i}
defines the one φ_{P} on P, by
(∀i∈I, π_{i}∈Mor_{L}(P,E_{i})) ⇔
(∀i∈I, φ_{i}০^{L}(π_{i})
= π_{i}০φ_{P}) ⇔
φ_{P} = ∏_{i∈I} φ_{i}০^{L}(π_{i})
thus (Inc) suffices to determine the algebraic structure of P, and imply the reverse inclusion.
In the more general case, assuming (Inc), the reverse inclusion not only defines Mor(F,P),
but also determines all Mor(P,F) from the category if it allows such a product as an object, by
making essentially unique any coexisting products of a given family of objects in a given
category. This essential uniqueness is verified in the following more general case.
Products in categories
A product of any family of objects (E_{i})_{i∈I}
in a category, is a final (thus essentially unique) data (P, φ) of an object P with
φ∈∏_{i∈I} Mor(P,E_{i}), i.e. making bijective all
f ↦ (φ_{i}•f)_{i∈I} :
For all object F, ∏_{i∈I}
Hom (F,φ_{i}) :
Mor(F,P) ↔ ∏_{i∈I} Mor(F,E_{i})
Empty products (I=∅) are the final objects. The concept of embedding
is a variant of the unary case (itself trivial).
In concrete categories, for any (P, φ) and any F, (∏φ : P
↪ ∏_{i∈I} E_{i}) ⇒
Inj ∏_{i∈I} Hom (F,φ_{i})
but products as just defined may exist without admitting as such the set theoretical one
(P, π) where P = ∏_{i∈I}
E_{i} and ∏π = Id_{P}.
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,
seeing M as an Mset interpreting • as left action, (M, e) is
an initial object of C' ; initial objects are the (X,x)
where x is a free and generating element of X.
 Conversely, for any initial object (M,e) of C' (if that exists), there
is a unique monoid structure (M,e,•) with an action on every other object
X of C (beyond • on M itself), such that for all objects X,
Y of C we have Mor(X,Y) ⊂ Mor_{M}(X,Y)
and Mor(M,X) = Mor_{M}(M,X).
Proof. 1. by properties of acts
as algebraic structures and inverses, as x is
free and generating in X if and only if (X,x) is isomorphic to (M, e).
2. Defining ∀x∈X, h_{x} ∈ Mor(M,X) ∧
h_{x}(e) = x, provides an Mstructure on
each X which interprets each a∈M in X as defined by the tuple (e,a).
So they are preserved: Mor(X,Y) ⊂ Mor_{M}(X,Y),
which implies the axioms of Macts.
The composition in M coming as this
Mstructure for M = X, satisfies the same axioms.
The last axiom of monoid, h_{e} = Id_{M} comes from the
uniqueness of h_{e} obeying its definition, and ensures the reverse inclusion:
∀g∈Mor_{M}(M,X),
g = h_{g(e)} ∴ g ∈ Mor(M,X). ∎
This monoid (M,e,•) is essentially the opposite of the monoid
End(M). Indeed for all a, b∈M we have h_{a}
∈ End(M), h_{b} ∈ End(M) and
h_{a}০h_{b}(e) =
h_{a}(b) = b•a.
3.9. Algebraic terms
Algebraic drafts
The concept of algebraic term with a purely algebraic language L
and a set V of variable symbols (no predicate, logical symbols nor
binders), which was first intuitively introduced in
1.5), is going to be formalized as systems
in a set theoretical framework. For convenience let us work with one type
(the generalization to many types is easy), and start with a wider class of
systems.
Let us call Ldraft
any 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, with domain O_{D} = Im D = D\V
called the set of occurrences in D (which differs from our first intuitive
notion of occurrences), and its complement V_{D} = D∩V
is the set of used variables of D;
 〈V_{D}〉_{L}= D (wellfoundedness condition).
Let us denote ∀x∈O_{D},
Ψ_{D}(x) = (σ(x), l_{x})
∈ ^{L}D where σ∈L^{OD} and
l_{x}∈D^{nσ}^{(x)}.
Equivalent formulations of wellfoundedness are
∀A⊂O_{D}, (∀x∈O_{D},
Im l_{x} ⊂ A∪V ⇒ 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} = ∅
A ground draft is a draft with no variable, i.e. V_{D}=∅. Thus,
Ψ_{D}: D→ ^{L}D and Sub_{L}D
= {D}.
Variables in a draft may be reinterpreted as constants: extending Ψ_{D}
by Id_{VD} : V_{D} → V,
forms a ground (L∪V)draft.
Subdrafts and terms
Drafts do not have interesting stable subsets (by wellfoundedness), but
another stability concept: 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 a subdraft. Moreover,
any union of subdrafts is also a subdraft (unlike for subalgebras with an operation
with arity >1, which from arguments in different subalgebras may give a result escaping
their union).
The subdraft cogenerated by a subset of a draft, is the intersection of all subdrafts
that include it. A term is a draft cogenerated by a single element that is its root.
Each x in a draft D defines a term T_{x} with
root x, subdraft of D cogenerated by {x}.
Each draft D is ordered by x ≤ y ⇔ x∈T_{y}.
It is obviously a preorder.
Proof of antisymmetry (uniqueness of the root):
∀x∈O_{D}, V_{D} ⊂
A={y∈Dx∉T_{y}} which is a subdraft
by transitivity of ≤.
x∉A ∴ ∃z∈O_{D}\A,
Im l_{z}⊂A.
A∪{z} is a subdraft, thus T_{z}⊂A∪{z}
by definition of T_{z}.
z∈O_{D}\A ∴
x∈T_{z} ∴ 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 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}=
^{L}f০Ψ_{D})
where the equality condition can be split as
σ_{E}০f_{OD}
= σ_{D}
∀x∈O_{D},
l_{f(x)}=f০l_{x}
Another concrete category is that of drafts with variablespreserving morphisms, where V
is fixed and morphisms f from a draft D are subject to
f_{VD} = Id_{VD}.
This is equivalently expressed reinterpreting variables as constants, as the category of ground
(L∪V)drafts.
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}০^{L}f০Ψ_{D},
also expressible as
∀x∈O_{D}, f(x) =
σ(x)_{E}(f০l_{x})
Any interpretation v∈E^{V} of variables in an algebra E
determines an interpretation of any draft D in E. To simplify formulations,
restricting v to V_{D} reduces the problem to the case
V_{D}=V.
Theorem. For any Ldraft D with V_{D}=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).
Uniqueness is deduced from
wellfoundedness : ∀g,h∈Mor_{L}(D,E),
g_{V} = v = h_{V} ⇒
V⊂ {x∈Dg(x) = h(x)} ∈
Sub_{L}D ⇒ g=h.
Let us now prove existence (using conditional operator).
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}(^{L}h(Ψ_{D}(x)))))
∈ K
D_{*}(^{L}C) ⊂ C
C=D ∎
Operations defined by terms
Any element t of an Ldraft D defines a Vary
operation symbol, interpreted in each Lalgebra E by
∀v∈E^{V}, t_{E}(v) = h(t)
for the unique h∈Mor_{L}(D,E)
such that h_{VD} =
v_{VD}.
This formalizes the operation
defined by a term, namely the Lterm with root t in D (which
can replace D here without modifying the interpretations of t).
This interpreted operation symbol being the structure defined by
(Id_{V},t), is preserved by all Lmorphisms, thus
can be added to L without changing the category of Lalgebras.
Symbols s∈L come back as the particular cases of the terms they form
themselves where Ψ(t) = (s, Id_{V}).
For the case of "small" (concretely written) terms, this preservation also has a
schema of one proof for each term: reexpressing
the term as a formula defining a relation (graph of the operation) using symbols ∃ and ∧,
we can use the preservation
of structures defined by such formulas.
3.10. Term algebras
Condensed drafts
A draft D is condensed if, equivalently, D is functional,
i.e. Ψ_{D} is injective;
 D has an injective interpretation in some algebra;
 For any two distinct elements of D there is an algebra interpreting
them differently.
1.⇒2. if D≠∅ (otherwise replace D by a singleton),
∃φ∈D^{LD},
φ০Ψ_{D} = Id_{OD}, i.e.
Id_{D} interprets D in (D,φ).
2.⇒3.
3.⇒1. ∀x,y∈O_{D}, if Ψ_{D}(x) =
Ψ_{D}(y) then x,y have the same interpretation
in every algebra.
Any draft D can be reduced to a condensed draft as follows.
Give
℘(D) the Lalgebra structure (s,u) ↦
{x∈O_{D}  σ(x)=s ∧ l_{x}∈∏u}.
Then the interpretation of D in ℘(D) which sends any variable x to {x},
is the curried form of the only equivalence relation on D which quotients it
into a condensed draft.
Let us call condensation of D this projection of D
to a condensed draft. This is the (not typographically convenient) way to confuse
the repeated subterms of a given term (or draft), which will have the same meaning
in all algebras.
This equivalence relation is included in that of any interpretation
of D in any algebra, thus quotienting interpretations of D.
We can also compare separately given terms by reducing them
to this case as any disjoint union
of drafts (only keeping variables in common) is a draft.
If L only has symbols with arity 0 or 1 then every Lterm is condensed.
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 a condensed Ldraft with Ψ_{E}
= φ_{E}^{1}. Another usual assumption is that
V=V_{D}=E\Im φ_{E}, i.e.
used variables of a term algebra are usually not regarded 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
Lalgebra is an algebra both minimal and injective, and thus also bijective.
If L has no constant then ∅ is a ground term Lalgebra.
If L only has constants, then ground term Lalgebras are the
copies of L.
From any injective Lalgebra (E,φ_{E}) and
V ⊂ E \ Im φ_{E} one can form the term algebra
〈V〉_{L}. In particular the existence of an injective
algebra implies that of a ground term algebra.
Whenever present as object, any ground term Lalgebra is an
initial object in
any category of Lalgebras, and a final object in any category of ground
Ldrafts. It is thus essentially unique for the given L.
Conversely any initial Lalgebra (E,φ_{E})
is a ground term algebra:
 minimal : ∃f∈Mor_{L}(E,Min_{L}E),
f∈Mor_{L}(E,E)∴ f=Id_{E} ∴
Min_{L}E=E
 injective : (F = ^{L}E ∧ φ_{F} =
^{L}φ_{E}) ⇒
φ_{E}∈Mor_{L}(F,E) ∴
∃f∈Mor_{L}(E,F),
φ_{E}০f = Id_{E}
∴ f০φ_{E} =
φ_{F}০^{L}f =
^{L}(φ_{E}০f) = Id_{F}.
Similarly, term Lalgebras (E,φ_{E}) with
E\Im φ_{E}=V are the final objects in any
variablespreserving category of Ldrafts for a given V (this is
deducible from the above by replacing variables by constants).
Proposition. For any ground term Lalgebra K
and any injective Lalgebra M, the unique
f∈Mor_{L}(K,M) is injective.
Proof 1. By the injectivity lemma,
{x∈K  ∀y∈K,
f(x) = f(y) ⇒ x=y}
∈ Sub_{L}K, thus = K.
Proof 2. Im f ∈ Sub_{L}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
As any draft can be seen as a family of terms, any term algebra (final draft)
F precisely plays the more role of the "set of all terms" (with the given list
V of variable symbols), as it contains exactly one representative image
of each term (operation symbol defined by a term), i.e. any two "equivalent terms"
(defining the same operation) have the same image. Namely, any
Lterm T with root t and V_{T}⊂V, is
represented in F by the image of the f∈Mor(T,F) such that
f_{VT} = Id_{VT},
with root f(t).
This f plays the role of condensation (so is injective if and only if
T is condensed), respecting the interpretation in any Lalgebra
E extending any v∈E^{V}, as the unique
g∈Mor_{L}(F,E) and
h∈Mor_{L}(T,E) extending v, are related by
h=g০f, thus
h(t)=g(f(t)).
For any subset A of an Lalgebra E and any term algebra
whose set of variables is a copy of A, the image of its interpretation
in E is 〈A〉_{L}.
Free monoids
If it exists, any unary term Lalgebra M (essentially determined by L),
is a monoid acting on all Lalgebras, whose actions are preserved by all
Lmorphisms (Mor_{L} ⊂ Mor_{M} as they form a category of acts). It serves as
set of all (function symbols defined by) unary Lterms. The set of function
symbols from L is canonically injected there by j(s) =
s_{M}(e) so that in any Lalgebra E, ∀x∈E,
j(s)⋅x = s_{E}(x).
Conversely if L is made of function symbols then essentially
L ⊂ M, thus Mor_{L} = Mor_{M}.
The monoid structure of M was defined from its Lstructure; now let us
take the monoid structure as primitive and review alternative descriptions from it, of the
situation when L was made of function symbols. These function symbols
can be replaced by (reinterpreted as) constant symbols, as these 2 interpretations
can be defined from each other by terms using the monoid structure: the function defines
the constant as s = s(e), while the constant defines the function as
∀x∈M, s(x) = s•x.
For any set X, let us call Xmonoid any (X∪{e,•})algebra M
seeing X as a set of constant symbols by some j:X→M, such that
(e,•) is a monoid structure on M.
Denoting X_{1} the copy of X seen a set of function
symbols, the following statements on M are equivalent; such an M is
called a free monoid on X.
 M is a unary term X_{1}algebra with variable e,
interpreting the copy x'∈X_{1} of each x∈X
as ∀y∈M, x'_{M}(y) = j(x)•y
 For any X_{1}algebra E there is a unique left action
⋅ of M on E such that ∀x∈X, ∀y∈E,
j(x)⋅y = x_{E}(y)
 M is an initial object in the category of Xmonoids.
(The proof of this equivalence remains to be completed, using the property of trajectories
and the representation theorem)
1. is equivalent to: for any X_{1}algebra E and any x ∈ E
there is a unique h_{x} ∈
Mor_{X1}(M,E) such that
h_{x}(e)=x.
That is the curried form of the action ⋅ : M×E → E.
The uniqueness of the morphism to other Xmonoids is expressed by
〈X〉_{{e,•}} = M.
When writing terms with multiple uses of an associative operation symbol, all parenthesis
may be removed. For monoids, this removal of parenthesis and also of occurrences of e
seen as the empty chain of symbols, is operated by the interpretation of any
Vary {e,•}term in the free monoid on V.
The image of M by any morphism of monoid is the submonoid generated by the image of L.
3.11. Integers and recursion
The set ℕ
An arithmetic is any theory describing the system ℕ of natural numbers.
There are diverse such theories, depending on the choice of a logical framework,
then of a language and axioms. First is the set theoretical one,
which is the most precise as it determines the isomorphism class of ℕ in
the given universe :
Definition. ℕ is a ground
term algebra with two symbols: a constant
symbol 0 called zero, and a unary symbol S called the successor.
The essential uniqueness of such systems removes any uncertainty attached
to fixing a choice of ℕ among them, at least once any irrelevant questions are made
inexpressible by seeing ℕ as a set of pure elements.
The existence of a ground term {0,S}algebra is our first expression 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 will imply the existence
of term algebras with any language.
The above use of algebraic concepts in the definition of ℕ may make it look circular, as
our study of algebras used natural
numbers as arities of operation symbols. But these definitions may also be written
without reference to numbers when used symbols have small arities only
(for arithmetic, arities are first just 0 and 1, then later 2).
Namely, the most convenient expression of the axiom of infinity consists in inserting arithmetic into
set theory, by first inserting the language of {0,S}algebra in the form of 3
constant symbols: ℕ (as a set) and the images of both algebraic symbols 0 and S,
with axioms 0∈ℕ and S:ℕ→ℕ; then making this a ground term algebra by the
following 3 axioms :
(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. 
More constant symbols can be defined from there:
1=S0, 2=S1=SS0, 3=S2=SSS0, ...
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})_{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)),
In this view, associativity appears as (a+b)+n =
S^{n}(S^{b}(a)) =
S^{b}^{+}^{n}(a) =
a+(b+n). From now on, use of associativity will be implicit, omitting parenthesis.
Multiplication
By the concept of cardinals of finite
sets (counting their elements)
that will be defined in 4.1., multiplication in ℕ
may be defined as the cardinal of a product, making obvious its
basic properties, including commutativity.
Without this, multiplication can be defined by the following recursion,
which needs to treat sides differently until commutativity is deduced.
Let us choose the side that fits common language, though it is opposite
(transpose) to the usual one from the literature on the axioms of arithmetic:
∀x∈ℕ, 0⋅x = 0
∀x,y∈ℕ, (Sx)⋅y = (x⋅y)+y
which can be summed up as x⋅y =
(S^{y})^{x}(0). Then generally, ∀f∈E^{E}, f^{ x⋅y}
= (f^{ y})^{x}.
∀x∈ℕ, x⋅0 = 0 is deduced by induction.
Right distributivity ∀x,y,z∈ℕ, (x+y)⋅z =
x⋅z + y⋅z comes by induction on y, or as
(S^{z})^{x+y} =
(S^{z})^{y}০(S^{z})^{x}.
Left distributivity ∀x,y,z∈ℕ, x⋅(y+z) =
x⋅y + x⋅z comes by induction on x using commutativity of +. In particular this gives ∀x,y∈ℕ, x⋅Sy = (x⋅y)+x, so that the transpose of multiplication, satisfying the same recursive definition, coincides with it : multiplication is commutative.
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 a commutative group because it is generated by {1, 1}, which commute and are the
inverse of each other : (1)+1=0=1+(1).
The formula of its inverse, (n)+n = 0 = n+(n) can be deduced either
from symmetry ((n)+n∈ℕ ⇔ n+(n)∈ℕ) and commutativity, or from the
above result.
3.12. Presburger Arithmetic
Firstorder theories of arithmetic
Our first formalization of ℕ
was based on the framework of set theory, using the powerset to determine the isomorphism class of ℕ.
This allowed recursion, from which addition and multiplication could be defined.
Let us now review firstorder theories describing ℕ as their only type, called theories
of 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 as the set theoretical
framework was involved to justify recursive definitions, the successor function no
more suffices to define addition and multiplication in firstorder logic.
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 is arithmetic with addition. It still
cannot define multiplication.
 Full arithmetic, named Z_{1},
admits symbols 0,S, + and ⋅ , and
all axioms of their definitions. It
can express any other recursion.
Presburger arithmetic
A minimal formalization describes the set ℕ* of nonzero natural
numbers, with symbols 1 (constant) and + (binary operation), and axioms :
∀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 we shall use set
theoretical notations in such ways that they can be read as abbreviations of works in
firstorder logic: as long as we only consider subsets of ℕ* defined by firstorder formulas
in this arithmetical language, (Ind)
and (Min) can be read as abbreviations of schemas of statements, 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).
Let (Ind_{1}) be the statement ∀A⊂ℕ*,
(1∈A ∧ (∀x∈A, x+1 ∈A)) ⇒ A=ℕ*.
(Ind_{1}) ⇒ (Ind) ; (Ind) ⇒ (Ind_{1}) using A∪{0}.
One may instead use {x∈ℕx+1∈A} once noted that (Ind) ⇒ Im S = ℕ*.
(Ind_{1}) ⇒ (Min)
(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_{{S}}(M,ℕ).
Im f_{x} = f_{x} [〈0〉_{{S}}] =
〈x〉_{{S}} ⊂ M.
As M is stable by + and contains 1, it equals ℕ.∎
(As ∧ Min) ⇒ (Ind) as directly convertible to 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.∎
So, all possible axiom pairs are equivalent:
(A1 ∧ Min) ⇔ (As ∧ Min) ⇔ (As ∧ Ind) ⇔ (A1 ∧ Ind), and imply commutativity.
Parity
A number n∈ℕ is even if ∃x∈ℕ, n=x+x; it is odd
if ∃x∈ℕ, n=x+x+1.
Obviously, if n is even then n+1 is odd; if n is odd then n+1 is even thanks to commutativity. Thus by induction, any number is either even or odd.
But to show that it cannot be both and that this x is unique, also requires the use of
(Inj). These are left as a possible exercise. But instead of (Inj) we proposed axiom (F).
This raises the question of their equivalence.
(F) ⇔ (∀x∈ℕ*, ∀y∈ℕ, x+y ≠ y)
because x+0 = x ≠ 0.
(Inj ∧ Ind ∧ A1) ⇒ (F) because ∀x∈ℕ*,
{y∈ℕ  x+y ≠ y} ∈ Sub_{{0,S}}ℕ .
For the converse, we need to use the order relation.
The order relation
In any model of Presburger arithmetic,
let us define binary relations ≤ and < as x<y ⇔ ∃z∈ℕ*, y =
x+z
x≤y ⇔ ∃z∈ℕ, y = x+z
(A1 ∧ Ind) implies that
 < is transitive
 x≤y ⇔ (x<y ∨ x=y)
 x<y ⇔ x+1≤y
 ∀A⊂ℕ, A≠∅ ⇒ ∃x∈A, ∀y∈A,
x≤y (meaning a schema of formulas in 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}. Or using 3, A={x∈ℕ
∀y∈ℕ, x<y ∨ x=y ∨ y<x}
⇒ (0∈A ∧ ∀x∈A, x+1∈A)
 y = x+n ⇒ y+z = x+z+n
∎
Now the full system (A1 ∧ Ind ∧ F) implies that  < is a strict total order, associated
with the total order ≤
 ∀x,y,z∈ℕ, x<y ⇔ x+z
< y+z
 + is cancellative (which gives (Inj) as a particular case).
Proof. (F) means that < is irreflexive, which with transitivity (1.) implies
that it is a strict order, which is total by 5.
There must be one true formula among (x<y),
(x
= y), (y<x), which by 6. respectively imply
(x+z<y+z),
(x+z = y+z), (y+z<x+z).
But only one of the latter can be true, thus each implication must be an equivalence.
Cancellativity on one side extends to the other side by commutativity.
∎
Finally, by 4., every nonempty subset A of ℕ has a smallest element
(unique by antisymmetry), written min A.
This order coincides with the order
between terms in the common particular case of the set theoretical ℕ, as will
be clear from the properties of generated preorders.
Arithmetic with order
It is possible to express a firstorder arithmetic with language {0,S, ≤}, more
expressive than {0,S} but less than Presburger arithmetic, in the sense that
addition cannot be defined from ≤.
There, ≤ is related to S by the following property (which determines it in set theory,
but no more in bare arithmetic due to the poverty of its
interpretation of induction by an axiom schema):
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 in set theory (not firstorder arithmetic) by induction
on n; its uniqueness for a fixed n is deduced by induction on x.
Trajectories of recursive sequences
For any recursive sequence u∈Mor(ℕ,(E,a,f)), the trajectory
K = Im u = {f^{ n}(a)  n∈ℕ} of an
action of ℕ on E is generated by a, which is a free element for the image of
ℕ as a transformation monoid of K thanks to the commutativity of +.
Therefore K can be seen as a commutative monoid, whose description
coincides with the above arithmetic without axiom (F), where the roles of the neutral element 0
and the generator 1 are respectively played by a and f(a). However for convenience, let us focus on the set theoretical viewpoint on the remaining case, when
u is not injective so that K is not a copy of ℕ. Then K must be a
noninjective {0,S}algebra: there must be a pair in {0,S}⋆K
mapped to a singleton, but we shall see that such a pair is unique.
Let y the minimal number such that ∃x<y, u_{x} =
u_{y}. This x is unique because y is minimal.
{u_{n}  n<y} ∈ Sub_{{0,S}}K,
thus =K.
As Inj f_{K} ⇔ x=0 ⇔ a∈ Im
f_{K} ⇔ f^{y}(a)=a
⇔ (f_{K})^{y} = 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. Then replacing
a by another element of 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