3. Algebra 1

This section on algebra will mainly (for about 80-90%) be formed of concepts extracted from the existing literature on universal algebra and category theory. Not being erudite in it, I cannot assess how new are the points and tricks I figured out myself, and for which I coined my own vocabulary and notations. I cared to form a relatively short and coherent exposition, not overloaded (as unfortunately usual in the literature) by many more complex concepts which may be less relevant to my goal of providing a solid framework for relatively basic approaches to the foundations of mathematics, geometry and physics.

3.1. Galois connection

The set of fixed points of a function f is written

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 on sets of 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).
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. 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)

General example. Any relation RX×Y defines a (⊥,⊤) ∈ 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 (as shown in below pdf): Gal(℘(X),℘(Y)) ⥬ ℘(X×Y).

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.

Closure. 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 connection
3.2. Relational systems and concrete categories
3.3. Algebras
3.4. Special morphisms
3.5. Monoids
3.6. Actions of monoids
3.7. Invertibility and groups
3.8. Categories
3.9. Initial and final objects
3.10. Products of systems
3.11. Eggs, basis and varieties
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry