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 We then denote the set of all operations OpE = ⋃n∈ℕ OpE(n), and that of all relations RelE = ∐n∈ℕ ℘(En).

Languages

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)

Relational systems

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 Lf : LELF defined by (s,x) ↦ (s,fx).
Im Lf = LIm 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, (Lf)*(LB) = L(f*(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))
Lf[E]⊂FE⊂(Lf)*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

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| φFLf = 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, (Lf(x),f(y))∈F) ⇔ (∀xLE, φF(Lf(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[LIm f] = φF[Im Lf] = Im (f০φE) ⊂ Im f

Stable subsets of systems

The concept of subagebra is generalized to relational L'-systems (E,E) with possibly non-functional structure E ⊂ (LEE, as the following condition of stability for subsets A (which no more makes them 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, (Lf(x),f(y))∈F∴ (xLALf(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, xLX ⇒ (∀BX, xLByB) ⇒ y∈∩X. ∎

Other way: E*(LX) = 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 = {xE | ∀B∈SubLE, ABxB} = ∩{B∈SubLE | AB} ∈ SubLE

For fixed E and L, the function A↦〈AL is the closure, with image SubLE, from the relation ∈ between E and SubLE:
XE, ∀Y⊂SubLE, X ⊂ ∩Y ⇔ (∀BY, XB) ⇔ Y ⊂ {B∈SubLE | XB}.
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[LMinLE] ⊂ Im φE
  4. AE, ⋃xA〈{x}〉L ⊂ 〈AL = A∪φE[LAL] ⊂ 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[LAL] ∈ 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) ⊂ LBQ zLE, φF(Lf(z)) = y.
    As φFLf = 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-systems (E,E) and (F,F) and any f : EF we have f∈Mor(E,F) ⇔ Lf[E]⊂F.
If f : EF and Lf[E] = F then f will be called a projection from E to F.
The role it gives to F is that of quotient of E by ∼f. Namely, for any equivalence relation R on E, the quotient set E/R has a natural L-structure E/R defined as LR[E]. It is the smallest L-structure on E/R such that R∈Mor(E, E/R).
If R ⊂ ∼f then (f ∈ Mor(E,F) ⇔ f/R ∈ Mor(E/R,F).

Given an algebraic language L, an equivalence relation R on E is said to be compatible with an L'-structure E if the quotient structure is a functional graph. If E is an algebra structure then Dom(E/R) = L(E/R) so that the compatibility condition means that the quotient is also an algebra.
For any L'-systems (E,E) and (F,F), any f : EF, BF and A= f*(B) we have
(f∈Mor(E,F) ∧ B∈SubLF) ⇒ A∈SubLE
(FfL[E] ∧ A∈SubLE) ⇒ B∈SubLF
Lf[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 = Lf*(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).

For any relational system E and any subset AE, defining the structure of A by restricting that of E to A,

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

(Lf)-1 = L(f -1) ∴ φELf -1 = f -1f০φELf -1 = f -1০φFLfLf -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). It is nontrivial if it differs from IdE.
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. ∎

The Galois connection (End, Inv)

For any set E and any n∈ℕ, the preservation relation (∀xR, fxR) between fEE and R∈RelE(n) gives a Galois connection (End, Inv(n)) between their powersets, where Inv(n)(M) is the set of n-ary relations invariant by MEE. In particular, Inv(1) M = SubM :

MEE, ∀F⊂℘(E), M ⊂ EndFE ⇔ (∀fM, ∀AF, f[A] ⊂ A) ⇔ F ⊂ SubME.

Gathering all arities forms the Galois connection (End, Inv) with

Inv = ∏n∈ℕ Inv(n) : ℘(EE) → ∏n∈ℕ ℘(RelE(n)) ≅ ℘(RelE).

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.

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 another 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.

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)

Effectiveness and free elements

A left action of M on X is said effective if this morphism from M to XX 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

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

Denoting A = 〈XL, M = 〈L{Id,০} and K = {f(x) | (f,x)∈M×X}, the claim is that A = K. As we shall formalize later, both A and K mean the set of all composites of any number of functions in L, applied to any xX.
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

For a monoid M, Inv M is made of unions of trajectories of tuples. Other cases come down to this as ∀LEE, Inv L = Inv 〈L{Id,০}, so that closures can be written

EndInv(n)L E = {gEE| ∀xEn, ∃f∈〈L{Id,০}, fx=gx}.
EndInv L E = {gEE| ∀n∈ℕ,∀xEn, ∃f∈〈L{Id,০}, fx=gx}.

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

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).

Special actions

The above 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.
Now this can qualify actions (M-sets) themselves: let us call an action monogenic if it is a trajectory (it is generated by a single element), and free if it is generated by the set of its free elements.
Let us call it regular if it is both monogenic and free. Then there is a free element that generates it, i.e. it is M-isomorphic to M.
Proof: a generator being generated by the set of free elements, must be in the trajectory of one of them, which is thus also generating. (On the other hand, a monogenic action may have free elements without being free).

An action of a group G on a set X, is equivalently an action of monoid, or a group morphism from G to the symmetric group of X.

As inversion is an anti-morphism, it switches any left action ▪ of G on X into a right action • by ∀xX, ∀gG, x•g = g-1x.

If an action of group is monogenic then every element is generating ; if it is free then all elements are free, so that all parts of its partition into orbits are regular.

The Galois connection (Aut, sInv)

For any set E, the relation of strong preservation between its set RelE of relations and its set ⤹E of permutations, defines a Galois connection (Aut, sInv) similar to (End, Inv), where sInv gives the set of strong invariants :

P⊂⤹E, sInv P = Inv (P ∪ -P) = Inv (P) ∩ Inv(-P) ⊂ RelE
L⊂RelE, ∀P⊂ ⤹E, L ⊂ sInv PP ⊂ AutL E.

For any subgroup G of ⤹E (automorphism group in any category), sInv G = Inv G.

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

Again, an automorphism of an object E, is an isomorphism from E to itself. Their set Aut(E) is the group of invertible elements of the monoid End(E)=Mor(E,E).

Functions defined by composition

In any category, any f ∈ Mor(E,F) defines functions by currying composition with other morphisms to or from another object X: let us denote (almost following wikipedia but adapted to our concept of concrete category)
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).∎

A morphism f is an isomorphism if and only if Hom(X,f) : Mor(X,E) ↔ Mor(X,F); its inverse is then Hom(X, f -1).

In any category, Isomorphism ⇔ (Retraction ∧ Monomorphism) ⇔ (Section ∧ Epimorphism)
In concrete categories, Section ⇒ Injective morphism ⇒ Monomorphism
In categories of relational systems, Retraction ⇒ Quotient ⇒ Surjective morphism ⇒ Epimorphism

Representation theorem

Theorem. Any small category is isomorphic to that of all morphisms in a family of typed algebras.

The proof essentially repeats the formulas on acts as algebraic structures, transposed. From the given small category, a family of typed algebras is formed as follows. Each u ∈ Mor(E,F) acts on each type t by Hom(t,u) : tEtF. These for all u and t define f : Mor(E,F) → FE, so that the system of these for all E, F respects identities and compositions (they form an action in a sense generalized from monoids to small categories). Let us prove that f : Mor(E,F) ↔ MorL(E,F).
Im f ⊂ MorL(E,F) by associativity (f commutes with the action of L).
The existence of an isomorphism ktE ensures that f is injective (as k is epic) and MorL(E,F) ⊂ Im f:
g∈MorL(E,F), u = g(k)•k-1 ∈ Mor(E,F) ⇒ (∀xE, ∃sL, ks = xg(x) = g(ks) = g(k)•s = uks = ux) ⇒ g = f(u) ∎

In particular for any monoid M there is a language L of function symbols and an L-algebra X such that EndL X is isomorphic to M.
Any group is isomorphic to a permutation group, namely the group of automorphisms of an algebra.

3.8. Initial and final objects

In any category, an object X is called an initial object if all sets Mor(X,Y) are singletons. Of course any object isomorphic to an initial object is also an initial object, as all isomorphic objects have the same properties. But conversely all initial objects (if they exist) are isomorphic, by a unique isomorphism between any two of them:
For any initial objects X, Y, ∃f∈Mor(X,Y), ∃g∈Mor(Y,X), 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 ?

Embeddings in concrete categories

In categories of relational systems, any section is an embedding, but without converse in general.
For any subset A of an object of such a category,

(There exists a section with image A) ⇔ (for any object N, Mor(A,N) = {g|A | g∈Mor(E,N)}) ⇒ (any embedding with image A is a section).

For images A of embeddings which are not sections, that formula for Mor(A,N) would not generally fit the concept of morphisms for any relational structure on A. Also in some categories of systems, not all subsets A of systems E are images of embeddings, because they do not fit as objects, particularly if the restricted structure on A fails at some chosen axiom. For example categories of algebras do not accept all subsets as sub-algebras.

Let us generalize the concept of embedding to any concrete category C, making it work the same as in categories of relational systems beyond the case of sections (but unlike sections, it will require checking the whole category). For any subset A of an object E of C, let To-A be the category where

The injectivity of f implies the uniqueness of any To-A-morphism to f.

Now a morphism f in C is an embedding if it is a final object of any To-A. Then it is also a final object of To-(Im f). It is an embedding onto A if moreover A = Im f.
All such embeddings, even non-injective ones, are monic : Section ⇒ Embedding ⇒ Monomorphism.

While C may have been given with pairwise disjoint objects ("forgetting" the canonical injections between them), any image A = Im f of an injective embedding f may receive a role of object added to C (we may call it a sub-object), as an additional representative of an existing isomorphism class in C, by copying to A through f (seen as an isomorphism) the sets of morphisms involving Dom f (independently of the choice of f because of its essential uniquess as a final object of To-A). But for an image A of non-injective embedding, the new object must stay another set with a surjection to A.

Products in concrete categories

For any family of objects (Ei)iI of a concrete category C, the set P = ∏iI Ei is called a product in C if it plays the role of an object with sets of morphisms to it defined by

For any object F, Mor(F,P) ≅ ∏iI Mor(F,Ei)

i.e. the canonical injection from Mor(F,P) to ∏iI EiF has image ∏iI Mor(F,Ei).

In this equality condition, the inclusion (Inc) of the image of Mor(F,P) into ∏iI Mor(F,Ei) for all F, is equivalent to ∀iI, πi∈Mor(P,Ei).
Any data of L-algebra structures φi on each Ei defines the one φP on P, by

(∀iI, πi∈MorL(P,Ei)) ⇔ (∀iI, φiLi) = πi০φP) ⇔ φP = ∏iI φiLi)

thus (Inc) suffices to determine the algebraic structure of P, and imply the reverse inclusion.
In the more general case, assuming (Inc), the reverse inclusion not only defines Mor(F,P), but also determines all Mor(P,F) from the category if it allows such a product as an object, by making essentially unique any coexisting products of a given family of objects in a given category. This essential uniqueness is verified in the following more general case.

Products and coproducts in categories

A product of any family of objects (Ei)iI in a category C, is a final (thus essentially unique) data

(P, φ) = CiI Ei

of an object P with φ∈∏iI Mor(P,Ei), i.e. making bijective all f ↦ (φif)iI :

For all F, ∏iI Hom (Fi) : Mor(F,P) ↔ ∏iI Mor(F,Ei)

Empty products (I=∅) are the final objects. The concept of embedding is a variant of the unary case (itself trivial).

In concrete categories, for any (P, φ) and any F, (∏φ : P ↪ ∏iI Ei) ⇒ Inj ∏iI Hom (Fi) but products as just defined may exist without admitting as such the set theoretical one (P, π) where P = ∏iI Ei and ∏π = IdP.

Symetrically by taking the opposite category, a coproduct of a family of objects (Ei)iI in a category C, is an initial data

(K, j) = CiI Ei

of an object K with j∈∏iI Mor(Ei, K), i.e. making bijective all f ↦ (fji)iI :

For all F, ∏iI HomK(ji, F) : Mor(K,F) ↔ ∏iI Mor(Ei,F)

In the concrete category of all sets with all functions between them, the coproduct is the disjoint union with its canonical injections. In useful concrete categories the ji are also usually injective, but curiosity exceptions exist.

3.9. Eggs, basis, clones and varieties

Eggs

Let us generalize the concept of free and generating element from actions of monoids to actions of categories. For any concrete category C, or more generally any category with a given action, let us call egg of C (*) an initial object (M,e) of the category where In other words, for any object E the function Mor(M,E) ∋ ff(e) is bijective to E.
For any egg of an acting category, its image in the resulting concrete category is also an egg.

Proposition. Any egg (M,e) (if that exists), can be seen in a unique way as a monoid (M,e,•) with an action on every other object X (beyond • on M itself), such that for all objects X, Y, Proof. 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.

For any object M of a category C, the action of C defined by M has an egg (MM, 1M), with the monoid action directly given by composition. This just simplifies conventions, taking Mor(M,E) as the definition of the set underlying E on which the category acts, instead of saying they are in bijection. If C was already a concrete category with an egg (M,e) then MC is just a copy of C (with correspondence using the choice of e).

Proposition. For a monoid (M,e, •) seen as an M-set interpreting • as action, (M, e) is an egg of the category of M-sets; other eggs are the (X,x) where x is a free and generating element of X.

Proof: 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). ∎

Basis and algebraic structures

As an egg is a language of function symbols, let us generalize this to any other arity.
A basis of an object X of a concrete or acting category C, is a family bXI such that (X,b) is an egg for the action of C giving to each object E the set EI:

uEI, ∃!f∈Mor(X,E), fb=u.

If an object with several elements exists in the category then any basis b is injective, thus can also be viewed as the subset B = Im bX (from which the view as a family can be restored taking b = IdB).
This gives X the role of the set of all possible I-ary operation symbols s interpreted in each object E and preserved in C: these are the structures defined by each (b,s) for sX, which are here functional. Its essential uniqueness means that any two basis in C which are equinumerous (a bijection between them exists), give their objects the role of the same set of operation symbols.
Given an egg (M, e), that is an object M with basis a singleton {e} where eM, an object X with basis B plays the role of the B-ary coproduct (of the constant family), CiB M, with the ji ∈ Mor(M,X) defined for each iB by ji(e) = i. These ji are sections.
For any category C, any objects M, X, and any B ∈ Mor(M,X)I, (X, B) is a coproduct CiI M if and only if B is a basis of MX in the concrete category MC.

Clones

Putting all arities together gives an algebraic language called the clone of C:

L = ∐n∈ℕ Ln

where each set Ln of n-ary symbols is an object of C with a chosen basis of n elements 1n = (ei,n)i<nLnn. Thus, ∀n∈ℕ, Ln = Ci<n L1.

Depending on C, a clone may exist or not, but it is essentially unique, serving as the maximal algebraic language for objects of C.

Each object E of C, gets the L-algebra structure φE = ∐n∈ℕ φE(n), where φE(n) : Ln × EnE is defined taking as ⃖φE(n) the inverse of Mor(Ln,E) ∋ ff০1n which is bijective to En because 1n is a basis in C. This definition is expressible by both axioms which extend to clones those defining the action of an egg in a category:
  1. Each ei,n acts as the i-th projection from En to E, i.e. ∀i<n, ∀uEn, ei,nu = ui.
  2. n∈ℕ, ⃖φE(n) : En → Mor(Ln,E).
This implies (for all objects E, F),

Mor(E,F) ⊂ MorL(E,F)
n∈ℕ, Mor(Ln,E) = MorL(Ln,E).

Let us recall the proof of MorL(Ln,E) ⊂ Mor(Ln,E) previously seen for n=1. From 1n being a basis of Ln and IdLn ∈ Mor(Ln,Ln), comes
  1. xLn, x = x⋅1n
Thus ∀f∈MorL(Ln,E), (∀xLn, f(x) = f(x⋅1n) = x⋅ (f০1n) ∴ f = ⃖φE(n)(f০1n) ∈ Mor(Ln,E).∎

3. implies that 1n generates Ln in the sense that 〈1nLn = Ln ∴ 〈1nL = Ln.

Abstract clones and varieties

A clone L may be conceived independently of C (like monoids are independent of their actions), as the small concrete category made of the sequence of objects (Ln)n∈ℕ, called an abstract clone. It defines on L a structure of typed algebra with types Ln and operations Generalizing the concept of action to such a typed algebra, an L-module (or representation of L), is an L-algebra M satisfying the above 1. and 2. where 2. uses MorL :

n,p∈ℕ, ∀sLp, ∀xLnp, ∀uMn, (sx) ⋅ u = s ⋅ ((xiu)i<p)

The variety of L is the category of all L-modules with Mor = MorL.
A typed algebra L = ∐n∈ℕ Ln with such symbols, is an abstract clone if each Ln satisfies the above axioms 1., 2. and 3. extending to L the axioms of monoid for L1:
As will be seen later, the general concept of variety will use algebraic languages that do not need to be abstract clones, and not even typed algebras.
(*) I took the initiative to call it "egg" as I am not aware of any existing name for that concept in the literature.

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