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 self-contained, 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 : 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 ∈ FE and g ∈ EF are both monotone (resp. both antitone) and g⚬f = IdE, then f is strictly monotone (resp. strictly antitone).

Order between functions, extensive functions

For all sets E, F where F is ordered, the set FE is ordered as a product (f ≤ g ⇔ ∀x∈E, f(x) ≤ g(x)).
Then, ∀f,g∈FE, ∀h∈EG, f ≤ g ⇒ f⚬h ≤ g⚬h, i.e. f ↦ f⚬h is always monotone.
The particular case F = V2 is that h⋆ is monotone from ℘(E) to ℘(G) for the inclusion order.
If F and G are ordered and u ∈ GF is monotone (resp. antitone) then FE ∋ f ↦ u⚬f ∈ GE is monotone (resp. antitone).
In an ordered set E, a function f ∈ EE is said extensive if IdE ≤ 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) = {(⊥,⊤) ∈ FE×EF|∀x∈E, ∀y∈F, x ≤E⊤(y) ⇔ y ≤F ⊥(x)} = tGal(F,E)
Gal+(E,F) = {(u,v) ∈ FE×EF|∀x∈E, ∀y∈F, x ≤E v(y) ⇔ u(x) ≤F y} = Gal(E,F−)

Lemma. ∀⊥ ∈ FE, !⊤ ∈ EF, (⊥,⊤) ∈ Gal(E,F).
Proof: ∀⊤ ∈ EF, (⊥,⊤) ∈ 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: 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 =⊤⚬⊥ ∈ EE and Cl′=⊥⚬⊤ ∈ FF satisfy
  1. Cl and Cl′ are extensive.
  2. ⊥ and ⊤ are antitone
  3. Cl and Cl′ are monotone
  4. ⊥⚬⊤⚬⊥ = ⊥, and similarly ⊤⚬⊥⚬⊤ = ⊤
  5. Im ⊤ = Im Cl = Fix Cl, called the set of closed elements of E.
  6. Cl⚬Cl = Cl
  7. (⊥ strictly antitone) ⇔ Inj ⊥ ⇔ Cl = IdE ⇔ Im ⊤ = E
  8. ∀x,x′∈E, ⊥(x) ≤ ⊥(x′) ⇔ (Im⊤∩ ≤⃗(x) ⊂ ≤⃗(x′)).
  9. Denoting K = Im ⊤, ⊤⚬⊥|K = IdK, 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.) IdE ≤ 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 = IdE ⇔ (Im ⊤ = E ∧ Cl⚬⊤ = ⊤);
Cl = IdE ⇒ ⊥ strictly antitone ⇒ Inj ⊥.
(8.) ⊥(x) ≤ ⊥(x′) ⇔ (∀y∈F, x≤⊤(y) ⇒ x′≤ ⊤(y)).
(9.) K = Fix(⊤⚬⊥) ⇒ ⊤⚬⊥⚬IdK = IdK.
Other proof : (⊥|K,⊤) ∈ Gal(K,F) with ⊤ surjective.
In ⊤|Im⊥⚬⊥|K = IdK 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 ≤ IdF.

Characterization of closures

A closure of an ordered set E is an f ∈ EE such that, equivalently:
  1. There exists a set F and an (u,v) ∈ Gal(E,F) or Gal+(E,F) such that v⚬u=f
  2. f is monotone, idempotent and extensive
  3. ∀x∈E, ∀y∈ Im f, x ≤ y ⇔ f(x) ≤ y, i.e. (f, IdK) ∈ 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:

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 We then denote the set of all operations OpE = ∐n∈ℕ OpE(n), and that of all relations RelE = ∐n∈ℕ ℘(En). Or, we could write OpE with ⋃n∈ℕ since the OpE(n) are pairwise disjoint when E≠∅.

Languages

A language L is a set of symbols, with the data of the intended arity ns∈ℕ of each s∈L. For any set E, let

LE = ∐s∈L Ens

Then ∀A⊂E, ∀(s,x)∈LE, (s,x) ∈ LA ⇔ Im x ⊂ A.

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

∏s∈L ℘(Ens) ⥬ ℘(LE).

For any function f : E → F, let Lf : LE → LF defined by (s,x) ↦ (s,f⚬x). Then

LIdE = IdLE
∀fncf,g, Im f ⊂ Dom g ⇒ L(g⚬f) = Lg ⚬ Lf
Inj f ⇒ Inj Lf
Im Lf = LIm 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 Lf⋆ = (Lf)⋆. Then,

∀A⊂E, Lf[LA] = L(f[A])
∀B⊂F, Lf⋆(LB) = L(f⋆(B))

Relational systems

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

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

sE = {x∈Ens | s(x)} = E⃗(s)
E = {(s,x)∈LE | s(x)} = ∐s∈L sE.

Morphisms

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

f ∈ MorL(E,F) ⇔ ∀(s,x)∈E, (s,f⚬x)∈F
⇔ (∀s∈L,∀x∈Ens, s(x) ⇒ s(f⚬x))
⇔ Lf[E] ⊂ F ⇔ E ⊂ (Lf)⋆F.

Concrete categories

The concept of concrete category is what remains of a class of systems with their morphisms, when we forget which are the structures that the morphisms are preserving (as we will see this list of structures can be extended without affecting the sets of morphisms). Let us formalize concrete categories as made of the following data (making this slightly "more concrete" than the official concept of concrete category from other authors)
satisfying the following axioms:
The last condition is easily verified for L-morphisms : ∀(s,x)∈E, (s,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) = FE.

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 L-systems, 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 sE ⊂ Ens 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∈sE, f⚬x∈sF. From definitions, each symbol in a language L is preserved in any category of L-systems.
In any given category of L-systems, or any concrete category with a given list L of preserved interpreted symbols, any further invariant structure whose defining formula only uses symbols in L and logical symbols ∧,∨,0,1,=,∃, is preserved.
Proof. For any L-morphism f∈MorL(E,F), In particular: 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:

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 = (Ei)i∈τ, or as a set E with a function tE : 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 tE (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):

3.3. Algebras

Algebras and their morphisms

Given an algebraic language L, an L-algebra is the data (E,φ) of a set E with an L-algebraic structure φ : LE → E, sum of a family of interpretations of each symbol s∈L as an operation φ⃗(s) ∈ OpE(ns).
Again, we shall usually consider a class of L-algebras 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 :

sE : Ens → E
φE = ∐s∈L sE : LE → E

(but these sE cannot be the restrictions of a common ns-ary operator to each E, if we want to let constant symbols r and s interpreted in algebras E and F such that rE = sE but rF ≠ sF).
Algebras form a concrete category with the following sets of morphisms. For any L-algebras E, F,

MorL(E,F) = {f∈FE | ∀(s,x)∈LE, sF(f⚬x) = f(sE(x))} = {f∈FE| φF⚬Lf = f⚬φE}.

When c∈L is a constant symbol (nc = 0), this condition on f says f(cE) = cF.

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 ns' = ns+1, so that

L'E ⇌ ∐s∈L Ens×E ⇌ LE × E = {((s,x),y) | s∈L ∧ x∈Ens ∧ y∈E}.
∐s∈L Gr sE ⇌ Gr φE ⊂ LE × E

Let us call L-system any set E with a structure formalized as E ⊂ LE × E.
All concepts defined for relational systems are equally applicable through this canonical bijection.

Qualities of systems with algebraic languages

Further properties of L-systems (E, E) will be named after the qualities of the relation E: let us qualify (E, E) asThe concept of morphism between algebras (E, φE), (F, φF) is the particular case of the one between systems when they are algebraic :

∀f∈FE, (∀(x,y)∈Gr φE, (Lf(x),f(y)) ∈ Gr φF) ⇔ (∀x∈LE, φF(Lf(x)) = f(φE(x))).

Similarly, between a partial algebra (E, Gr φE) and an injective system (F, tGr ψF), sets of morphisms are defined by

MorL(E,F) = {f∈FE | Im f⚬φE ⊂ Dom ψF ∧ Lf|Dom φE = ψF⚬f⚬φE}
MorL(F,E) = {f∈EF | Im Lf⚬ψF ⊂ Dom φE ∧ φE⚬Lf⚬ψF = f|Dom ψF}

If there exists a injective morphism from E to F then If there exists a surjective morphism from E to F then

Stable subsets and subalgebras

Any subset A⊂E of an L-system (E, E), forms a system with structure A = E ∩ (LA × A). If E is functional or injective then A has the same property.
We shall say that A is L-stable, if E⋆(LA) ⊂ A. The set of stable subsets of E is written SubL E:

SubL E = {A⊂E | E⋆(LA) ⊂ A} = {A⊂E | ∀((s,x),y)∈E, Im x⊂A ⇒ y∈A}.

We have E ∈ SubL E.
If E is serial and A is L-stable then A is serial.
If E is algebraic and A is L-stable then A is algebraic, thus called an L-subalgebra of E. As an L-algebra, its structure is φA = φE|LA.
If a formula of the form (∀(variables), formula without binder) is true in an L-algebra, then it is true in each of its L-subalgebras.

Diverse properties of stability

Intersections of stable subsets. ∀X ⊂ SubLE, ⋂X ∈ SubL E where ⋂X ≝ {x∈E | ∀B∈X, x∈B}.

Proof: ∀(x,y)∈E, x∈L⋂X ⇒ (∀B∈X, x∈LB ∴ y∈B) ⇒ y∈⋂X. ∎

Other way: E⋆(L⋂X) = E⋆(⋂B∈X LB) ⊂ ⋂B∈X E⋆(LB) ⊂ ⋂X.

Stable set generated by a subset. ∀A⊂E, we denote 〈A〉L,E or simply 〈A〉L, the smallest L-stable subset of E including A (called L-subalgebra of E generated by A if E is an algebra):

〈A〉L = {x∈E | ∀B∈ SubLE, A⊂B ⇒ x∈B} = ⋂{B∈ SubLE | A⊂B} ∈ SubLE

For fixed E and L, the function A↦〈A〉L is the closure, with image SubLE, from the relation ∈ between E and SubLE:

∀X⊂E, ∀Y⊂SubLE, X ⊂ ⋂Y ⇔ (∀B∈Y, X⊂B) ⇔ Y ⊂ {B∈ SubLE | 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 L-morphisms f,g∈MorL(E,F) from an L-system E to a partial L-algebra F, is L-stable.

Proof : LEq(f, g) = {(s,x)∈LE | f⚬x = g⚬x} = {x∈LE | Lf(x) = Lg(x)}
∀(x,y)∈E, (Lf(x) = Lg(x) ∧ (Lf(x), f(y)) ∈ F ∧ (Lg(x), g(y)) ∈ F) ⇒ f(y) = g(y). ∎
Proof when F is an algebra : ∀(x,y)∈E, Lf(x) = Lg(x) ⇒ f(y) = φF(Lf(x)) = g(y).

Minimal systems

For any L-system E, its minimal stable subset is defined as

MinLE = 〈∅〉L,E = ⋂ SubL E ∈ SubL E.

It is called minimal subalgebra if E is an L-algebra.

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

For any minimal L-system E and any partial L-algebra F, !: MorL(E,F).

For any L-system E and any A⊂E,

For the last property, we already know MinL A ⊂ A ∩ MinL E; for the converse, using MinL A ∈ SubL A,
E⋆A ⊂ LA ⇒ MinL A ∪ (E\A) ∈ SubL E ⇒ MinL E ⊂ MinL A ∪ (E\A) ⇒ A ∩ MinL E ⊂ MinL A.∎

Cantor-Bernstein 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 non-trivial if it differs from IdE.

An automorphism of E is an isomorphism of E to itself:

Automorphism ⇔ (Endomorphism ∧ Isomorphism)

Embeddings

Let L a relational language, and two L-systems E and F.
A relation symbol r interpreted as rE in E and rF in F is called strongly preserved by a function f ∈ FE, if both r and ¬r are preserved :

∀x∈Enr, x∈rE ⇔ f⚬x∈rF.

If f ∈ MorL(E,F) strongly preserves all structures (E = Lf⋆(F)), it will be called a pre-embedding. The construction of the order quotient of a preorder (2.9) forms a general example of pre-embedding.
An embedding is an injective pre-embedding. Injectivity can be made a consequence of the pre-embedding 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 pre-embedding 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 ∩ LA. It is the only structure on A such that, equivalently

Thus any f ∈ MorL(E,F) is the composite of 2 morphisms IdA⚬f where A = Im f and f ∈ MorL(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 IdA∈MorL(A,F), we deduce for all systems N, MorL(A,N) ⊂ {g|A | g∈MorL(F,N)} but generally without equality (details in 3.8).

Elementary embeddings

Pre-embeddings 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 first-order 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 IdA : 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.

Non-surjective elementary embeddings, and more generally the diversity of elementarily equivalent but non-isomorphic systems, play special roles in high-level studies of the foundations of mathematics, as we shall see with Skolem's paradox and non-standard models of arithmetic. However they are ignored by the most usual practice of mathematics, because of how far-fetched (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 :

The Galois connection (End, Inv)

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

∀M⊂EE, ∀F⊂℘(E), M ⊂ EndFE ⇔ (∀f∈M, ∀A∈F, f[A] ⊂ A) ⇔ F ⊂ SubME.

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

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

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 ∈ MorL(E,F) between L-systems as full if

∀x∈LE, ∀y∈F, (Lf(x),y) ∈ F ⇒ ∃z∈E, f(z) = y ∧ (x,z)∈E.

Equivalently, ∀A⊂LE, f[E⋆(A)] = F⋆(Lf[A]) which implies ∀A⊂E, f[E⋆(LA)] = 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⚬Lf = f⚬φE ∧ Inj f) ⇒ ∀(x,y)∈LE×E, f(y) = φF(Lf(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 pre-embedding and (E is surjective, or some sE is injective for one of its arguments) then f is injective.
Bijective morphisms between algebras are isomorphisms. This can also be deduced by

(Lf)-1 = L(f -1) ∴ φE ⚬ Lf -1 = f -1 ⚬ f ⚬ φE ⚬ Lf -1 = f -1 ⚬ φF ⚬ Lf ⚬ Lf -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⋆(LA) ⊂ A ⇒ F⋆(L(f[A])) ⊂ f[A]
∀A∈ SubLE, f[A] ∈ SubLF

In particular,

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

Proof : φF[LIm f] = φF[Im Lf] = Im (f⚬φE) ⊂ Im f ∎
Also, the image of a morphism from an algebra to a partial algebra is stable and an algebra.

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

Proof. Let A=f⋆B.
For L-algebras, ∀(s,x)∈LA, f⚬x ∈ Bns∴ f(sE(x)) = sF(f⚬x) ∈B ∴ sE(x)∈A.
For L-systems, ∀(x,y)∈E, (Lf(x),f(y))∈F∴ (x∈LA ⇒ Lf(x)∈LB ⇒ f(y)∈B ⇒ y∈A).∎

Proposition. For any L-systems E, F, ∀f ∈MorL(E,F),

  1. f [MinLE] is minimal (thus f [MinLE] ⊂ MinLF).
  2. ∀A⊂E, f[〈A〉L] = 〈f[A]〉L,f[〈A〉L] ⊂ 〈f[A]〉L
Proof of 1. M = MinLE ⇒ ∀B ∈ SubL f[M], f⋆(B) ∈ SubL 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 [MinLE] = MinLF
∀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 EE of all transformations of E, seen as an algebra with two operations: the constant Id, and the binary operation ⚬ of composition.
A transformation monoid of E is a {Id,⚬}-algebra M ∈ Sub{Id,⚬}EE of transformations of E : 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 Both equalities in the identity axiom may be taken separately, forming two different concepts : 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,▪)), 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').

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

f(e) = e'
∀a,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 sub-monoids as obviously e∈C(A).
This can be understood as an intersection of submonoids in the case of a transformation monoid M⊂XX :

∀A⊂M, CM(A) = M ∩ EndA 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:

∘ : 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 : 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 re-reading 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, XX) : Examples:

Acts as algebraic structures

For any sets M, X with M-algebra 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 ∈ MorM(M,X) ⇔ ∀a,b∈M, (a•b)⋅x = a⋅(b⋅x)
•⃖e = IdM ⇔ (∀a∈M, a•e = a) ⇒ ∀g∈ MorM(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∈XM, g = ⋅⃖x ⇔ (g ∈ MorM(M,X) ∧ g(e) = x)

⇒ expresses the axioms of action of M on X ; an M-algebra X satisfying these is called an M-set.
⇐ is implied by the last monoid axiom (•⃖e = IdM); conversely, the variant of ⇐ replacing (X, ⋅) by (M, •) implies this axiom :

(IdM ∈ MorM(M,M) ∧ IdM(e) = e) ∴ •⃖e = IdM

Effectiveness and free elements

An action of M on X is said effective if ⋅⃗ : M ↪ XX :

∀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,⚬}XX), 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 M-set (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 ∈ SubM E.
The converse is obvious.

Right actions

A right action, also called co-action, of a monoid M on a set X, is like an action with sides switched: it is an operation ⋅ : X × M → X such that
It amounts to an action of the opposite monoid, and defines an anti-morphism from M to XX.

The commutation of 2 submonoids of XX looks like an associativity formula when written as acting by opposite sides on X: a∈M acting on X commutes with b∈N co-acting 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:

∀CX, (1X)α = IdXα
∀CX,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 ∀CX,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 co-action β of a category C (forming a co-acting 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 anti-preserving compositions:

∀CX, (1X)β = IdXβ
∀CX,Y,Z, ∀f∈ Mor(X,Y), ∀g∈ Mor(Y,Z), (g∘f)β = fβ⚬gβ

In the literature, co-actions of categories are called presheafs.
Actions and co-actions of a category may be seen as typed meta-algebras with types given by its objects, and function symbols given by its morphisms.

Some constructions of actions

Given an action α of C, a sub-action of α is an action β of C defined by restriction of α to a preserved unary predicate:

∀CX, Xβ ⊂ Xα
∀CX,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

∀CX, X(M) = Mor(M,X)
∀f∈Mor(X,Y), f(M) = Hom(M, f) = ∘⃗(f)|Mor(M,X) : X(M) → Y(M)

and a co-acting category C(M) of co-action to M where

∀CX, 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 sub-action of CM (which to each X gives XM), and C(M) is a sub-co-action of CM (which to each X gives MX).

The axioms for monoids M and M-sets 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 M-set X = K(E) = E(K). As actions by composition on opposite sides commute by associativity, morphisms in the co-acting category C(K) preserve this M-structure :

∀f ∈Mor(E,F), f(K) ∈ MorM(F(K), E(K))
∀x∈X=Mor(E,K), x(K) = ⋅⃖x ∈ MorM(K(K), E(K)).

Trajectories of tuples in concrete categories

For any concrete category C and any number n∈ℕ, trajectories of the action Cn of C are preserved relations : for any fixed n-tuple t of elements of an object K, the trajectory s of t by C, interpreted as ∀CE, sE = {f⚬t | f ∈ Mor(K,E)}, is preserved.

Proof : ∀g∈Mor(E,F), ∀x∈sE, ∃f∈Mor(K,E), (x = f⚬t ∧ g⚬f ∈ Mor(K,F)) ∴ g⚬x = g⚬f⚬t ∈ sF.∎

With an inclusion between objects E ⊂ F, the so defined sE may differ from the restriction of sF 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∈EE| 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 first-order 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 = IdE 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 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 sub-monoid which is a group (while sub-monoids of group are not all groups, for example ℕ in ℤ).
The core of a monoid M, is its set of invertible elements; it is a sub-monoid of M and a group: Its subgroups are all the submonoids of M which are groups, which may then be called the subgroups of M.
Between groups, a group morphism is equivalently an {e,•,-1}-morphism, or an {e,•}-morphism, as the latter also preserve inversion. More generally any {e,•}-morphism from a group to a monoid preserves the inversion relation {(x,y) | 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 M-set X will be called regular if it is both free and generating. This means that the M-morphism ⋅⃖x is both injective and surjective, thus an M-isomorphism 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 M-set 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 M-set 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 M-set X is M-stable, and thus an M-set. It is generated by x, and stays so when replacing the language M by its image as a transformation monoid N ⊂ YY.
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 N-set). 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 anti-morphism, it switches any action ⋅ of G on X into a co-action ▪ by ∀x∈X, ∀g∈G, x▪g = g-1⋅x.
If an action of group is monogenic then every element is generating; if it is regular then every element is regular.

The Galois connection (Aut, sInv)

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

∀P⊂𝔖E, sInv P = Inv (P ∪ -P) = Inv (P) ∩ Inv(-P) ⊂ RelE
∀L⊂RelE, ∀P⊂ 𝔖E, L ⊂ sInv P ⇔ P ⊂ AutL 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 = 1E ∧ f∘g = 1F)}

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:

∀CX, ∀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 :

∀CX, ∀g,h∈Mor(F,X), f;g = f;h ⇒ g = h
∀CX, f(X) : X(F) ↪ X(E)
f(C) : C(F) ↪ C(E).

As actions by composition on opposite sides commute, an epimorphism f defines a meta-embedding between acting categories C(F) and C(E), seen as C-typed Mor-algebras. 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 = 1E 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
  1. ∃f∈Mor(E,F), f;g = 1E
  2. For any action α of C, gα is surjective (Im gα = Eα).
  3. 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 1E ∈ Im g(E).∎

Dually, f∈Mor(E,F) is a section (or section in F if the category is concrete), if, equivalently,

  1. ∃g∈Mor(F,E), f;g = 1E.
  2. For any co-action β of C, fβ is surjective (Im fβ = Eβ).
  3. f(E) is surjective, i.e. Im f(E) = End(E).
Since left invertible functions are injective, 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 b-module if b(M) : Y(M) ↔ X(M).

If b is an isomorphism then all objects are b-modules, i.e. b is an epic section, and

∀CX, (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 = 1X ∴ b;g;b = 1X;b = b;1Y ∴ g;b = 1Y.∎

Thus :

To say Y is a b-module, 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 b-module 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 b-modules, i.e. b is not a section, i.e. X is not a b-module).

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 IdX 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 Re-module, a Sy-module and a Tr-module, where the morphisms Re, Sy and Tr are respectively defined by

Similarly, antisymmetry is expressible as being a module by a non-injective morphism.

So formalized, this general case of a bijective b can be thought of as giving Z the role of a set of L-typed X-ary algebraic symbols, which for every set M gives to LM the Z-structure {((s,Lu|X),Lu(s)) | (s,u) ∈ Z×MX}, so that

(M, M) is a b-module ⇔ M ∈ SubZ LM.

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 HomY(f, X) as f may not suffice to determine Y. From there, more concepts also need this parameter: In any concrete category, any injective morphism is monic, and any morphism with image F is F-epic. 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 re-express 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 IdS : 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 meta-preordered 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 meta-preorder :

(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

(Not seen elsewhere in this very general form; but its essential content appears in a still more general form as Yoneda’s Lemma).

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

The proof essentially repeats the formulas on acts as algebraic structures, transposed. From the given small category, a family of typed algebras is formed as follows. Each u ∈ Mor(E,F) acts as ψ(u) = ∐t∈T jt ⚬ u(t) : ∐t∈T E(t) → ∐t∈TF(t).
Let us prove that ψ : Mor(E,F) ↔ MorL(E,F).
Im ψ ⊂ MorL(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 MorL(E,F) ⊂ Im ψ:
∀g∈MorL(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 EndL X for an algebra X on some language L of function symbols; any group is isomorphic to an automorphism group of such an algebra.

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): 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 : Exercise. Given two fixed sets A and B, consider the category where Does it have an initial object ? a final object ?

Eggs

(Despite its usefulness, this concept seems unnamed in the literature; this name fits well 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

∀CE, (Mor(M,E) ∋ f ↦ fα(e)) : E(M) ↔ Eα.

which easily implies that Equivalently, an egg is an initial object of the category of points of Cα where For any object M of a category C, (M, 1M) is an egg of C(M).
Dually, a co-egg of a co-acting category Cβ is an egg of the opposite acting category, i.e. a final object of its category of co-points (E,x) where x ∈ Eβ and Mor((E,x),(F,y)) = {f∈Mor(E,F) | fβ(y) = x}.

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 co-action on these powersets by preimages (Set⋆). Does it have a co-egg ?
Hint : use the numbers of elements of involved finite sets.

Embeddings in concrete categories

Let us generalize the concepts of embedding and pre-embedding from categories of relational systems to any concrete category C.
A morphism f ∈ Mor(E,F) will be called a pre-embedding if

∀CX, Mor(X,E) = {g∈EX | f⚬g ∈ Mor(X,F)}

(This formula actually implies f∈Mor(E,F)).
Equivalently, the co-egg (E, IdE) of CE is also co-egg of its sub-co-action C(f) defined by

∀CX, X(f) = {g∈EX | f⚬g ∈ Mor(X,F)}.

Then, an embedding is an injective pre-embedding, i.e. an f : E ↪ F such that, equivalently

∀CX, Mor(X,E) = {f -1⚬h | h ∈ Mor(X,F) ∧ Im h ⊂ Im f}
∀CX, {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 sub-co-action C(A) of C(F) by

∀CX, X(A) = {g∈X(F) | Im g ⊂ A}

Now let us call quasi-embedding any f∈Mor(E,F) such that (E,f) is a co-egg of C(Im f) :

∀CX, ∀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 quasi-embedding will be embeddings ; exceptions are easy to find in other categories designed for this purpose.

The diverse properties of a morphism f∈Mor(E,F) are related as follows.

  1. If Im f ⊂ A ⊂ F then
    ((E,f) is co-egg of C(A)) ⇔ (f is a quasi-embedding and ∀g∈Mor(E,F), Im g ⊂ A ⇒ Im g ⊂ Im f)
  2. Injection ⇒ (pre-embedding ⇔ quasi-embedding)
  3. Quasi-embedding ⇒ monomorphism
  4. (Monomorphism ∧ pre-embedding) ⇒ injection
  5. Section ⇒ embedding
Proofs.
  1. ∀x∈E, ϕ = (E∋y ↦ (f(y) = f(x) ? x : y)) ⇒ f ⚬ ϕ = f ⇒ (ϕ ∈ End E ∴ ϕ = IdE).
  2. ∃h∈Mor(F,E), h ⚬ f = 1E ∴ ∀g∈EX, f ⚬ g ∈ Mor(X,F) ⇒ g = h ⚬ f ⚬ g ∈ Mor(X,E).∎
Let f∈Mor(E,F) a quasi-embedding. If there exists a pre-embedding g∈Mor(X,F) with the same image Im g = Im f = A ⊂ F and ACA holds then f is an embedding.

Proof.

A subobject (X,u) of E will be qualified as embedded (resp. quasi-embedded) if u is an embedding (resp. a quasi-embedding) from X to E.

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, IdA) ≡ (E,f). (For a quasi-embedding 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)}.

Submodules

Let X,Y,F be objects of a concrete category and b∈Mor(X,Y). A subset A ⊂ F will be called b-stable if

∀g∈Mor(Y,F), Im g⚬b ⊂ A ⇒ Im g ⊂ A.

In particular, if b is surjective then all subsets of objects are b-stable.
Let us call b-submodule of an object F, any subobject (E,f) of F such that E is a b-module.
For any b-module F and f∈ Mor(E,F),
  1. If f is a pre-embedding and b is bijective then E is a b-module;
  2. If f is a quasi-embedding and Im f is b-stable then (E,f) is a b-submodule.
Proofs:
  1. ∀u∈Mor(X,E), f⚬u⚬b-1 ∈ Mor(Y,F) ∴ u⚬b-1∈Mor(Y,E).
  2. ∀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

Products of actions

Given a family of actions (αi)i∈I of a category C, their product is an action β of C defined by

∀CX, Xβ = ∏i∈I Xαi
∀CX,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(xi) = yi

Products of families of co-actions are defined in the same way.
The action CM mentioned in 3.6 was the constant M-ary product of the primitive action of C.

Products in categories

A product of a family (Ei)i∈I of objects in a category C, written C∏i∈I Ei, is a co-egg (P, π) of the product of co-actions C(Ei), thus made of an object P with π ∈ ∏i∈I Mor(P,Ei) such that all f ↦ (πi∘f)i∈I are bijective :

∀CF, ⊓i∈I πi(F) : P(F) ↔ ∏i∈I Ei(F)

The products in C of the empty family (I = ∅) are the final objects of C.

The product in the category of sets, coincides with the product of sets (⊓ : ∏i∈I EiF ⥬ PF).

Products in concrete categories

In many concrete categories, any family of objects has a product (P, π) whose role can usually be played by the product of sets P = ∏i∈I Ei with its natural family of projections π = ⊓ IdP.
Then in particular, final objets are singletons (even if other, non-isomorphic singletons may be objects).
Namely, given any product (P, π), this preferable convention is possible when ⊓π : P ↔ ∏i∈I Ei, transferring the role of P to ∏i∈I Ei by this bijection. (Its injectivity already implies for any F, Inj ⊓i∈I πi(F)).
An important kind of exceptions will be categories of typed systems: with a set τ of types, a product of objects with base sets Ei = ∐t∈τ Et,i will have base set

∐t∈τ ∏i∈I Et,i.

This is identifiable to a subset of ∏i∈I Ei if I ≠ ∅ but a copy of τ if I = ∅.

On the other hand, if the product as sets P = ∏i∈I Ei 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,Ei).

The inclusion side of this equality is equivalent to (∀i∈I, πi ∈ Mor(P,Ei)). Indeed, By essential uniqueness of products, this also determines all Mor(P,F) from the category.

If C is a concrete category with products, the statement of (M,e) being an egg can be re-expressed as

∀CE, ∃!f∈Mor(M,EE), f(e) = IdE.

Products of modules

For any morphism b∈Mor(X,Y) in any category C, any product of b-modules is also a b-module.
Proof. Let (P, π) a product of a family (Ei)i∈I of b-modules. Then ∀f∈Mor(X,P), If C has products, the condition for an object M to be a b-module can be re-expressed 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)) = πx|Mor(X,M)

Products of relational systems

In a category of all relational L-systems (with fixed L), any family of systems (Ei, Ei) has a product P given by the product of sets, with structure

P = ⋂i∈I Lπi⋆(Ei) = ∐s∈L ⊓[ ∏i∈I si]

For a binary product of L-systems G = E×F these structures are

sG = {x⊓y | x∈sE ∧ y∈sF} = {z∈Gns | π0⚬z ∈sE ∧ π1⚬z ∈sF}

To check that it forms a product in this category, for any L-system F and any f = ⊓i∈I fi ∈ PF, i.e. ∀i∈I, fi = πi⚬f ∈ EiF,

f ∈ MorL(F,P) ⇔ Lf[F] ⊂ P ⇔ ∀i∈I, Lf[F] ⊂ Lπi⋆(Ei)
⇔ ∀i∈I, fi ∈ MorL(F,Ei) ⇔ ⊓f ∈ ∏i∈I MorL(F,Ei)

For a symbol s of trajectory of a tuple in a concrete category, sP ⊂ ⊓[ ∏i∈I si] with equality if ACI holds.

Products of algebras

With an algebraic language L, the product P = ∏i∈I Ei of a family of L-algebras (Ei, φi) has L-algebra structure φP defined by

(∀i∈I, πi ∈ MorL(P,Ei)) ⇔ (∀i∈I, φi⚬Lπi = πi⚬φP) ⇔ φP = ⊓i∈I φi⚬Lπi

Indeed, for any L-system F and any f = ⊓i∈I fi ∈ PF,

f ∈ MorL(F,P) ⇔ φP⚬Lf = f⚬φF ⇔ ∀i∈I, φi⚬Lfi = φi⚬Lπi⚬Lf = fi⚬φF
⇔ ∀i∈I, fi ∈ MorL(F,Ei) ⇔ ⊓f ∈ ∏i∈I MorL(F,Ei)

This comes as a particular case of product of relational systems :

∀(x,y)∈LP×P, y = φP(x) ⇔ ∀i∈I, yi = φi(Lπi(x))

The structure φP of a constant product P = EI of an L-algebra E can be written

LP∋(s,x) ↦ sE ⚬ ⊓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 ACI 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.

Intersections of subobjects

For any object F in a category C, an intersection of a family of subobjects of F, is a product of them in the category of co-points of C(F); it is then also a subobject of F. The reason to call this an "intersection" is that it is related to the "inclusion" between subobjects the same way an intersection of sets is characterized from set inclusion.

In any concrete category, any intersection of quasi-embedded subobjects is quasi-embedded, 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 b-submodules (Ei,ei) of F indexed by I can be deduced to be also a b-submodule under either additional assumption:
  1. if F is a b-module ;
  2. or, if I ≠ ∅ and b is epic.
For case 1 the easy straightforward proof is left as an exercise for the reader.
Another method, also left as an exercise, is to apply the above result on products of modules in the category of co-points of C(F). For this, the need is to prove that the condition for a subobject of F to be a b-submodule in C, is equivalent to it being a bh-module in the category of co-points of C(F) for every h∈Mor(Y,F), where bh is the copy of b in Mor((X,h∘b), (Y,h)).

Here is the proof for case 2 (a bit longer).
Let us denote (A,a) this intersection, with ϕi∈Mor(A,Ei) such that a = ei∘ϕ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,Ei), v∘b = ϕi∘u
∀j∈I, ∃!w∈Mor(Y,Ej), w∘b = ϕj∘u ∴ ej∘w∘b = ej∘ϕj∘u = a∘u = ei∘ϕi∘u = ei∘v∘b ∴ ej∘w = ei∘v.
As (A,a) is an intersection of the (Ej,ej),
∃w∈Mor(Y,A), a∘w = ei∘v ∴ a∘w∘b = ei∘v∘b = ei∘ϕ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 IdE : E↪F. Then, the intersection of a family of subobjects (Ei, Ei) of (F, F) is represented by (⋂I∈I Ei, ⋂I∈I Ei) 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 :

In the latter case, for a bijective b, the fact an intersection of b-module structures is a b-module 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 M-sets 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 M-algebra structure on every object X satisfying both axioms of action and MorM(M,X) ⊂ Mor(M,X). This structure • on M makes (M,e,•) a monoid acting on all objects and ∀CX,Y, Mor(X,Y) ⊂ MorM(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) ⊂ MorM(X,Y). Thus it actually satisfies both axioms of action.
The last monoid axiom comes as IdM fits the definition of •⃖e.
We conclude MorM(M,X) ⊂ Mor(M,X) by ∀g∈ MorM(M,X), g = ⋅⃖g(e) ∈ Mor(M,X).∎

In a concrete category with products, the definition of ⋅ can be written

⋅⃗ ∈ Mor(M,XX) ∧ ⋅⃗(e) = IdX.

Anyway ⋅⃗ ∈ MorM(M,XX).

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 co-action 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 b-modules, forming a concrete category with the same sets of morphisms between given objects :

∀CE, ∀u∈E(V), ∃!f∈Mor(K,E), f⚬b = u

Seeing V as a set of variables and K as a set of V-ary operation symbols, each object E of C, being a b-module, gets a partial K-algebra structure φE with domain K×E(V) defined for each s∈K as the trajectory of (b,s):

∀CE, ∀u∈E(V), φ⃖E(u) = ℩{f∈Mor(K,E) | f⚬b = u} = b(E)-1(u)
∴ Mor(K,E) = {φ⃖E(u) | u∈E(V)}
∀CE,F, Mor(E,F) ⊂ MorK(E,F)

On a product of b-modules, this K-structure 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 MorK(K,E), once K is given a proper K-structure. 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) = {IdK} gives to K its smallest trajectories-defined K-structure {((s,b),s) | s∈K}. This gives the greatest candidate MorK(K,E), equal to Mor(K,E); but the reverse inclusion Mor(K,E) ⊂ MorK(K,E) is another natural requirement (preservation of the K-structure). So the equality is necessary.

For φE to be algebraic, we shall assume V to be structureless, which means ∀E, E(V) = EV. For this to hold with K-morphisms (MorK(V,E) = EV),

With a structureless V, a non-injective b would only let singletons and ∅ as possible objects in C. Excluding this case, we usually take b = IdV : 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∈KV, such that all objects in C are b-modules; equivalently, these are the elements in UV having a unique morphism to any element in CV.
If moreover K is in C then b is called a basis of K in C. Equivalently, (K,b) is an egg of CV. 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) V-ary operation in objects of C, the element s' = sK(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' = sK(x) for any injective substitution of variables x : Vns ↪ V. Such a s' plays the same role as s with unused extra variables (∀CE, ∀u∈EV, s'E(u) = sE(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 (Ei)i∈I of objects of C, written

(K, j) : C∐i∈I Ei

is an egg (K, j) of the product of actions C(Ei), thus an object K with j ∈ ∏i∈I Mor(Ei, K) making all f ↦ (f∘ji)i∈I bijective :

∀CF, ⊓i∈I ji (F) : K(F) ↔ ∏i∈I Ei (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 FEi ⥬ 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 Lji[Ei].

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 ji 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 V-ary 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 jx are sections, as the set of left inverses of jx has a natural bijection with {u∈MV | u(x) = e} (while the components of j in non-constant 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 Ei of objects Ei with respective basis bi : Vi → Ei, is an object with a basis indexed by the disjoint union ∐i∈I Vi of these bases.

Equational systems

Let us specify the above by taking an algebraic language L and a category U of L-systems with Mor = MorL.
Let us call L-equational system any L-system K with a b ∈ KV, such that 〈Im b〉L = K. This implies
  1. Any L-stable subset of an L-system is b-stable
  2. Thus, any L-stable subset of a b-module is a b-module.
  3. For any partial L-algebra E, Inj b(E), i.e. ∀u∈EV, !g∈MorL(K,E), g⚬b = u.
Proof of 3. By stability of equalizers, ∀u∈EV, ∀g,h∈MorL(K,E),
g⚬b = u = h⚬b ⇒ Im b ⊂ {x∈K | g(x) = h(x)} ∈ SubLK ⇒ g = h.∎

So, equational systems usually aim 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 L-structure of V to be empty.

Examples Beyond equational systems, the concept of module by some b ∈ MorL(X,Y) where 〈Im b〉L = Y but X has non-empty 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 L-terms as L-systems, 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

∀grR,S, R;S = {(x0,y1) | (x,y)∈R×S ∧ x1=y0}
∀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 (1E = 𝛿E = Gr IdE).
(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 non-functional cases).
This category faithfully acts by direct images (⋆) on the powersets of its objects, and co-acts 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 Ei is given by their union, with the morphisms 𝛿Ei from each Ei 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 re-expressed in terms of composition: ∀R⊂E×F, ∀A⊂E, ∀B⊂F,

＊×(R⋆A) = (＊×A);R
(R⋆B)×＊ = R;(B×＊)

By associativity of composition, they form a third kind of Galois connection:

(＊×A);R;(B×＊) = ∅ ⇔ A ∩ R⋆(B) = ∅ ⇔ B ∩ R⋆(A) = ∅
(∁F⚬R⋆, ∁E⚬R⋆) ∈ Gal(℘(E), ℘(F))
(R⋆, ∁E⚬R⋆⚬∁F) ∈ Gal+(℘(E), ℘(F))

Re-expressing 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: ∀grR,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 Ri indexed by I and any graph T,

T;⋃i∈I Ri = ⋃i∈I T;Ri
T⚬⋃i∈I Ri = ⋃i∈I T⚬Ri

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)), ℘(EE)) introduced in 3.4, is equivalent to that of single relations R ⊂ E2 (non-functional structures named by a single function symbol) in the Galois connection (Po, Sub)∈ Gal(℘(℘(E)), ℘(E2)) defined as relating any A⊂E to (x,y)∈E2 by (x∈A ⇒ y∈A):

A ∈ SubR E ⇔ R⋆A ⊂ A ⇔ (∀(x,y)∈R, x∈A ⇒ y∈A) ⇔ ∁E A ∈ SubtR E

Indeed any set of transformations can be replaced by the union of their graphs; inversely, any (x,y)∈E2 can be replaced by

E ∋ z ↦ (z=x ? y : z).

The set Im Po of closed elements of ℘(E2) 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×E|x∈A}. Namely, ∈⃗ defines a pre-embedding from (E,Po(S)) to (℘(S),⊂).

The closure Po(SubRE) of any R ⊂ E2 is called the preorder on E generated by R; we shall write it ⌈R⌉.

Generated stable subsets

Lemma. Any union of R-stable subsets is R-stable.
(This does not generalize to structures of other arities).

First proof. (∀i∈I, R⋆Ai ⊂ Ai) ⇒ R⋆⋃i∈I Ai = ⋃i∈I R⋆Ai ⊂ ⋃i∈I Ai ∎
Second proof. Use A ∈ SubR E ⇔ ∁E A ∈ SubtR 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∈SubRE, 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 ∈ SubR 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⊂E2, ⌈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⊂E2, the smallest transitive T⊂E2 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⌉.∎

Well-founded relations

A relation R ⊂ E2 is called well-founded if ∀A⊂E, A ⊂ R⋆A ⇒ A = ∅.
This does not depend on E, and implies that any S ⊂ R is also well-founded.
Any well-founded relation is irreflexive : ∀x,¬{x}⊂R⋆{x}.

Proposition. The transitive closure T of a well-founded relation R is well-founded.

Proof. If R ⊂ E2 is well-founded, T = R⚬P and P = 𝛿E ∪ T (namely, P=⌈R⌉), then T is well-founded:

∀A⊂E, A ⊂ T⋆A ⇒ P⋆A = A∪ T⋆A = R⋆P⋆A = ∅ ∎

Note (possible exercise): if R is well-founded then actually !P, P = 𝛿E ∪ R⚬P.

Proposition. If R is well-founded 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 well-founded R can also be deduced by ∀x,y,¬{x,y}⊂R⋆{x,y})

Well-order

A relation R ⊂ E2 is called a strict well-order on E if

∀A⊂E, A = ∅ ∨ ∃!:A\(R⋆A)

It is easy to see that any strict well-order is a well-founded strict total order; conversely, any well-founded R ⊂ E2 whose complement ∁E2 R is antisymmetric, is a strict well-order on E.
Given that the corresponding total order ≤ equals ∁E2 tR, the condition for a relation ≤ to be a well-order, which means a total order whose strict version is a strict well-order 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 well-order 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 first-order foundations
5. Second-order foundations
6. Foundations of Geometry