# 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 with stability requirements expressed as first-order 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 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.
### 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*
is interpreted as relating 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 saying the right composition by *y* is surjective ({*z*•*y*|*z*∈*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 and any right inverse of *x* are equal,
and thus unique, called the inverse of *x* and written *x*^{-1}:
*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 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*:
*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 of a monoid (such as a
transformation), regardless the replacement of this monoid by a sub-monoid
containing it (a transformation monoid).
### Groups

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 :
- 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
(the last axiom of group beyond the axioms of monoid)
∀*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 *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
∀*x*∈*X*, ∀*g*∈*G*, *x•g* = *g*^{-1}▪*x*.
In a group, the subgroup 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