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 En abbreviate the product EVn = E×...×E (n times), that is the set of n-tuples of elements of E.
The sets of all n-ary relations and of all n-ary operations in E are defined as Languages. A language is a set L of "symbols", with the data of the intended arity ns∈ℕ of each symbol sL. It may be For any language L and any set E, let LE = ∐sL Ens
A relational language L, aims to be interpreted in a set E as a family of relations, which belongs to

sL ℘(Ens) ≅ ℘(LE)

Let us now conceive an L-system as a pair (E,E) made of a set E with an L-structure ELE.
Most often, we shall only use one L-structure on each set, so that E can be treated as implicit, determined by E. Precisely, let us take a class of L-systems where each E is the intersection of LE with a fixed class of (s,x), denoted as s(x) because the ns-ary relation sE interpreting each symbol sL in each system E is somehow independent of E:

E={(s,x)∈LE | s(x)}.
sE = {xEns | s(x)} = E(s)
E=∐sL sE.

Morphism. Between any 2 L-systems E,F, we define the set of L-morphisms from E to F as

MorL(E,F) = {fFE|∀sL,∀xEns, s(x)⇒ s(fx)}
= {fFE|∀(s,x)∈E, (r,fx)∈F}.

For any function f, let fL = (L⋆Domf ∋(s,x) ↦ (s,fx)). This gives shorter definitions for sets of morphisms
MorL(E,F) = {fFE| fL[E]⊂F} = {fFE| EfL*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
satisfying the following axioms
The last condition is easily verified for L-morphisms : ∀(s,x)∈E, (s,fx)∈F ∴ (s,gfx)∈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 L-systems.

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 sE = {ft | f∈ Mor(K,E)} is preserved.

Proof : ∀g∈Mor(E,F), ∀xsE, ∃f∈ Mor(K,E), (x = ftgf∈ Mor(K,F)) ∴ gx = gftsF.∎

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 variable K).
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, even if we could take "all these structures" to turn these objects into relational systems (a possibility only ensured in small categories because of K ranging over all objects), 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 L-systems, 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 L-morphism f∈MorL(E,F), Thus, for any f ∈MorL(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 (¬,⇒,∀).

Morphisms between systems with several types

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:

3.2. Notion of algebra

Algebras. Given an algebraic language L, an L-algebra is a set E with an interpretation of each sL as an ns-ary operation in E.
Again, let us assume a fixed class of L-algebras E where each s is interpreted as the restriction sE of an ns-ary operator s independent of E,
sE = (Ensxs(x)).
These can be packed as one function

φE = ∐sL sE = ((s,x) ↦ s(x)) : LEE.

Such a class of algebras forms a concrete category with the following concept of morphism.

Morphisms of algebras. For any L-algebras E, F,

MorL(E,F) = {fFE | ∀(s,x)∈LE, sF(fx) = f(sE(x))} = {fFE| φFfL = f০φE}.

When cL is a constant (i.e. nc =0), this condition on f says f(cE)=cF.

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 sL corresponds s'L' with increased arity ns' = ns+1, so that
L'E ≡ ∐sL Ens×E ≡ (LEE
also expressible as the set of triples (s,x,y) such that sL, xEns and yE.
Each ns-ary operation sE defines an ns'-ary relation s'EGr sE. These are packed as an L'-structure
E = Gr φE ≡ ∐sL s'E.
The resulting condition for an fFE to be a morphism is equivalent :
(∀(x,y)∈E, (fL(x),f(y))∈F) ⇔ (∀xLE, φF(fL(x))= fE(x))).

Subalgebras. A subset AE of an L-algebra E will be called an L-subalgebra of E, if φE[LA]⊂A.
Then the restriction φA of φE to LA gives it a structure of L-algebra.
The set of all L-subalgebras of E will be denoted SubL E. It is nonempty as E ∈ SubL E.

For any formula of the form (∀(variables), some formula without any binder), its truth in E implies its truth in each A∈SubL E.

Images of algebras. For any two L-algebras E,F, ∀f ∈MorL(E,F), Im f ∈ SubLF.

The proof uses the finite choice theorem with (AC 1)⇒(6):
∀(s,y)∈ L⋆Im f, ∃xEns, fx = ysF(y) = f(sE(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 ⊂ (LEE 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 ∈ SubL E ⇔ (E*(LA) ⊂A) ⇔ (∀(s,x,y)∈E, Im xAyA).

Stability is no more preserved by direct images by morphisms, but is still preserved by preimages:

Preimages of stable subsets.f∈MorL(E,F), ∀B∈SubLF, f *(B) ∈ SubL E.

Let A=f *B. Proof for L-algebras:
∀(s,x)∈LA, fxBnsf(sE(x)) = sF(fx) ∈BsE(x)∈A.
Proof for L'-systems:
∀(x,y)∈E, (fL(x),f(y))∈F∴ (xLAfL(x)∈LBf(y)∈ByA).∎
Proposition. For any L'-system E and any L-algebra F,

f,g∈MorL(E,F), {xE|f(x)=g(x)}∈ SubLE.

Proof : ∀(s,x,y)∈E, fx=gxf(y) = s(fx) = g(y). ∎

Intersections of stable subsets.X ⊂ SubLE,X ∈ SubL E where ∩X {xE|∀BX, xB}.

Proof: ∀(x,y)∈E, xL⋆∩X ⇒ (∀BX, xLByB) ⇒ y∈∩X. ∎

Other way: E*(L⋆∩X) = E*(∩BX LB) ⊂∩BX E*(LB) ⊂∩X.

Subalgebra generated by a subset.AE, the L-subalgebra of E generated by A, written 〈AL,E or more simply 〈AL, is the smallest L-subalgebra of E including A:

AL= ∩{B∈SubLE|AB}= {xE|∀B∈SubL E, ABxB}∈ SubLE.

For fixed E and L, this function of A is a closure with image SubLE.
We say that A generates E if 〈AL=E.

Minimal subalgebra. For any L-algebra (or other L'-system) E, its minimal subalgebra (or minimal stable subset) is MinLE =〈⌀〉L,E = ∩SubLE ∈SubLE.

An L-algebra E is minimal when E = MinL E, or equivalently SubLE = {E}.

Proposition. For any L-algebra E, ∀A∈SubLE, Proof:
MinLE ⊂ MinLA because SubL A ⊂ SubL E.
MinL A ⊂ MinL E because ∀B∈SubLE, AB∈SubLA. ∎
(Among subsets of E, other minimal L'-systems are included in MinL E but are not stable).
We can redefine generated subalgebras in terms of minimal subalgebra with a different language: 〈AL,E= MinLA E where A is seen as a set of constants.

Injective, surjective algebras. An L-algebra (EE) will be called injective if φE is injective, and surjective if Im φE = E.

Proposition. For any L-algebras E, F,

  1. AE, Im φEAA∈SubLE.
  2. Any minimal L-algebra is surjective.
  3. MinLE = φE[L⋆MinLE] ⊂ Im φE
  4. AE, 〈AL = A∪φE[L⋆〈AL] ⊂ A∪Im φE.
  5. f ∈MorL(E,F), f [MinLE] = MinLF ; more generally ∀AE, f [〈AL] = 〈f [A]〉L
  1. φE[LA] ⊂ Im φEAA∈SubLE
  2. Im φE ∈ SubLE
  3. MinLE is surjective
  4. A∪φE[L⋆〈AL] ∈ SubLAL
  5. B ∈ SubLF, f *(B)∈SubL E ∴ MinLEf*(B) ∴ f [MinLE]⊂B.∎

Proposition. If E is a surjective algebra and F is an injective one then ∀f ∈MorL(E,F),

  1. A= {xE | ∀yE, f(x) = f(y) ⇒ x=y} ∈ SubLE.
  2. For each uniqueness quantifier Q (either ∃! or !), B = {yF | QxE, y = f(x)} ∈ SubLF
They are essentially the same but let us write separate proofs:
  1. ∀(s,x)∈LA, ∀yE,
    f(sE(x)) = f(y) ⇒ (∃(t,z)∈φE(y), sF(fx) = f(sE(x)) = f(y) = f(tE(z)) = tF(fz) ∴ (s=tfx=fz) ∴ x=z)sE(x)=y.
  2. As φF is injective, ∀y∈φF[LB], ∃!: φF(y) ⊂ LBQzLE, φF(fL(z)) = y.
    As φFfL = f০φE and φE is surjective, we conclude QxE, y = f(x). ∎

Schröder–Bernstein theorem. If there exist injections f: EF and g: FE then there exists a bijection between E and F.

Replacing F by the bijectively related set Im g, simplifies things to the case FEg=IdF.
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.

Isomorphism. In any concrete category, an isomorphism between objects E and F, is a morphism f ∈Mor(E,F) such that f : EF and f -1∈Mor(F,E). Or equivalently, ∃g∈Mor(F,E), gf= IdEfg= IdF, which will serve as definition in more general categories.
Two objects E, F are said to be isomorphic if there exists an isomorphism between them.

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, ∀fEE, ∀AE, A ∈ Sub{f} Ef ∈ 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.

Strong preservation. A function fFE 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 :

Embeddings. An f ∈MorL(E,F) is called an L-embedding if it strongly preserves all structures : ∀rL,∀xEnrxrEfxrF.
Every injective morphism f between algebras is an embedding :

∀(s,x,y)∈L'E, f(y) = sF(fx) = f(sE(x)) ⇒ y=sE(x).

Any embedding between algebras f ∈ MorL(E,F), is injective whenever Im φE = E or some sE 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

fL-1 = (f-1)L ∴ φEfL-1 = f -1f০φEfL-1 = f -1০φFfLfL-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 non-injective embeddings.
Injective embeddings are isomorphisms to their images.
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 first-order logic comes by removing this restriction on the order of use of logical symbols:

Elementary embedding. An f ∈ MorL(E,F) is called an elementary embedding (or elementary L-embedding) if it (strongly) preserves all invariant structures (defined by first-order formulas with language L).

Every isomorphism is an elementary embedding.

Isomorphism ⇒ Elementary embedding ⇒ Embedding ⇒ Injective morphism

If f∈ End(E) is an invariant elementary embedding then it is an automorphism:
Im f is also invariant (defined by ∃yE, f(y)=x)
xE, x∈Im ff(x)∈Im f
Im f = E. ∎

Elementary equivalence. Different systems are said to be elementarily equivalent, if they have all the same true ground first-order 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 non-isomorphic systems, as well as non-surjective elementary embeddings. However, they exist and play a special role in the foundations of mathematics, as we shall see with Skolem's paradox and non-standard models of arithmetic.

Quotient systems

For any relational language L, any L-system (E,E) and any equivalence relation R on E, the quotient set E/R has a natural L-structure defined as  RL[E].
It is the smallest L-structure 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 EE 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, ০}EE, of transformations of E: 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 EE| Inj f ∧ Im f=E} = {f EE|f:EE} 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 ∧ ∀fG, f -1G.

It will be seen as an algebra with one more operation : the inversion function ff -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 first-order stability axioms, ignoring the containing sets EE or ⤹E.


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

xE, 〈{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}〉LK
IdE∈〈L{Id, ০}xK
(f∈〈L{Id, ০},∀gL, gf∈〈L{Id, ০}g(f(x))∈K)K∈SubLE
Proof of K ⊂ 〈{x}〉L
L ⊂ {fEE| 〈{x}〉L ∈ Sub{f} E} = End{〈{x}〉L}E ∈ Sub{Id, ০}EE ∴ ∀f∈ 〈L{Id, ০}, 〈{x}〉L ∈ Sub{f} Ef(x)∈〈{x}〉L. ∎
The trajectory of an element xE 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)|fG} ⊂ 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.


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

Both equalities in the last axiom may be considered separately, forming two different concepts

If both a left identity and a right identity exist then they are equal : e = ee' = e' which makes it the identity of • (the unique element satisfying both identity conditions). 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'.


An operation • is called cancellative if all transformations defined by currying it on any side are injective:

x,y,z, (xy=xzy=z) ∧ (xz=yzx=y).

Cancellative operations cannot have several identities on one side.
Not all monoids are cancellative. For example the monoid of addition in the set of 3 elements {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 sub-monoid.
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 If the target forms a monoid (X,▪, e') then (by uniqueness of the identity in A)

f(e)=e'e'AA ∈ Sub{e, ▪} X

but these equivalent formulas may still be false, unless X is cancellative (aa = a = ae'a = e').

3.5. Actions of monoids

Left and right 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: This turns X into an M-algebra (where M is seen as a set of function symbols), called an M-set.
Equivalently by currying, a left action of M on X is a {e, •}-morphism from M to XX.
A left action is said effective if this morphism is injective:

a, bM, (∀xX, 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 re-expressible (from their initial expressions via the axioms for function) as determined by the function evaluator.
An element xX of an M-set, 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:

(∃xX, ∀abM, a·xb·x) ⇒ (∀abM, ∃xX, a·xb·x)

General example. The monoid of endomorphisms of any typed system E= ∐iI Ei, acts on every type Ei it contains, by the morphism of monoid from End(E) to EiEi defined by restricting to Ei each endomorphism of E.

Remark. Let M, X be given structures of M-algebras by any operations • : M×MM and ⋅ : M×XX. Then for any xX, the map hx = (Maax) satisfies by definition the following equivalences

hx(e) = xex = x
hx ∈ MorM(M,X) ⇔ ∀a,bM, (ab) ⋅ x = a ⋅ (bx).

As the concept of monoid is formally symmetric between left and right, transposing "composition" (switching positions of arguments), leads to the similar concept of right action of a monoid M on a set X: it is an operation ⋅ : X × MX such that

It defines a function f : MXX that is not exactly a morphism of monoid but let us call it an anti-morphism, which means a morphism where one monoid is replaced by its opposite, i.e. seen with its composition transposed :

a,bM, f(ab) = f(b) ০ f(a)


The commutant of any subset AE for a binary operation # in E, is defined as

C(A) = {xE|∀yA, x#y = y#x}.

This is a Galois connection: ∀A,BE, BC(A) ⇔ AC(B).
A binary operation # in a set E, is called commutative when C(E) = E, i.e. ∀x,yE, x#y = y#x.

Proposition. For any associative operation # on a set E, ∀AE,

  1. C(A) ∈ Sub#F
  2. If AC(A) then # is commutative in 〈A#
  1. x,yC(A), (∀zA, (x#y)#z = x#z#y = z#(x#y)) ∴ x#yC(A)
  2. AC(A)∈ Sub#F ⇒〈A#C(A) ⇒ AC(〈A#)∈ Sub#F ⇒ 〈A#C(〈A#).


As e commutes with all elements, the commutant of a subset of a monoid, is a sub-monoid. In this case the word "centralizer" is used instead of "commutant".
By definitions, the centralizer of any GEE, is its monoid of endomorphisms EndG E. The concept of centralizer will be later generalized from this unary case (sets of transformations) to clones of operations with all arities.

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 aM acting on the left and bN acting on the right on X is written
xX, (ax)b = a(xb)
which formally looks like an associativity law.

Representation theorem

Let us verify that both axioms of monoid suffice to gather all properties of transformation monoids, and even all properties of monoids of endomorphisms.

Theorem. For any monoid M there exists a language L of function symbols and an L-algebra X such that the monoid EndL X is isomorphic to M.


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, XX) represent the left action of M on X also copied from the composition in M.
Im f ⊂ EndL 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.
EndL X ⊂ Im f because
g∈EndLX, ∃uM, g(k)=uk ∴ (∀xX, ∃sL, ks=xg(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.

3.6. 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:

satisfying the axioms

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)
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, gf)
HomF(f, X) ০ HomG(g, X) = HomG(gf, X)

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), gf=hfg=h.
In our concept of concrete category, we must specify F: we say that f∈Mor(E,F) is F-epic, or an F-epimorphism, if all HomF(f,X) are injective.

In any concrete category, all injective morphisms are monic, and any morphism with image F is F-epic. However, the converses may not hold, and exceptions may be uneasy to classify, especially as the condition depends on the whole category.

The following 2 concepts may be considered cleaner as they admit a local characterization:

Sections, retractions. When gf=IdE we say that f is a section of g, and that g is a retraction of f.

Proof: if gf=IdE then for all objects X, HomF(f,X) ০ HomE(g,X) = HomE(IdE,X) = IdMor(E,X), thus Similarly, Hom(X,g) ০ Hom(X,f) = Hom(X,IdE) = IdMor(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 f∈Mor(E,F) is an isomorphism : gf=IdEfgf = IdFffg=IdF
Similarly, 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

Initial and final objects

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), gf ∈Mor(X,X) ∧ fg ∈Mor(Y,Y).
But IdX ∈ Mor(X,X) which is a singleton, thus gf= IdX. Similarly, fg=IdY.
Thus f is an isomorphism, unique because Mor(X,Y) is a singleton.∎

By this isomorphism X and Y may be treated as identical to each other. We may 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: Exercise. Given two fixed sets X and Y, consider the category whose objects are all (E,φ) where E is a set and φ: E×XY, and the morphisms from (E,φ) to (E',φ') are all f : EE' such that ∀aE,∀xX, φ(a,x) = φ'(f(a),x).
Does it have an initial object ? a final object ?

3.7. 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 L-draft will be an L'-system (D,D) where D⊂ (LDD, such that:

Let us denote ∀xOD, ΨD(x)=(σ(x), lx) ∈ LD where s(x)∈L and lxDnσ(x). We can also denote σD(x)=σ(x) to let σD be a function with domain OD.
Well-foundedness can be equivalently written in any of these forms

AOD, (∀xOD, Im lxAVDxA) ⇒ A=OD
AD, (VDAD*(LA) ⊂A) ⇒ A = D
AD, VDAD ⇒ ∃xOD\A, Im lxA
AOD, A≠∅ ⇒ ∃xA, A⋂ Im lx = ∅

The set of used variables of (D,D), those which effectively occur, is VD⋂⋃xOD Im lx. Unused variables can be added or removed in D while keeping D fixed (by changing DOD∪(⋃xOD Im lx)), so that their presence may be irrelevant.
A ground draft is a draft with no variable, i.e. VD=∅. Thus, ΨD: DLD and SubLD = {D}.
More generally a draft is ground-like if it has no used variable (Dom DLOD).

Sub-drafts and terms

Drafts do not have interesting stable subsets (by well-foundedness), but let us introduce another stability concept for them.
A subset AD is a sub-draft of D (or a co-stable subset of D) if, denoting OA = AOD and ΨA= ΨD|OA, we have (Im ΨALA), i.e. ∀xOA, Im lxA.
Indeed, it remains well-founded, as can be seen on the last formulation of well-foundedness.

Like with stable subsets, any intersection of sub-drafts is also a sub-draft; the sub-draft co-generated by a subset is the intersection of all sub-drafts that include it.
A term is a draft co-generated by a single element which is its root.
Moreover, any union of sub-drafts is also a sub-draft (which was not the case for sub-algebras because an operation with arity >1 whose arguments take values in different sub-algebras may give a result outside their union).

There is a natural order relation on each draft D defined by xy ⇔ 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 well-founded relations in the study of Galois connections.

Categories of drafts

As particular relational systems, classes of L-drafts form concrete categories. Between two L-drafts D,E,

f ∈MorL(D,E) ⇔ (f[OD]⊂OE ∧ ΨEf|OD= fL০ΨD)

where the equality condition can be split as

σEf|OD = σD
xOD, lf(x)=flx

Another kind of category of drafts can be considered, with objects also L-drafts but with a common set of variables (VD=VE=V) and taking smaller sets of morphisms: the variables-preserving morphisms, i.e. moreover satisfying f|V = IdV.
But for any element t in any draft, the term T co-generated by {t} has as set of variables TV (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 co-generated by singletons in such a category requires this loosening of the condition. This naturally simplifies when reformulating such categories as those of ground (LV)-drafts: in each draft, variable symbols are replaced (reinterpreted) by constant symbols added to the language, so ΨE is extended by IdV, to form a ground (LV)-draft.

Intepretations of drafts in algebras

For any L-draft D and any L-algebra E, an interpretation of D in E is a morphism f∈MorL(D,E), i.e. f|OD= φEfL০ΨD, which can also be written

xOD, f(x) = σ(x)E(flx)

Theorem. For any L-draft D with set of variables V and any L-algebra E, any vEV is uniquely extensible to an interpretation of D:
∃!h∈MorL(D,E), h|V = v, equivalently ∃!hEOD, vh ∈MorL(D,E).

The uniqueness comes from a previous proposition.

Proof of existence.
S = {AD | VA∧ Im ΨALA}
vK = ⋃AS {f∈MorL(A,E) | f|V =v}
f,gK, B = Dom f ⋂ Dom g ⇒ (f|BKg|BK) ⇒ f|B=g|B
fK Gr f = Gr h
C= Dom h = ⋃fK Dom fS
(CD*(LC) ∋ x↦ (xC ? h(x) : φE(hLD(x))))) ∈ K (see conditional operator)
D*(LC) ⊂ C

Operations defined by terms

A new operation symbol can be defined by any element t of an L-draft D : it is the V-ary operation defined by the L-term with root t, that is co-generated by t in D. Its interpretation in each E is defined by ∀vEV, tE(v) = h(t) for the unique h∈MorL(T,E) such that h|TV=v.

As a particular case of a relation defined by a tuple, here (IdV,t), these operations are preserved by all morphisms between L-algebras, 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 re-expressed 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 L-algebra (EE) is called a term algebra if it is injective and 〈E\Im φEL = E. Thus it is also an L-draft 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 L-algebra.
If L only contains constants, then ground term L-algebras 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 L-algebra is a final object in any category of ground L-drafts, and an initial object in any category of L-algebras. In any variables-preserving category of L-drafts with a fixed set V of variables (category of ground (LV)-drafts), any term L-algebra F, when present, is a final object.

Proposition. For any ground term L-algebra K and any injective L-algebra M, the unique f∈MorL(K,M) is injective.

Proof 1. By a previous result, {xK | ∀yK, f(x) = f(y) ⇒ x=y} ∈ SubLK, thus = K.
Proof 2. The subalgebra Im f of M is both injective and minimal, thus a ground term L-algebra, so the morphism f between initial L-algebras 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 sub-draft of F it co-generates, thus where it is the root.
For any L-term T with root t and variables ⊂V, the unique f∈Mor(T,F) such that f|TV = IdTV represents it in F as the term Imf with root f(t).
Then its interpretation in any L-algebra E extending any vEV, is determined by the unique g∈MorL(F,E) extending v, as gf∈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 L-algebra E, any term algebra FA whose set of variables is a copy of A, represents the set of all L-terms with variables interpreted in A. Then, the L-subalgebra 〈AL of E is the image of the interpretation of FA in E, i.e. the set of all values of these terms.

The monoid of unary terms

Let M be a unary term L-algebra (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 L-terms, and preserved by morphisms across all L-algebras, including M itself. Therefore, thanks to a previous remark, M is natually a monoid acting on all L-algebras.
If L is only made of function symbols then for any L-algebra E, the image of M in EE is the transformation monoid generated by the image of L.

3.8. Integers and recursion

The set ℕ

Any theory that aims to describe the system ℕ of natural numbers is called an Arithmetic. In details, there are several such formal theories, depending on the language (list of basic structures), and the logical framework (affecting the expressibility of axioms).

Our first "definition" of ℕ will characterize it in a set theoretical framework. This way of starting to formalize ℕ now may look circular, as we already used natural numbers as arities of operation symbols of algebras, of which arithmetic is a particular case. But this case only uses operation symbols with arity 0, 1 or 2, for which previous definitions might as well be specially rewritten without any general reference to integers.

Definition. The set ℕ of natural numbers is a ground term algebra with a language of two symbols: one constant symbol 0 ("zero"), and one unary symbol S.

The interpretation of S there is called the successor, understood as adding one unit (Sn=n+1).

This concept of ground term algebra can be expanded as the following 3 axioms on this {0,S}-algebra :
n∈ℕ, Sn ≠ 0
(H0), i.e. 0 ∉ Im S
n,p∈ℕ, Sn = Sp n = p (Inj), i.e. S is injective
A⊂ℕ, (0∈A ∧ ∀nA,SnA) ⇒ A=ℕ (Ind) : induction axiom (ℕ is a minimal (0,S)-algebra).

We can define 1=S0, 2=SS0...

This insertion of arithmetic into set theory, adding to set theory the constant symbol ℕ with some basic structure symbols interpreted in this ℕ, is the natural way to complete set theory (as we progressively introduced from the beginning to 2.5, + eventually the axiom of choice), to form the standard foundation of mathematics as practiced by most mathematicians. Its implicit choice of a fixed ℕ in the class of ground term {0,S}-algebras, does not introduce any arbritrariness, since, as an initial {0,S}-algebra, it is essentially unique (any two systems in this class are identifiable by an isomorphism which is unique inside the same universe).

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 uE such that u ∈ Mor(ℕ,(E,a,f)), where (E,a,f) is the {0,S}-algebra E interpreting 0 as aE and S as fEE :

n∈ℕ, uSn = f(un).

As un 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 integer n represents a term with symbols 0 and S respectively interpreted in E as a and f. 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))
In another curried view of this map from E×EE×ℕ to E we can re-interpret 0 as a variable instead of a constant symbol. Then each integer n becomes a term Sn with n occurrences of the function symbol S and one variable, interpreted in each {S}-algebra (E,f) as the function f nEE recursively defined by
f 0 = IdE
n∈ℕ, f Sn = ff n
In particular, f1=f.
More generally, for any functions fEE, gEX, the sequence of functions recursively defined by
n∈ℕ, hSn = fhn
is hn=f ng.


The operation of addition in ℕ can be defined as n+p = Sp(n), i.e. by the recursive definition
n + 0 = n
p∈ℕ, n+S(p) = S(n+p).
n+1 = n+S0 = S(n+0) = Sn
As ∀aE ,∀fEE, (pf n+p(a))∈Mor(ℕ,(E,fn(a),f)), i.e. fn+0=fn and ∀p∈ℕ, fn+Sp = fS(n+p) = ffn+p we have
n,p∈ℕ , f n+p = f pf n.
Addition is associative: (a+b)+n = Sn(Sb(a)) = Sb+n(a) = a+(b+n).
Recursive sequences are actions of this monoid of natural numbers (ℕ, 0 +), particular case of monoid of unary terms.


Multiplication in ℕ can be defined as xy = (Sx)y(0), so that

x∈ℕ, x⋅0 = 0
x,y∈ℕ, x⋅(Sy) = (xy)+x

More generally, for any aE and fEE, we have fxy(a) = (fx)y(a).

A more general form of recursion

Some useful sequences need recursive definitions where the term defining uSn uses not only un but also n itself. Somehow it would work all the same, but trying to directly adapt to this case the proof we gave would require to define some special generalizations of previous concepts, and specify their resulting properties. To simplify, let us proceed another way, similar to the argument in Halmos's Naive Set Theory, but generalized.
For any algebraic language L, let us introduce a general concept of "recursive condition" for functions u : EF, where, instead of a draft, E is first assumed to be an L-algebra (then a ground term algebra to conclude).
The version we saw was formalized by giving the term in the recursive definition as an L-algebra structure on F, φF: LFF, then expressing the request for u to satisfy this condition as u∈Mor(E,F), namely

∀(s,x)∈LE, u(sE(x)) = φF(s,ux).

Let us generalize this as u(sE(x)) = φ(s,x,ux) which by the canonical bijection Dom φ ≡ ∐sL Ens ×Fns ≡ ∐sL (E×F)ns = L⋆(E×F) can be written using h : L⋆(E×F) → F such that ∀(s,x,y)∈ Dom φ, φ(s,x,y) = h(s,x×y), as

u(sE(x)) = h(s,x×(ux)).

As ∀uFE, x×(ux) = (IdE×u)০x, this becomes the second component of the formula IdE×u ∈ Mor(E, E×F) when giving E×F the structure φE×F = (φE০πLh.
The first component (φE০πL) we give to φE×F, makes π∈ Mor(E×F, E) and makes tautological the first component of the formula IdE×u ∈ Mor(E, E×F), namely
IdE(sE(x)) = φE(s,x) = (φE০πL)(s,x×(ux)).
It is then possible to conclude by re-using the previous result of existence of interpretations:
If E is a closed term L-algebra then ∃!f ∈ Mor(E, E×F), which is of the form IdE×u because π০f ∈ Mor(E, E) ∴ π০f = IdE.
But one can do without it, based on the following property of this L-algebra E×F:

uFE, IdE×u ∈ MorL(E, E×F) ⇔ Gr u ∈ SubL(E×F)

The ⇒ is a case of image of an algebra by a morphism, Gr u = Im (IdE×u).
For the converse, the inverse of the bijective morphism π|Gr u ∈ MorL(Gr u, E) is a morphism IdE×u ∈ MorL(E, Gr u) ⊂ MorL(E, E×F).
This reduces the issue to the search of subalgebras of E×F which are graphs of functions from E to F.
Now if E is a ground term L-algebra then M = MinL(E×F) is one of them because π|M∈ MorL(M, E) from a surjective algebra to a ground term algebra must be bijective.
Any other subalgebra of E×F must include M, thus to stay functional it must equal M. ∎

Interpretation of first-order formulas

Trying to extend the formal definitions of terms interpreted in algebras, to formalize the general concept of formula interpreted in systems, the difficulty is to cope with the interpretation of quantifiers (or generally binders, if we wish to still generalize). A possible solution, is to treat all variables as bound throughout the formula.
Binding all variables modifies the view on the above concept of interpretation of a term T with set of variables V in an algebra E by re-currying the family (hv) of functions from T to E where v runs over EV, into a function from T to EEV. So, a first-order formula interpreted in a system E can be understood as a term interpreted in an algebra whose base set is the set OpE ∪ RelE of all operations and all relations in E where

OpE = ⋃n∈ℕ OpE(n) and RelE = ⋃n∈ℕ ℘(En).

We might not need the full sets of these, but at least, an algebra of these (a subset stable by all needed logical operations).
We took ℕ for the case we would need to see "all possible formulas" as terms interpreted in one same algebra.

3.9. Arithmetic with addition

First-order 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 first-order logic, thus called first-order arithmetic. As first-order 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 first-order 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 non-equivalent versions of first-order arithmetic depending on the choice of the primitive language, thus non-equivalent versions of the axiom schema of induction whose range of expressible classes depends on this language:

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,yA, x+yA) ⇒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 first-order logic, as long as we only consider subsets of ℕ* defined by first-order 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,bA,
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 ℕ∋xx+1.
These definitions directly imply (H0).

(Ind) ⇒ (Min) :
A⊂ℕ*, the set A0= A∪{0} satisfies 0∈A0 and
(1∈A ∧ (∀x,yA, x+yA)) ⇒ (S0∈A0 ∧ (∀xA, Sx=x+1 ∈AA0)) ⇒ A0=ℕ.∎
(As ∧ Min) ⇒ (Ind) in set theory (ignoring our previous definition of ℕ)
Let M=Min{0,S}ℕ.
xM, M∈Sub(ℕ,x,S) ∧ fx=(Myx+y)∈Mor((M,0,S),(ℕ,x,S)).
Images of minimal algebras by morphisms are included in any subalgebras: Im fxM.
As M is stable by + and contains 1, it equals ℕ.∎
(As ∧ Min) ⇒ (Ind) in first-order logic
Let A∈Sub{0,S}ℕ, and B = {y∈ℕ* |∀xA, x+yA}.
y,zB, (∀xA, x+yx+y+zA) ∴ y+zB.
(∀xA, x+1 ∈A) ⇔ 1∈B ⇒ ((Min)⇒ B=ℕ*).
0∈A ⇒ (∀yB, 0+yA) ⇒ BA.∎
(F) ⇔ (∀x∈ℕ*, ∀y∈ℕ, x+y y) because x+0 = x ≠ 0.
(Inj ∧ Ind ∧ A1) ⇒ (F) : ∀x∈ℕ*,
x+0 ≠ 0
y∈ℕ, x+y yx+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
xy ⇔ ∃z∈ℕ, y = x+z

For this, here are successive consequences of (Ind ∧ A1) :
  1. < is transitive
  2. xy ⇔ (x<yx=y)
  3. x<yx+1≤y
  4. A⊂ℕ, A≠∅ ⇒ ∃xA, ∀yA, xy (to be interpreted as a schema of formulas if we study Presburger arithmetic)
  5. x,y∈ℕ, xyyx
  6. x<yx+z < y+z
Proofs :
  1. using (As), x < y < z ⇒ (∃n,p∈ℕ*, z = y+p = x+n+p) ⇒ x <z.
  2. obvious from definitions;
  3. thanks to (Ind), ℕ is a bijective {0,S}-algebra;
  4. xy ⇒ (x+1≤yx=y)
    0∈{x∈ℕ |∀yA, xy}=B
    xB, x+1∈BxA
    AB=∅ ⇒ (B=ℕ ∴ A=∅)
  5. from 4. with A={x,y}
  6. y = x+n y+z = x+z+n
(for 5. it is also possible to more directly prove for A={x∈ℕ |∀y∈ℕ, x<yx=y y<x} that 0∈A and ∀xA, 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<yx+z < y+z) and (x = yx+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 of ℕ has a smallest element, which is unique by antisymmetry.

Arithmetic with order

It is possible to express a first-order 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∈ℕ | nx} is the unique A⊂ℕ such that
x∈ℕ, xA ⇔ (x = n ∨∃yA, Sy=x).
Its existence in ℘(ℕ) can be deduced by induction on n; its uniqueness for a fixed n is deduced by induction on x.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Model Theory