# 3.6. Invertibility and groups

### Permutation groups

A *permutation* of a set *E *is a bijective
transformation of *E*.

The set ⤹*E *={*f *∈ *E*^{E}| Inj *f* ∧ Im
*f*=*E*} = {*f *∈ *E*^{E}|*f*:*E*↔*E*}
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* ∧ ∀*f*∈*G*, *f*^{ -1}∈ *G*.

It will be seen as an algebra with one more operation : the inversion function *f*↦*f*^{ -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
satisfying the above first-order stability axioms, ignoring the containing sets *E*^{E}
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 (*y*∈〈{*x*}〉_{G})
is a preorder; it is an equivalence relation if *G* is a permutation group.
### Inverses

In a monoid (*M*, *e*, •), the formula *x*•*y*=*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 *x*•*y*=*e*
becomes an invertibility of transformations :
∀*z,t*∈*M*, *y*•*z* = *t* ⇒ *x*•*t* = *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 the surjectivity of the right composition by *y* ({*x*•*y*|*x*∈*M*} = *M*)
and implies that *y* is left cancellative:*x*•*y* =
*e* ⇒ ∀*z*∈*M*, *z*•*x*•*y* = *z*

∀*z,t*∈*M*, (*y*•*z* = *y*•*t* ∧ *x*•*y*=*e*) ⇒
(*z* = *x*•*y*•*z* = *x*•*y*•*t*
= *t*)

An element *x* both left invertible and right invertible is called invertible.
Then any left inverse *y* and any right inverse *z* must be equal,
and thus unique, simply called the inverse of *x* and written *x*^{-1}.

Proof: *y*•*x* = *e* = *x*•*z* ⇒ *y*
= *y*•*x*•*z* = *z*

If a left invertible element *y* is also right cancellative then it is invertible: *x*•*y*=*e* ⇒ *y*•*x*•*y*
= *e*•*y* ⇒ *y*•*x*=*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 *h*_{x}∈ Mor_{M}(*M*,*X*) is both surjective
and injective, thus an isomorphism between the *M*-sets *M*
and *X*. Then we can still make sense of its invertibility by saying it has an inverse
*M*-morphism from *X* to *M*.

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 (equivalently on one or both sides): *x*•*x*=*e*. This qualifies an element such as a
transformation, regardless the choice of sub-monoid containing it (a transformation monoid).
### Groups

A *group* is a monoid where all elements are invertible.

The set of invertible elements in any monoid, is a group :
- it is a sub-monoid : if
*x* and *y* are invertible then *x*•*y* is invertible,
with inverse *y*^{-1}•*x*^{-1} (like in 2.6).
- Inverses are invertible (and by uniqueness of the inverse, inversion is an involutive transformation of any 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
- a sub-monoid which is a group, or
- a subalgebra for the
*language of groups* {*e*, •,^{-1}} extending the one {*e*, •} of monoids,
with the function symbol ^{-1} of inversion.

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*,* x*•*x*^{-1} =
*x*^{-1}•*x* = *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 ∀*x*∈ *X*, ∀*g*∈*G*,
*x**•g* = *g*^{-1}*▪x*.
The subgroup of a group generated by a subset *A*, coincides with the
submonoid *G* generated by *A*∪-*A* where -*A*={*x*^{-1}|*x*∈*A*} .

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