3. Algebra 1

3.1. Relational systems and concrete categories

Let us formalize the concept of system, focusing for simplicity on those with only one type. For any number n∈ℕ and any set E, let us denote We then denote the set of all operations OpE = ⋃n∈ℕ OpE(n), and that of all relations RelE = ∐n∈ℕ ℘(En).


A language L is a set of symbols, with the data of the intended arity ns∈ℕ of each sL. For any set E, let

LE = ∐sL Ens

A relational language is a language L of relation symbols, where each sL aims to be interpreted in any set E as an ns-ary relation. These form a family called an L-structure on E, element of

sL ℘(Ens) ≅ ℘(LE)

Relational systems

A relational system with language L, or L-system, is the data (E,E) of a set E with an L-structure ELE.

The case of an algebraic language, whose symbols aim to represent operations, will be studied in 3.2.

Most often, we shall only use one L-structure on each set, so that E can be treated as implicit, determined by E. Precisely, let us imagine given a class of L-systems where each E is the intersection of LE with a fixed class of (s,x), denoted as a predicate s(x) for how it is naturally curried: each symbol sL is interpreted in each system E as the ns-ary relation sE somehow independent of E,

sE = {xEns | s(x)} = E(s)
E = {(s,x)∈LE | s(x)} = ∐sL sE.

For any function f : EF, let Lf : LELF defined by (s,x) ↦ (s,fx).
Im Lf = LIm f by finite choice with (AC 1)⇒(6), as arities of symbols are finite (otherwise it still goes for injective f, or using AC).
BF, (Lf)*(LB) = L(f*(B))


Between any L-systems E,F, we define the set MorL(E,F) ⊂ FE of L-morphisms from E to F by ∀fFE,

f ∈ MorL(E,F) ⇔ ∀(s,x)∈E, (r,fx)∈F
⇔ (∀sL,∀xEns, s(x) ⇒ s(fx))

Concrete categories

The concept of concrete category is what remains of a class of systems with their morphisms, when we forget which are the structures that the morphisms are preserving (as we will see this list of structures can be extended without affecting the sets of morphisms). Let us formalize concrete categories as made of the following data (making this slightly "more concrete" than the official concept of concrete category from other authors)
satisfying the following axioms:
The last condition is easily verified for L-morphisms : ∀(s,x)∈E, (s,fx)∈F ∴ (s,gfx)∈G.
A relational symbol s with the data of an interpretation sEEns in every object E of a given concrete category, is said to be preserved if all morphisms of the category are also morphisms for this symbol, i.e. ∀f∈Mor(E,F), ∀xsE, fxsF. From definitions, each symbol in a language L is preserved in any category of L-systems.

A category is small if its class of objects is a set.

The official concept of concrete category mainly differs from this by allowing different objects to have the same underlying set : in the case of relational systems, such objects are systems consisting of different choices of structures on the same set.

Preservation of some defined structures

In any given category of L-systems, or any concrete category with a given list L of preserved interpreted symbols, any further invariant structure whose defining formula only uses symbols in L and logical symbols ∧,∨,0,1,=,∃ is preserved.
Indeed, for any L-morphism f∈MorL(E,F), Thus, for any f ∈MorL(E,F), if a ground formula with language L using the only logical symbols (=,∧,∨,0,1,∃), is true in E, then it is also true in F. However morphisms may no more preserve structures defined with other symbols (¬,⇒,∀).

The above cases of 0, 1, ∨ and ∧ are mere particular cases (the nullary and binary cases) of the following:

Rebuilding structures in a concrete category.

The preserved relations of any concrete category can be generated from the following kinds of "smallest building blocks".

Proposition. In any concrete category, for any choice of n-tuple t of elements of some object K, the relation s defined in each object E as sE = {ft | f∈Mor(K,E)} is preserved.

Proof : ∀g∈Mor(E,F), ∀xsE, ∃f∈Mor(K,E), (x = ftgf∈Mor(K,F)) ∴ gx = gftsF.∎
From these definitions it might happen between objects EF that sEsFEn but we shall not face this in our use.

In a small concrete category, the preserved families of relations are precisely all choices of unions of those : each preserved s equals the union of those with t ranging over s (with K ranging over all objects).

However the class of relational systems obtained by even giving in this way "all possible structures" to the objects of an otherwise given concrete category such as topology, may still admit more morphisms than those we started with (like a closure).

Categories of typed systems

While we introduced the notion of morphism in the case of systems with a single type, it may be extended to systems with several types as well. Between systems E,F with a common list τ of types (and interpretations of a common list of structure symbols), morphisms can equivalently be conceived in the following 2 ways, apart from having to preserve all structures:

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. 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
5. Second-order foundations
6. Foundations of Geometry