3.9. Eggs, basis, clones and varieties


Let us generalize the concept of free and generating element from actions of monoids to actions of categories. For any concrete category C, or more generally any category with a given action, let us call egg of C (*) an initial object (M,e) of the category where In other words, for any object E the function Mor(M,E) ∋ ff(e) is bijective to E.
For any egg of an acting category, its image in the resulting concrete category is also an egg.

Proposition. Any egg (M,e) (if that exists), can be seen in a unique way as a monoid (M,e,•) with an action on every other object X (beyond • on M itself), such that for all objects X, Y, Proof. Defining ∀xX, hx ∈ Mor(M,X) ∧ hx(e) = x, provides an M-structure on each X which interprets each aM in X as defined by the tuple (e,a). So they are preserved: Mor(X,Y) ⊂ MorM(X,Y), which implies the axioms of M-acts.
The composition in M coming as this M-structure for M = X, satisfies the same axioms.
The last axiom of monoid, he = IdM comes from the uniqueness of he obeying its definition, and ensures the reverse inclusion:
g∈MorM(M,X), g = hg(e)g ∈ Mor(M,X). ∎
This monoid (M,e,•) is essentially the opposite of the monoid End(M). Indeed for all a, bM we have ha ∈ End(M), hb ∈ End(M) and

hahb(e) = ha(b) = ba.

For any object M of a category C, the action of C defined by M has an egg (MM, 1M), with the monoid action directly given by composition. This just simplifies conventions, taking Mor(M,E) as the definition of the set underlying E on which the category acts, instead of saying they are in bijection. If C was already a concrete category with an egg (M,e) then MC is just a copy of C (with correspondence using the choice of e).

Proposition. For a monoid (M,e, •) seen as an M-set interpreting • as action, (M, e) is an egg of the category of M-sets; other eggs are the (X,x) where x is a free and generating element of X.

Proof: by properties of acts as algebraic structures and inverses, as x is free and generating in X if and only if (X,x) is isomorphic to (M,e). ∎

Basis and algebraic structures

As an egg is a language of function symbols, let us generalize this to any other arity.
A basis of an object X of a concrete or acting category C, is a family bXI such that (X,b) is an egg for the action of C giving to each object E the set EI:

uEI, ∃!f∈Mor(X,E), fb=u.

If an object with several elements exists in the category then any basis b is injective, thus can also be viewed as the subset B = Im bX (from which the view as a family can be restored taking b = IdB).
This gives X the role of the set of all possible I-ary operation symbols s interpreted in each object E and preserved in C: these are the structures defined by each (b,s) for sX, which are here functional. Its essential uniqueness means that any two basis in C which are equinumerous (a bijection between them exists), give their objects the role of the same set of operation symbols.
For any objects M, X of a category C, and any B ∈ Mor(M,X)I,

(B is a basis of MX in the concrete category MC) ⇔ (X, B) = CiI M.

Thus, given an egg (M, e), that is an object M with basis a singleton {e} where eM, an object X with basis B plays the role of the B-ary coproduct (of the constant family), CiB M, with the ji ∈ Mor(M,X) defined for each iB by ji(e) = i. These ji are sections.


Putting all arities together gives an algebraic language called the clone of C:

L = ∐n∈ℕ Ln

where each set Ln of n-ary symbols is an object of C with a chosen basis of n elements 1n = (ei,n)i<nLnn. Thus, ∀n∈ℕ, Ln = Ci<n L1.

Depending on C, a clone may exist or not, but it is essentially unique, serving as the maximal algebraic language for objects of C.

Each object E of C, gets the L-algebra structure φE = ∐n∈ℕ φE(n), where φE(n) : Ln × EnE is defined taking as ⃖φE(n) the inverse of Mor(Ln,E) ∋ ff০1n which is bijective to En because 1n is a basis in C. This definition is expressible by both axioms which extend to clones those defining the action of an egg in a category:
  1. Each ei,n acts as the i-th projection from En to E, i.e. ∀i<n, ∀uEn, ei,nu = ui.
  2. n∈ℕ, ⃖φE(n) : En → Mor(Ln,E).
This implies (for all objects E, F),

Mor(E,F) ⊂ MorL(E,F)
n∈ℕ, Mor(Ln,E) = MorL(Ln,E).

Let us recall the proof of MorL(Ln,E) ⊂ Mor(Ln,E) previously seen for n=1. From 1n being a basis of Ln and IdLn ∈ Mor(Ln,Ln), comes
  1. xLn, x = x⋅1n
Thus ∀f∈MorL(Ln,E), (∀xLn, f(x) = f(x⋅1n) = x⋅ (f০1n) ∴ f = ⃖φE(n)(f০1n) ∈ Mor(Ln,E).∎

3. implies that 1n generates Ln in the sense that 〈1nLn = Ln ∴ 〈1nL = Ln.

Abstract clones and varieties

A clone L may be conceived independently of C (like monoids are independent of their actions), as the small concrete category made of the sequence of objects (Ln)n∈ℕ, called an abstract clone. It defines on L a structure of typed algebra with types Ln and operations Generalizing the concept of action to such a typed algebra, an L-module (or representation of L), is an L-algebra M satisfying the above 1. and 2. where 2. uses MorL :

n,p∈ℕ, ∀sLp, ∀xLnp, ∀uMn, (sx) ⋅ u = s ⋅ ((xiu)i<p)

The variety of L is the category of all L-modules with Mor = MorL.
A typed algebra L = ∐n∈ℕ Ln with such symbols, is an abstract clone if each Ln satisfies the above axioms 1., 2. and 3. extending to L the axioms of monoid for L1:
As will be seen later, the general concept of variety will use algebraic languages that do not need to be abstract clones, and not even typed algebras. Roughly speaking, a variety is a category of algebras which has a clone and is equivalent to the variety of this clone. But other equivalent definitions are possible.
(*) I took the initiative to call it "egg" as I am not aware of any existing name for that concept in the literature.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of relational systems and concrete categories
3.2. Algebras
3.3. Special morphisms
3.4. Monoids
3.5. Actions of monoids
3.6. Invertibility and groups
3.7. Categories
3.8. Initial and final objects
3.9. Eggs, basis, clones and varieties
4. Arithmetic and first-order foundations