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 transformation monoid of E such that

G ⊂ ⤹E ∧ ∀fG, f -1G.

It will be seen as an algebra with one more operation : the inversion function ff -1. So it is a {Id,०, -1}-subalgebra of ⤹E.

Unlike full transformation monoids and symmetric groups, the concepts of transformation monoid and permutation group make sense independently of the powerset, as sets of transformations with stability requirements expressed as first-order axioms, ignoring the containing sets EE or ⤹E.

Trajectories are usually called orbits in the case of a permutation group.
As noted in the example in 2.7, the binary relation on E defined by trajectories by a transformation monoid or an action of a monoid M on E, (y∈〈{x}〉M) is a preorder. 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", and "y is a right inverse of x". Seeing M as a transformation monoid by left action on itself, this xy=e is interpreted as relating transformations :

z,tM, yz = txt = z

We say x is right invertible when a right inverse y exists; similarly, y is left invertible.
As right invertible functions are surjective and left invertible functions are injective, the left invertibility of y is equivalent to saying 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 both left invertible and right invertible is called invertible. Then any left inverse and any right inverse of x are equal, and 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.
This characterization of invertible elements also makes sense for an element x of an M-set X: saying that x is both generating and free, means that the morphism hx∈ MorM(M,X) is both surjective and injective, 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.
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 of a monoid (such as a transformation), regardless the replacement of this monoid by a sub-monoid containing it (a transformation monoid).


A group is a monoid where all elements are invertible.
For a transformation monoid, being a permutation group is equivalent to being a group.
The set of invertible elements in any monoid, is a group : As any group is cancellative, any submonoid of a group is also cancellative. This has a partial converse (not very easy to prove): any commutative cancellative monoid can be embedded into a commutative group. We shall soon see the example of the monoid ℕ embedded in the group ℤ.

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 (the last axiom of group beyond the axioms of monoid)

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 M preserves the inversion relation, thus its image G' is a group (subgroup of the group of invertible elements of M), and f is a group morphism 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-1x.

In a group, the subgroup generated by a subset A, coincides with the submonoid G generated by A∪-A where -A={x-1|xA} .

Proof: to check that G is stable by inversion, notice that the definition of G is stable by inversion (which is involutive), thus -G = G.

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. Algebraic terms and term algebras
3.9. Integers and recursion
3.10. Arithmetic with addition
4. Model Theory