# 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 {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 (∐_{x∈E}
〈{*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.
### Inverses

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*.

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*

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 ({*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* 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 a left invertible element *y* is also right cancellative then it is invertible:
*x*•*y*=*e* ⇒ *y*•*x*•*y*
= *e*•*y* ⇒ *y*•*x*=*e*.

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*. In particular *e* is involutive.
### Groups

The concept of *group* is the theory obtained by adding to that of monoid, equivalently
- The axiom that all elements are invertible, or
- The function symbol
^{-1} of inversion, with the axiom
∀*x*,* x*•*x*^{-1} = *x*^{-1}•*x* = *e*

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 set of invertible elements in any monoid *M*, is a group:
- If
*x*, *y* have inverses *x*^{-1}, *y*^{-1},
then *x*•*y* has inverse *y*^{-1}•*x*^{-1}.
- Any inverse
*x*^{-1} is invertible, with
(*x*^{-1})^{-1} = *x* (inversion is an
involutive transformation of any 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 *G* generated by *A*∪-*A* where -*A* =
{*x*^{-1}|*x*∈*A*}. (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 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*.

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 left action ▪ of *G* on *X* into a right 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 free then all elements are free, so that all parts of its partition into orbits are regular.

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. Algebraic terms

3.10. Term algebras

3.11. Integers and recursion

3.12. Presburger Arithmetic

4. Model Theory