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^{−})
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
Lemma. ∀⊥ ∈ F^{E}, !⊤ ∈
E^{F},(⊥,⊤) ∈ Gal(E,F).
Proof: ∀⊤ ∈ E^{F}, (⊥,⊤) ∈ Gal(E,F) ⇔
≤⃖_{E}⚬⊤ =⊥^{*}⚬ ≤⃗_{F},
while ≤⃖_{E} is injective.∎
Properties. 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
Set theory and foundations
of mathematics
1. First foundations of
mathematics
2. Set theory
3. Algebra 1
3.1. Galois connections
3.2. Relational systems
and concrete categories
3.3. Algebras
3.4. Special morphisms
3.5. Monoids and categories
3.6. Actions of monoids and categories
3.7. Invertibility and groups
3.8. Properties in categories
3.9. Initial and final objects
3.10. Products of systems
3.11. Basis
4. Arithmetic and firstorder foundations
5. Secondorder foundations
6. Foundations of Geometry
Other languages:
FR :
Correspondances de Galois