# 5.2. First-order invariants in concrete categories

### Multiple automorphisms and models

Most geometries, except RCF, have a big group of automorphisms in each model. To produce such spaces from a framework without automorphisms (ZF with only sets and no pure elements, or second-order arithmetic), requires not only developments but also to forget some structures, and notice how some permutations then become automorphisms.

Spaces with non-trivial automorphisms will be interestingly seen as non-unique in each isomorphic class (instead of picking one to represent them all), for the following reason. Any isomorphism f between 2 systems E and F induces a bijection gfg from Aut(E) to the set of isomorphisms between E and F. Thus, a plurality of automorphisms of E means a plurality of isomorphisms between E and F. This plurality makes the difference between E and F meaningful, as an object in E may correspond to several possible ones in F, depending on the choice of isomorphism, so choosing an object in E does not mean choosing an object in F in any invariant way. By contrast, the uniqueness of isomorphism between standard models of ℕ or ℝ makes them unambiguously play the role of each other (copies of each other), making their plurality superfluous.

### The Galois connection (Aut, sInv)

For any set E, the relation of strong preservation between its set RelE of relations and its set ⤹E of permutations, defines a Galois connection (Aut, sInv) similar to (End, Inv), where sInv gives the set of strong invariants :

P⊂⤹E, sInv P = Inv (P ∪ -P) = Inv (P) ∩ Inv(-P) ⊂ RelE
L⊂RelE, ∀P⊂ ⤹E, L ⊂ sInv PP ⊂ AutL E.

For any subgroup G of ⤹E (automorphism group in any category), sInv G = Inv G.
Any relation defined by an expression with language LR without parameters is invariant by automorphisms, so is in Inv(AutL E). This means that adding it to L preserves AutL E (like other sets of isomorphisms between models).
Constructions leave unchanged the automorphism groups seen as abstract groups, providing more types on which they act.

### The double meaning of "invariance"

Unlike provability which by the completeness theorem ranges over all truths of models, definability by language L without parameters may not fill Inv(AutL(E)), for the following reason.
Structures r ∈ Inv(AutL(E)), distinguishing any tuple tr from those outside r, are those for which no element of AutL(E) can move t out. This suggests that t is not similar to anyone outside r with respect to L, unless the trouble is to choose an automorphism witnessing the similarity. But this dissimilarity, and thus r itself, may be formally inexpressible from L as it may require infinitely complex descriptions. For example, there is no nontrivial automorphism in ℝ, or in a model of second-order arithmetic, yet not all objects of an uncountable type (real numbers or sets of integers) can be defined without parameter (but, as objects, they are definable with a parameter: themselves).
Both concepts of invariance can be still reconciled in different ways:
• For first-order logic, non-trivial automorphisms may externally exist over non-standard models of second-order arithmetic, thus also non-standard real closed fields (moving undefinable real numbers to infinitely close neighbors);
• In second-order logic, we may admit "second-order" ways of defining structures where any subset of ℕ is "defined" by the infinite data of all its elements(*).
A set of axioms of a theory can be seen as a mere tool to approach an intended range of models, on the other side of the (Mod,Tru) connection. Similarly, a language may be a mere tool to approach an intended concept of invariance better defined by a group G on the other side of the (Aut, sInv) connection. Specifying the geometry of a space E by a permutation group G of E intended as Aut(E), was a core idea of Felix Klein's Erlangen Program. Thus, "invariance" in geometry will be meant by G, and equivalently qualify structures defined with parameters in ℝ or among structures over ℝ only.

Now starting with a mere concrete category of intended spaces whose class of morphisms is given by intuition, let us review methods to produce invariant structures.

### Basis and algebraic structures

We already gave the construction of all invariant relations, elements of Inv(End E) or Inv(Aut E), from the trajectories or orbits of tuples.
Algebraic structures come as functional cases of relations defined by tuples, as already seen with categories of acts and interpretations of drafts in algebras:
A basis of a space X is a subset BX such that (X,IdB) is an initial object of the category of all (E,u) where E is a space and uEB:

uEB, ∃!f∈Mor(X,E), f|B=u.

This gives X the role of the set of all possible B-ary operation symbols interpreted in each E and preserved in the given category. Its essential uniqueness means that any equinumerous basis in the same concrete category, give their spaces the role of the same set of operation symbols.
Given an egg (M, e), that is a space M with a basis of one element e, a space X with basis B plays the role of the B-ary coproduct (of the constant family), ∐iB M, with the ji ∈ Mor(M,X) defined for each iB by ji(e) = i. These ji are sections.
For any category C, any objects M, X, and any B ∈ Mor(M,X)I, (X, B) is a coproduct ∐iI M in C if and only if B is a basis of MX in the concrete category MC.

### Clones

Let us extend to all arities the concept of egg of a given concrete category C, seen as a language of function symbols, as follows (another presentation of what is usually called an abstract clone). Let us call clone of C, an algebraic language L = ∐n∈ℕ Cn, where each set Cn of n-ary symbols is an object of C with a chosen basis of n elements 1n = (ei,n)i<nCnn.
Depending on C, a clone may exist or not, but it is essentially unique, serving as the maximal algebraic language for objects of C.

Then, C1 is an egg, and each Cn is the n-ary coproduct ∐i<n C1 in C.

Each object E of C, gets the L-algebra structure φE = ∐n∈ℕ φE(n), where φE(n) : Cn × EnE is defined taking as ⃖φE(n) the inverse of Mor(Cn,E) ∋ ff০1n which is bijective to En because 1n is a basis in C. This is expressible by both axioms (extending those for categories of acts)
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(Cn,E).
This implies (for all objects E, F),

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

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

3. implies that 1n generates Cn in the sense that 〈1nCn = Cn ∴ 〈1nL = Cn.

### Varieties

One may conceive a clone L without any a priori data of a category C. First we may take as C the small category made of the sequence of objects (Cn)n∈ℕ. The structure of L, defined by the morphisms between these objects only, can be presented as that of a typed algebra, with types Cn and operation symbols:
• the constant symbols ei,n
• an L-algebra structure on each Cn, formalizable as a sequence of operations ⋅ : Cp × CnpCn for each p∈ℕ.
Between other objects, thus L-algebras, one may choose the sets of morphisms as the widest possibility Mor(E,F) = MorL(E,F).
An L-module (or representation of L), is an L-algebra M satisfying 1. and 2. where in 2., Mor is defined as MorL :

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

The category of all L-modules with Mor = MorL, that is the maximal choice of C for a given clone, is called a variety. It extends to all arities the concept of action.
We shall study later the general concept of variety, defined as the category of all L-algebras satisfying conditions eventually expressible like this one of being modules, but without assuming L to be a clone: the spaces (or other sets) with basis that L is made of, need not be one per arity; they need not belong to the given category (but are seen as additional objects to this category for making sense of the basis), and even need not be algebras (as happened with terms with respect to algebras). Instead, with a simple algebraic language L, conditions may be expressed by a list of axioms made of ∀ over equalities of L-terms. As will be shown, such categories are still qualified as varieties in the sense of having a clone ∐n∈ℕ Cn, and being identifiable with the variety of this clone; L may differ from it, but generates it in the sense that each L-algebra Cn is L-generated by (the image of) its basis, i.e. is the set of all symbols definable by n-ary L-terms (where the role of the symbols of variable is played by the symbols ei,n):

n∈ℕ, 〈1nL = Cn.

For a typed algebra L = ∐n∈ℕ Cn with the above mentioned symbols (thus made of L-algebras Cn), it is qualified as a clone if each Cn satisfies the above axioms 1., 2. and 3. :
• 1. and 2. make Cn an L-module.
• 3. makes 1n a basis of Cn in this variety, by ∀M, ∀f∈MorL(Cn,M), f = ⃖φM(n)(f০1n).
These axioms generalize the 3 axioms of monoid (as C1 is a monoid).
Equivalently, an algebraic language is a clone when, for some given class of interpretations (algebras), it is stable by definitions by terms, in the sense that any two symbols keeping the same interpretation throughout this class are confused.

We already saw two examples of varieties

• That of all L-algebras for any given algebraic language L; its clone is the sequence of term algebras with each finite arity.
• That of all monoids; its clone is made of free monoids.

(*)This bridge to Inv(AutL(E)) by means of extended kinds of "definitions" (with infinite amounts of data) has been investigated by Borner, Martin Goldstern, and Saharon Shelah : short presentation in .ps - full article.