3.7. Invertibility and groups
Permutation groups
A permutation of a set E is a bijective transformation of E.
The set πE = {fβEE| f : EβE}
of all permutations of E, is a transformation monoid of E called the
symmetric group of E.
A permutation group of a set E,
is a {Id,β¬, -1}-subalgebra of πE.
In a permutation group, trajectories are usually called orbits.
The binary relation on a set E defined by trajectories by any transformation
monoid (or acting monoid) M, βxβE
β©{x}βͺM
is a preorder
on E (as seen in example in 2.9).
If M is a group then this preorder is an equivalence relation,
whose partition of E is the set of orbits. While the concepts of full transformation monoid and symmetric group depend on the
powerset, those of transformation monoid
and permutation group do not use it, being expressed as first-order theories.
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.
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 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.
Transpositions
Here are the simplest permutations beyond the identity of each set.
A transposition of a set E is a permutation of E that swaps two elements
and leaves all others fixed : βx,yβE,
(x y)E = (E β z β¦ (z = x ? y :
(z = y ? x : z))) = (y x)E β πE
thus (x x)E = IdE which is not called a transposition.
Any transposition is involutive (this may give the simplest formal proof that it is a permutation).
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
β’ and e.
If a transformation monoid is a group then it is a permutation group (as any inverse of a
transformation in the sense of monoids is also its inverse as a function).
A subgroup of a group is a {e, β’,-1}-subalgebra, or equivalently a
sub-monoid which is a group (while sub-monoids of group are not all groups, for
example β in β€).
The core of a monoid M, is its set of invertible elements; it is a sub-monoid of M
and a group: - e is its own inverse.
- 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 generated by Aβͺ-A where -A =
{x-1|xβA}. (It is stable by
inversion because its definition is unchanged by inversion, which is involutive)
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
An element x of an M-set X will be called regular if it is both
free and generating. This means that the M-morphism β
βx
is both injective and surjective, thus an M-isomorphism from M
to X. The identity element of M is regular for the natural
action of M on itself.
Let us qualify an action after this: an M-set will be called monogenic if it is
a trajectory (it is generated by a singleton), and regular if it has a regular element.
If an M-set is both monogenic and generated by the set of its free elements,
then it is regular (there is a free element that generates it).
Proof: as a generator is in the set generated by that of free elements, it
must be in the trajectory of one of them, which is thus also generating.β
(A monogenic action of a monoid may have free elements without being generated by them ;
but if a monogenic action of a group has a free element then all its elements are free).
The trajectory Y of any element x of an M-set X is M-stable,
and thus an M-set. It is generated by x, and stays so when replacing the language
M by its image as a transformation monoid N β YY.
Now if N is commutative (which is the case if M is commutative) then x
is free for the action of N (thus Y is a regular N-set).
The proof is easy and left as an exercise.
An action of a group G on a set X, is equivalently
an action of monoid, or a group morphism from G to πX.
As inversion is an anti-morphism,
it switches any action β
of G on X into a co-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 regular then every
element is 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
P β P β AutL E.
For any permutation group G, sInv G = Inv G.
Definability without parameters implies invariance by automorphisms, as will be explained in 4.10.
Isomorphisms
An isomorphism between objects E and F in any category, is an invertible
morphism :
Iso(E,F) = {fβMor(E,F) | βgβMor(F,E),
gβf = 1E β§ fβg = 1F)}
This g is unique, called the inverse of
f and written f -1.
A groupoid is a category where all morphisms are invertible.
Groups are the groupoids with only one object, and the monoid of endomorphisms of any object
of a groupoid is a group.
Generalizing from monoids, the core of a category is the groupoid with
the same objects and only accepting isomorphisms as morphisms.
An automorphism of an object E, is an isomorphism from E to itself.
Their set Aut(E), core of End(E), is a group called the automorphism group of E.
Set theory and foundations
of mathematics
1. First foundations of
mathematics
2. Set theory
3. Algebra 1
3.1. Galois
connections
3.2. Relational systems
and concrete categories
3.3. Algebras
3.4. Special morphisms
3.5. Monoids and categories
3.6. Actions of monoids and categories
3.7. Invertibility and groups
3.8. Properties in categories
3.9. Initial and final objects
3.10. Products of systems
3.11. Basis
3.12. The category of relations
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry
Other languages:
FR :
InversibilitΓ© et groupes