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 :

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₂ 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)} = ^tGal(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:

_x∈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⁻¹ = ⊤_|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.