3.6. Invertibility and groups

Permutation groups

A permutation of a set E is a bijective transformation of E.
The set ⤹E = {fEE| Inj f ∧ Im f = E} = {fEE| f : EE} of all permutations of E, is a transformation monoid of E called the symmetric group of E.
A permutation group G of a set E, is a {Id,০, -1}-subalgebra of ⤹E, i.e. a transformation monoid of E made of permutations and stable by inversion.

While the concepts of full transformation monoid and symmetric group depend on the powerset, those of transformation monoid and permutation group can be defined independently of it, as first-order theories with 2 types.

Trajectories are usually called orbits in the case of a permutation group.
For any transformation monoid or action of a monoid M on a set E, the relation defined by its trajectories (∐xE 〈{x}〉M) is a preorder on E (as seen in example in 2.7). If M is a group then this preorder is an equivalence relation, whose partition of E is the set of orbits.


In a monoid (M,e,•), the formula xy = 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.
Seeing M as a transformation monoid by left action on itself, this xy = e is interpreted as relating transformations :

z,tM, yz = txt = z

As right invertible functions are surjective and left invertible functions are injective, the left invertibility of y means that the right composition by y is surjective ({zy|zM} = M) and implies that y is left cancellative:

xy = e ⇒ ∀zM, zxy = z
z,tM, (yz = ytxy = e) ⇒ (z = xyz = xyt = t)

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:

yx = e = xzy = yxz = z

If a left invertible element y is also right cancellative then it is invertible: xy=eyxy = eyyx=e.
If x commutes with an invertible element y then it also commutes with its inverse z:

xy = yxx = yxzzx = xz

An element x of a monoid is called involutive if it is its own inverse: xx = e. In particular e is involutive.


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 those of • and e.
Permutation groups are the transformation monoids which are groups (in the first above sense).
A subgroup of a group is equivalently, a sub-monoid which is a group (not all are: the sub-monoid ℕ of the group ℤ is not a sub-group), or a {e, •,-1}-subalgebra.
The core of a monoid M, is its set of invertible elements; it is a sub-monoid of M and forms 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) | xy = e = yx}, thus its image is a group.

In a group, the subgroup generated by a subset A, coincides with the submonoid G generated by A∪-A where -A = {x-1|xA}. (To check that G is stable by inversion, notice that the definition of G is stable by inversion, which is involutive, thus -G = G.)

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

The above characterization of invertible elements also makes sense for an element x of an M-set X: saying that x is both free and generating, means that the morphism hx∈ MorM(M,X) is both injective and surjective, thus an isomorphism between the M-sets M and X. Then we might still say it has an inverse in the form of an M-morphism from X to M.
Now this can qualify actions (M-sets) themselves: let us call an action monogenic if it is a trajectory (it is generated by a single element), and free if it is generated by the set of its free elements.
Let us call it regular if it is both monogenic and free. Then there is a free element that generates it, i.e. it is M-isomorphic to M.
Proof: a generator being generated by the set of free elements, must be in the trajectory of one of them, which is thus also generating. (On the other hand, a monogenic action may have free elements without being free).

An action of a group G on a set X, is equivalently an action of monoid, or a group morphism from G to the symmetric group of X.

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

If an action of group is monogenic then every element is generating ; if it is free then all elements are free, so that all parts of its partition into orbits are 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 PP ⊂ AutL E.

For any permutation group G, sInv G = Inv G. Definability without parameters implies invariance by automorphisms, as will be explained in 4.8.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
3.1. Morphisms of 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