3. Algebra
This section on algebra will mainly (for about 3/4) be formed of concepts extracted
from the existing literature on universal algebra and category theory. This exposition aims
to be relatively short, optimized and selfcontained, focused on the relatively few basic
aspects I found relevant for providing a solid framework for the main concepts of
the foundations of mathematics, geometry and physics.
In contrast, the literature on the topic appears overloaded by less efficient choices of
formalization and many more concepts less relevant to this goal. Not being erudite in it
(being discouraged by its size), I cannot check how new are the points and tricks I
figured out myself, and for which I coined some original vocabulary and notations.
3.1. Galois connections
Fixed points, idempotent functions
The set of fixed points of any function f is defined as
∀_{Fnc} f, Fix f = {x∈ Dom f
 f(x) = x} ⊂ Dom f ⋂ Im f
Then, ∀_{Fnc} f,g, Im f ⊂ Fix g
⇔ (Im f ⊂ Dom g ∧ g⚬f = f)
A function f is called idempotent if, equivalently,
Im f ⊂ Dom f ∧ f⚬f = f
Im f = Fix f
Monotone, antitone, strictly monotone functions
Between ordered sets E and F, a function f :
E → F will be said :
 monotone if ∀x,y∈E, x ≤
y ⇒ f(x) ≤ f(y)
 antitone if ∀x,y∈E, x ≤
y ⇒ f(y) ≤ f(x)
 strictly monotone if ∀x,y∈E, x
≤ y ⇔ f(x) ≤ f(y)
 strictly antitone if ∀x,y∈E, x
≤ y ⇔ f(y) ≤ f(x).
Any composite of a chain of monotone or antitone functions, is
monotone if the number of antitone functions in the chain is even,
or antitone if it is odd.
Any strictly monotone or strictly antitone
function is injective.
If f ∈ F^{E}
and g ∈ E^{F} are both monotone
(resp. both antitone) and g⚬f = Id_{E},
then f is strictly monotone (resp. strictly antitone).
Order between functions, extensive functions
For all sets E, F where F is ordered, the
set F^{E} is ordered as a product
(f ≤ g ⇔ ∀x∈E, f(x)
≤ g(x)).
Then, ∀f,g∈F^{E},
∀h∈E^{G}, f ≤ g ⇒ f⚬h
≤ g⚬h, i.e. f ↦ f⚬h is always
monotone.
The particular case F = V_{2}
is that h_{⋆} is monotone from ℘(E)
to ℘(G) for the inclusion order.
If F and G are ordered and u ∈ G^{F}
is monotone (resp. antitone) then F^{E} ∋ f
↦ u⚬f ∈ G^{E} is monotone
(resp. antitone).
In an ordered set E, a function f ∈ E^{E}
is said extensive if Id_{E} ≤ f, i.e.
∀x∈E, x ≤ f(x).
The composite of two extensive functions is extensive.
Galois connections : definition and examples
For any ordered sets E, F,
denoting F^{−} the set F with the
transposed order, the sets of (antitone) Galois connections
between E and F, and monotone Galois connections
from E to F, are defined by
Gal(E,F)
= {(⊥,⊤) ∈ F^{E}×E^{F}∀x∈E,
∀y∈F, x ≤_{E}⊤(y) ⇔ y
≤_{F} ⊥(x)} = ^{t}Gal(F,E)
Gal^{+}(E,F) = {(u,v) ∈
F^{E}×E^{F}∀x∈E,
∀y∈F, x ≤_{E} v(y) ⇔ u(x)
≤_{F} y} = Gal(E,F^{−})
Lemma. ∀⊥ ∈ F^{E}, !⊤ ∈
E^{F}, (⊥,⊤) ∈ Gal(E,F).
Proof: ∀⊤ ∈ E^{F}, (⊥,⊤) ∈ Gal(E,F) ⇔
≤⃖_{E}⚬⊤ = ⊥_{⋆}⚬ ≤⃗_{F},
while ≤⃖_{E} is injective.∎
Galois connections between powersets. Any R ⊂ X×Y
defines (⊥,⊤) ∈ Gal(℘(X),℘(Y)) by
∀A⊂X, ⊥(A) = {y∈Y 
∀x∈A, x R y} =
∩_{x∈A} R⃗(x)
∀B⊂Y, ⊤(B) = {x∈X
 ∀y∈B, x R y} = {x∈X
 B ⊂ R⃗(x)}
Then, ⊥(∅) = Y and ⊤(∅) = X.
Proof : ∀A⊂X, ∀B⊂F, A ⊂ ⊤(B) ⇔
A×B ⊂ R ⇔ B ⊂ ⊥(A).∎
This is actually a bijection: Gal(℘(X),℘(Y))
⥬ ℘(X×Y). Proof:
if (⊥,⊤) ∈ Gal(℘(X),℘(Y)) and R = ∐_{x∈X}
⊥({x}) then
∀B⊂Y, ∀x∈X, x ∈ ⊤(B) ⇔
B ⊂ ⊥({x}) = R⃗(x).∎
Monotone Galois connections between powersets. Any relation
R ⊂ X×Y defines a (u,v) ∈
Gal^{+}(℘(X),℘(Y)) by
∀A⊂X, u(A) = {y∈Y 
∃x∈A, x R y} = ⋃_{x∈A}
R⃗(x)
∀B⊂Y, v(B) = {x∈X
 R⃗(x) ⊂ B}.
This way, the graph of any function f : X → Y defines
(A ↦ f[A], B ↦
f_{⋆}(B)) ∈ Gal^{+}(℘(X),℘(Y))
Properties of Galois connections
For all (⊥,⊤) ∈ Gal(E,F), the closures
Cl =⊤⚬⊥ ∈ E^{E} and Cl′=⊥⚬⊤ ∈ F^{F}
satisfy  Cl and Cl′ are extensive.
 ⊥ and ⊤ are antitone
 Cl and Cl′ are monotone

⊥⚬⊤⚬⊥ = ⊥, and similarly ⊤⚬⊥⚬⊤ = ⊤

Im ⊤ = Im Cl = Fix Cl, called the set of closed elements of E.

Cl⚬Cl = Cl

(⊥ strictly antitone) ⇔ Inj ⊥ ⇔ Cl = Id_{E} ⇔ Im ⊤ = E

∀x,x′∈E, ⊥(x) ≤ ⊥(x′) ⇔
(Im⊤∩ ≤⃗(x) ⊂ ≤⃗(x′)).
 Denoting K = Im ⊤, ⊤⚬⊥_{K} =
Id_{K}, thus ⊥_{K}
is strictly antitone and ⊥_{K}^{−1} = ⊤_{Im⊥}.
Proofs:
(1.) ∀x∈E, ⊥(x) ≤ ⊥(x) ∴ x ≤ ⊤(⊥(x)).
(1. ⇒ 2.) ∀x,y∈E, x ≤ y ≤ ⊤(⊥(y))⇒⊥(y) ≤ ⊥(x).
(1.∧2. ⇒ 4.) Id_{E} ≤ Cl ⇒⊥⚬Cl ≤ ⊥ ≤ Cl′⚬⊥ = ⊥⚬⊤⚬⊥.
(4.⇒5.) Cl = ⊤⚬⊥ ∴ Im Cl ⊂ Im⊤ ;
Cl⚬⊤ = ⊤ ∴ Im ⊤ ⊂ Fix Cl ⊂ Im Cl.
2. ⇒ 3. and 4. ⇒ 6. are obvious.
(7.) (Inj ⊥ ∧ ⊥⚬Cl = ⊥) ⇔ Cl = Id_{E} ⇔ (Im ⊤ = E ∧ Cl⚬⊤ = ⊤);
Cl = Id_{E} ⇒ ⊥ strictly antitone ⇒ Inj ⊥.
(8.) ⊥(x) ≤ ⊥(x′) ⇔ (∀y∈F, x≤⊤(y)
⇒ x′≤ ⊤(y)).
(9.) K = Fix(⊤⚬⊥)
⇒ ⊤⚬⊥⚬Id_{K} = Id_{K}.
Other proof : (⊥_{K},⊤) ∈ Gal(K,F) with ⊤ surjective.
In ⊤_{Im⊥}⚬⊥_{K} = Id_{K} the roles of ⊤
and ⊥ are symmetrical. ∎
Remark. Properties 1. and 2. conversely imply that (⊥,⊤) ∈ Gal(E,F).
Proof: ∀x∈E, ∀y∈F, x ≤ ⊤(y) ⇒ y ≤
⊥(⊤(y)) ≤ ⊥(x).∎
Analogues of the above properties for monotone Galois connections
are obtained by reversing the order in F:
If (u,v) ∈
Gal^{+}(E,F) then u and v are monotone,
v⚬u is extensive and u⚬v ≤ Id_{F}.
Characterization of closures
A closure of an ordered set E
is an f ∈ E^{E} such that, equivalently:
 There exists a set F and an (u,v) ∈
Gal(E,F) or Gal^{+}(E,F)
such that v⚬u=f

f is monotone, idempotent and extensive

∀x∈E, ∀y∈ Im f, x ≤ y
⇔ f(x) ≤ y, i.e. (f, Id_{K})
∈ Gal^{+}(E,K)
where K = Im f
Proof of equivalence:
3. ⇒ 1. ⇒ 2.
For 2. ⇒ 3., ∀x∈E,∀y∈K, x ≤ f(x)
≤ y ⇒ x ≤ y ⇒ f(x) ≤ f(y)
= y. ∎
Notes:
 2.⇒3. is a particular case of the remark: f⚬f =
f ⇒ f⚬Id_{K}
≤ Id_{K} (extensivity of f⚬Id_{K}
in K^{−}).
 ∀K⊂E, ∀f∈K^{E},
(f,Id_{K}) ∈ Gal^{+}(E,K) ⇒
Im f = K from the above 7. with Id_{K} injective.
More on Galois
connections
3.2. Relational systems and concrete categories
Let us formalize the concept of system, focusing for simplicity on those
with only one type. For any number n∈ℕ and any set E, let us denote
 E^{n} = E×...×E = E^{Vn},
set of all ntuples of
elements of E (nary product
or exponentiation).
 Rel_{E}^{(n)} = ℘(E^{n}),
set of all nary relations in E
 Op_{E}^{(n)}
= E^{En}, set of all nary operations in E.
We then denote the set of all operations Op_{E} = ∐_{n∈ℕ}
Op_{E}^{(n)},
and that of all relations Rel_{E } = ∐_{n∈ℕ} ℘(E^{n}).
Or, we could write Op_{E} with ⋃_{n∈ℕ} since the
Op_{E}^{(n)} are pairwise disjoint when E≠∅.
Languages
A language L is a set of symbols, with the data of the intended arity
n_{s}∈ℕ of each s∈L. For any set E, let
^{L}E = ∐_{s∈L}
E^{ns}
Then ∀A⊂E, ∀(s,x)∈^{L}E,
(s,x) ∈ ^{L}A ⇔ Im x ⊂ A.
A relational language is a language L of relation symbols,
where each s∈L aims to be interpreted in any Lsystem E as
an n_{s}ary relation. These form a family called an Lstructure
on E, element of
∏_{s∈L} ℘(E^{ns})
⥬ ℘(^{L}E).
For any function f : E → F, let ^{L}f :
^{L}E → ^{L}F defined by
(s,x) ↦ (s,f⚬x). Then
^{L}Id_{E} = Id_{LE}
∀_{fnc}f,g, Im f
⊂ Dom g ⇒ ^{L}(g⚬f) =
^{L}g ⚬ ^{L}f
Inj f ⇒ Inj ^{L}f
Im ^{L}f = ^{L}Im f
The latter comes by
finite choice applied to (AC1)⇒(AC7),
as arities of symbols are finite (otherwise it still goes for injective f,
or using AC).
We shall omit parenthesis in notations of direct and inverse images
in the way ^{L}f_{⋆} = (^{L}f)_{⋆}.
Then,∀A⊂E, ^{L}f[^{L}A]
= ^{L}(f[A])
∀B⊂F, ^{L}f_{⋆}(^{L}B) =
^{L}(f_{⋆}(B))
Relational systems
A relational system with language L, or Lsystem, is the
data (E,E) of a set E with an Lstructure E ⊂
^{L}E.
The case of an algebraic language, whose symbols aim to represent operations,
will be studied in 3.3.
Most often, we shall only use one Lstructure on each set, so that E
can be treated as implicit, determined by E. Precisely, let us imagine given a class of
Lsystems where each E is the intersection of ^{L}E
with a fixed class of (s,x), denoted as a predicate s(x) for how it is
naturally curried: each symbol s∈L is interpreted in each system E as the
n_{s}ary relation s_{E} somehow independent of E,
s_{E} = {x∈E^{ns}
 s(x)} = E⃗(s)
E = {(s,x)∈^{L}E  s(x)} =
∐_{s∈L} s_{E}.
Morphisms
Between any Lsystems E,F,
we define the set Mor_{L}(E,F) ⊂ F^{E}
of Lmorphisms from E to F
by ∀f∈F^{E},
f ∈ Mor_{L}(E,F) ⇔
∀(s,x)∈E, (s,f⚬x)∈F
⇔ (∀s∈L,∀x∈E^{ns},
s(x) ⇒ s(f⚬x))
⇔
^{L}f[E] ⊂ F ⇔ E ⊂
(^{L}f)_{⋆}F.
Concrete categories
The concept of concrete category is what remains of a class of systems with their
morphisms, when we forget which are the structures that the morphisms are preserving
(as we will see this list of structures can be extended without affecting the sets of morphisms).
Let us formalize concrete categories as made of the following data (making this
slightly "more concrete" than the official concept of concrete category from other authors)
 a class of sets called objects ;
 a class of functions called morphisms; then for any objects
E,F, we define
Mor(E,F) = {f∈F^{E}  f is a morphism}
satisfying the following axioms:
 Every morphism belongs to some Mor(E,F), i.e.
its domain is an object and its image is included in an object
(in practice, images of morphisms will be objects too);
 For any object E, Id_{E} ∈ Mor(E,E)
;
 Any composite of morphisms is a morphism: for any 3 objects E,F,G
, ∀f ∈ Mor(E,F), ∀g∈Mor(F,G),
g⚬f ∈ Mor(E,G).
The last condition is easily verified for Lmorphisms : ∀(s,x)∈E,
(s,f⚬x)∈F ∴ (s,g⚬f⚬x)∈G.
The simplest example is the category of sets where all sets are objects, and
Mor(E,F) = F^{E}.
A category is small if its class of objects is a set.
The official concept of concrete category mainly differs from this by allowing different objects to
have the same base set : in the case of relational systems, such objects are systems consisting
of different choices of structures on the same set. The above version of the concept may
simulate this by taking disjoint copies of a given set for all structures we consider to use on it ;
but this construction does not match the use of subsets as objects in their own right.
We do not need to specify a fixed consistent formalization as long as we shall not play on
the ambiguity in any way which might lead to wrong conclusions. Generally speaking,
when we define a system and declare it an object of a category, we only need that some
copy of this system is an object.
For example, we shall speak of the category of all Lsystems, which gives back
the category of sets when L is empty.
Preservation of some defined structures
A relational symbol s with the data of an interpretation s_{E} ⊂
E^{ns} in every object E of a given concrete
category, is said to be preserved if all morphisms of the category are also morphisms
for this symbol, i.e. ∀f∈Mor(E,F), ∀x∈s_{E},
f⚬x∈s_{F}. From definitions, each symbol in a language
L is preserved in any category of Lsystems.
In any given category of Lsystems, or any concrete category with a given list L
of preserved interpreted symbols, any further invariant structure
whose defining formula only uses symbols in L and logical symbols
∧,∨,0,1,=,∃, is preserved.
Proof. For any Lmorphism
f∈Mor_{L}(E,F),
 Substituting arguments of a s∈L by a map σ to n' other variables
(∀E,∀x∈E^{n'}, s'(x) ⇔ s(x⚬σ)),
works :
s'(x) ⇒ s(x⚬σ) ⇒
s(f⚬x⚬σ) ⇒ s'(f⚬x).
 ∀s,s'∈L, n_{s} = n_{s'} ⇒
∀x∈E^{ns}, (s(x) ∧ s'(x))
⇒ (s(f⚬x) ∧ s'(f⚬x))
 ∀s,s'∈L, n_{s} = n_{s'} ⇒
∀x∈E^{ns}, (s(x) ∨ s'(x))
⇒ (s(f⚬x) ∨ s'(f⚬x))
 For 0 and 1 it is trivial
 ∀x,y∈E, x = y ⇒ f(x) = f(y)
 ∀x∈E^{ns},(∃y∈E,
s(x,y)) ⇒ (∃z=f(y)∈F,
s(f⚬x, z)) ∎
In particular:
 In the nullary case: for any f ∈ Mor_{L}(E,F),
if a ground formula with language L using only these logical symbols is true in
E, then it is also true in F.
 The graph of any operation defined by a term is expressible in this way,
and thus also preserved. But the proofs given by the above means are only a
schema of one proof for each "small" (concretely written) term. A single proof for the full
range of all terms will be given in 4.1.
However, morphisms may no more preserve structures defined with other
symbols (¬,⇒,∀).
The above cases of 0, 1, ∨ and ∧ are mere particular cases (the nullary and binary cases)
of the following:
 Any union of a family of preserved structures in a concrete category is a preserved structure.
 Any intersection of a family of preserved structures is also a preserved structure.
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. The domain (range of objects)
of a typed system may be formalized in set theory, either as a family of sets
E = (E_{i})_{i∈τ}, or as a set E
with a function t_{E} : E → τ giving the type of each element.
The translation between both formalizations is obtained one way taking the sum, and in
the other way taking the fibers of t_{E} (what we called an indexed partition
but allowing empty components).
Then the concept of morphism between systems E,F
with a common list τ of types (and interpreting the same language),
is respectively and equivalently formalized as follows (aside the condition of having to
preserve all structures):
 As a tuple or family of functions (f_{i})_{i∈τ},
where ∀i∈τ, f_{i} : E_{i} → F_{i}
;
 As a τmorphism f : E → F seeing τ as a list of unary relation
symbols (like for the use of classes
as notions in set theory), i.e. a function such
that t_{F} ⚬ f = t_{E}.
3.3. Algebras
Algebras and their morphisms
Given an algebraic language L, an Lalgebra is the data
(E,φ) of a set E with an Lalgebraic structure φ : ^{L}E →
E, sum of a family of interpretations of each symbol s∈L as an operation
φ⃗(s) ∈ Op_{E}^{(ns)}.
Again, we shall usually consider a class of Lalgebras with only one choice of algebraic
structure φ_{E} on each set E, so that an algebra
(E,φ_{E}) can be designated in the short form of its underlying set E :
s_{E} : E^{ns}
→ E
φ_{E} = ∐_{s∈L}
s_{E} : ^{L}E → E
(but these s_{E} cannot be the restrictions of a common n_{s}ary
operator to each E, if we want to let constant symbols r and s interpreted
in algebras E and F such that r_{E} = s_{E}
but r_{F} ≠ s_{F}).
Algebras form a concrete category with the following sets of morphisms.
For any Lalgebras E, F,
Mor_{L}(E,F) = {f∈F^{E} 
∀(s,x)∈^{L}E, s_{F}(f⚬x) =
f(s_{E}(x))} = {f∈F^{E}
φ_{F}⚬^{L}f = f⚬φ_{E}}.
When c∈L is a constant symbol (n_{c} = 0), this condition
on f says f(c_{E}) = c_{F}.
Algebras as relational systems
Any category of algebras is identifiable with a category of relational systems
with functional structure, as follows.
Let L' be the copy of L as a relational language,
where the copy s'∈L' of each s∈L has
increased arity n_{s'} = n_{s}+1, so that
^{L'}E ⇌ ∐_{s∈L}
E^{ns}×E ⇌
^{L}E × E = {((s,x),y)  s∈L ∧
x∈E^{ns} ∧ y∈E}.
∐_{s∈L} Gr s_{E} ⇌ Gr φ_{E}
⊂ ^{L}E × E
Let us call Lsystem any set E with a structure formalized
as E ⊂ ^{L}E × E.
All concepts defined for relational systems are equally applicable through this canonical
bijection. Qualities of systems with algebraic languages
Further properties of Lsystems (E, E) will be named after
the qualities of the relation
E: let us qualify (E, E) as Functional or a partial
algebra if E is functional (graph of a function from a subset of ^{L}E);
 Serial if Dom E = ^{L}E;
 Algebraic if a serial partial algebra, i.e. essentially an algebra
(E, φ_{E}) by E = Gr φ_{E} ;
 Injective if ^{t}E is functional ;
 Surjective if Im E = E.
The concept of morphism between algebras (E, φ_{E}),
(F, φ_{F}) is the particular case of the one between
systems when they are algebraic :
∀f∈F^{E}, (∀(x,y)∈Gr φ_{E},
(^{L}f(x),f(y)) ∈ Gr φ_{F}) ⇔
(∀x∈^{L}E, φ_{F}(^{L}f(x))
= f(φ_{E}(x))).
Similarly, between a partial algebra (E, Gr φ_{E}) and an injective system
(F, ^{t}Gr ψ_{F}), sets of morphisms are defined by
Mor_{L}(E,F) =
{f∈F^{E}  Im f⚬φ_{E} ⊂ Dom ψ_{F} ∧
^{L}f_{Dom φE} =
ψ_{F}⚬f⚬φ_{E}}
Mor_{L}(F,E) =
{f∈E^{F}  Im ^{L}f⚬ψ_{F}
⊂ Dom φ_{E} ∧
φ_{E}⚬^{L}f⚬ψ_{F} = f_{Dom
ψF}}
If there exists a injective morphism from E to F then
 If F is functional then E is functional;

If F is injective then E is injective.
If there exists a surjective morphism from E to F then
 If E is serial then F is serial;

If E is surjective then F is surjective.
Stable subsets and subalgebras
Any subset A⊂E of an Lsystem (E, E), forms a system with
structure A = E ∩ (^{L}A × A). If E is functional
or injective then A has the same property.
We shall say that A is Lstable, if
E^{⋆}(^{L}A) ⊂ A. The set of stable subsets of
E is written Sub_{L} E:
Sub_{L} E = {A⊂E  E^{⋆}(^{L}A)
⊂ A} = {A⊂E  ∀((s,x),y)∈E,
Im x⊂A ⇒ y∈A}.
We have E ∈ Sub_{L} E.
If E is serial and A is Lstable then A is serial.
If E is algebraic and A is Lstable then A is algebraic, thus called
an Lsubalgebra of E. As an Lalgebra,
its structure is φ_{A} = φ_{ELA}.
Conversely, any algebraic subset of a partial algebra is stable.
If a formula of the form (∀(variables), formula without
binder) is true in an Lalgebra, then it is true in each of its Lsubalgebras.
A very abstract and general formulation of this will come in 3.9.
Diverse properties of stability
Intersections of stable subsets. ∀X ⊂ Sub_{L}E,
⋂X ∈ Sub_{L} E where ⋂X ≝
{x∈E  ∀B∈X, x∈B}.
Proof:
∀(x,y)∈E, x∈^{L}⋂X ⇒ (∀B∈X,
x∈^{L}B ∴ y∈B) ⇒ y∈⋂X. ∎
Other way:
E^{⋆}(^{L}⋂X) =
E^{⋆}(⋂_{B∈X} ^{L}B)
⊂ ⋂_{B∈X}
E^{⋆}(^{L}B) ⊂ ⋂X.
Stable set generated by a subset. ∀A⊂E, we denote
〈A〉_{L,E} or simply 〈A〉_{L}, the
smallest Lstable subset of E including A
(called Lsubalgebra of E generated by A if E is an algebra):
〈A〉_{L} =
{x∈E  ∀B∈ Sub_{L}E, A⊂B
⇒ x∈B} =
⋂{B∈ Sub_{L}E  A⊂B} ∈ Sub_{L}E
For fixed E and L, the function A↦〈A〉_{L} is the
closure, with
image Sub_{L}E, from the relation ∈ between E and Sub_{L}E:
∀X⊂E, ∀Y⊂Sub_{L}E, X ⊂ ⋂Y
⇔ (∀B∈Y, X⊂B) ⇔ Y ⊂ {B∈ Sub_{L}E  X⊂B}.
We say that A generates E or is a generating subset of E if 〈A〉_{L} = E.
Stability of equalizers. The equalizer Eq(f, g) = {x∈E  f(x) = g(x)} of any two Lmorphisms f,g∈Mor_{L}(E,F) from
an Lsystem E to a partial Lalgebra F, is Lstable.
Proof : ^{L}Eq(f, g) = {(s,x)∈^{L}E 
f⚬x = g⚬x} = {x∈^{L}E 
^{L}f(x) = ^{L}g(x)}
∀(x,y)∈E, (^{L}f(x) = ^{L}g(x) ∧
(^{L}f(x), f(y)) ∈ F ∧ (^{L}g(x), g(y)) ∈ F)
⇒ f(y) = g(y). ∎
Proof when F is an algebra : ∀(x,y)∈E,
^{L}f(x) = ^{L}g(x) ⇒
f(y) = φ_{F}(^{L}f(x)) = g(y).
Minimal systems
For any Lsystem E, its minimal stable subset
is defined as
Min_{L}E = 〈∅〉_{L,E}
= ⋂ Sub_{L} E ∈ Sub_{L} E.
It is called minimal subalgebra if E is an Lalgebra.
An Lsystem E is minimal when E = Min_{L}
E, or equivalently Sub_{L}E = {E}.
For any minimal Lsystem E and any
partial Lalgebra F, !: Mor_{L}(E,F).
For any Lsystem E and any A⊂E,
 ∀B∈ Sub_{L}E, A ∩ B ∈ Sub_{L} A
 Min_{L} A ⊂ Min_{L} E
 A is minimal ⇒ A ⊂ Min_{L} E
 A ∈ Sub_{L}E ⇒ E^{⋆}(^{L}A)
∈ Sub_{L}E ∩ ℘(A) = Sub_{L}A
 A ∈ Sub_{L}E ⇒
Min_{L}A = Min_{L}E
 A = Min_{L}E ⇔ (A is minimal ∧ A∈ Sub_{L}E) ⇒ E^{⋆}(^{L}A) = A
In particular, any minimal system is surjective.
 〈A〉_{L} = Min_{L∪A} E where A
is seen as a set of constants.
 A ∪ E^{⋆}(^{L}A) ⊂ 〈A〉_{L} =
A ∪ E^{⋆}(^{L}〈A〉_{L})
 E_{⋆}A ⊂ ^{L}A ⇒ Min_{L} A = A ∩ Min_{L} E
For the last property, we already know Min_{L} A ⊂ A ∩ Min_{L} E; for
the converse, using Min_{L} A ∈ Sub_{L} A,
E_{⋆}A ⊂ ^{L}A ⇒ Min_{L} A ∪
(E\A) ∈ Sub_{L} E ⇒ Min_{L} E ⊂ Min_{L} A ∪
(E\A) ⇒ A ∩ Min_{L} E ⊂ Min_{L} A.∎
CantorBernstein theorem
If there exist injections f: E ↪ F and
g: F ↪ E then there exists a bijection between E and F.
Proof. 〈∁_{E} Im g〉_{{g⚬f}} = A =
(∁_{E} Im g) ∪ g[f[A]] ⇒ ∁_{E}
A = g[∁_{F} f[A]] ⇒ (E ∋ x ↦
x∈A ? f(x) : g^{1}(x)) : E ↔ F ∎
3.4. Special morphisms
Let us introduce diverse qualifications for morphisms between
objects of diverse concrete categories.
Isomorphisms, endomorphisms, automorphisms.
Between objects E and F of a concrete category, an
isomorphism is a bijective morphism f
whose inverse is also a morphism : f ∈Mor(E,F) ∧
(f : E ↔ F) ∧ f^{ 1}∈Mor(F,E).
This will be later generalized to other (abstract) categories, where the following
other concepts are directly applicable.
Two objects E, F 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 is a class of objects which
is the isomorphism class of some object in it (independently of the choice).
An endomorphism of an object E, is an element of
Mor(E,E) = End(E). It is called nontrivial if it
differs from Id_{E}.
An automorphism of E is an isomorphism of E to itself:
Automorphism ⇔ (Endomorphism ∧ Isomorphism)
Embeddings
Let L a relational language, and two Lsystems E and F.
A relation symbol r interpreted as r_{E} in E and
r_{F} in F is called strongly preserved by a
function f ∈ F^{E}, if both r and ¬r are preserved :
∀x∈E^{nr},
x∈r_{E} ⇔ f⚬x∈r_{F}.
If f ∈ Mor_{L}(E,F) strongly preserves all structures
(E = ^{L}f_{⋆}(F)), it will be called a
preembedding. The construction of the order quotient of a preorder (2.9)
forms a general example of preembedding.
An embedding is an injective preembedding. Injectivity can be made a
consequence of the preembedding condition by adding = to the language (as injectivity
means strongly preserving =). Yet if this = symbol is not required to keep its standard
interpretation, but may be interpreted as any relation fitting the axioms of equality, then any
preembedding can still fit the condition, only playing a role of embedding relatively
to the use of this symbol in guise of equality, which reflects that it becomes a true
embedding after quotienting the systems by this equivalence relation (this quotient
reduces the interpretation of = to the standard one, and strongly preserves other structures).
For any subset A⊂F of a relational system F, we define its
structure by restriction : A = F ∩ ^{L}A. It is the only
structure on A such that, equivalently
 Id_{A} : A ↪ F is an embedding ;
 For any system E, Mor_{L}(E,A) =
{h∈Mor_{L}(E,F)  Im h ⊂ A}
Thus any f ∈ Mor_{L}(E,F) is the composite of
2 morphisms Id_{A}⚬f where A = Im f and
f ∈ Mor_{L}(E,A).
Then f is an embedding into F if and only if it is an isomorphism to
A. In particular, isomophisms are the bijective embeddings.
From Id_{A}∈Mor_{L}(A,F), we deduce
for all systems N,
Mor_{L}(A,N)
⊂ {g_{A}  g∈Mor_{L}(F,N)}
but generally without equality (details in 3.8).
Elementary embeddings
Preembeddings also strongly preserve structures defined with symbols in L
and logical symbols ∧,∨,0,1,¬, and also = in
the case of embeddings.
Thus, they also preserve invariant structures defined
using symbols of L and ∧,∨,0,1,¬,∃ but where all occurrences
of ∃ precede those of ¬.
Removing this restriction on the order of logical symbols, gives the full use
of firstorder logic. Then a morphism that (strongly) preserves all invariant structures,
is called an elementary embedding.
Isomorphism ⇒ Elementary embedding ⇒ Embedding ⇒ Injective morphism
An elementary subsystem of a system F is an A⊂F
such that Id_{A} : A ↪ F is an elementary
embedding, i.e. the value of any formula with parameters in A is
the same whether its quantifiers range all in F or all in A.
Elementary equivalence. Different systems are said to be elementarily equivalent,
if they have all the same properties.
The existence of an elementary embedding between systems implies that they
are elementarily equivalent.
Nonsurjective elementary embeddings, and more generally the diversity of
elementarily equivalent but nonisomorphic systems, play special roles in highlevel
studies of the foundations of mathematics, as we shall see with Skolem's paradox and
nonstandard
models of arithmetic. However they are ignored by the most usual practice of
mathematics, because of how farfetched (hard to find) they usually are.
Here is an aspect of such "difficulties" which is very easy to prove.
If an elementary embedding f : E ↪ E is invariant then it is surjective,
thus an automorphism :
Im f is also invariant (defined by
∃y∈E, f(y) = x)
∀x∈E,
x ∈ Im f ⇔ f(x) ∈ Im f
Im f = E. ∎
The Galois connection (End, Inv)
For any set E and any n∈ℕ, the preservation relation
(∀x∈R, f⚬x∈R) between f∈E^{E}
and R∈Rel_{E}^{(n)} gives
a Galois connection (End, Inv^{(n)}) between their
powersets, where Inv^{(n)}(M) is the set of nary relations
invariant by M ⊂ E^{E}. In particular,
Inv^{(1)} M = Sub_{M} :
∀M⊂E^{E}, ∀F⊂℘(E),
M ⊂ End_{F}E ⇔ (∀f∈M, ∀A∈F,
f[A] ⊂ A) ⇔ F ⊂ Sub_{M}E.
Gathering all arities forms the Galois connection (End, Inv) with Inv =
⊓_{n∈ℕ} Inv^{(n)} : ℘(E^{E}) →
∏_{n∈ℕ} ℘(Rel_{E}^{(n)}) ⥬
℘(Rel_{E}).
This concept of "invariance" is a priori distinct from the one previously introduced and used above (definability without parameters) ; yet both are related, and versions of these will be effectively linked by implications and even some equivalences, as will be seen later. This is basically because the concept of definability without parameters is a closure function, which to a given set of "primitive symbols" gives the set of all symbols generated by it through the definition process, and thus may be compared to other closure functions such as Inv ⚬ End.
Morphisms of algebras
For an algebraic language L, let
us qualify a morphism
f ∈ Mor_{L}(E,F) between Lsystems as full
if ∀x∈^{L}E, ∀y∈F,
(^{L}f(x),y) ∈ F ⇒ ∃z∈E,
f(z) = y ∧ (x,z)∈E.
Equivalently, ∀A⊂^{L}E, f[E^{⋆}(A)]
= F^{⋆}(^{L}f[A])
which implies ∀A⊂E, f[E^{⋆}(^{L}A)] =
F^{⋆}(^{L}(f[A])).
Any morphism from a serial system to a partial algebra is full. In particular, any morphism
between algebras is full.
Any injective full morphism is an embedding.
There is a more direct way to check that any injective morphism between algebras is an embedding : (φ_{F}⚬^{L}f = f⚬φ_{E}
∧ Inj f) ⇒ ∀(x,y)∈^{L}E×E,
f(y) = φ_{F}(^{L}f(x))
⇒ y = φ_{E}(x).
Similarly, one can directly check that any injective morphism from a serial system to a partial algebra, or
from a surjective system to an injective one, is an embedding.
Conversely, if f is a preembedding and (E is surjective, or some
s_{E} is injective for one of its arguments) then f is injective.
Bijective morphisms between algebras are isomorphisms. This can also
be deduced by
(^{L}f)^{1} =
^{L}(f^{ 1})
∴ φ_{E} ⚬ ^{L}f^{ 1} =
f^{ 1} ⚬ f ⚬ φ_{E} ⚬
^{L}f^{ 1} = f^{ 1} ⚬
φ_{F} ⚬ ^{L}f ⚬ ^{L}f^{ 1}
= f ^{1} ⚬ φ_{F}.
Images and preimages with algebraic languages
The direct image of a stable subset by a full morphism is stable:
∀A⊂E, E^{⋆}(^{L}A)
⊂ A ⇒ F^{⋆}(^{L}(f[A]))
⊂ f[A]
∀A∈ Sub_{L}E,
f[A] ∈ Sub_{L}F
In particular,
Images of algebras. For any two Lalgebras E,F, ∀f
∈Mor_{L}(E,F), Im f ∈ Sub_{L}F.
Proof : φ_{F}[^{L}Im f] = φ_{F}[Im
^{L}f] = Im (f⚬φ_{E}) ⊂ Im f ∎
Also, the image of a morphism from an algebra to a partial algebra is stable and an algebra.
Preimages of stable subsets.
∀f∈Mor_{L}(E,F),
∀B∈ Sub_{L}F, f_{⋆}(B) ∈
Sub_{L} E.
Proof. Let A=f_{⋆}B.
For Lalgebras,
∀(s,x)∈^{L}A, f⚬x
∈ B^{ns}∴
f(s_{E}(x))
= s_{F}(f⚬x) ∈B ∴
s_{E}(x)∈A.
For Lsystems, ∀(x,y)∈E,
(^{L}f(x),f(y))∈F∴
(x∈^{L}A ⇒ ^{L}f(x)∈^{L}B
⇒ f(y)∈B ⇒ y∈A).∎
Proposition.
For any Lsystems E, F,
∀f ∈Mor_{L}(E,F),

f [Min_{L}E] is minimal (thus f
[Min_{L}E] ⊂ Min_{L}F).

∀A⊂E, f[〈A〉_{L}] =
〈f[A]〉_{L,f[〈A〉L]} ⊂
〈f[A]〉_{L}
Proof of 1. M = Min_{L}E ⇒ ∀B ∈ Sub_{L}
f[M], f_{⋆}(B) ∈ Sub_{L} M
∴ f_{⋆}(B) = M ∴ B = f[M].
1. ⇒ 2. by adding A as a set of constants into L.∎
Thus when f is full (in particular when E, F are algebras)
we have equalities:
f [Min_{L}E] = Min_{L}F
∀A⊂E, f [〈A〉_{L}] =
〈f [A]〉_{L}.
3.5. Monoids
Transformations monoids
A transformation of a set E, is a function from E
to E. The full transformation monoid of E is the set E^{E}
of all transformations of E, seen as an algebra
with two operations: the constant Id, and the binary
operation ⚬ of composition.
A transformation monoid of E is a {Id,⚬}algebra M ∈
Sub_{{Id,⚬}}E^{E} of transformations of E :
 Id_{E} ∈ M
 ∀f,g∈M, g⚬f ∈ M.
The set End(E) of endomorphisms of any object E in a concrete category, is a
transformation monoid.
Any transformation monoid can be seen as a concrete category with only one object.
Monoids
A monoid is an algebra behaving like a transformation monoid, but without
specifying a set which its elements may transform. As both symbols Id and ⚬ lose
their natural interpretation, they are respectively renamed as e and •. So, the
concept of monoid is the theory
with only one type and
 Two operation symbols
 a constant symbol e of "identity"
 a binary operation • of "composition"
 Axioms
 Associativity : ∀x,y,z, x•(y•z)
= (x•y)•z so that either term can be
written x•y•z
 Identity axiom : ∀x, x•e = x
= e•x
Both
equalities in the identity axiom may be taken separately, forming two different concepts :
 A left identity of a binary
operation • is an element e such that ∀x,
e • x = x ;
 A right identity of • is an element e' such that ∀x,
x•e' = x.
If both a left identity e and a right identity e' exist then they are
equal : e = e•e' = e' which makes
it the identity of • (the unique identity element on either side).
The existence of a right identity thus implies the uniqueness of a left identity, but otherwise
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 axiom. This preserves
associativity; but any identity element from E loses its status of identity in E'.
Any {e,•}subalgebra of a monoid is a monoid, thus called a
submonoid.
Cancellativity
An element x is left cancellative for a binary operation • if the transformation
•⃗(x) (called left composition by x) is injective: ∀y,z, x•y = x•z ⇒ y = z.
Similarly x is right cancellative if •⃖(x) is injective:
∀y,z, y•x = z•x ⇒ y = z.
A cancellative operation is an operation where 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.
The existence of a left cancellative element implies the uniqueness of a right identity :
a•e' = a = a•e ⇒ e' = e.
Other concepts of submonoids and morphisms
Modifying the formalization of monoid by replacing the status of e as a constant
by ∃e in the identity axiom, would weaken the concepts of submonoids
and morphism (allowing more of them) as follows.
For any monoid (M,e,•), any set X with a binary operation
▪, and any morphism of composition f ∈ Mor((M,•),(X,▪)),
 its image is a monoid (A,a,▪) where A = Im f
and a = f(e)
 f is a morphism of monoid from M
to this monoid A.
If the target forms a monoid (X,e',▪)
then (by uniqueness of the identity in A)
f ∈ Mor_{{e}}(M,X) ⇔
a = e' ⇔
e' ∈ A ⇔ A ∈ Sub_{{e, ▪}} X
but these equivalent formulas may still be false, unless a is cancellative on one side
(a▪a = a = a▪e' ⇒ a = e').
Antimorphisms. The opposite of a monoid is the monoid
with the same base set but where composition is replaced by its transpose. An
antimorphism from (M,e,•) to (X,e',▪) is a morphism
f from one
monoid to the opposite of the other (or equivalently viceversa):
f(e) = e'
∀a,b∈M, f(a•b) =
f(b)▪f(a)
Commutants and centralizers
The commutant of any subset A⊂E for a binary operation • in E,
is defined as
C(A) = {x∈E∀y∈A,
x•y = y•x}.
This forms a Galois connection : ∀A,B⊂E,
B⊂C(A) ⇔ A⊂C(B).
Such A,B are said to commute, as each element of A
commutes with each element of B.
If • is associative then ∀A⊂E, C(A)
∈ Sub_{{•}}F.
Proof: ∀x,y∈C(A),
(∀z∈A, x•y•z = x•z•y =
z•x•y) ∴ x•y∈C(A).
Commutants in monoids are called centralizers. They are more precisely submonoids as
obviously e∈C(A).
This can be understood as an intersection of submonoids in the case of a transformation
monoid M⊂X^{X} : ∀A⊂M,
C_{M}(A) = M ∩ End_{A} X
(Compared to the (End, Inv^{(2)}) connection, this one comes by
restricting the preservation relation to the set of graphs of functions in M).
A binary operation • in a set E, is called
commutative when • = ^{t}•,
i.e. C(E) = E.
If A⊂C(A) and 〈A〉_{{•}} = E then • is commutative.
Proof: A⊂C(A)∈ Sub_{{•}}F
⇒ E = C(A)
⇒ A⊂C(E) ∈ Sub_{{•}}F ⇒
C(E) = E.∎
In the case of monoids the conditions
A ⊂ C(A) and 〈A〉_{{e,•}} = E suffice.
Categories
The concept of monoid came as an abstraction of transformation
monoids (= concrete categories with a single object). Now, the concept of category
(or abstract category) does the same with pluralities of objects : it differs from the
concept of concrete category, by forgetting that objects are sets and that morphisms
are functions. So, a category C is made of:
 the class of its "objects" ; the category is small if this class is a set;
 to any objects E,F is given a set Mor(E,F) of
«morphisms from E to F»; these are usually regarded as pairwise disjoint;
 to any object E is given a constant symbol 1_{E} ∈ Mor(E,E);
 to any triple of objects E,F,G is given a "composition" operation
(abusively all denoted by the same symbol)
∘ :
Mor(F,G)×Mor(E,F) → Mor(E,G)
satisfying both axioms of identity and associativity, where quantifiers ∀_{C}
mean to range in the class of objects :
 ∀_{C} E,F, ∀x∈Mor(E,F),
x∘1_{E} = x = 1_{F}∘x
 ∀_{C} E,F,G,H, ∀x∈Mor(E,F),
∀y∈Mor(F,G),∀z∈Mor(G,H),
(z∘y)∘x = z∘(y∘x) ∈ Mor(E,H)
For display convenience, composition may also be written transposed, by the semicolon notation from
computer science : ; = ^{t}∘ :
Mor(E,F)×Mor(F,G) → Mor(E,G)
x;y = y∘x
The set End(E) = Mor(E,E) of endomorphisms of any object E,
can be seen as a monoid in both opposite ways, by restriction of either ∘ or ;.
The concept of opposite category is defined similarly to opposite monoids,
as rereading the category with sides reversed, the Mor(E,F) of the one serving as
the Mor(F,E) of the other. For any concept relative to a given category, its
dual will mean the similar concept following the same definition with sides reversed, which
amounts to applying this concept to the opposite category; it will usually be called by appending
the prefix co to the concept's name.
3.6. Actions of monoids and categories
Actions of monoids
Since monoids lost their role as sets of transformations, such a role can be given back to
them as follows.
An action (or left action) of a monoid (M,e, •) on a
set X, is an operation ⋅ : M×X → X such that
⋅⃗ ∈ Mor_{{e,•}}(M, X^{X}) :
 ∀x∈X, e⋅x = x
 ∀a,b∈M, ∀x∈X,
(a•b)⋅x = a⋅(b⋅x)
Examples:
 Any monoid naturally acts on itself by its composition operation.
 Any transformation monoid (or other acting monoid) M on a set E, also
acts by restriction on any Mstable subset A⊂E (preserved
unary predicate in the concrete category M with object E).

In particular, the monoid of endomorphisms of any typed system E =
∐_{i∈I} E_{i},
acts on every type E_{i} it contains.
Acts as algebraic structures
For any sets M, X with Malgebra structures • : M×M → M
and ⋅ : M×X → X (seeing M as a set of function symbols),
∀x∈X, ⋅⃖_{x}(e) =
x ⇔ e⋅x = x
⋅⃖_{x} ∈ Mor_{M}(M,X) ⇔
∀a,b∈M, (a•b)⋅x = a⋅(b⋅x)
•⃖_{e} = Id_{M} ⇔ (∀a∈M,
a•e = a) ⇒ ∀g∈ Mor_{M}(M,X),
⋅⃖_{g(e)} = g
where the last ⇒ comes by ∀a∈M, a⋅g(e) =
g(a•e) = g(a). So in the following equivalence
∀x∈X, ∀g∈X^{M},
g = ⋅⃖_{x} ⇔
(g ∈ Mor_{M}(M,X) ∧ g(e) = x)
⇒ expresses the axioms of action of M on X ;
an Malgebra X satisfying these is called an Mset.
⇐ is implied by the last monoid axiom (•⃖_{e} =
Id_{M}); conversely, the variant of ⇐ replacing (X, ⋅) by
(M, •) implies this axiom : (Id_{M}
∈ Mor_{M}(M,M) ∧ Id_{M}(e)
= e) ∴ •⃖_{e} = Id_{M}
Effectiveness and free elements
An action of M on X is said effective if ⋅⃗ : M
↪ X^{X} :
∀a,b∈M, (∀x∈X,
a·x = b·x) ⇒ a = b
An effective action is a way of seeing a monoid as a transformation monoid (Im ⋅⃗
∈ Sub_{{Id,⚬}}X^{X}), by using this action in guise of function evaluator.
Indeed, the effectiveness condition is similar to the axiom (=_{Fnc}),
making unique the function with given domain E fitting any
definition of the form (∀x∈E, f(x) =...)
This way, the axioms of action amount to defining e and • as playing with
this action, the same roles as those of Id and ⚬ with the function evaluator.
An element x∈X of an Mset (X, ·), is free
if ⋅⃖_{x} : M ↪ X.
The existence of a free element implies the effectiveness of the action :
(∃x∈X,
∀a≠b∈M, a·x ≠ b·x)
⇒ (∀a≠b∈M, ∃x∈X,
a·x ≠ b·x)
Inj(π_{x} ⚬ ⋅⃗ ) ⇒ Inj ⋅⃗
For the natural action of a monoid on itself, the identity element is free. Thus, this action is effective.
Trajectories
The trajectory of an element x∈E by a monoid
M acting on E, can be defined in 2 equivalent ways:
〈{x}〉_{M} = {a⋅x  a∈M} =
Im ⋅⃖_{x} ⊂ E
Indeed, 〈{x}〉_{M} ⊂ Im ⋅⃖_{x} because
x = ⋅⃖_{x}(e) ∈ Im ⋅⃖_{x} ∈
Sub_{M} E.
The converse is obvious.
Right actions
A right action, also called coaction, of a monoid M on a set X,
is like an action with sides switched: it is an operation
⋅ : X × M → X
such that
 ∀x∈X, x⋅e = x
 ∀a,b∈M, ∀x∈X,
(x⋅a)⋅b = x ⋅(a•b)
It amounts to an action of the opposite monoid, and defines an antimorphism
from M to X^{X}.
The commutation of 2 submonoids of X^{X} looks like an
associativity formula when written as acting by opposite sides on X:
a∈M acting on X commutes with b∈N
coacting on X when
∀x∈X,
(a⋅x)⋅b = a⋅(x⋅b)
Actions of categories
Generalizing from the above case of monoids, an action α of a category C gives
for each object X of C a set X^{α}, and for each morphism
f ∈ Mor(X,Y) a function f^{α} :
X^{α} → Y^{α}, preserving identities and compositions:
∀_{C}X, (1_{X})^{α}
= Id_{Xα}
∀_{C}X,Y,Z, ∀f∈ Mor(X,Y),
∀g∈ Mor(Y,Z), (g∘f)^{α} =
g^{α}⚬f^{α}
The category C with the action α will be called an acting category
and denoted C^{α}.
An acting category C^{α}
is effective if ∀_{C}X,Y,
Inj(Mor(X,Y)∋ f ↦ f^{α}).
An effective acting category is synonymous with a concrete category.
Even if not effective, an acting category C^{α} defines a concrete
category C^{α} with objects the sets X^{α}, and
with sets of morphisms
Mor(X^{α}, Y^{α}) =
{f^{α}  f∈Mor(X,Y)}
Dually, a coaction β of a category C (forming a coacting category
C_{β}) gives for each object X of C a set
X_{β}, and for each morphism
f ∈ Mor(X,Y) a function f_{β} :
Y_{β} → X_{β}, preserving identities, and
antipreserving compositions: ∀_{C}X,
(1_{X})_{β} = Id_{Xβ}
∀_{C}X,Y,Z, ∀f∈ Mor(X,Y),
∀g∈ Mor(Y,Z), (g∘f)_{β} =
f_{β}⚬g_{β}
In the literature, coactions of categories are called presheafs.
Actions and coactions of a category may be seen as typed metaalgebras with
types given by its objects, and function symbols given by its morphisms.
Some constructions of actions
Given an action α of C, a subaction of α is an action β of C defined by restriction
of α to a preserved unary predicate:
∀_{C}X, X^{β} ⊂ X^{α}
∀_{C}X,Y, ∀f∈ Mor(X,Y),
f^{α}[X^{β}] ⊂ Y^{β} ∧
f^{β} = f^{α}_{Xβ}.
Generalizing the natural actions of monoids on themselves, every choice of an object
M defines an action C^{(M)} of C called action from
M, where ∀_{C}X, X^{(M)} =
Mor(M,X)
∀f∈Mor(X,Y), f^{(M)} =
Hom(M, f)
= ∘⃗(f)_{Mor(M,X)} :
X^{(M)} → Y^{(M)}
and a coacting category C_{(M)} of coaction to M where
∀_{C}X, X_{(M)} =
Mor(X,M)
∀f∈Mor(X,Y), f_{(M)}
= Hom(f,M) = ∘⃖(f)_{Mor(Y,M)} :
Y_{(M)} → X_{(M)}
If C is a concrete category then C^{(M)} is a subaction
of C^{M} (which to each X gives X^{M}),
and C_{(M)} is a subcoaction of C_{M}
(which to each X gives M^{X}).
The axioms for monoids M and Msets X can be read as contained
in the axioms of categories. Namely, pick an object K of a category C,
and let M = End(K). Then any object E defines an Mset
X = K^{(E)} = E_{(K)}.
As actions by composition on opposite sides commute by associativity, morphisms
in the coacting category C_{(K)} preserve this Mstructure :
∀f ∈Mor(E,F), f_{(K)} ∈
Mor_{M}(F_{(K)}, E_{(K)})
∀x∈X=Mor(E,K), x_{(K)} =
⋅⃖_{x} ∈ Mor_{M}(K_{(K)},
E_{(K)}).
Trajectories of tuples in concrete categories
For any concrete category C and any number n∈ℕ, trajectories of the
action C^{n} of C are preserved
relations : for any fixed ntuple t of elements of an object
K, the trajectory s of t by C, interpreted as
∀_{C}E, s_{E} = {f⚬t 
f ∈ Mor(K,E)}, is preserved.
Proof : ∀g∈Mor(E,F), ∀x∈s_{E},
∃f∈Mor(K,E), (x = f⚬t ∧
g⚬f ∈ Mor(K,F)) ∴
g⚬x = g⚬f⚬t ∈ s_{F}.∎
With an inclusion between objects E ⊂ F, the so defined
s_{E} may differ from the restriction of s_{F} to E,
but we shall usually not face this kind of issue.
3.7. Invertibility and groups
Permutation groups
A permutation of a set E is a bijective transformation of E.
The set 𝔖_{E} = {f∈E^{E} f : E↔E}
of all permutations of E, is a transformation monoid of E called the
symmetric group of E.
A permutation group of a set E,
is a {Id,⚬, ^{1}}subalgebra of 𝔖_{E}.
In a permutation group, trajectories are usually called orbits.
The binary relation on a set E defined by trajectories by any transformation
monoid (or acting monoid) M, ∐_{x∈E}
〈{x}〉_{M}
is a preorder
on E (as seen in example in 2.9).
If M is a group then this preorder is an equivalence relation,
whose partition of E is the set of orbits. While the concepts of full transformation monoid and symmetric group depend on the
powerset, those of transformation monoid
and permutation group do not use it, being expressed as firstorder theories.
Inverses
In a monoid (M,e,•), the formula x•y = e is read
"x is a left inverse of y", or "y is a right inverse of x"; this
x is right invertible (it has a right inverse), and y is left
invertible.
An element x is called invertible if it is so both sides. Then its left and right
inverses are equal, thus unique, called the inverse of x and written x^{1}:
y•x = e = x•z ⇒ y
= y•x•z = z
If x commutes with an invertible element y then it also commutes
with its inverse z:
x•y = y•x ⇔ x = y•x•z
⇔ z•x = x•z
An element x of a monoid is called involutive
if it is its own inverse: x•x = e.
Transpositions
Here are the simplest permutations beyond the identity of each set.
A transposition of a set E is a permutation of E that swaps two elements
and leaves all others fixed : ∀x,y∈E,
(x y)_{E} = (E ∋ z ↦ (z = x ? y :
(z = y ? x : z))) = (y x)_{E} ∈ 𝔖_{E}
thus (x x)_{E} = Id_{E} which is not called a transposition.
Any transposition is involutive (this may give the simplest formal proof that it is a permutation).
Groups
The concept of group is the theory obtained by adding to that of monoid, equivalently
 The axiom that all elements are invertible, or
 The function symbol ^{1} of inversion, with the axiom
∀x, x•x^{1} = x^{1}•x = e
Indeed this latter axiom determines the interpretation of ^{1} from
• and e.
If a transformation monoid is a group then it is a permutation group (as any inverse of a
transformation in the sense of monoids is also its inverse as a function).
A subgroup of a group is a {e, •,^{1}}subalgebra, or equivalently a
submonoid which is a group (while submonoids of group are not all groups, for
example ℕ in ℤ).
The core of a monoid M, is its set of invertible elements; it is a submonoid of M
and a group:  e is its own inverse.
 If x, y have inverses
x^{1}, y^{1},
then x•y has inverse y^{1}•x^{1}.
 Any inverse x^{1} is invertible, with
(x^{1})^{1} = x (inversion is an
involutive transformation of any group).
Its subgroups are all the submonoids
of M which are groups, which may then be called the subgroups of M.
Between groups, a group morphism is equivalently an
{e,•,^{1}}morphism, or an {e,•}morphism, as the latter also
preserve inversion. More generally any {e,•}morphism
from a group to a monoid preserves the inversion relation
{(x,y)  x•y = e = y•x},
thus its image is a group.
In a group, the subgroup generated by a subset A coincides with the
submonoid generated by A∪A where A =
{x^{1}x∈A}. (It is stable by
inversion because its definition is unchanged by inversion, which is involutive)
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
An element x of an Mset X will be called regular if it is both
free and generating. This means that the Mmorphism ⋅⃖_{x}
is both injective and surjective, thus an Misomorphism from M
to X. The identity element of M is regular for the natural
action of M on itself.
Let us qualify an action after this: an Mset will be called monogenic if it is
a trajectory (it is generated by a singleton), and regular if it has a regular element.
If an Mset is both monogenic and generated by the set of its free elements,
then it is regular (there is a free element that generates it).
Proof: as a generator is in the set generated by that of free elements, it
must be in the trajectory of one of them, which is thus also generating.∎
(A monogenic action of a monoid may have free elements without being generated by them ;
but if a monogenic action of a group has a free element then all its elements are free).
The trajectory Y of any element x of an Mset X is Mstable,
and thus an Mset. It is generated by x, and stays so when replacing the language
M by its image as a transformation monoid N ⊂ Y^{Y}.
Now if N is commutative (which is the case if M is commutative) then x
is free for the action of N (thus Y is a regular Nset).
The proof is easy and left as an exercise.
An action of a group G on a set X, is equivalently
an action of monoid, or a group morphism from G to 𝔖_{X}.
As inversion is an antimorphism,
it switches any action ⋅ of G on X into a coaction ▪ by
∀x∈X, ∀g∈G, x▪g = g^{1}⋅x.
If an action of group is monogenic then every element is generating; if it is regular then every
element is regular.
The Galois connection (Aut, sInv)
For any set E, the relation of strong
preservation between its set Rel_{E} 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) ⊂ Rel_{E}
∀L⊂Rel_{E}, ∀P⊂ 𝔖_{E}, L ⊂ sInv
P ⇔ P ⊂ Aut_{L} E.
For any permutation group G, sInv G = Inv G.
Definability without parameters implies invariance by automorphisms, as will be explained in 4.10.
Isomorphisms
An isomorphism between objects E and F in any category, is an invertible
morphism :
Iso(E,F) = {f∈Mor(E,F)  ∃g∈Mor(F,E),
g∘f = 1_{E} ∧ f∘g = 1_{F})}
This g is unique, called the inverse of
f and written f^{ 1}.
A groupoid is a category where all morphisms are invertible.
Groups are the groupoids with only one object, and the monoid of endomorphisms of any object
of a groupoid is a group.
Generalizing from monoids, the core of a category is the groupoid with
the same objects and only accepting isomorphisms as morphisms.
An automorphism of an object E, is an isomorphism from E to itself.
Their set Aut(E), core of End(E), is a group called the automorphism group of E.
3.8. Properties in categories
Monomorphisms, Epimorphisms
The concepts of cancellativity are generalized to any category C as follows.
A morphism f∈Mor(E,F) is called monic, or a
monomorphism, if all f^{(X)} are injective:
∀_{C}X, ∀g,h∈Mor(X,E),
f∘g = f∘h ⇒ g = h.
In the category of sets, monomorphisms
are the injections.
Dually, a morphism f∈Mor(E,F) is called epic, or an epimorphism,
if all f_{(X)} are injective :
∀_{C}X, ∀g,h∈Mor(F,X),
g∘f = h∘f ⇒ g = h
∀_{C}X, f_{(X)} :
F_{(X)} ↪ E_{(X)}
f_{(C)} : C^{(F)} ↪ C^{(E)}.
As actions by composition on opposite sides commute, an epimorphism f defines a
metaembedding between acting categories C^{(F)} and
C^{(E)}, seen as Ctyped Moralgebras. In particular, f is a free
element of the End(F)set F^{(E)}.
In the category of sets, epimorphisms are the surjections.
Sections, retractions
The concepts of invertibility are generalized to any category C as follows.
For any f∈Mor(E,F) and g∈Mor(F,E), the condition
f;g = 1_{E} is read: "f is a section of g", or
"g is a retraction of f".
Then a g∈Mor(F,E) is called a retraction (or retraction on E
if the category is concrete), if, equivalently
 ∃f∈Mor(E,F), f;g = 1_{E}
 For any action α of C, g^{α} is surjective
(Im g^{α} = E^{α}).
 g^{(E)} is surjective, i.e.
Im g^{(E)} = End(E).
Proof.
1. ⇒ 2. : ∀x∈E^{α},
x = g^{α}(f^{α}(x)), i.e. right
invertible functions are surjective.
2. ⇒ 3. obvious;
3. ⇒ 1. as 1_{E} ∈ Im g^{(E)}.∎
Dually, f∈Mor(E,F) is a section
(or section in F if the category is concrete), if, equivalently,
 ∃g∈Mor(F,E), f;g = 1_{E}.
 For any coaction β of C, f_{β} is surjective
(Im f_{β} = E_{β}).
 f_{(E)} is surjective, i.e.
Im f_{(E)} = End(E).
Since left invertible functions are injective,
 All actions of sections are injective; thus, all sections are monic;

All coactions of retractions are injective; thus, all retractions are epic.
Gathering the results, the qualities of morphisms in concrete categories are ordered as
Section ⇒ Injective morphism
⇒ Monomorphism
Retraction ⇒ Surjective morphism ⇒ Epimorphism
Modules
For any b∈Mor(X,Y), an object M will be called a bmodule
if b_{(M)} : Y_{(M)} ↔ X_{(M)}.
If b is an isomorphism then all objects are bmodules, i.e. b is an epic section, and
∀_{C}X, (b_{(M)}^{1}
= b^{1}_{(M)}) ∧ (b^{(M) 1} =
b^{1 (M)}).
Conversely, if b is a section and b_{(Y)} is injective then
b is an isomorphism.
Proof : ∃g∈Mor(Y,X), b;g = 1_{X} ∴
b;g;b = 1_{X};b = b;1_{Y}
∴ g;b = 1_{Y}.∎
Thus :
 If both X,Y are bmodules then all other objects are also bmodules ;
 Epic section ⇔ Isomorphism ⇔ Monic retraction ;
 If an element of a monoid is both left invertible and right cancellative, then it is invertible.
To say Y is a bmodule, is another way of saying b is a regular element of the
End(Y)set X_{(Y)}.
Yet b_{(Y)} being an End(Y)isomorphism from
Y_{(Y)} to X_{(Y)}, does not ensure its inverse
to come as g_{(Y)} for some g∈Mor(Y,X), such as
an inverse of b if it was an isomorphism in C.
Examples of modules
The concept of bmodule will be more often used when b is epic, thus distinguishing
the M such that the injection b_{(M)} is also surjective
(while not all objects are bmodules, i.e. b is not a section, i.e. X is
not a bmodule). In particular, for any algebraic language L, if
〈Im b〉_{L} = Y then b is epic in any
category included in that of partial Lalgebras.
An important kind of examples is when b is bijective (and thus epic), in the category
of relational systems for a given language L. To simplify, let b be the identity
Id_{X} into Y with larger structure Y = X
∪ Z.
For example, given a binary symbol r∈L, the properties of reflexivity, symmetry and
transitivity of the interpretation of r in a system M, are respectively expressible
as M being a Remodule, a Symodule and a Trmodule, where the morphisms Re, Sy and Tr are
respectively defined by
 (Re) : X = {0}, X = ∅, Z = {(r,(0,0))}
 (Sy) : X = {0,1}, X = {(r,(0,1))}, Z = {(r,(1,0))}
 (Tr) : X = {0,1,2}, X = {(r,(0,1)), (r,(1,2))}, Z = {(r,(0,2))}
Similarly, antisymmetry is expressible as being a module by a noninjective morphism.
So formalized, this general case of a bijective b can be thought of as giving
Z the role of a set of Ltyped Xary algebraic symbols, which for
every set M gives to ^{L}M the Zstructure
{((s,^{L}u_{X}),^{L}u(s))
 (s,u) ∈ Z×M^{X}},
so that
(M, M) is a bmodule
⇔ M ∈ Sub_{Z} ^{L}M.
More examples will be given in 3.11.
Subobjects
With our initial concept of concrete
category allowing for inclusion between objects, we need to write
Hom_{Y}(f, X) as f may not suffice to determine Y.
From there, more concepts also need this parameter:
 The antipreservation of ⚬ by C_{(X)}
is written Hom_{F}(f, X) ⚬ Hom_{G}(g,
X) = Hom_{G}(g∘f, X).
 f∈Mor(E,F) is Fepic, or an Fepimorphism,
if all Hom_{F}(f,X) are injective.
In any concrete category, any injective morphism is monic, and any morphism with
image F is Fepic. The converses may hold or not
depending the considered concrete category.
Let us analyze the concept of an object S being included in an object E of a
concrete category, to reexpress it as a separate object X with an isomorphism to S
(by which references to target sets of morphisms could be omitted). This concept has 2 variants.
The "weak" version is the concept of subobject
(by the standard terminology), applicable to any abstract category. It amounts to only requiring
the inclusion morphism of the subobject S in E (usually Id_{S} :
S ↪ E in concrete categories) to be monic, and not even necessarily
injective.
Namely, a subobject of E is formalized by a presentation in the form
(X,u) where u ∈ Mor(X,E) is monic (indirect description of
Im u seen as isomorphic to X, thus defining the morphisms to and from Im
u as copied from those X, but this direct meaning is lost in abstract categories).
The class of presentations (X,u) of subobjects of an object E, is
metapreordered by
(X, u) ⊆ (Y, v) ⇔ ∃ϕ∈Mor(X,Y),
u = v∘ϕ
while (!ϕ∈Mor(X,Y), u = v∘ϕ) because v is monic.
Then, ϕ is also monic because u is :
∀g,h∈Mor(Z,X),
ϕ∘g = ϕ∘h ⇒ u∘g = v∘ϕ∘g = v∘ϕ∘h = u∘h
⇒ g = h.
Such (X, u) and (Y, v) are said to present the same subobject
if they are equivalent for this
metapreorder : (X, u) ≡ (Y, v) ⇔ ((X, u) ⊆
(Y, v) ∧ (Y, v) ⊆ (X, u)) ⇔ (∃ϕ∈Iso(X,Y)  u = v∘ϕ).
Between subobjects of a given object, the order ⊆/≡ is called inclusion.
The "strong" version requires u to be an embedding. This concept of embedding,
first introduced for relational systems in 3.4, will be generalized to any concrete category in 3.9
(while expressible classes of monomorphisms in abstract categories which may play a similar role are
not equivalent).
Representation theorem
Theorem. Any small category is isomorphic to one made of a family of typed algebras
with all morphisms between them.
Its precise construction forms the small category version of Yoneda’s
embedding
(which expresses it at the meta level: any category is isomorphic to a category of typed metaalgebras).
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.
 As a set T of types, we can take a copy of the set of objects, but one type per isomorphism class suffices.
 Each object E is interpreted as a typed set ∐_{t∈T}
E^{(t)}.
 L = ∐_{t,t'∈T} Mor(t',t) seeing
Mor(t',t) as a set of functions symbols from
t to t', coacting on each E.
Each u ∈ Mor(E,F) acts as ψ(u) = ∐_{t∈T}
j_{t} ⚬ u^{(t)} :
∐_{t∈T} E^{(t)} →
∐_{t∈T}F^{(t)}.
Let us prove that ψ : Mor(E,F) ↔ Mor_{L}(E,F).
Im ψ ⊂ Mor_{L}(E,F) by associativity
(ψ commutes with the action of L).
The existence of an isomorphism k ∈ E^{(t)} ensures that
ψ is injective (as k is epic) and
Mor_{L}(E,F) ⊂ Im ψ:
∀g∈Mor_{L}(E,F),
(∀x∈E, g(x) = g(k∘k^{1}∘x) =
g(k)∘k^{1}∘x)
∴ g = ψ(g(k)∘k^{1}).∎
In particular,
 any monoid is isomorphic to the monoid of endomorphisms
of an algebra on a language of function
symbols;
 any group is isomorphic to an automorphism group of such an algebra.
Yet,
not all categories can be concrete.
Notice the symmetry of roles (called duality)
between sides, which not only switches the orientation of morphisms between two objects, but
also lets a category be somehow reworded as a special kind of mathematical theory
(so viewing category theory as a weak version of onetheory theory,
despite contextual differences):
 "Objects" in categories become "types",
 "Morphisms" become "invariant functions", implicitly generated by a language of function symbols only.
The weakness of that kind of "theory" is balanced by the development of concepts
at a meta level above it.
This symmetry leads to diverse insights:
 An epimorphism b ∈ Mor(X,Y) gives to Y a role of
subtype of X, so
that a bmodule is an object whose component of type X is filled by Y.
 To link both concepts of invariance : for any monoid M
(resp. small category) generated by
a set thought of as a language of (typed) function symbols (so M is made of
functions expressible as terms in this language), there exists a (set I of) algebraic
interpretation(s), i.e. actions, where M coincides with the category M' of all functions
(resp. interpreted function symbols) which are invariant by all endomorphisms
(resp. by all morphisms between interpretations in I). Anyway in any interpretation,
the concrete image of M is included in the corresponding M', because the
set M' of invariant functions by any given set of functions is (Id, ⚬)stable
(this can be dually rephrased by qualifying M' as the set of morphisms there).
A reference of book chapter by George M. Bergman presenting such concepts of
category theory in more traditional terms: an old version; the
new version is chapter 8 of his
book.
3.9. Initial and final objects
In any category, an object X is called an initial object if all
Mor(X,Y) are singletons. While isomorphic objects have all the same
properties, here is a small converse : any 2 initial objects are isomorphic, by a unique
isomorphism (so, initial objects form either a single isomorphism class, or none):
For any initial objects X, Y, ∃f∈Mor(X,Y),
∃g∈Mor(Y,X), {g∘f, 1_{X}} ⊂ Mor(X,X)
∴ g∘f = 1_{X}.
Similarly, f∘g = 1_{Y}.
Thus f is an isomorphism, unique as ∃!:Mor(X,Y). ∎
By this unique isomorphism, X and Y may be treated as identical to
each other. Initial objects are said to be essentially unique.
Dually, an object X is called a final object if all Mor(Y,X) are
singletons.
For example, in any category of relational systems with a given language
where every isomorphism class of possible systems has representatives :
 The empty set where Boolean constants are false is the initial system ;
 Final systems (with a single type) are the singletons where all relations are constantly true;
 Final multitype systems are made of one singleton per type.
Exercise. Given two fixed sets A and B, consider the category where
 Objects are all (X,ϕ) where X is a set and ϕ: X×A→B ;
 Mor((X,ϕ),(Y,ϕ') = {f∈Y^{X} 
∀x∈X,∀a∈A, ϕ(x,a) = ϕ'(f(x),a)}.
Does it have an initial object ? a final object ?
Eggs
(This is called universal element
in the literature; I use the name "egg" to fit with that of clone.)
Generalizing the concept of regular
element, let us call egg of an acting category C^{α}, any
(M,e) where M is an object and e ∈ M^{α}, such that
∀_{C}E, (Mor(M,E) ∋ f ↦
f^{α}(e)) : E^{(M)} ↔ E^{α}.
Equivalently, it is an initial object of the category of elements of C^{α} where
 Objects are all data (E,x) of
an object E of C and x ∈ E^{α}
 Mor((E,x),(F,y)) =
{f∈Mor(E,F)  f^{α}(x) = y}
Dually, a coegg of a coacting category C_{β} is an egg of the
opposite acting category, i.e. a final object of its category of coelements (E,x)
where x ∈ E_{β} and Mor((E,x),(F,y)) =
{f∈Mor(E,F)  f_{β}(y) = x}.
Again, an action (resp.coaction) will be called regular if it has an egg (resp. a coegg); it
is called representable elsewhere
in the literature.
If (M,e) is an egg of C^{α} then (M^{α},e)
is an egg of C^{α}.
For any object M of C, (M, 1_{M}) is an egg of
C^{(M)} and a coegg of C_{(M)}.
In the literature (wikipedia), a category
of elements of some C^{(M)} is called an undercategory and denoted
M/C, while a category of coelements of some C_{(M)}
is called an overcategory and denoted C/M.
Yoneda's lemma
can be expressed in our terminology as follows : if (M,x) is a (co)egg of a
(co)action α of a category C, then (α,x) is an egg of the action on M
of the metacategory of all (co)actions of C.
Precisely, for any object M, any action β of C and any
x∈M^{β}, the unique metamorphism ϕ from
C^{(M)} to C^{β} such that
ϕ_{M}(1_{M}) = x is defined by
∀_{C}E,
∀y∈E^{(M)},
ϕ_{E}(y) = y^{β}(x)
Proof of (metamorphism ⇒ defining formula): ϕ_{E}(y) =
ϕ_{E}(y∘1_{M})
= y^{β}(ϕ_{M}(1_{M}))
= y^{β}(x).
The proof of the converse is as easy and left to the reader.
When (M,x) is an egg, this gives a metaisomorphism
(like any bijective morphism between algebras is an isomorphism). ∎
Obviously, the image of ϕ is the trajectory of x in C^{β}.
Exercise. Consider the category of sets and their functions
acting by direct images on the powersets of its objects (Set^{⋆}). Does it have an egg ?
Similarly, consider its coaction on these powersets by preimages (Set_{⋆}). Does it have a coegg ?
Hint : use the numbers of elements of involved finite sets.
Subobjects as subcoactions
Any f∈Mor(E,F) defines by composition a metamorphism
f^{(C)} from C_{(E)} to
C_{(F)}, which is injective precisely when f is monic.
Any presentation (E,f) of a subobject of F is also a coegg of the
subcoaction Im f^{(C)} of C_{(F)}.
Inversely, any subcoaction of C_{(F)} with a coegg
(E,f) is the trajectory of (E,f) and metaisomorphic to
C_{(E)} by f^{(C)}, and f is monic
from E to F.
So, the notion of subobject of F can be redefined as that of a regular
subcoaction of C_{(F)}, whose coeggs are its presentations.
So conceived, it becomes strictly independent of a choice of presentation (but
ontologically more expensive).
Diverse operations usually involving subsets, such as direct images and preimages by
morphisms, can be extended to subobjects, by literally applying them to subcoactions,
then presenting the resulting subcoaction as a subobject if it is regular. This regularity
condition often holds depending on the category, and can be verified in diverse kinds of
categories, especially categories of systems, by explicitly describing the result as a subsystem.
Things especially works like this for the operation of preimage.
Strictly applying this method, the direct image of a subobject of E with
presentation (X,u) by an f∈Mor(E,F), would be
given by the trajectory Im f∘u^{(C)} of
(X,f∘u) in C_{(F)},
and thus presented by f∘u if it is monic. In particular, this holds when
f is itself monic.
However, many categories of systems have a construction of direct images of subsystems
which remains naturally applicable even when that image trajectory fails to be regular (a simple
example can be found in the category of relational systems with 2 unary relation symbols).
Such a direct image can still be characterized in terms of pure categories, as the subobject
generated by f∘u, i.e. the smallest regular subcoaction which contains it.
Embeddings in concrete categories
While the concepts of embedding
and preembedding were introduced for
categories of relational systems, let us generalize them to any concrete category C.
A morphism f ∈ Mor(E,F) will be called a preembedding
if ∀_{C}X, Mor(X,E) =
{g∈E^{X}  f⚬g ∈ Mor(X,F)}
This formula actually implies f∈Mor(E,F).
In other words, while f∈Mor(E,F) makes (E, Id_{E})
an element of the coaction giving to
each X the set {g∈E^{X}  f⚬g ∈ Mor(X,F)} (subcoaction of C_{E}),
f is a preembedding when (E, Id_{E}) is a generator and thus
also a coegg of this coaction.
Then, an embedding is an injective preembedding, i.e. an
f : E ↪ F such that, equivalently
∀_{C}X, Mor(X,E) =
{f^{ 1}⚬h  h ∈ Mor(X,F) ∧
Im h ⊂ Im f}
∀_{C}X,
{h ∈ Mor(X,F) 
Im h ⊂ Im f} = {f⚬g  g∈Mor(X,E)}
Let us introduce a related concept.
Any fixed subset A ⊂ F defines a subcoaction
C_{(A)} of C_{(F)} by
∀_{C}X, X_{(A)} =
{g∈X_{(F)}  Im g ⊂ A}
Now let us call quasiembedding any f∈Mor(E,F) such that
(E,f) is a coegg of some C_{(A)} and thus also of C_{(Im f)} :
∀_{C}X, ∀g∈Mor(X,F), Im g ⊂ Im f ⇒
∃!ϕ∈Mor(X,E), f ⚬ ϕ = g
(Inj f implies one side of this condition: ∀g∈Mor(X,F),
!ϕ∈Mor(X,E), f ⚬ ϕ = g)
In most
useful concrete categories, all quasiembeddings will be
embeddings ; exceptions are easy to build in other categories designed for this purpose.
Dependencies between some properties of morphisms
The diverse properties of a morphism f∈Mor(E,F) in a concrete category
C, are related as follows.
 If Im f ⊂ A ⊂ F then
((E,f) is coegg of C_{(A)}) ⇔ (f is a quasiembedding and
∀g∈Mor(E,F), Im g ⊂ A ⇒ Im g ⊂ Im f)
 Injection ⇒ (preembedding ⇔ quasiembedding)
 Quasiembedding ⇒ monomorphism
 (Monomorphism ∧ preembedding) ⇒ injection
 Section ⇒ embedding
Proofs. ∀x∈E, ϕ = (E∋y ↦ (f(y) = f(x) ?
x : y)) ⇒ f ⚬ ϕ = f ⇒ (ϕ ∈ End E ∴ ϕ = Id_{E}).

∃h∈Mor(F,E), h ⚬ f = 1_{E} ∴
∀g∈E^{X}, f ⚬ g ∈ Mor(X,F) ⇒
g = h ⚬ f ⚬ g ∈ Mor(X,E).∎
Let f∈Mor(E,F) a quasiembedding.
If there exists a preembedding g∈Mor(X,F) with the same image Im g = Im
f = A ⊂ F and
AC_{A} holds then f is an embedding.
Proof.
∃h∈X^{A}, g⚬h = Id_{A} ∴
g⚬h⚬f = f ∈ Mor(E,F) ∴ h⚬f
∈ Mor(E,X)
∃ϕ∈Mor(X,E), f⚬ϕ = g ∴ f⚬ϕ⚬h⚬f
= g⚬h⚬f = f ∴ ϕ⚬h⚬f = Id_{E}.∎
A subobject (X,u) of E will be qualified as embedded
(resp. quasiembedded) if u is an
embedding (resp. a quasiembedding) from X to E. This does not depend
on the choice of presentation of a given subobject.
If a subset A of an object F is the image of an embedding f∈Mor(E,F), this gives
A the status of an embedded subobject (A, Id_{A}) ≡ (E,f).
(For a quasiembedding we can do similarly with a copy of E attached to A and thought of
as independent of E).
Then for any object X, we can define Mor(X,A) from Mor(X,F)
directly as X_{(A)}, while Mor(A,X) is only directly defined
from Mor(F,X) if f is a section, as {g_{A} 
g∈Mor(F,X)}.
Equalizers
The equalizer
Eq(f, g) ⊂ E of any two functions f,g with domain
E, was defined in 3.3; it was noticed to be a subalgebra when f,g
are morphisms in a category of algebras.
The more general concept of equalizer Eq(f, g) of
f,g∈Mor(E,F) in any category C, means the subobject
of E defined by the subcoaction C_{(f=g)} of
C_{(E)} where
∀_{C}X, X_{(f=g)} =
{h∈X_{(E)}  f∘h = g∘h}
(if it is regular; it is anyway a subcoaction by stability of equalizers)
In any concrete category, all equalizers are quasiembedded subobjects,
since X_{(f=g)} = X_{(Eq(f, g))}
where Eq(f, g) ⊂ E is the equalizer of the functions
f, g in the category of sets.
Any section f∈Mor(E,F) is an equalizer: if
g∈Mor(F,E) and g∘f = 1_{E}
then f is an equalizer of (1_{F}, f∘g).
Submodules
For any b∈Mor(X,Y), let us call bsubmodule of an
object F, any subobject (E,f) of F such that E
is a bmodule.
Equivalently, ∀h∈Mor(X,E),
∃!j∈Mor(Y,E), f∘j∘b = f∘h
When F is itself a bmodule, ∃!g∈Mor(Y,F),
g∘b = f∘h
and the submodule condition becomes equivalent to each of
 ∀k∈ Im f^{(X)}, ∃g∈
Im f^{(Y)}, g∘b = k

∀g∈Mor(Y,F), g∘b∈ Im f^{(X)}
⇒ g∈Im f^{(Y)}
This is a stability condition on Im f^{(C)}, namely
b_{(F)}^{1}[Im
f^{(X)}] ⊂ Im f^{(Y)}.
Even if F is not a bmodule, the formula 2.
(no more equivalent to other conditions) is still a stability condition on
Im f^{(C)}, namely by the transpose of Gr
b_{(F)}.
It holds in particular if b is epic and f is an equalizer (precisely, when
f is an equalizer of a pair in Mor(F,G) and
b_{(G)} :
Y_{(G)} ↪ X_{(G)}).
Let us apply this stability concept to the case of quasiembedded subobjects in a concrete category:
a subset A of an object F will be called
bstable if b_{(F)⋆}(X_{(A)})
⊂ Y_{(A)}, or more explicitly
∀g∈Mor(Y,F), Im g⚬b ⊂ A ⇒
Im g ⊂ A
In particular:  In any category made of Lsystems for some algebraic language L,
for any b∈Mor(X,Y) such that 〈Im b〉_{L} = Y,
 any Lstable subset is bstable;
 in particular, any Lstable subset of a bmodule is a bmodule.
 If b is surjective then all subsets of objects are bstable.
For any bmodule F and f∈ Mor(E,F),
 If f is a preembedding and b is bijective then E is a bmodule;
 If f is a quasiembedding and Im f is bstable then
(E,f) is a bsubmodule.
Proofs:
 ∀u∈Mor(X,E), f⚬u⚬b^{1} ∈
Mor(Y,F) ∴ u⚬b^{1}∈Mor(Y,E).
 ∀u∈Mor(X,E), (∃!g∈Mor(Y,F),
g⚬b = f⚬u ∴ Im g ⊂ Im f)
∴ (∃!h∈Mor(Y,E), f⚬h⚬b = f⚬u)
∴ (∃!h∈Mor(Y,E), h⚬b = u).∎
3.10. Products of systems
We shall now introduce the concept of product of a family of objects in a category,
and its particular uses in diverse concrete categories. This generalizes the concept of
product of a family of sets, as both will essentially coincide in the case of the
category of sets.
It can be thought of as the dual
concept to that of product of types in a given theory.
The concept of product of an ntuple of types, namely the condition for a type
to play this role, was formalized in 2.3
("Tuples" and "Tuples axiom"). It consisted in introducing or distinguishing an
ntuple of function symbols (serving as projections), an nary operation symbol
(tuples definer), and axioms making both the inverse of each other. But, it needs to be adapted to the
framework of category theory, weaker than onetheory theory. The formalization in category theory
keeps the projection symbols (which are function symbols), but needs to reexpress the tuples
definer in terms of "invariant functions"
alone. The solution is to use the concept of product
of functions (2.8). The product of any family of invariant functions is also invariant (thinking of
it as defined using the tuples definer). This naturally leads to the standard concept
of product in category theory, which we shall formalize below.
Products of actions
Given a family of actions (α_{i})_{i∈I} of a category C,
their product is an action β =
∏_{i∈I} α_{i} of C defined by
∀_{C}X, X^{β} =
∏_{i∈I} X^{αi}
∀_{C}X,Y, ∀f∈ Mor(X,Y),
f^{ β} = ⨉_{i∈I}
f^{ αi} = ⊓_{i∈I}
f^{ αi} ⚬ π_{i}
∀x∈X^{β}, ∀y∈Y^{β},
f^{ β}(x) = y ⇔ ∀i∈I,
f^{ αi}(x_{i}) = y_{i}
Products of families of coactions are defined in the same way.
The action C^{M} mentioned in 3.6 was the constant
Mary product of the primitive action of C.
Products in categories
A product of a family (E_{i})_{i∈I} of objects
in a category C, written ^{C}∏_{i∈I}
E_{i}, is a coegg (P, π) of the product of coactions
∏_{i∈I} C_{(Ei)}.
In other words, it is the data of an object P with a family
π ∈ ∏_{i∈I} Mor(P,E_{i}) making bijective
all functions of the form (f ↦ (π_{i}∘f)_{i∈I})
where the f are morphisms with target P :∀_{C}F, ⊓_{i∈I}
π_{i}^{(F)}
: P^{(F)} ↔ ∏_{i∈I}
E_{i}^{(F)}
Their inverses define the products of morphisms, generalizing the concept of product
of functions ⊓ to any category beyond the category of sets :⊓ :
∏_{i∈I} Mor(F, E_{i}) ↔
Mor(F, P)
The products in C of the empty family (I = ∅) are the final objects of C.
Products in concrete categories
In a concrete category C, a product (P, π) of a family of objects has a natural function
into the set theoretical product, given by the product of functions
⊓π : P →
∏_{i∈I} E_{i}
Its image is the common target set of all set theoretical products of morphisms
f_{i}∈Mor(F, E_{i}) for a fixed object F
and variable i∈I.
If C is regular then this ⊓π is bijective. This generally holds for acting categories, obviously
from definitions when written as C^{(F)} for some object F.
The bijectivity of ⊓π lets the role of categorical product (P,π) be played by the product of sets
∏_{i∈I} E_{i} with its natural family of projections
π = ⊓ Id_{P}.
Then in particular, final objets are singletons (even
if among objects there may be other, nonisomorphic singletons).
On the other hand, if the product as sets P = ∏_{i∈I}
E_{i} of objects in a concrete category C is otherwise given a role of
object, then the condition for it to serve as the product in C is that
∀F, ⊓[Mor(F,P)] = ∏_{i∈I}
Mor(F,E_{i}).
The inclusion side of this equality is equivalent to (∀i∈I, π_{i} ∈
Mor(P,E_{i})). Indeed,
(π_{i})_{i∈I} =
⊓ Id_{P} ∈ ⊓[Mor(P,P)] ⊂ ∏_{i∈I}
Mor(P,E_{i}) ⇒ ∀i∈I, π_{i} ∈
Mor(P,E_{i}).
Conversely (simple reason) : ∀i∈I, π_{i} ∈
Mor(P,E_{i}) ⇒ ∀f∈Mor(F,P),
π_{i}⚬f ∈ Mor(F,E_{i}).
Other presentation : ∀F, ⊓[Mor(F,P)] = Im
⊓_{i∈I} π_{i}^{(F)} ⊂
∏_{i∈I} Mor(F,E_{i}). ∎
By essential uniqueness of products, this also determines all Mor(P,F) from the category.
In a concrete category, for any family of
elements
((E_{i},x_{i}))_{i∈I}, if the family of
objects (E_{i})_{i∈I} has a product (P, π) then the
existence of a product of the (E_{i},x_{i}) in the category of
elements is equivalent to ∃!: ⊓π_{•}(x) and implies that
((P, ℩⊓π_{•}(x)),π) is such a product.
(The proof is straightforward and left as an exercise)
Thus, if a setproduct of concrete objects also serves as their categorical product then the family
definer is also what provides the representatives there of the products in the
category of elements.
In a concrete category C with products, the claim that
(M,e) is an egg can be reexpressed as
∀_{C}E, ∃!f∈Mor(M,E^{E}),
f(e) = Id_{E}.
Products of modules
For any morphism b∈Mor(X,Y) in any category C, any product of
bmodules is also a bmodule.
Proof. Let (P, π) a product of a family
(E_{i})_{i∈I} of bmodules. Then
∀f∈Mor(X,P),
(∀i∈I, ∃!g∈Mor(Y,
E_{i}), g∘b = π_{i}∘f)
∴ ∃!h∈Mor(Y,P), ∀i∈I, π_{i}∘h∘b
= π_{i}∘f.
By Inj ⊓_{i∈I} π_{i}^{(X)} we conclude ∃!h∈Mor(Y,P), h∘b = f.
∎
If C has products, the condition for an object M to be a bmodule
can be reexpressed as
∃!h∈Mor(Y, ^{C}∏_{Mor(X,M)}
M), ∀u∈Mor(X,M), π_{u}∘h∘b = u.
If moreover C is concrete, this formula (∀u∈Mor(X,M), ∀x∈X,
π_{u}(h(b(x))) = u(x)) can also be written
∀x∈X, h(b(x)) = π_{xMor(X,M)}
Products of relational systems
In a category of all relational Lsystems (with fixed L),
any family of systems (E_{i}, E_{i}) has a product
P given by the product of sets, with structure P =
⋂_{i∈I}
^{L}π_{i⋆}(E_{i})
= ∐_{s∈L} ⊓[ ∏_{i∈I}
s_{i}]
For a binary product of Lsystems G = E×F these structures ares_{G} = {x⊓y  x∈s_{E}
∧ y∈s_{F}} = {z∈G^{ns} 
π_{0}⚬z ∈s_{E} ∧ π_{1}⚬z
∈s_{F}}
To check that it forms a product in this category, for any Lsystem F and any
f = ⊓_{i∈I} f_{i} ∈ P^{F}, i.e.
∀i∈I, f_{i} = π_{i}⚬f ∈ E_{i}^{F},
f ∈ Mor_{L}(F,P) ⇔
^{L}f[F] ⊂ P ⇔ ∀i∈I,
^{L}f[F]
⊂ ^{L}π_{i⋆}(E_{i})
⇔ ∀i∈I, f_{i} ∈ Mor_{L}(F,E_{i})
⇔ ⊓f ∈ ∏_{i∈I}
Mor_{L}(F,E_{i})
For a symbol s of trajectory
of a tuple in a concrete category,
s_{P} ⊂ ⊓[ ∏_{i∈I} s_{i}] with equality if AC_{I} holds.
Products of algebras
With an algebraic language L, the product P = ∏_{i∈I}
E_{i} of a family of Lalgebras (E_{i}, φ_{i})
has Lalgebra structure φ_{P} defined by
(∀i∈I, π_{i} ∈
Mor_{L}(P,E_{i})) ⇔
(∀i∈I, φ_{i}⚬^{L}π_{i}
= π_{i}⚬φ_{P}) ⇔ φ_{P} =
⊓_{i∈I} φ_{i}⚬^{L}π_{i}
Indeed, for any Lsystem F and any
f = ⊓_{i∈I} f_{i} ∈ P^{F},
f ∈ Mor_{L}(F,P) ⇔
φ_{P}⚬^{L}f = f⚬φ_{F}
⇔ ∀i∈I, φ_{i}⚬^{L}f_{i} =
φ_{i}⚬^{L}π_{i}⚬^{L}f =
f_{i}⚬φ_{F}
⇔ ∀i∈I, f_{i}
∈ Mor_{L}(F,E_{i})
⇔ ⊓f ∈
∏_{i∈I}
Mor_{L}(F,E_{i})
This comes as a particular case of product of relational systems :
∀(x,y)∈^{L}P×P, y =
φ_{P}(x) ⇔ ∀i∈I, y_{i} =
φ_{i}(^{L}π_{i}(x))
The structure φ_{P} of a constant product P =
E^{I} of an Lalgebra E can be written
^{L}P∋(s,x) ↦ s_{E}
⚬ ⊓x
The product of a family of actions of a given monoid, particular case of product of actions
of a category, is also a particular case of product of algebras (precisely modules among these).
Among systems, aside the case of algebras, any product of partial algebras is a partial algebra ;
any product of injective systems is an injective system ; if AC_{I} holds then
any product over I of serial systems is serial. But the surjectivity of a product system
cannot be ensured unless it is achieved by a single symbol in L.
Graphs of morphisms
For any morphism f∈ Mor(E,F) in a category with products, the morphism
Id_{E}⊓f from E to a product G = E×F is a section,
thus defining the graph of f as an embedded subobject of G if the category is concrete.
Let us review some more specific properties of graphs of morphisms between systems.
Let L an algebraic language, and E, F two Lsystems.
If F is algebraic then
Mor_{L}(E,F) = {f∈F^{E} 
Gr f ∈ Sub_{L}(E×F)}
This result may be split in two parts (whose proofs are left as exercises):
 (F serial ∧ Gr f ∈ Sub_{L}(E×F)) ⇒
f ∈ Mor_{L}(E,F)

(F functional ∧ f ∈ Mor_{L}(E,F)) ⇒
Gr f ∈ Sub_{L}(E×F)
When both E,F are algebraic (and thus E×F too), these may be seen as
deducible from previous results: 
(Gr f ∈ Sub_{L}(E×F)
∧ π_{0Gr f} ∈ Mor_{L}(Gr f, E))
⇒ Id_{E}⊓f = (π_{0Gr f})^{1} ∈ Mor_{L}(E, Gr f)
⊂ Mor_{L}(E, E×F).

f ∈ Mor_{L}(E,F)
⇔ Id_{E}⊓f ∈ Mor_{L}(E,E×F)
⇒ Gr f = Im(Id_{E}⊓f ) ∈ Sub_{L}(E×F).∎
and it gives another proof of the stability
of equalizers
∀f,g∈Mor_{L}(E,F),
(Gr f ∩ Gr g) ∈ Sub_{L} (E×F)
∴ Eq(f,g) = π_{0}
[Gr f ∩ Gr g] ∈ Sub_{L} E.∎
On the other hand (with no algebraicity condition), denoting H = Gr f ⊂
G = E×F, we have ∀f∈F^{E},
(E injective ∧ H ⊂ G^{⋆}(^{L}H))
⇒ f ∈ Mor_{L}(E,F)
(E surjective ∧ f ∈ Mor_{L}(E,F)) ⇒ H
⊂ G^{⋆}(^{L}H)
Fiber products
An important kind of concrete categories with products whose underlying sets differ from the
products of sets, are the categories of typed systems. The effect of a categorical product
between systems of a given kind which has multiple types, is dual to that of a product
between types in a theory interpreted across multiple systems: it behaves as a product
of sets for each type taken separately.
So, reusing the notations of 3.2, given
a set τ of types and a family of typed concrete objects E_{i} =
∐_{t∈τ} E_{t,i} for each i∈I,
their product will have base set
∐_{t∈τ} ∏_{i∈I}
E_{t,i}.
This is identifiable to a subset of ∏_{i∈I}
E_{i} if I ≠ ∅ but a copy of τ if I = ∅.
Our other formalization
of the category of typed sets expressed its objects in the form
(E, h_{E}) where h_{E} : E → τ, and
morphisms from (E, h_{E})
to (F, h_{F}) are the f : E → F such that
h_{F} ⚬ f = h_{E}.
As already mentioned, such a category (with a fixed list τ of types) is an overcategory Set/τ of the category of sets.
A wide pullback or
wide fiber product of a nonempty family
(f_{i})_{i∈I} of morphisms f_{i}
∈ Mor(E_{i} , T) to a fixed object T in a category C, is their
product in the overcategory C/T. So it is a final object of the category whose objects
are the triples of
 an object P of C,
 a q ∈ Mor(P,T)

and a family
p ∈ ∏_{i∈I} Mor(P,E_{i}) such that
∀i∈I, f_{i} ∘ p_{i} = q
and whose morphisms from such an object to a similar (P', q',
(p'_{i})_{i∈I})
are the h ∈ Mor(P, P') such that
∀i∈I, p'_{i} ∘ h = p_{i}
which implies q' ∘ h = q.
Indeed since I ≠ ∅, with a chosen k∈I we have
q' ∘ h = f_{k} ∘ p'_{k} ∘ h
= f_{k} ∘ p_{k} = q.
An equivalent formalization of wide pullbacks eliminates the use of q
replaced by f_{k} ∘ p_{k}
for a fixed k∈I (independently of this choice), or all of them:
∀i,k∈I, f_{i} ∘
p_{i} = f_{k} ∘ p_{k}.
Hence the simpler definition in the binary case (when I is a pair):
a pullback or fiber product of two morphisms f ∈ Mor(E,
T), g ∈ Mor(F, T), is a coegg of the subcoaction of the product
coaction C_{(E)}×C_{(F)}, giving to each
X the set of all
(p_{0},p_{1}) ∈ Mor(X, E)× Mor(X, F)
such that f ∘ p_{0} = g ∘ p_{1}.
In terms of coactions, this is an equalizer inside a product. So, the same can be said in terms of
categories when (E, F) has a product (G, π_{0}, π_{1})
where π_{0}∈ Mor(G, E), π_{1}∈ Mor(G, F).
Namely, the pullback of (f,g) is identifiable with the subobject
Eq(f∘π_{0},g∘π_{1}) of G, that is
the subcoaction C_{(f∘π0=g∘π1)}
of C_{(G)} made of the p_{0}⊓p_{1}
∈ Mor(X, G) for the (p_{0},p_{1})
that fit the above condition.
Thus, any category with binary products and equalizers also has pullbacks; and in
any concrete category where the underlying sets of products and equalizers are the
setlike versions of these (such in as categories of all algebras or all systems over a given
language), the same goes for its pullbacks obtained from these. In particular, any
category of all typed algebras with a given set τ of types, has products given by
the wide pullback over τ (which plays the role of final object of such a category).
Conversely, any category with binary products and pullbacks also has equalizers: any equalizer
e = Eq(f, g) where f, g∈ Mor(E, F) can be
extracted from a pullback in two ways:
 Pullbacks of (f⊓1_{E}, g⊓1_{E})
are of the form (e,e);
 Pullbacks of (f⊓g, 1_{F}⊓1_{F})
are of the form (e, f∘e).
Products can themselves come as particular cases of wide pullbacks in categories with final objects.
There is a special use of pullbacks, namely to construct fiber
bundles, where in the pullback (p_{0},
p_{1}) of (f,g), f and p_{1} serve as the
components of a single morphism along two types, while g and p_{0}
interpret a single function symbol in two systems.
Intersections of subobjects
Applying the concept of wide pullback to families of monomorphisms f_{i}
∈ Mor(E_{i} , F), gives an operation between
subobjects of F, called their intersection.
Indeed, the resulting morphism to F is also monic, it is related to the "inclusion"
between subobjects the same way an intersection of sets is characterized
from set inclusion, and it coincides with the operation of intersection between subcoactions.
In any concrete category, any intersection of quasiembedded subobjects is quasiembedded, with image
the greatest image of a morphism into the intersection of images of given subobjects.
Intersections of submodules
For a given b∈Mor(X,Y), an intersection of a family of bsubmodules
(E_{i},e_{i}) of F indexed by I can be
deduced to be also a bsubmodule under either additional assumption:
 if F is a bmodule ;
 or, if I ≠ ∅ and b is epic.
The simple proof with 1. is that an intersection of stable subsets is stable.
A more complex proof would use the above result on products of modules in
the category of coelements of C_{(F)}. This requires to prove that the
condition for a subobject of F to be a bsubmodule in C, is equivalent to it being a
b_{h}module in the category of coelements of C_{(F)} for every
h∈Mor(Y,F), where b_{h} is the copy of b
in Mor((X,h∘b), (Y,h)).
The proof for case 2. comes from the fact any wide pullback can be expressed as an intersection
of equalizers inside a product (which anyway exist as coactions). This can be lengthily written
as follows.
Let us denote (A,a) this intersection, with
ϕ_{i}∈Mor(A,E_{i}) such that
a = e_{i}∘ϕ_{i} for each i∈I.
Let u∈Mor(X,A). As b is epic we just need to prove
(∃w∈Mor(Y,A), w∘b = u).
∃i∈I, ∃v∈Mor(Y,E_{i}), v∘b =
ϕ_{i}∘u
∀j∈I, ∃!w∈Mor(Y,E_{j}), w∘b =
ϕ_{j}∘u ∴ e_{j}∘w∘b =
e_{j}∘ϕ_{j}∘u
= a∘u = e_{i}∘ϕ_{i}∘u = e_{i}∘v∘b
∴ e_{j}∘w = e_{i}∘v.
As (A,a) is an intersection of the (E_{j},e_{j}),
∃w∈Mor(Y,A), a∘w = e_{i}∘v
∴ a∘w∘b = e_{i}∘v∘b =
e_{i}∘ϕ_{i}∘u = a∘u ∴ w∘b = u.∎
Intersections of subsystems
In any category of relational systems, subobjects of a system (F, F)
are bijectively represented by its subsystems (E, E) in the sense that E⊂F ∧ E⊂F, with the monomorphism
Id_{E} : E↪F.
Then, the intersection of a family of subobjects (E_{i},
E_{i}) of (F, F) is represented by
(⋂_{I∈I} E_{i}, ⋂_{I∈I}
E_{i}) if we use the cateogry of all systems with a given language,
or more generally if this system belongs to the considered category (which will be
usually the case for categories defined as those of systems which are modules for some
morphisms). This has two important special cases :
 Intersections of embedded subsystems (∀i∈I, E_{i} =
F∩^{L}E_{i}): these are also embedded;
 Intersections of structures on the same system (∀i∈I, E_{i} = F).
In the latter case, for a bijective b, the fact an intersection of bmodule
structures is a bmodule structure can be seen as a case of the fact any intersection
of stable subsets is stable.
As first noted in 2.9 for a binary
relation symbol, an intersection of preimages of structures by some functions from a given set,
coincides with the preimage of the product structure by the product function.
3.11. Basis
Eggs as acting monoids
For any monoid (M,e, •), the eggs of the category of Msets are (M,
e) and other regular elements.
Conversely, for any egg (M,e) of a concrete category, seeing M
as a set of function symbols, there is a unique Malgebra structure on every object
X satisfying both axioms of action and Mor_{M}(M,X) ⊂
Mor(M,X).
This structure • on M makes (M,e,•) a monoid acting on all objects
and
∀_{C}X,Y, Mor(X,Y) ⊂
Mor_{M}(X,Y), with equality for X = M.
This can be seen as another use of Yoneda's lemma, but let us write a separate proof.
The hypothesis imply ∀x∈X, ⋅⃖_{x} ∈
Mor(M,X) ∧ ⋅⃖_{x}(e) = x.
As (M,e) is an egg, this defines the structure ⋅ on X interpreting
each a∈M as the trajectory of (e,a). Thus
∀X,Y, Mor(X,Y) ⊂ Mor_{M}(X,Y).
Thus it actually satisfies both axioms of action.
The last monoid axiom comes as
Id_{M} fits the definition of •⃖_{e}.
We conclude Mor_{M}(M,X) ⊂
Mor(M,X) by ∀g∈ Mor_{M}(M,X),
g = ⋅⃖_{g(e)} ∈ Mor(M,X).∎
In a concrete category with products, the definition of ⋅ can be written
⋅⃗ ∈ Mor(M,X^{X}) ∧
⋅⃗(e) = Id_{X}.
Anyway ⋅⃗ ∈ Mor_{M}(M,X^{X}).
This monoid (M,e,•) is essentially the opposite of the monoid End(M).
Indeed
∀x,y∈M, •⃖_{x} ∈ End(M)
∧ •⃖_{y} ∈ End(M) ∧ •⃖_{x} ⚬
•⃖_{y} (e)
= •⃖_{x}(y) = y•x.
For any object M of a category C, the action of the egg
M^{(M)} of C^{(M)} on each object
E^{(M)}
coincides with the coaction of End(M) on Mor(M,E) by composition.
Algebraic structures on modules
The role of an egg as a set of function symbols in a concrete category, has diverse
generalizations giving sets of operation symbols interpreted as algebraic structures
on objects.
For the most general case, consider a concrete category U, a morphism
b∈ Mor(V,K), and a class C of bmodules, forming
a concrete category with the same sets of morphisms between given objects : ∀_{C}E, ∀u∈E^{(V)},
∃!f∈Mor(K,E), f⚬b = u
Seeing V as a set of variables and K as a set of Vary operation symbols,
each object E of C, being a bmodule, gets a partial Kalgebra
structure φ_{E} with domain K×E^{(V)}
defined for each s∈K as the trajectory of (b,s):
∀_{C}E, ∀u∈E^{(V)},
φ⃖_{E}(u) = ℩{f∈Mor(K,E) 
f⚬b = u} = b_{(E)}^{1}(u)
∴ Mor(K,E) = {φ⃖_{E}(u) 
u∈E^{(V)}}
∀_{C}E,F, Mor(E,F) ⊂
Mor_{K}(E,F)
On a product of bmodules, this Kstructure is the product of those on
components, independently of the axiom of choice.
Elements of Im b play the role of projection symbols (∀x∈V,
π_{x} = b(x)), behaving as such in C.
As Mor(K,E) was expressed from φ_{E}, it will more precisely
coincide with Mor_{K}(K,E), once K is given a proper
Kstructure. A minimal natural candidate is the trajectory of (b,s),
which depends on End(K); but the choice of End(K) (fitting axioms of
categories with fixed Mor(K,E)) will not matter.
Indeed, the smallest End(K) =
{Id_{K}} gives to K its smallest trajectoriesdefined Kstructure
{((s,b),s)  s∈K}. This gives the greatest candidate
Mor_{K}(K,E), equal to Mor(K,E); but the reverse
inclusion Mor(K,E) ⊂ Mor_{K}(K,E) is another natural
requirement (preservation of the Kstructure). So the equality is necessary.
For φ_{E} to be algebraic, we shall assume V to be
structureless, which means ∀E,
E^{(V)} = E^{V}. For this to hold with Kmorphisms
(Mor_{K}(V,E) = E^{V}),
 The empty structure V = ∅ ensures it in all
U in any case (then K ≠ ∅ ⇒ Mor_{K}(K,V) = ∅).
 For example V = {((π_{x},Id_{V}),x)  x∈V}
still gives Mor_{K}(V,E) = Mor(V,E) for
bmodules E structured by trajectories ;
precisely, Mor_{K}(V,E) = E^{V}
when all π_{x} work in E as projections from E^{V} to E.
With a structureless V, a noninjective b would only let singletons and ∅ as possible
objects in C. Excluding this case, we usually take b = Id_{V} :
V↪K, so that f⚬b = f_{V}.
Basis
From the above with fixed choices of U, C and a structureless
V, let b and K vary : let B be the class of (K,b)
where K is in U and b∈K^{V}, such that all objects in C
are bmodules; equivalently, these are the elements in
U^{V} having a unique morphism to any element in C^{V}.
If moreover K is in C then b is called a basis of K in C.
Equivalently, (K,b) is an egg
of C^{V}. Then it is a final object of B.
For any object K in C with a chosen basis b, and any possible symbol
s of (preserved) Vary operation in objects of C, the element
s' = s_{K}(b) ∈ K is the unique element of K
whose role of operation in all objects of C (trajectory of (b,s')) coincides
with s. In particular for any (X,a) in B and any s∈X,
this s' is the image of s by the unique morphism from (X,a) to
(K,b).
Any operation s with lower arity also has a copy s' = s_{K}(x)
for any injective substitution of variables x : V_{ns} ↪ V.
Such a s' plays the same role as s with unused extra variables
(∀_{C}E, ∀u∈E^{V},
s'_{E}(u) = s_{E}(u⚬x)), except for the
inability of languages without constants to replace the role of a constant symbol to
exclude ∅ (the empty algebra) from the considered category.
Coproducts
Similarly to products with sides reversed, a coproduct in C of a family
(E_{i})_{i∈I} of objects of C, written
(K, j) : ^{C}∐_{i∈I}
E_{i}
is an egg (K, j) of the product of actions
C^{(Ei)}, thus an object K with j
∈ ∏_{i∈I} Mor(E_{i}, K) making all
f ↦ (f∘j_{i})_{i∈I} bijective :
∀_{C}F, ⊓_{i∈I}
j_{i (F)} : K_{(F)} ↔
∏_{i∈I} E_{i (F)}
The coproducts in C of the empty family are the initial objects of C.
While the general definions of product and coproduct only determine their isomorphism classes,
we shall usually speak of the product and the coproduct of any family of objects in
explicitly described categories, to refer to the most natural explicit construction of a specific
representative of each such class, which could be written in the given category.
The category of sets has coproducts given by the
disjoint union with its
natural injections
(∏_{i∈I} F^{Ei}
⥬ F^{∐i∈I Ei}).
In categories of all relational systems with fixed language L, the coproduct is
given by the disjoint union, with structure ⋃_{i∈I}
^{L}j_{i}[E_{i}].
In other concrete categories, the underlying sets of coproducts may differ from disjoint
unions, more often than those of products differ from the products of sets.
The injectivity of each j_{i} often remains, but already fails in
categories of partial algebras (4.2).
Basis and coproducts
For any objects M, K of any category C, and any b ∈
Mor(M,K)^{V},
(b is a basis of K^{(M)} in
C^{(M)}) ⇔ (K, b) :
^{C}∐_{x∈V} M.
Similarly in a concrete category with an egg (M, e) : a constant Vary
coproduct (K,j) : ^{C}∐_{x∈V} M
is an object K with basis b = ⊓j(e).
Equivalently, j = (⋅⃖_{b(x)})_{x∈V}
where ⋅ is the action of (M, e).
These j_{x} are sections, as the set of left inverses of j_{x}
has a natural bijection with {u∈M^{V} 
u(x) = e}
(while the components of j in nonconstant coproducts are not always sections).
Products and coproducts have associativity properties like first seen
with the product of sets : any product of products of objects, is naturally isomorphic to a simple product indexed by
the disjoint union of indexing sets; and the same for coproducts.
In particular, a coproduct
(K, j) : ^{C}∐_{i∈I} E_{i} of
objects E_{i} with respective basis b_{i} : V_{i}
→ E_{i},
is an object with a basis indexed by the disjoint union ∐_{i∈I} V_{i}
of these bases.
Equational systems
Let us specify the above by taking an algebraic language L and a category U of
Lsystems with Mor = Mor_{L}.
Let us call Lequational system any data of a structureless
set V, an Lsystem K and a b ∈ K^{V}, such that
〈Im b〉_{L} = K. This
implies
 Any Lstable subset of an Lsystem is bstable
 Thus, any Lstable subset of a
bmodule is a bmodule.
 For any partial Lalgebra
E, Inj b_{(E)}, i.e. ∀u∈E^{V},
!g∈Mor_{L}(K,E), g⚬b = u.
Proof of 3. By stability of equalizers,
∀u∈E^{V}, ∀g,h∈Mor_{L}(K,E),
g⚬b = u = h⚬b ⇒
Im b ⊂ {x∈K  g(x) = h(x)} ∈
Sub_{L}K ⇒ g = h.∎
So, equational systems may be used to distinguish among algebras (or partial algebras) E,
those for which the injection b_{(E)} is also surjective. In many cases L
has no projection symbol, obliging the chosen Lstructure of V to be empty.
Examples
 If all symbols in L are nary, then
V_{n} ↪ V_{n} ⊔ L with structure
{((s, Id_{Vn}), s)  s ∈ L}
is an equational system, whose modules among Lsystems are the algebraic ones ;
 Any monoid K forms a Kequational system with V = {e}; then,
the Ksets are the partial Kalgebras which are bmodules. Indeed
any bmodule E gets a Kset structure included in
E, then equality is deduced from the functionality of E.
 In the construction of algebraic structures on modules we described K as a
Kequational system.
 The axiom of identity on a system
is expressible as it being a module by an equational system with V a singleton, and
K a pair (details are left as an exercise to the reader) ;
 Similarly for associativity with a 3elements V and a 6elements K.
Beyond equational systems, the concept of module by some b ∈
Mor_{L}(X,Y)
where 〈Im b〉_{L} = Y but X has nonempty structure,
is an expression of axioms using ⇒, such as left cancellativity (of a constant, or of all elements).
The systematic understanding of these facts relies on the formalization of Lterms as
Lsystems, which will be presented in 4.1 and 4.3.
3.12. Composition of relations
The category of relations
This category extends the category of sets, keeping the same objets (the sets)
and defining Mor(E,F) as the set ℘(E×F) of all relations between E and F.
Their composition is defined by
∀_{gr}R,S, R;S = {(x_{0},y_{1}) 
(x,y)∈R×S ∧ x_{1}=y_{0}}
∀R⊂E×F, ∀S⊂F×G, R;S =
{(x,z)∈E×G  ∃y∈F, xRy ∧ ySz}
= ∐_{x∈E}
S^{⋆}R⃗(x)
This extends the composition of functions coming as functional relations, with the
same identity elements (1_{E} = 𝛿_{E} = Gr Id_{E}).
(This is the only natural way to extend composition, as the other expression of the composite of functions by
their graphs, with ∀y∈F, xRy ⇒ ySz, would lose associativity in nonfunctional cases).
This category faithfully acts by direct images (^{⋆})
on the powersets of its objects, and coacts on them by preimages (_{⋆}):
∀R⊂E×F, ∀S⊂F×G, ∀A⊂E,
(S⚬R)^{⋆}A = S^{⋆}(R^{⋆}A)
∀B⊂G, (R;S)_{⋆}B = R_{⋆}(S_{⋆}B)
For this action, each object (set) E has a basis made of its singletons :
({x})_{x∈E}, following the canonical bijection
(℘(F))^{E} ⥬ ℘(E×F).
Thus, coproducts in this category are given by the disjoint unions of objects
(which operate as products on the powersets acted on). So, a coproduct of pairwise disjoint sets
E_{i} is given by their union, with the morphisms 𝛿_{Ei} from each
E_{i} to it.
By symmetry of duality, this disjoint union also serves as a
product.
The eggs of this action are the ({x}, {x}) for any x. A standard choice
of singleton is given by the notations ＊ = {•}. Then, direct and inverse images can be
reexpressed in terms of composition: ∀R⊂E×F,
∀A⊂E, ∀B⊂F, ＊×(R^{⋆}A) = (＊×A);R
(R_{⋆}B)×＊ = R;(B×＊)
By these action and coaction, morphisms in this category behave as a third form of expression of Galois connections
(after the ordinary and monotone ones). Indeed by associativity of composition,
(＊×A);R;(B×＊) = ∅ ⇔
A ∩ R_{⋆}(B) = ∅ ⇔
B ∩ R^{⋆}(A) = ∅
(∁_{F}⚬R^{⋆}, ∁_{E}⚬R_{⋆}) ∈ Gal(℘(E), ℘(F))
(R^{⋆}, ∁_{E}⚬R_{⋆}⚬∁_{F}) ∈
Gal^{+}(℘(E), ℘(F))
Reexpressing properties of relations
Each side (curried form) of the composition of relations, behaves similarly to direct
images, which it can be seen as made of: ∀_{gr}R,S,T,
R⊂S ⇒ R;T ⊂ S;T
R⊂S ⇒ T;R ⊂ T;S
(R∪S);T = R;T ∪ S;T
T;(R∪S) = T;R ∪ T;S
and for any family of graphs R_{i} indexed by I and any graph T,
T;⋃_{i∈I} R_{i} =
⋃_{i∈I} T;R_{i}
T⚬⋃_{i∈I} R_{i} =
⋃_{i∈I} T⚬R_{i}
The reflexivity (𝛿_{E} ⊂ R) of a relation R on a set E,
implies ∀S⊂E×F, S ⊂ R;S
∀S⊂F×E, S ⊂ S;R
The transitivity of R can be written R;R ⊂ R.
Thus if R is a preorder then R;R = R but the converse does not always hold.
Generated preorders
The role of sets of transformations of E as defining stability conditions on subsets A⊂E,
reflected by the Galois connection (End, Sub)∈ Gal(℘(℘(E)), ℘(E^{E}))
introduced in 3.4, is equivalent to that of single relations R ⊂ E^{2}
(nonfunctional structures named by a single function symbol) in the Galois connection
(Po, Sub)∈ Gal(℘(℘(E)), ℘(E^{2})) defined as relating any A⊂E
to (x,y)∈E^{2} by (x∈A ⇒ y∈A):
A ∈ Sub_{R} E ⇔ R^{⋆}A
⊂ A ⇔ (∀(x,y)∈R, x∈A ⇒ y∈A) ⇔
∁_{E} A ∈ Sub_{tR} E
Indeed any set of transformations can be replaced by the union of their graphs; inversely, any
(x,y)∈E^{2} can be replaced by
E ∋ z ↦ (z=x ? y : z).
The set Im Po of closed elements of ℘(E^{2}) there, is the set of preorders of E.
Indeed, for any set K and any G⊂K×E,∀x,y∈E,
(x,y)∈Po(G⃗[K]) ⇔ (∀z∈K, zGx ⇒
zGy) ⇔ G⃖(x)⊂G⃖(y)
which, according to 2.9, gives all preorders on E (intersections of preimages
of the natural order on {0,1}).
Now the inclusion order on any S⊂℘(E) appears that way with
{(A,x)∈S×Ex∈A}.
Namely, ∈⃗ defines a preembedding from (E,Po(S)) to (℘(S),⊂).
The closure Po(Sub_{R}E) of any R ⊂ E^{2} is called the
preorder on E generated by R; we shall write it ⌈R⌉.
Generated stable subsets
Lemma. Any union of Rstable subsets is Rstable.
(This does not generalize to structures with other arities).
First proof. (∀i∈I, R^{⋆}A_{i}
⊂ A_{i}) ⇒ R^{⋆}⋃_{i∈I} A_{i} =
⋃_{i∈I} R^{⋆}A_{i} ⊂ ⋃_{i∈I} A_{i} ∎
Second proof. Use A ∈ Sub_{R} E ⇔ ∁_{E} A ∈ Sub_{tR} E and the similar property with intersections.∎
Proposition. ∀A⊂E,
〈A〉_{R} = ⌈R⌉^{⋆}A.
Proof. First, when A is a singleton {x}, both definitions coincide :
∀y∈E, x⌈R⌉y ⇔
(∀A∈Sub_{R}E, x∈A ⇒ y∈A)
⇔ y∈〈{x}〉_{R}
Then, ⌈R⌉^{⋆}A = ⋃_{x∈A}
〈{x}〉_{R} ⊂ 〈A〉_{R} because A ↦ 〈A〉_{R}
is monotone.
We conclude by ⌈R⌉^{⋆}A ∈ Sub_{R} E from the above lemma.∎
From the end of 3.3 we get ∀A⊂E, 〈A〉_{R} =
A ∪ R^{⋆}〈A〉_{R}.
By the faithfulness of the action, it can also be written
⌈R⌉ = 𝛿_{E} ∪ R⚬⌈R⌉
An easy consequence of the above is that for any sets K, E and any
G⊂K×E and R⊂E^{2}, ⌈R⌉⚬G is the smallest
S⊂K×E such that G ∪ R⚬S ⊂ S, and it
is a case of equality (G ∪ R⚬S = S).
Transitive closure
For any R⊂E^{2}, the smallest transitive T⊂E^{2}
such that R⊂T (which exists as transitivity is preserved by intersections),
called the transitive closure of R, is
T = R⚬⌈R⌉ = ⌈R⌉⚬R.
Proof. By hypothesis, R ⊂ T and R⚬T ⊂ T⚬T ⊂ T, thus
⌈R⌉⚬R ⊂ T by the above result (⌈R⌉⚬R is the smallest T such that R ∪ R⚬T ⊂ T).
Then, ⌈R⌉⚬R fulfills both conditions for which T is smallest : R ⊂ ⌈R⌉⚬R, and transitivity:
R⚬⌈R⌉ ⊂ ⌈R⌉ = ⌈R⌉⚬⌈R⌉ ∴
⌈R⌉⚬R⚬⌈R⌉⚬R ⊂ ⌈R⌉⚬⌈R⌉⚬R = ⌈R⌉⚬R
Hence T = ⌈R⌉⚬R. By duality, T = R⚬⌈R⌉.∎
Wellfounded relations
A relation R ⊂ E^{2} is called wellfounded if
∀A⊂E, A ⊂ R^{⋆}A ⇒ A = ∅.
This does not depend on E such that R ⊂ E^{2} for a given graph
R, and implies that any S ⊂ R is also wellfounded.
Any wellfounded relation is irreflexive : ∀x, x ∉ R^{⋆}{x}.
Proposition. The transitive closure T of any wellfounded relation R is
also wellfounded.
Proof. If R ⊂ E^{2} is wellfounded, T = R⚬P and P =
𝛿_{E} ∪ T (namely, P=⌈R⌉), then T is wellfounded:
∀A⊂E,
A ⊂ T^{⋆}A ⇒ P^{⋆}A =
A∪ T^{⋆}A = R^{⋆}P^{⋆}A = ∅ ∎
Note: the wellfoundedness of R implies the uniqueness of P such that
P = 𝛿_{E} ∪ R⚬P.
The proof goes by considering A = {x∈E  P⃖(x)
≠ P'⃖(x)} for P and P' with this property ;
this is an example of a definition by wellfounded induction, concept which will be developed later.
Proposition. If R is wellfounded then ⌈R⌉ is an order, whose strict order coincides with
the transitive closure of R.
Proof. The transitive closure T of R, being both transitive and irreflexive,
is a strict order, and ⌈R⌉ = 𝛿_{E} ∪ T.∎
(The antisymmetry of a wellfounded R can also be deduced by ∀x,y,¬{x,y}⊂R^{⋆}{x,y})
Wellorder
A relation R ⊂ E^{2} is called a strict wellorder on E if
∀A⊂E, A = ∅ ∨ ∃!:A\(R^{⋆}A)
It is easy to see that any strict wellorder is a wellfounded strict total order;
conversely, any wellfounded R ⊂ E^{2} whose complement
∁_{E2} R is antisymmetric, is a strict wellorder on E.
Given that the corresponding total order ≤ equals ∁_{E2} ^{t}R,
the condition for a relation ≤ to be a wellorder, which means a total order whose strict version is
a strict wellorder on E, can be written
∀A⊂E, A = ∅ ∨ ∃!x∈A, A ⊂ ≤⃗(x)
or equivalently : it is antisymmetric and ∀A⊂E, A = ∅ ∨ ∃x∈A,
A ⊂ ≤⃗(x).
Greatest and least elements
In any ordered set (E,≤), an x∈E is called a lower bound (resp.
upper bound) of a subset A⊂E if A ⊂ ≤⃗(x)
(resp. A ⊂ ≤⃖(x)). If moreover x∈A, it is then called
a least element (resp. greatest element) of A, which we shall denote
x :min A (resp. x :max A). These concepts only
depend on the set A ordered by restriction of ≤, ignoring the rest of E and ≤.
By antisymmetry of ≤, these relations are functional from ℘(E) to E, which is
why they are usually denoted as functions min (the least element) and max (the greatest element):
∀A⊂E, ∀x∈E,
x :min A ⇔ (x∈A ∧ A ⊂ ≤⃗(x))
⇔ (A∈ Dom min ∧ x = min A)
x :max A ⇔ (x∈A ∧ A ⊂ ≤⃖(x))
⇔ (A∈ Dom max ∧ x = max A)
The successor function
In any ordered set (E,≤) with strict order <, the successor is the functional relation
S on E defined by ∀x,y∈E,
xSy ⇔ y :min <⃗(x) ⇔ ≤⃗(y) = <⃗(x)
This last equivalence is easy to check.
If the order is total then S is injective and its definition is symmetric in the sense that
xSy ⇔ x :max <⃖(y) ⇔ ≤⃖(x) = <⃖(y)
If it is a wellorder then ∀x∈E,
x ∉ Dom S ⇔ <⃗(x) = ∅ ⇔ x :max E.
Set theory and foundations
of mathematics
1. First foundations of
mathematics
2. Set theory (continued)
3. Algebra 1
4. Arithmetic and firstorder foundations
5. Secondorder foundations
6. Foundations of Geometry