3.11. Basis

Eggs as acting monoids

For any monoid (M,e, •), the eggs of the category of M-sets are (M, e) and other regular elements.

Conversely, for any egg (M,e) of a concrete category, seeing M as a set of function symbols, there is a unique M-algebra structure on every object X satisfying both axioms of action and MorM(M,X) ⊂ Mor(M,X). This structure • on M makes (M,e,•) a monoid acting on all objects and ∀CX,Y, Mor(X,Y) ⊂ MorM(X,Y), with equality for X = M.

This can be seen as another use of Yoneda's lemma, but let us write a separate proof.
The hypotheses imply ∀x∈X, ⋅⃖x ∈ Mor(M,X) ∧ ⋅⃖x(e) = x.
As (M,e) is an egg, this defines the structure ⋅ on X interpreting each a∈M as the trajectory of (e,a). Thus ∀X,Y, Mor(X,Y) ⊂ MorM(X,Y). Thus it actually satisfies both axioms of action.
The last monoid axiom comes as IdM fits the definition of •⃖e.
We conclude MorM(M,X) ⊂ Mor(M,X) by ∀g∈ MorM(M,X), g = ⋅⃖g(e) ∈ Mor(M,X).∎

In a concrete category with products, the definition of ⋅ can be written

⋅⃗ ∈ Mor(M,XX) ∧ ⋅⃗(e) = IdX.

Anyway ⋅⃗ ∈ MorM(M,XX).

This monoid (M,e,•) is essentially the opposite of the monoid End(M). Indeed

∀x,y∈M, •⃖x ∈ End(M) ∧ •⃖y ∈ End(M) ∧ •⃖x ⚬ •⃖y (e) = •⃖x(y) = y•x.

For any object M of a category C, the action of the egg M(M) of C(M) on each object E(M) coincides with the co-action of End(M) on Mor(M,E) by composition.

Algebraic structures on modules

The role of an egg as a set of function symbols in a concrete category, has diverse generalizations giving sets of operation symbols interpreted as algebraic structures on objects.
For the most general case, consider a concrete category U, a morphism b∈ Mor(V,K), and a class C of b-modules, forming a concrete category with the same sets of morphisms between given objects :

∀CE, ∀u∈E(V), ∃!f∈Mor(K,E), f⚬b = u

Seeing V as a set of variables and K as a set of V-ary operation symbols, each object E of C, being a b-module, gets a partial K-algebra structure φE with domain K×E(V) defined for each s∈K as the trajectory of (b,s):

∀CE, ∀u∈E(V), φ⃖E(u) = ℩{f∈Mor(K,E) | f⚬b = u} = b(E)-1(u)
∴ Mor(K,E) = {φ⃖E(u) | u∈E(V)}
∀CE,F, Mor(E,F) ⊂ MorK(E,F)

On a product of b-modules, this K-structure is the product of those on components, independently of the axiom of choice.
Elements of Im b play the role of projection symbols (∀x∈V, πx = b(x)), behaving as such in C.

As Mor(K,E) was expressed from φE, it will more precisely coincide with MorK(K,E), once K is given a proper K-structure. A minimal natural candidate is the trajectory of (b,s), which depends on End(K); but the choice of End(K) (fitting axioms of categories with fixed Mor(K,E)) will not matter.
Indeed, the smallest End(K) = {IdK} gives to K its smallest trajectories-defined K-structure {((s,b),s) | s∈K}. This gives the greatest candidate MorK(K,E), equal to Mor(K,E); but the reverse inclusion Mor(K,E) ⊂ MorK(K,E) is another natural requirement (preservation of the K-structure). So the equality is necessary.

For φE to be algebraic, we shall assume V to be structureless, which means ∀E, E(V) = EV. For this to hold with K-morphisms (MorK(V,E) = EV),

With a structureless V, a non-injective b would only let singletons and ∅ as possible objects in C. Excluding this case, we usually take b = IdV : V↪K, so that f⚬b = f|V.

Basis

From the above with fixed choices of U, C and a structureless V, let b and K vary : let B be the class of (K,b) where K is in U and b∈KV, such that all objects in C are b-modules; equivalently, these are the elements in UV having a unique morphism to any element in CV.
If moreover K is in C then b is called a basis of K in C. Equivalently, (K,b) is an egg of CV. Then it is a final object of B.

For any object K in C with a chosen basis b, and any possible symbol s of (preserved) V-ary operation in objects of C, the element s' = sK(b) ∈ K is the unique element of K whose role of operation in all objects of C (trajectory of (b,s')) coincides with s. In particular for any (X,a) in B and any s∈X, this s' is the image of s by the unique morphism from (X,a) to (K,b).

Any operation s with lower arity also has a copy s' = sK(x) for any injective substitution of variables x : Vns ↪ V. Such a s' plays the same role as s with unused extra variables (∀CE, ∀u∈EV, s'E(u) = sE(u⚬x)), except for the inability of languages without constants to replace the role of a constant symbol to exclude ∅ (the empty algebra) from the considered category.

Coproducts

Similarly to products with sides reversed, a coproduct in C of a family (Ei)i∈I of objects of C, written

(K, j) : C∐i∈I Ei

is an egg (K, j) of the product of actions C(Ei), thus an object K with j ∈ ∏i∈I Mor(Ei, K) making all f ↦ (f∘ji)i∈I bijective :

∀CF, ⊓i∈I ji (F) : K(F) ↔ ∏i∈I Ei (F)

The coproducts in C of the empty family are the initial objects of C.
While the general definions of product and coproduct only determine their isomorphism classes, we shall usually speak of the product and the coproduct of any family of objects in explicitly described categories, to refer to the most natural explicit construction of a specific representative of each such class, which could be written in the given category.

The category of sets has coproducts given by the disjoint union with its natural injections (∏i∈I FEi ⥬ F∐i∈I Ei).
In categories of all relational systems with fixed language L, the coproduct is given by the disjoint union, with structure ⋃i∈I Lji[Ei].

In other concrete categories, the underlying sets of coproducts may differ from disjoint unions, more often than those of products differ from the products of sets. The injectivity of each ji often remains, but already fails in categories of partial algebras (4.2).

Basis and coproducts

For any objects M, K of any category C, and any b ∈ Mor(M,K)V,

(b is a basis of K(M) in C(M)) ⇔ (K, b) : C∐x∈V M.

Similarly in a concrete category with an egg (M, e) : a constant V-ary coproduct (K,j) : C∐x∈V M is an object K with basis b = ⊓j(e). Equivalently, j = (⋅⃖b(x))x∈V where ⋅ is the action of (M, e).
These jx are sections, as the set of left inverses of jx has a natural bijection with {u∈MV | u(x) = e} (while the components of j in non-constant coproducts are not always sections).

Products and coproducts have associativity properties like first seen with the product of sets : any product of products of objects, is naturally isomorphic to a simple product indexed by the disjoint union of indexing sets; and the same for coproducts.
In particular, a coproduct (K, j) : C∐i∈I Ei of objects Ei with respective basis bi : Vi → Ei, is an object with a basis indexed by the disjoint union ∐i∈I Vi of these bases.

Equational systems

Let us specify the above by taking an algebraic language L and a category U of L-systems with Mor = MorL.
Let us call L-equational system any data of a structureless set V, an L-system K and a b ∈ KV, such that 〈Im b〉L = K. This implies
  1. Any L-stable subset of an L-system is b-stable
  2. Thus, any L-stable subset of a b-module is a b-module.
  3. For any partial L-algebra E, Inj b(E), i.e. ∀u∈EV, !g∈MorL(K,E), g⚬b = u.
Proof of 3. By stability of equalizers, ∀u∈EV, ∀g,h∈MorL(K,E),
g⚬b = u = h⚬b ⇒ Im b ⊂ {x∈K | g(x) = h(x)} ∈ SubLK ⇒ g = h.∎

So, equational systems may be used to distinguish among algebras (or partial algebras) E, those for which the injection b(E) is also surjective. In many cases L has no projection symbol, obliging the chosen L-structure of V to be empty.

Examples Beyond equational systems, the concept of module by some b ∈ MorL(X,Y) where 〈Im b〉L = Y but X has non-empty structure, is an expression of axioms using ⇒, such as left cancellativity (of a constant, or of all elements). The systematic understanding of these facts relies on the formalization of L-terms as L-systems, which will be presented in 4.1 and 4.3.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : 3.11. Bases