3.7. Invertibility and groups

Permutation groups

A permutation of a set E is a bijective transformation of E.
The set 𝔖E = {f∈EE| f : E↔E} of all permutations of E, is a transformation monoid of E called the symmetric group of E.
A permutation group of a set E, is a {Id,⚬, -1}-subalgebra of 𝔖E.
In a permutation group, trajectories are usually called orbits. The binary relation on a set E defined by trajectories by any transformation monoid (or acting monoid) M,

∐x∈E 〈{x}βŒͺM

is a preorder on E (as seen in example in 2.9). If M is a group then this preorder is an equivalence relation, whose partition of E is the set of orbits.

While the concepts of full transformation monoid and symmetric group depend on the powerset, those of transformation monoid and permutation group do not use it, being expressed as first-order theories.


In a monoid (M,e,β€’), the formula xβ€’y = e is read "x is a left inverse of y", or "y is a right inverse of x"; this x is right invertible (it has a right inverse), and y is left invertible.
An element x is called invertible if it is so both sides. Then its left and right inverses are equal, thus unique, called the inverse of x and written x-1:

yβ€’x = e = xβ€’z β‡’ y = yβ€’xβ€’z = z

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

xβ€’y = yβ€’x ⇔ x = yβ€’xβ€’z ⇔ zβ€’x = xβ€’z

An element x of a monoid is called involutive if it is its own inverse: xβ€’x = e.


Here are the simplest permutations beyond the identity of each set. A transposition of a set E is a permutation of E that swaps two elements and leaves all others fixed :

βˆ€x,y∈E, (x y)E = (E βˆ‹ z ↦ (z = x ? y : (z = y ? x : z))) = (y x)E ∈ 𝔖E

thus (x x)E = IdE which is not called a transposition.
Any transposition is involutive (this may give the simplest formal proof that it is a permutation).


The concept of group is the theory obtained by adding to that of monoid, equivalently Indeed this latter axiom determines the interpretation of -1 from β€’ and e.
If a transformation monoid is a group then it is a permutation group (as any inverse of a transformation in the sense of monoids is also its inverse as a function).
A subgroup of a group is a {e, β€’,-1}-subalgebra, or equivalently a sub-monoid which is a group (while sub-monoids of group are not all groups, for example β„• in β„€).
The core of a monoid M, is its set of invertible elements; it is a sub-monoid of M and a group: Its subgroups are all the submonoids of M which are groups, which may then be called the subgroups of M.
Between groups, a group morphism is equivalently an {e,β€’,-1}-morphism, or an {e,β€’}-morphism, as the latter also preserve inversion. More generally any {e,β€’}-morphism from a group to a monoid preserves the inversion relation {(x,y) | xβ€’y = e = yβ€’x}, thus its image is a group.

In a group, the subgroup generated by a subset A coincides with the submonoid generated by Aβˆͺ-A where -A = {x-1|x∈A}. (It is stable by inversion because its definition is unchanged by inversion, which is involutive)

Any submonoid of a group is cancellative. This has no general converse, but some partial ones, such as: any commutative cancellative monoid has an embedding to a commutative group (this is not very easy to prove).

Special actions

An element x of an M-set X will be called regular if it is both free and generating. This means that the M-morphism β‹…βƒ–x is both injective and surjective, thus an M-isomorphism from M to X. The identity element of M is regular for the natural action of M on itself.
Let us qualify an action after this: an M-set will be called monogenic if it is a trajectory (it is generated by a singleton), and regular if it has a regular element.

If an M-set is both monogenic and generated by the set of its free elements, then it is regular (there is a free element that generates it).
Proof: as a generator is in the set generated by that of free elements, it must be in the trajectory of one of them, which is thus also generating.∎
(A monogenic action of a monoid may have free elements without being generated by them ; but if a monogenic action of a group has a free element then all its elements are free).

The trajectory Y of any element x of an M-set X is M-stable, and thus an M-set. It is generated by x, and stays so when replacing the language M by its image as a transformation monoid N βŠ‚ YY.
Now if N is commutative (which is the case if M is commutative) then x is free for the action of N (thus Y is a regular N-set). The proof is easy and left as an exercise.

An action of a group G on a set X, is equivalently an action of monoid, or a group morphism from G to 𝔖X.
As inversion is an anti-morphism, it switches any action β‹… of G on X into a co-action β–ͺ by βˆ€x∈X, βˆ€g∈G, xβ–ͺg = g-1β‹…x.
If an action of group is monogenic then every element is generating; if it is regular then every element is regular.

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 P ⇔ P βŠ‚ AutL E.

For any permutation group G, sInv G = Inv G. Definability without parameters implies invariance by automorphisms, as will be explained in 4.10.


An isomorphism between objects E and F in any category, is an invertible morphism :

Iso(E,F) = {f∈Mor(E,F) | βˆƒg∈Mor(F,E), g∘f = 1E ∧ f∘g = 1F)}

This g is unique, called the inverse of f and written f -1.

A groupoid is a category where all morphisms are invertible. Groups are the groupoids with only one object, and the monoid of endomorphisms of any object of a groupoid is a group.
Generalizing from monoids, the core of a category is the groupoid with the same objects and only accepting isomorphisms as morphisms.
An automorphism of an object E, is an isomorphism from E to itself. Their set Aut(E), core of End(E), is a group called the automorphism group of E.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
3.1. Galois connections
3.2. Relational systems and concrete categories
3.3. Algebras
3.4. Special morphisms
3.5. Monoids and categories
3.6. Actions of monoids and categories
3.7. Invertibility and groups
3.8. Properties in categories
3.9. Initial and final objects
3.10. Products of systems
3.11. Basis
3.12. The category of relations
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry

Other languages:
FR : InversibilitΓ© et groupes