Groups, automorphisms and invariants

Inverse elements

In a monoid (M, e, •), the formula xy=e is read "x is a left inverse of y", and "y is a right inverse of x". We say x is right invertible when a right inverse y exists; similarly, y is left invertible. Seeing M as a transformation monoid by left action on itself, this xy=e becomes an invertibility of transformations :

z,tM, yz = txt = z

An element x both left invertible and right invertible is called invertible; then any left inverse y and any right inverse z of x are equal (proof: yx = e = xz y = yxz = z), and thus unique, written x-1.
Similarly in any category, the inverse of any isomorphism (= invertible morphism) is unique.
As left invertible functions are injective, left invertible elements are left cancellative:
z,tM, (yz = ytxy=e) ⇒ (z = xyz = xyt = t)
If a left invertible element is also right cancellative then it is invertible.

Any left cancellative element of a finite monoid is invertible.
Proof: it acts as an injective transformation of a finite set, thus a permutation, by which the preimage of e is a right inverse, thus an inverse.

If x commutes with an invertible element y then it also commutes with its inverse z:


An element x of a monoid is called involutive if it is its own inverse (equivalently on one or both sides): xx=e. This qualifies an element such as a transformation, regardless the choice of sub-monoid containing it (a transformation monoid).


A group is a monoid where all elements are invertible.
The set of invertible elements in any monoid, is a group : Any group is cancellative. Thus, any submonoid of a group is also cancellative, but it may not be a group. For example, ℕ is a sub-monoid of ℤ.

Subgroups. The concept of subgroup of a group, is equivalently defined as The interpretation of inversion is determined from those of • and e by the axiom (whose truth in a group implies its truth in every subgroup)

x, xx-1 = x-1x = e

The admission of inversion as a symbol, has no effect on morphisms: any morphism of monoid f from a group G to a monoid preserves the inversion relation, thus its image G' is a group, and f is a morphism of groups from G to G'. Thus, an action of a group G on a set X, can be equivalently conceived as an action of monoid, or as a group morphism from G to the symmetric group of X. By the representation theorem, any group is isomorphic to some permutation groups, among which the group of automorphisms of an algebra.

As inversion is an anti-morphism, it switches any left action ▪ of G on X into a right action • by ∀xX, ∀gG, x•g = g-1▪x.

For any set G⊂⤹E, the permutation group generated by G, is the generated subalgebra of ⤹E with these 3 symbols, and is also transformation monoid generated by G ∪ {f-1|fG}.

Proposition. Any commutative and cancellative monoid can be embedded in a commutative group.
But (according to wikipedia - I don't know any example) a cancellative monoid cannot always be embedded in a group (i.e. be isomorphic to a submonoid of a group).

The Galois connection (Aut, sInv) between structures and permutations

For any relational system E with any language L, the set of automorphisms of an L-system E, is a permutation group

AutL(E) ={f∈ EndL(E)∩⤹E|f -1∈EndL(E)}.

The automorphism group of a given system, was defined as the set of permutations which preserve all structures of its language (and thus also all other structures definable from them).
It is part of a Galois connection between powersets of

Indeed for any LR, the automorphism group AutL(E), is defined as { fB | L×{f} ⊂ I} from the relation of "strong preservation" I = ⋃n I(n)R×B where
I(n)={(r,f)∈℘(EnB |∀xEn, xrfxr}:

When extending a theory by a definition, the model is modified (as it interprets one more symbol), but keeps the interpretation of types in each model and the sets of isomorphisms between models. This is similar to the case of proofs as follows.

Now can we rebuild a theory by the return way of this Galois connection: starting with a set G of permutations of a set E, looking for the structures preserved by all permutations in G, and finding a few of them from which the others can be defined, letting G be its automorphism group ? This idea is a key to the Erlangen Program for the foundations of geometry.

So to any set GB of permutations, we associate the set of strong invariants of G,
sInv (G) = {rR |{rGI}
satisfying the characteristic property of Galois connections
LR,∀GB, L⊂sInv (G) ⇔ G⊂AutL (E)

This set sInv (G) of strong invariants (relations "strongly preserved" by all elements of G, i.e. for which elements of G are embeddings, and thus automorphisms since GB), may be smaller than the set Inv G of all (weak) invariants that are only "preserved" (for which elements of G are endomorphisms), that will be used later : GB ⇒ sInv (G) = Inv (G ∪{g-1|gG}).

For any model of a theory with several types, its automorphism group is effective on the whole system, but its action (by restriction) on each type it not always effective; then it also acts on each further type that \can be constructed from available ones (as we explained with developments of theories). Thus, constructions of new types preserve the automorphism group of the model seen as an abstract group, separately from its action on specific types.

When extending a theory by a definition, the model is modified (as it interprets one more symbol), but keeps the interpretation of types in each model and the sets of isomorphisms between models. This is similar to the case of proofs as follows.

Closures given by this connection

The composites of these functions give two closures :

For every set LR of relations (i.e. every system based on E), its closure, the set of invariants Inv(AutL(E)) ⊃ L (taking strong or weak invariants gives the same result since AutL(E) is a group), contains every relation definable from L, because isomorphisms preserve all defined structures.
Conversely, a structure r ∈ Inv(AutL(E)) can only distinguish tuples that cannot be moved one to the other by a permutation preserving each structure in L. This intuitively suggests that they are "not similar to each other for the chosen L", so that their distinction by r expresses a dissimilarity that would be expressible from structures in L. However, this reasoning is not rigorous, and the conclusion is not exactly true: both concepts of "invariants" can differ in a way we shall further comment below.

For every set GB, its closure is the automorphism group Aut(sInv G)(E) ⊃ G (the set of all permutations strongly preserving all strong invariants of G). It includes the group G' generated by G, but differs from G' .

Precisely, Aut(sInv G)(E) is the group of permutations that coincide on any n-tuple with some element of the group G' algebraically generated by G, for every number n that we accepted as an arity of a structure : denoting sInv(n)(G) = {rEn | G×{r} ⊂ I(n)},
f∈Aut(sInv(n)(G)(E) ⇔ ∀xEn, ∃ gG',  fx = gx.
Draft of proof :
For every set GB,
For every explicit natural number n = 1+...+1,
For every permutation fB,
the following formulas are equivalent:
f∈Aut(E, sInv(n)(G))
rS(n), r ∈ sInv(n)(G) ⇒ (f,r)∈R(n)
rS(n), G ⊂ Aut(E,{r}) ⇒ (f,r)∈R(n)
rS(n), G' ⊂ Aut(E,{r}) ⇒ (f,r)∈R(n)
s ∈ sInv(n)(G), ∀x1,..,xnE, s(x1,..,xn)⇔s(f(x1),...,f(xn))
sS(n), (∀gG, ∀x1,..,xnE, (x1,..,xn)∈s ⇔ (g(x1),..,g(xn))∈s) ⇒ (∀x1,..,xnE, (x1,..,xn)∈s ⇔ (f(x1),...,f(xn))∈s)
⇔( be continued) (This can be proven using orbits).
x1,..,xnE, ∃ gG', (f(x1),...,f(xn))=(g(x1),...,g(xn))

(to be completed)

Back to Set theory and foundations homepage