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 ggf = f)

A function f is called idempotent if, equivalently,

Im f ⊂ Dom fff = f
Im f = Fix f

Monotone, antitone, strictly monotone functions

Between ordered sets E and F, a function f : EF 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 fFE and gEF are both monotone (resp. both antitone) and gf = 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 (fg ⇔ ∀xE, f(x) ≤ g(x)).
Then, ∀f,gFE, ∀hEG, fgfhgh, i.e. ffh 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 uGF is monotone (resp. antitone) then FEfufGE is monotone (resp. antitone).
In an ordered set E, a function fEE is said extensive if IdEf, i.e. xE, xf(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|∀xE, ∀yF, xE⊤(y) ⇔ yF ⊥(x)} = tGal(F,E)
Gal+(E,F) = {(u,v) ∈ FE×EF|∀xE, ∀yF, xE v(y) ⇔ u(x) ≤F y} = Gal(E,F)

Galois connections between powersets. Any RX×Y defines (⊥,⊤) ∈ Gal(℘(X),℘(Y)) by

AX, ⊥(A) = {yY | ∀xA, x R y} = xA R(x)
BY, ⊤(B) = {xX | ∀yB, x R y} = {xX | BR(x)}

Then, ⊥(∅) = Y and ⊤(∅) = X.
Proof : ∀AX, ∀BFA ⊂ ⊤(B) ⇔ A×BRB ⊂ ⊥(A).∎
This is actually a bijection: Gal(℘(X),℘(Y)) ⥬ ℘(X×Y). Proof: Monotone Galois connections between powersets. Any relation RX×Y defines a (u,v) ∈ Gal+(℘(X),℘(Y)) by

AX, u(A) = {yY | ∃xA, x R y} = xA R(x)
BY, v(B) = {xX | R(x) ⊂ B}.

This way, the graph of any function f : XY defines

(Af[A], Bf*(B)) ∈ Gal+(℘(X),℘(Y))

Properties of Galois connections

Lemma. ∀⊥ ∈ FE, !⊤ ∈ EF,(⊥,⊤) ∈ Gal(E,F).
Proof: ∀⊤ ∈ EF, (⊥,⊤) ∈ Gal(E,F) ⇔ ≤E⚬⊤ =⊥*⚬ ≤F, while ≤E is injective.∎

Properties. 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.) ∀xE, ⊥(x) ≤ ⊥(x) ∴ x ≤ ⊤(⊥(x)).
(1. ⇒ 2.) ∀x,yE, xy ≤ ⊤(⊥(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′) ⇔ (∀yF, 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: ∀xE, ∀yF, 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, vu is extensive and uv ≤ IdF.

Characterization of closures

A closure of an ordered set E is an fEE such that, equivalently:
  1. There exists a set F and an (u,v) ∈ Gal(E,F) or Gal+(E,F) such that vu=f
  2. f is monotone, idempotent and extensive
  3. xE, ∀y∈ Im f, xyf(x) ≤ y, i.e. (f, IdK) ∈ Gal+(E,K) where K = Im f
Proof of equivalence:

3. ⇒ 1. ⇒ 2.
For 2. ⇒ 3., ∀xE,∀yK, xf(x) ≤ yxyf(x) ≤ f(y) = y. ∎

Notes:

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 first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : Correspondances de Galois