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 A language L is a set of symbols, with the data of the intended arity ns∈ℕ of each sL. For any set E, let

LE = ∐sL Ens

A relational language is a language L of relation symbols, where each sL aims to be interpreted in any set E as an ns-ary relation. These form a family called an L-structure on E, element of

sL ℘(Ens) ≅ ℘(LE)

A relational system with language L, or L-system, is the data (E,E) of a set E with an L-structure ELE.

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 L-structure on each set, so that E can be treated as implicit, determined by E. Precisely, let us imagine given a class of L-systems where each E is the intersection of LE with a fixed class of (s,x), denoted as a predicate s(x) for how it is naturally curried: each symbol sL is interpreted in each system E as the ns-ary relation sE somehow independent of E,

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

For any function f : EF, let fL : LELF defined by (s,x) ↦ (s,fx).
Im fL = 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).
BF, fL*(LB) = Lf*(B)

Morphism. Between any L-systems E,F, we define the set MorL(E,F) ⊂ FE of L-morphisms from E to F by ∀fFE,

f ∈ MorL(E,F) ⇔ ∀(s,x)∈E, (r,fx)∈F
⇔ (∀sL,∀xEns, s(x) ⇒ s(fx))
fL[E]⊂FEfL*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)
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 s with the data of an interpretation sEEns 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), ∀xsE, fxsF. From 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.

Preservation of some defined structures

In any given category of L-systems, 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 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 (¬,⇒,∀).

The above cases of 0, 1, ∨ and ∧ are mere particular cases (the nullary and binary cases) of the following:

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 n-tuple t of elements of some object K, the relation s 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.∎
From these definitions it might happen between objects EF that sEsFEn 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:

3.2. Notion of algebra

Algebras. Given an algebraic language L, an L-algebra is the data (E,φ) of a set E with an L-algebraic structure φ : LEE, sum of a family of interpretations of each symbol sL as an operation ⃗φ(s)∈OpE(ns).
Again, we shall usually consider a class of L-algebras with only one choice of algebraic structure on each set:

sE : EnsE
φE = ∐sL sE : LEE

This would be the case if the sE were the restrictions of a common ns-ary operator to each E, but this would not allow to interpret constant symbols r and s in algebras E and F with rE=sE but rFsF.
These form 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 the copy s'L' of each sL has increased arity ns' = ns+1, so that
L'E ≡ ∐sL Ens×E ≡ (LEE ≡ {(s,x,y) | sLxEnsyE}.
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 is called stable by L or an L-subalgebra of E if φE[LA]⊂A. It is also an L-algebra, with structure φA restriction of φE to LA. The set of L-subalgebras of E is written SubL E = {AE | φE[LA]⊂A}.

If a formula of the form (∀(variables), formula without binder) is true in E, then it is true in each A∈SubLE.

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

Proof : φF[L⋆Im f] = φF[Im fL] = Im (f০φE) ⊂ Im f

Let us generalize these concepts to categories of relational L'-systems (E,E) whose structure E ⊂ (LEE no more needs to be functional:

Stable subsets. The concept of stability of a subset A can be defined in any L'-system E beyond the case of algebras :

A ∈ SubL E ⇔ (E*(LA) ⊂A) ⇔ (∀(s,x,y)∈E, Im xAyA).

We have E ∈ SubL E. 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.

Proof. Let A=f *B.
For L-algebras, ∀(s,x)∈LA, fxBnsf(sE(x)) = sF(fx) ∈BsE(x)∈A.
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) = sF(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, we denote 〈AL,E or simply 〈AL, the smallest L-stable subset of E including A (called L-subalgebra of E generated by A if E is an algebra):

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

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

Minimal subalgebra. For any L'-system E, its minimal stable subset (or minimal subalgebra for an L-algebra) is defined as
MinLE = 〈∅〉L,E = ∩SubLE ∈ SubLE.

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

Proposition. For any L'-system 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.
The stable subset generated by A is the minimal one for the extended language with A seen as a set of constants: 〈AL,E= MinLA E.

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, ⋃xA〈{x}〉L ⊂ 〈AL = A∪φE[L⋆〈AL] ⊂ A∪Im φE
  5. f ∈MorL(E,F), f [MinLE] = MinLF ∧ ∀AE, f [〈AL] = 〈f [A]〉L
Proofs:
  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.∎

Injectivity lemma. 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.

Proof : replacing F by the bijectively related set Im g, simplifies things to the case FE.
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 L-system (E,E) and any equivalence relation R on E, the quotient set E/R has a natural L-structure E/R defined as RL[E].
It is the smallest L-structure on E/R such that R∈Mor(E, E/R). Indeed for any L-system (F,F) and any f : EF we have f∈Mor(E,F) ⇔ fL[E]⊂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 : EF, BF and A= f*(B) we have
(f∈Mor(E,F) ∧ B∈SubLF) ⇒ A∈SubLE
(FfL[E] ∧ A∈SubLE) ⇒ B∈SubLF
fL[E]=F ⇒ (B∈SubLFA∈SubLE)

Embeddings and isomorphisms

Strong preservation. A relation symbol r interpreted as rE in E and rF in F is strongly preserved by a function fFE, if both r and ¬r are preserved :

xEnr, xrEfxrF.

Embeddings. An f ∈MorL(E,F) is called an L-embedding if it strongly preserves all structures : E = fL*(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 non-injective embeddings.

Isomorphism. Between objects E and F of a concrete category, an isomorphism is a bijective morphism (f ∈Mor(E,F) ∧ f : EF) 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).

Embeddings of algebras

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.

Elementary embeddings

L-embeddings 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 first-order logic comes by removing this restriction on the order of use of logical symbols: an elementary embedding (or elementary L-embedding) is a morphism that (strongly) preserves all invariant structures (defined by first-order formulas with language L).
An elementary subsystem of a system E is an FE interpreting L by restriction, such that IdF 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 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.

Endomorphisms, automorphisms.

An endomorphism of an object E in a category, is an element of Mor(E,E) = End(E).
For any set E, we have a Galois connection (Sub, End) between the powersets of EE and ℘(E):

GEE, ∀F⊂℘(E), G ⊂ EndFE ⇔ (∀fG, ∀AF, f[A] ⊂ A) ⇔ F ⊂ SubGE.

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 ∃yE, f(y)=x)
xE, x∈Im ff(x)∈ Im f
Im f = 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 EE 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,০}EE : 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.

Trajectories

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

xE, 〈{x}〉L = {f(x)|f∈〈L{Id,০}}
XE, 〈XL = ⋃f∈〈L{Id,০} f[X] = ⋃xX 〈{x}〉L

As we shall formalize later, this is because both mean the same : the set of all composites of any number of functions in L, applied to any xX. But here is a simple proof, denoting A=〈XL, M=〈L{Id,০} and K={f(x) | (f,x)∈M×X}:
Proof of AK
IdEMXK
gL, ∀yK, ∃(f,x)∈M×X, y=f(x) ∧ gfMg(y) = gf(x)∈K
K ∈ SubLE
Proof of KA
L ⊂ {fEE| A ∈ Sub{f}E} = End{A}E ∈ Sub{Id,০}EE
M ⊂ End{A}E
fM, XA ∈ Sub{f}Ef[X] ⊂ A. ∎
The trajectory of an element xE by a transformation monoid M of E, is the set it generates:

〈{x}〉M = {f(x)|fM} ⊂ E

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

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 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, xy = xzy = z.
Similarly it is right cancellative if yx = zxy = z.
If a right identity e is left cancellative then it is the unique right identity : ee' = e = eee' = 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 AE for a binary operation • in E, is defined as

C(A) = {xE|∀yA, xy = yx}.

This is a Galois connection: ∀A,BE, BC(A) ⇔ AC(B). Such A,B are said to commute as each element of A commutes with each element of B.

If • is associative then ∀AE, C(A) ∈ SubF. (Proof: ∀x,yC(A), (∀zA, xyz = xzy = zxy) ∴ xyC(A))

Commutants in monoids are called centralizers. They are more precisely sub-monoids as obviously eC(A).
This can be understood for transformation monoids MXX by the fact it is an intersection of submonoids: AM, CM(A) = M ∩ EndA 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,yE, xy = yx.

If AC(A) and 〈A=E then • is commutative
Proof: AC(A)∈ SubFE=C(A) ⇒ AC(E) ∈ SubFC(E) = E.∎
In the case of monoids the conditions AC(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), If the target forms a monoid (X,e',▪) then (by uniqueness of the identity in A)

f ∈ Mor{e}(M,X) ⇔ a = e'e'AA ∈ Sub{e, ▪} X

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

Anti-morphisms. The opposite of a monoid is the monoid with the same base set but where composition is replaced by its transpose. An anti-morphism from (M,e,•) to (X,e',▪) is a morphism f from one monoid to the opposite of the other (or equivalently vice-versa):

f(e) = e'
a,bM, f(ab) = 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×XX such that Seing M as a set of function symbols, an M-algebra (X, ⋅) satisfying these axioms is called an M-set.
In curried view, a left action of M on X is a {e,•}-morphism from M to the full transformation monoid XX.

Effectiveness and free elements

A left action is said effective if this morphism is injective (thus an embedding):

a,bM, (∀xX, 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 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. Any transformation monoid M of a set E acts by restriction on any M-stable subset A of E, i.e. any preserved AE in the concrete category M with object E. Thus, the monoid of endomorphisms of any typed system E= ∐iI Ei, acts on every type Ei it contains.

Acts as algebraic structures

Let M, X be given structures of M-algebras by any operations • : M×MM and ⋅ : M×XX. Then denoting ∀xX, hx = (Maax), we have directly from definitions

hx(e) = xex = x
hx ∈ MorM(M,X) ⇔ ∀a,bM, (ab)⋅x = a⋅(bx)
he = IdM ⇔ (∀aM, ae = a) ⇒ ∀g∈MorM(M,X), g=hg(e).

So in the formula

gXM, ∀xX, g=hx ⇔ (g∈MorM(M,X) ∧ g(e)=x)

the ⇒ expresses the axioms of left action of M on X; the ⇐ is implied by (∀aM, ae = 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 :

(IdM ∈ MorM(M,M) ∧ IdM(e)=e) ⇒ he = IdM

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 × MX such that
It amounts to a left action of the opposite monoid, and defines an anti-morphism from M to XX.

The commutation of 2 submonoids of XX looks like an associativity formula when written as acting by opposite sides on X: aM left acting on X commutes with bN right acting on X when

xX, (ax)⋅b = a⋅(xb)

Representation theorem

The axioms of monoid actually suffice to give 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.

The proof essentially repeats the above formulas on acts as algebraic structures, transposed :

Let L and X be two copies of M.
Give L the right action on X copied from the composition in M.
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 making both actions on opposite sides commute.
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 last formula just needs k to be a generating element both sides, to bijectively (if also free) identify L and X as copies of M, but such a k is not necessarily unique.

Trajectories by commutative monoids

Let a monoid M act on a set X, and let kX. The trajectory Y of k by M is stable by M, thus defines a morphism of monoid from M to YY 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 = {fEE| Inj f ∧ Im f = E} = {fEE| 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 {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 first-order 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 (∐xE 〈{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 xy = 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 xy = e is interpreted as relating transformations :

z,tM, yz = txt = 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 ({zy|zM} = M) and implies that y is left cancellative:

xy = e ⇒ ∀zM, zxy = z
z,tM, (yz = ytxy = e) ⇒ (z = xyz = xyt = 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:

yx = e = xzy = yxz = z

If a left invertible element y is also right cancellative then it is invertible: xy=eyxy = eyyx=e.
This characterization of invertible elements also makes sense for an element x of an M-set X: saying that x is both generating and free, means that the morphism hx∈ MorM(M,X) is both surjective and injective, thus an isomorphism between the M-sets M and X. Then we might still say it has an inverse in the form of an M-morphism from X to M.
If x commutes with an invertible element y then it also commutes with its inverse z:

xy = yxx = yxzzx = xz

An element x of a monoid is called involutive if it is its own inverse: xx = e. In particular e is involutive.

Groups

The concept of group is the theory obtained by adding to that of monoid, equivalently 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 sub-monoid which is a group (not all are: the sub-monoid ℕ of the group ℤ is not a sub-group), or a {e, •,-1}-subalgebra.
The set of invertible elements in any monoid M, is a 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) | xy = e = yx}, thus its image is a group.
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 anti-morphism, it switches any left action ▪ of G on X into a right action • by ∀xX, ∀gG, x•g = g-1x.
By the representation theorem, any group is isomorphic to a permutation group, namely the group of automorphisms of an algebra.

In a group, the subgroup generated by a subset A, coincides with the submonoid G generated by A∪-A where -A = {x-1|xA}. (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).

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: such that Generalizing both isomorphisms in concrete categories, and invertible elements in monoids, an isomorphism f between objects E and F in an abstract category, is an f∈Mor(E,F) such that ∃g∈Mor(F,E), gf=1Efg=1F. This g is unique, called the inverse of f.

Representation of small categories. Any small category has an interpretation as a family of typed algebras, with all morphisms between them.

Proof. 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 any special status to this bijection).
See each object M as a system interpreting each type X' as the set Mor(X',M).
Take the language of function symbols where the set of those from type X' to type Y' is Mor(Y',X').
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)

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), fg = fhg = 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), gf = hfg = h.

In our concept of concrete category, we must specify F, saying 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.

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

Proof: if gf=1E then for all objects X, HomF(f,X) ০ HomE(g,X) = HomE(1E,X) = IdMor(E,X), thus Similarly, Hom(X,g) ০ Hom(X,f) = Hom(X,1E) = 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 is an isomorphism. Any monic retraction is an isomorphism.

These dependencies between qualities of morphisms, can be mapped as follows:

Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔ (Section ∧ Epimorphism)
Retraction ⇒ Quotient ⇒ Surjective morphism ⇒ Epimorphism
Section ⇒ Embedding ⇒ Injective morphism ⇒ Monomorphism

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), gf ∈ Mor(X,X) ∧ 1X ∈ Mor(X,X) ∴ gf = 1X.
Similarly, fg = 1Y. 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: Exercise. Given two fixed sets K and B, consider the category where Does it have an initial object ? a final object ?

Categories of acts

From a concrete category C, let C' be the category where Then we have
  1. If C is the category of M-sets for a monoid (M,e, •) then, seeing M as an M-set 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.
  2. 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) ⊂ MorM(X,Y) and Mor(M,X) = MorM(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 ∀xX, hx ∈ Mor(M,X) ∧ hx(e) = x, provides an M-structure on each X which interprets each aM in X as defined by the tuple (e,a). So they are preserved: Mor(X,Y) ⊂ MorM(X,Y), which implies the axioms of M-acts.
The composition in M coming as this M-structure for M = X, satisfies the same axioms.
The last axiom of monoid, he = IdM comes from the uniqueness of he obeying its definition, and ensures the reverse inclusion:
g∈MorM(M,X), g = hg(e)g ∈ Mor(M,X). ∎
This monoid (M,e,•) is essentially the opposite of the monoid End(M). Indeed for all a, bM we have ha ∈ End(M), hb ∈ End(M) and hahb(e) = ha(b) = ba.

3.8. 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 L-draft any L'-system (D,D) where D⊂ (LDD, such that:

Let us denote ∀xOD, ΨD(x) = (σ(x), lx) ∈ LD where σ∈LOD and lxDnσ(x).
Equivalent formulations of well-foundedness are

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

A ground draft is a draft with no variable, i.e. VD=∅. Thus, ΨD: DLD and SubLD = {D}.
Variables in a draft may be reinterpreted as constants: extending ΨD by IdVD : VDV, forms a ground (LV)-draft.

Sub-drafts and terms

Drafts do not have interesting stable subsets (by well-foundedness), but another stability concept: 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 a sub-draft. Moreover, any union of sub-drafts is also a sub-draft (unlike for sub-algebras with an operation with arity >1, which from arguments in different sub-algebras may give a result escaping their union).

The sub-draft co-generated by a subset of a draft, is the intersection of all sub-drafts that include it. A term is a draft co-generated by a single element that is its root. Each x in a draft D defines a term Tx with root x, sub-draft of D co-generated by {x}.
Each draft D is ordered by xyxTy. It is obviously a preorder. Proof of antisymmetry (uniqueness of the root):
xOD, VDA={yD|xTy} which is a sub-draft by transitivity of ≤.
xA ∴ ∃zOD\A, Im lzA.
A∪{z} is a sub-draft, thus TzA∪{z} by definition of Tz.
zOD\AxTzx=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 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 concrete category is that of drafts with variables-preserving morphisms, where V is fixed and morphisms f from a draft D are subject to f|VD = IdVD. This is equivalently expressed reinterpreting variables as constants, as the category of ground (LV)-drafts.

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, also expressible as

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

Any interpretation vEV of variables in an algebra E determines an interpretation of any draft D in E. To simplify formulations, restricting v to VD reduces the problem to the case VD=V.

Theorem. For any L-draft D with VD=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).

Uniqueness is deduced from well-foundedness : ∀g,h∈MorL(D,E), g|V = v = h|VV⊂ {xD|g(x) = h(x)} ∈ SubLDg=h.
Let us now prove existence (using conditional operator).
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
hK
(CD*(LC) ∋ x↦ (xC ? h(x) : φE(hLD(x))))) ∈ K
D*(LC) ⊂ C
C=D

Operations defined by terms

Any element t of an L-draft D defines a V-ary operation symbol, interpreted in each L-algebra E by ∀vEV, tE(v) = h(t) for the unique h∈MorL(D,E) such that h|VD = v|VD. This formalizes the operation defined by a term, namely the L-term 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 (IdV,t), is preserved by all L-morphisms, thus can be added to L without changing the category of L-algebras.
Symbols sL come back as the particular cases of the terms they form themselves where Ψ(t) = (s, IdV).
For the case of "small" (concretely written) terms, this preservation also has a schema of one proof for each term: re-expressing 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.9. Term algebras

Condensed drafts

A draft D is condensed if, equivalently,
  1. D is functional, i.e. ΨD is injective;
  2. D has an injective interpretation in some algebra;
  3. For any two distinct elements of D there exists an algebra where their interpretations differ.
1.⇒2. if D≠∅ (otherwise replace D by a singleton), ∃φ∈DLD, φ০ΨD = IdOD, i.e. IdD interprets D in (D,φ).
2.⇒3.
3.⇒1. ∀x,yOD, if ΨD(x) = ΨD(y) then x,y have the same interpretation in every algebra.

If L only has symbols with arity 0 or 1 then every L-term is condensed.

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. With this is usually assumed that V=VD=E\Im φE, i.e. variables of term algebras are usually used as an isolated set rather than 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 algebra is an algebra both minimal and injective, and thus also bijective.

If L has no constant then ∅ is a ground term L-algebra.
If L only has constants, then ground term L-algebras are the copies of L.
From any injective L-algebra (EE) and VE \ Im φE one can form the term algebra 〈VL. In particular the existence of an injective algebra implies that of a ground term algebra.

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 for a given V, any term L-algebra (EE) with E\Im φE=V, 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 the injectivity lemma, {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

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 element image of each term (operation symbol defined by a term) in the sense that two terms everywhere interpreted as the same operation have the same image.
Namely, any L-term T with root t and VTV, is represented in F by the image Im f with root f(t) of the f∈Mor(T,F) such that f|VT = IdVT.
Im f has the same interpretation as T in any L-algebra E extending any vEV because the unique g∈MorL(F,E) and h∈MorL(T,E) extending v, are related by h=gf, thus h(t)=g(f(t)).
Im f is condensed, and f is injective if and only if T is condensed.

For any subset A of an L-algebra E, the L-subalgebra 〈AL of E is the set of values of all L-terms with variables interpreted in A; it is the image of the interpretation in E, of a term algebra whose set of variables is a copy of A.

The unary term L-algebra M, essentially determined by L, represents all function symbols definable by unary L-terms. As a particular case of category of acts, its interpretations define actions of monoid preserved by morphisms across all L-algebras. Conversely if L is made of function symbols then any M-morphism is an L-morphism, because each sL plays the same role as sM(e)∈M.

A free monoid on a set X is a unary term X-algebra seeing X as made of function symbols; or equivalently, a monoid M such that XM and

This equivalence is deducible from the property of trajectories and the representation theorem.
The image of M by any morphism of monoid is the sub-monoid generated by the image of L.

3.10. Integers and recursion

The set ℕ

Any theory aiming to describe the system ℕ of natural numbers is called an Arithmetic. There are several of them, depending on the logical framework and the choice of language. Let us start with the set theoretical arithmetic, which is the most precise as it determines ℕ up to isomorphism, i.e. it is a definition of an isomorphism class of systems in a given universe. The use of algebra in this formalization may make it look circular, as our study of algebras used natural numbers as arities of operation symbols. But arithmetic only uses operation symbols with arity 0, 1 or 2, for which previous definitions might be as well written without reference to numbers.

Definition. ℕ is a ground term algebra with two symbols: a constant symbol 0 ("zero"), and a unary symbol S.
This S is called the successor. Its meaning is to add one unit (Sn=n+1) as will be seen below.

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

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

The existence of a ground term {0,S}-algebra is an equivalent form of the axiom of infinity, which completes the set theory we progressively introduced from the beginning to the powerset (with optionally the axiom of choice), to form what is essentially the standard foundation of mathematics as practiced by most mathematicians. It is most conveniently expressed by an insertion of arithmetic into set theory, in the form of the constant symbols of the set ℕ, its element 0 and its transformation S, and the above axioms (from which more symbols such as + and ⋅ can then be defined). It will be seen to imply the existence of term algebras of any language. Fixing ℕ in its class does not cause any uncertainty thanks to the essential uniqueness of initial {0,S}-algebras.

Recursively defined sequences

A sequence of elements of a set E, is a function from ℕ to E (a family of elements of E indexed by ℕ).
In particular, a recursive sequence in E is a sequence defined as the only 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 :

u0=a
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 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))
Re-interpreting the constant 0 as a variable, makes ℕ a unary term {S}-algebra, where each number n is a unary term Sn with n occurrences of S, 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, f 1=f and f 2 = ff.
Generally for any fEE, gEX, the sequence (hn) in EX recursively defined by (h0=g) and (∀n∈ℕ, hSn = fhn) is hn=f ng.

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 = Sp(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 pf n is deduced from
(fn+0=fn ∧ ∀p∈ℕ, fn+Sp = fS(n+p) = ffn+p) ∴ ∀aE, ∀fEE, (pf n+p(a))∈Mor(ℕ,(E,fn(a),f)),
from which associativity comes as (a+b)+n = Sn(Sb(a)) = Sb+n(a) = a+(b+n).

Multiplication

Multiplication in ℕ can be defined as xy = (Sx)y(0), or recursively as

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

Then generally, ∀fEE, f xy = (f x)y.

Inversed recursion and relative integers

By induction using commutativity (n+1 = 1+n),

f,gEE, gf = IdE ⇒ ∀n∈ℕ, gnf n = IdE.

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 = (fn)-1f.

The system of (relative) integers ℤ is defined as the {0,S}-algebra where 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 (EE, IdE, f), or an action of ℤ on E interpreting 1 as f.

Proof: the {0,S}-morphism condition requires on ℕ the same nf n as above; on -ℕ, it recursively defines f -n = (f -1)n, namely

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.11. Arithmetic with addition

First-order 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 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 as the set theoretical framework was involved to justify recursive definitions, the successor function no more suffices to define addition and multiplication in first-order logic. 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 we shall use set theoretical notations in such ways that they can be read as abbreviations of works in first-order logic: as long as we only consider subsets of ℕ* defined by first-order 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,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{S}(M,ℕ).
Im fx = fx [〈0〉{S}] = 〈x{S}M.
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.∎
So, all possible axiom pairs are equivalent: (A1 ∧ Min) ⇔ (As ∧ Min) ⇔ (As ∧ Ind) ⇔ (A1 ∧ Ind), and imply commutativity.
Now (F) ⇔ (∀x∈ℕ*, ∀y∈ℕ, x+y y) because x+0 = x ≠ 0.
(Inj ∧ Ind ∧ A1) ⇒ (F) because ∀x∈ℕ*, {y∈ℕ | x+yy} ∈ 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
xy ⇔ ∃z∈ℕ, y = x+z

(A1 ∧ Ind) implies that
  1. < is transitive
  2. xy ⇔ (x<yx=y)
  3. x<yx+1≤y
  4. A⊂ℕ, A≠∅ ⇒ ∃xA, ∀yA, xy (meaning a schema of formulas in 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}. Or using 3, A={x∈ℕ |∀y∈ℕ, x<yx=y y<x} ⇒ (0∈A ∧ ∀xA, x+1∈A)
  6. y = x+ny+z = x+z+n
Now the full system (A1 ∧ Ind ∧ F) implies that 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 first-order 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∈ℕ | nx} is the unique A⊂ℕ such that
x∈ℕ, xA ⇔ (x = n ∨ ∃yA, Sy=x).
Its existence in ℘(ℕ) can be deduced in set theory (not first-order 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 non-injective {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, ux = uy. This x is unique because y is minimal.
{un | n<y} ∈ Sub{0,S}K, thus =K.
As Inj f|Kx=0 ⇔ a∈ Im f|Kfy(a)=a ⇔ (f|K)y = IdK, 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