Semi-groupe inverse - Inverse semigroup

Dans le groupe théorie, un semi - groupe inverse (parfois appelé un semi - groupe d'inversion ) S est un semi - groupe dans lequel tous les éléments x dans S a une situation unique inverse y en S dans le sens où x = xyx et y = YXY , soit un semi - groupe régulier dans lequel chaque élément a un inverse unique. Les semi-groupes inverses apparaissent dans une gamme de contextes ; par exemple, ils peuvent être employés dans l'étude des symétries partielles .

(La convention suivie dans cet article sera celle d'écrire une fonction à droite de son argument, par exemple xf plutôt que f(x) , et de composer des fonctions de gauche à droite - une convention souvent observée dans la théorie des semi-groupes.)

Origines

Les semi-groupes inverses ont été introduits indépendamment par Viktor Vladimirovich Wagner en Union soviétique en 1952, et par Gordon Preston au Royaume-Uni en 1954. Les deux auteurs sont arrivés aux semi-groupes inverses via l'étude des bijections partielles d'un ensemble : une transformation partielle α d'un ensemble X est une fonction de A à B , où A et B sont des sous-ensembles de X . Soient α et β des transformations partielles d'un ensemble X ; α et β peuvent être composés (de gauche à droite) sur le plus grand domaine sur lequel il « logique » pour les composent:

${\displaystyle \operatorname {dom} \alpha \beta =[\operatorname {im} \alpha \cap \operatorname {dom} \beta ]\alpha ^{-1}\,}$

où α ⁻¹ désigne la préimage sous  α . Les transformations partielles avaient déjà été étudiées dans le cadre des pseudo - groupes . C'est cependant Wagner qui, le premier, a observé que la composition des transformations partielles est un cas particulier de la composition des relations binaires . Il a également reconnu que le domaine de composition de deux transformations partielles peut être l' ensemble vide , il a donc introduit une transformation vide pour en tenir compte. Avec l'ajout de cette transformation vide, la composition de transformations partielles d'un ensemble devient une opération binaire associative partout définie . Sous cette composition, l'ensemble de toutes les transformations partielles un-un d'un ensemble X forme un demi-groupe inverse, appelé demi-groupe inverse symétrique (ou monoïde) sur X , avec inverse l'inverse fonctionnel défini d'une image à un domaine (de manière équivalente, la relation inverse ). C'est le semi-groupe inverse « archétypal », de la même manière qu'un groupe symétrique est le groupe archétypal . Par exemple, tout comme chaque groupe peut être intégré dans un groupe symétrique , chaque semi-groupe inverse peut être intégré dans un semi-groupe inverse symétrique (voir § Homomorphismes et représentations des semi - groupes inverses ci - dessous). ${\displaystyle {\mathcal {I}}_{X}}$

Les bases

L'inverse d'un élément x d'un demi-groupe inverse S s'écrit habituellement x ^-1 . Les inverses dans un semi-groupe inverse ont plusieurs des mêmes propriétés que les inverses dans un groupe , par exemple, ( ab ) ^-1 = b ^-1 a ^-1 . Dans un monoïde inverse , xx ^-1 et x ^-1 x ne sont pas nécessairement égaux à l'identité, mais ils sont tous les deux idempotents . Un monoïde inverse S dans lequel xx ^-1 = 1 = x ^-1 x , pour tout x dans S (un monoïde inverse unipotent ), est, bien sûr, un groupe .

Il existe un certain nombre de caractérisations équivalentes d'un semi-groupe inverse S :

• Chaque élément de S a un unique inverse, dans le sens ci-dessus.
• Chaque élément de S a au moins un inverse ( S est un semi-groupe régulier ) et les idempotents commutent (c'est-à-dire que les idempotents de S forment un semi- réseau ).
• Chaque -classe et chaque -classe contient précisément un idempotent , où et sont deux des relations de Green .${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {R}}}$

L' idempotent dans la -classe de s est s ^-1 s , tandis que l' idempotent dans la -classe de s est ss ^-1 . Il existe donc une caractérisation simple des relations de Green dans un semi-groupe inverse : ${\displaystyle {\mathcal {L}}}$${\displaystyle {\mathcal {R}}}$

${\displaystyle a\,{\mathcal {L}}\,b\Longleftrightarrow a^{-1}a=b^{-1}b,\quad a\,{\mathcal {R}}\,b\ Flèche longuegauchedroite aa^{-1}=bb^{-1}}$

Sauf indication contraire, E(S) désignera le demi-réseau d'idempotents d'un demi-groupe inverse S .

Exemples de semi-groupes inverses

• Les bijections partielles sur un ensemble X forment un semi-groupe inverse sous composition.
• Chaque groupe est un semi-groupe inverse.
• Le semi - groupe bicyclique est inverse, avec ( a , b ) ^-1 = ( b , a ).
• Tout demi - réseau est inverse.
• Le semi - groupe de Brandt est inverse.
• Le semi - groupe de Munn est inverse.

Exemple de table de multiplication. Il est associatif et chaque élément a son propre inverse selon aba = a, bab = b. Il n'a pas d'identité et n'est pas commutatif.

Semi-groupe inverse

&	une	b	c	ré	e
une	une	une	une	une	une
b	une	b	c	une	une
c	une	une	une	b	c
ré	une	ré	e	une	une
e	une	une	une	ré	e

L'ordre partiel naturel

Un demi-groupe inverse S possède une relation d' ordre partiel naturel (parfois notée ω), qui est définie par ce qui suit :

${\displaystyle a\leq b\Longleftrightarrow a=eb,}$

pour un e idempotent dans S . De manière équivalente,

${\displaystyle a\leq b\Longleftrightarrow a=bf,}$

pour certains (en général, différents) idempotent f dans S . En fait, e peut être considéré comme aa ^-1 et f comme a ^-1 a .

L' ordre partiel naturel est compatible à la fois avec la multiplication et l'inversion, c'est-à-dire

${\displaystyle a\leq b,c\leq d\Longrightarrow ac\leq bd}$

et

${\displaystyle a\leq b\Longrightarrow a^{-1}\leq b^{-1}.}$

Dans un groupe , cet ordre partiel se réduit simplement à l'égalité, puisque l'identité est la seule idempotente . Dans un semi-groupe inverse symétrique, l' ordre partiel se réduit à une restriction d'applications, c'est-à-dire ≤ β si, et seulement si, le domaine de est contenu dans le domaine de β et x α = x β, pour tout x dans le domaine de .

L'ordre partiel naturel sur les interagit avec de l'inverse les relations de Green suit comme: si s ≤ t et s t , alors s = t . De même, si s t . ${\displaystyle \,{\mathcal {L}}\,}$${\displaystyle \,{\mathcal {R}}\,}$

Sur E(S) , l' ordre partiel naturel devient :

${\displaystyle e\leq f\Longleftrightarrow e=ef,}$

ainsi, puisque les idempotents forment un semi-réseau sous l'opération produit, les produits sur E(S) donnent les limites supérieures par rapport à .

Si E(S) est fini et forme une chaîne (c'est-à-dire que E(S) est totalement ordonné par ≤), alors S est une union de groupes . Si E(S) est une chaîne infinie , il est possible d'obtenir un résultat analogue sous des hypothèses supplémentaires sur S et E(S).

Homomorphismes et représentations des semi-groupes inverses

Un homomorphisme (ou morphisme ) de demi-groupes inverses est défini exactement de la même manière que pour tout autre demi-groupe : pour les demi-groupes inverses S et T , une fonction θ de S dans T est un morphisme si ( sθ )( tθ ) = ( st ) θ , pour tout s , t dans S . La définition d'un morphisme de semi-groupes inverses pourrait être augmentée en incluant la condition ( sθ ) ⁻¹ = s ⁻¹ θ , cependant, il n'y a pas lieu de le faire, puisque cette propriété découle de la définition ci-dessus, via le théorème suivant :

Théorème. L' image homomorphe d'un demi-groupe inverse est un demi-groupe inverse ; l'inverse d'un élément est toujours mappé à l'inverse de l' image de cet élément.

L'un des premiers résultats prouvés sur les semi-groupes inverses était le théorème de Wagner-Preston , qui est un analogue du théorème de Cayley pour les groupes :

Théorème de Wagner-Preston. Si S est un demi-groupe inverse, alors la fonction de S à , donnée par ${\displaystyle {\mathcal {I}}_{S}}$

dom ( a φ) = Sa ⁻¹ et x ( a φ) = xa

est une représentation fidèle de S .

Ainsi, tout semi-groupe inverse peut être noyé dans un semi-groupe inverse symétrique, et avec l'image fermée sous l'opération inverse sur les bijections partielles. Inversement, tout sous-groupe du demi-groupe symétrique inverse fermé sous l'opération inverse est un demi-groupe inverse. Par conséquent, un demi-groupe S est isomorphe à un sous-groupe du demi-groupe symétrique inverse fermé par inverses si et seulement si S est un demi-groupe inverse.

Congruences sur les semi-groupes inverses

Congruences sont définis sur semigroupes inverse exactement de la même façon que pour tout autre semi - groupe: une congruence ρ est une relation d'équivalence qui est compatible avec la multiplication des semi - groupe, à savoir,

${\displaystyle a\,\rho \,b,\quad c\,\rho \,d\Longrightarrow ac\,\rho \,bd.}$

La relation , définie sur un demi-groupe inverse S par ${\style d'affichage \sigma }$

${\displaystyle a\,\sigma \,b\Longleftrightarrow }$il existe un avec${\displaystyle c\in S}$${\displaystyle c\leq a,b.}$

On peut montrer que σ est une congruence et, en fait, il est un congruence de groupe , ce qui signifie que le facteur S / σ est un groupe. Dans l'ensemble de toutes les congruences de groupe sur un semi-groupe S , l'élément minimal (pour l'ordre partiel défini par l'inclusion d'ensembles) n'a pas besoin d'être le plus petit élément. Dans le cas particulier où S est un demi-groupe inverse σ est la plus petite congruence sur S telle que S / σ est un groupe, c'est-à-dire que si τ est une autre congruence sur S avec S / τ un groupe, alors σ est contenu dans τ . La congruence σ est appelée congruence minimale de groupe sur S . La congruence minimale de groupe peut être utilisée pour donner une caractérisation des semi-groupes inverses E -unitaires (voir ci-dessous).

A congruence ρ sur un inverse semi - groupe S est appelé idempotent pur si

${\displaystyle a\in S,e\in E(S),a\,\rho \,e\Longrightarrow a\in E(S).}$

E -semigroupes inverses unitaires

Une classe de semigroupes inverse qui a été largement étudiée au cours des années est la classe de E semigroupes inverse -unitary: l'inverse semigroupe S (avec semitreillis E de idempotents ) est E - unitaire si, pour tout e dans E et tous s en S ,

${\displaystyle es\in E\Longrightarrow s\in E.}$

De manière équivalente,

${\displaystyle se\in E\Rightarrow s\in E.}$

Une caractérisation plus poussée d'un E inverse de -unitary S est la suivante: si e est E et e ≤ s , pour certains s en S , alors s est dans E .

Théorème. Soit S soit un semi - groupe inverse avec semitreillis E de idempotents, et le groupe minimum congruence σ . Alors les éléments suivants sont équivalents :

• S est E -unitaire;
• σ est idempotente pur;
• ${\style d'affichage \sim }$= Σ ,

où est la relation de compatibilité sur S , définie par ${\style d'affichage \sim }$

${\displaystyle a\sim b\Longleftrightarrow ab^{-1},a^{-1}b}$ sont idempotents.

Théorème de couverture de McAlister. Tout semi-groupe inverse S a une couverture E-unitaire ; c'est-à-dire qu'il existe un idempotent séparant l'homomorphisme surjectif d'un demi-groupe E-unitaire T sur S.

Au centre de l'étude des semi-groupes inverses E -unitaires se trouve la construction suivante. Soit un ensemble partiellement ordonné , d'ordre ≤, et soit un sous - ensemble de avec les propriétés que ${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {Y}}}$${\displaystyle {\mathcal {X}}}$

• ${\displaystyle {\mathcal {Y}}}$est un demi - réseau inférieur , c'est-à-dire que chaque paire d'éléments A , B in a une plus grande borne inférieure A B in (par rapport à ≤);${\displaystyle {\mathcal {Y}}}$ ${\displaystyle \wedge }$ ${\displaystyle {\mathcal {Y}}}$
• ${\displaystyle {\mathcal {Y}}}$est un idéal de commande de qui est, pour A , B dans , si A est et B ≤ A , puis B est .${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {Y}}}$${\displaystyle {\mathcal {Y}}}$

Soit maintenant G un groupe qui agit sur (à gauche), tel que ${\displaystyle {\mathcal {X}}}$

• pour tout g dans G et tout A , B dans , gA = gB si, et seulement si, A = B ;${\displaystyle {\mathcal {X}}}$
• pour chaque g dans G et chaque B dans , il existe un A dans tel que gA = B ;${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {X}}}$
• pour tout A , B dans , A ≤ B si, et seulement si, gA ≤ gB ;${\displaystyle {\mathcal {X}}}$
• pour tout g , h dans G et tout A dans , g ( hA ) = ( gh ) A .${\displaystyle {\mathcal {X}}}$

Le triplet est également supposé avoir les propriétés suivantes : ${\style d'affichage (G,{\mathcal {X}},{\mathcal {Y}})}$

• pour tout X dans , il existe un g dans G et un A dans tel que gA = X ;${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {Y}}}$
• pour tout g dans G , g et ont une intersection non vide.${\displaystyle {\mathcal {Y}}}$${\displaystyle {\mathcal {Y}}}$

Un tel triple est appelé triple McAlister . Un triplet McAlister est utilisé pour définir les éléments suivants : ${\style d'affichage (G,{\mathcal {X}},{\mathcal {Y}})}$

${\displaystyle P(G,{\mathcal {X}},{\mathcal {Y}})=\{(A,g)\in {\mathcal {Y}}\times G:g^{-1} A\in {\mathcal {Y}}\}}$

avec la multiplication

${\style d'affichage (A,g)(B,h)=(A\coin gB,gh)}$.

Alors est un demi-groupe inverse sous cette multiplication, avec ( A , g ) ⁻¹ = ( g ⁻¹ A , g ⁻¹ ). L'un des principaux résultats de l'étude des semi-groupes inverses E -unitaires est le P-Théorème de McAlister : ${\displaystyle P(G,{\mathcal {X}},{\mathcal {Y}})}$

Le théorème P de McAlister. Soit un triple McAlister. Alors est un semi-groupe inverse E -unitaire. Inversement, chaque semi-groupe inverse E -unitaire est isomorphe à un de ce type. ${\style d'affichage (G,{\mathcal {X}},{\mathcal {Y}})}$${\displaystyle P(G,{\mathcal {X}},{\mathcal {Y}})}$

F -semigroupes inverses

Un demi-groupe inverse est dit F -inverse si chaque élément a un élément maximal unique au-dessus de lui dans l'ordre partiel naturel, c'est-à-dire que chaque σ -classe a un élément maximal. Tout semi-groupe F -inverse est un monoïde E -unitaire. Le théorème de couverture de McAlister a été affiné par MV Lawson pour :

Théorème. Chaque semi-groupe inverse a une couverture F -inverse.

Le P -théorème de McAlister a également été utilisé pour caractériser les semi-groupes F -inverses. Un triplet de McAlister est un semi-groupe F -inverse si et seulement si est un idéal principal de et est un semi-réseau. ${\style d'affichage (G,{\mathcal {X}},{\mathcal {Y}})}$${\displaystyle {\mathcal {Y}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {X}}}$

Semi-groupes inverses libres

Une construction similaire à un groupe libre est possible pour les semi-groupes inverses. Une présentation du demi-groupe libre inverse sur un ensemble X peut être obtenue en considérant le demi-groupe libre avec involution , où l'involution est la prise de l'inverse, puis en prenant le quotient par la congruence de Vagner

${\displaystyle \{(xx^{-1}x,x),\;(xx^{-1}yy^{-1},yy^{-1}xx^{-1})\;|\ ;x,y\in (X\cup X^{-1})^{+}\}.}$

Le problème des mots pour les semi-groupes inverses libres est beaucoup plus complexe que celui des groupes libres. Un résultat célèbre dans ce domaine dû à WD Munn qui a montré que les éléments du semi-groupe libre inverse peuvent être naturellement considérés comme des arbres, appelés arbres de Munn. La multiplication dans le semi-groupe inverse libre a un correspondant sur les arbres de Munn , qui consiste essentiellement à chevaucher des parties communes des arbres. (voir Lawson 1998 pour plus de détails)

Tout semi-groupe inverse libre est F -inverse.

Liens avec la théorie des catégories

La composition ci-dessus des transformations partielles d'un ensemble donne naissance à un semi-groupe inverse symétrique. Il existe une autre façon de composer les transformations partielles, plus restrictive que celle utilisée ci-dessus : deux transformations partielles α et β sont composées si, et seulement si, l'image de α est égale au domaine de β ; sinon, la composition est indéfinie. Sous cette composition alternative, la collection de toutes les transformations partielles un-un d'un ensemble ne forme pas un semi-groupe inverse mais un groupoïde inductif , au sens de la théorie des catégories . Ce lien étroit entre les semi-groupes inverses et les groupoïdes inductifs est incarné dans le théorème d'Ehresmann-Schein-Nambooripad , qui stipule qu'un groupoïde inductif peut toujours être construit à partir d'un semi-groupe inverse, et inversement. Plus précisément, un semi-groupe inverse est précisément un groupoïde dans la catégorie des posets qui est un groupoïde étale par rapport à sa topologie (duale) d' Alexandrov et dont le poset d'objets est un semi-treillis.

Généralisations des semi-groupes inverses

Comme indiqué ci-dessus, un semi-groupe inverse S peut être défini par les conditions (1) S est un semi - groupe régulier et (2) les idempotents de S commutent ; cela a conduit à deux classes distinctes de généralisations d'un semi-groupe inverse : les semi-groupes dans lesquels (1) est valable, mais (2) ne l'est pas, et vice versa.

Des exemples de généralisations régulières d'un semi-groupe inverse sont :

• Semigroupes réguliers : un semigroupe S est régulier si tout élément a au moins un inverse ; de manière équivalente, pour chaque a dans S , il existe un x dans S tel que axa = a .
• Semi-groupes localement inverses : un semi-groupe régulier S est localement inverse si eSe est un demi-groupe inverse, pour chaque idempotent e .
• Semigroupes orthodoxes : un semigroupe régulier S est orthodoxe si son sous-ensemble d' idempotents forme un sous-semigroupe.
• Semi-groupes inverses généralisés : un demi-groupe régulier S est appelé demi - groupe inverse généralisé si ses idempotents forment une bande normale, c'est-à-dire, xyzx = xzyx , pour tous les idempotents x , y , z .

La classe des demi-groupes inverses généralisés est l' intersection de la classe des demi-groupes localement inverses et de la classe des demi-groupes orthodoxes.

Parmi les généralisations non régulières d'un semi-groupe inverse sont :

• (gauche, droite, recto-verso) semi-groupes adéquats.
• (Gauche, droite, recto-verso) de vastes semi-groupes.
• (gauche, droite, recto-verso) semi-groupes semi-adéquates.
• Semi-groupes faiblement amples (gauche, droite, recto-verso).

Catégorie inverse

Cette notion d'inverse se généralise aussi volontiers aux catégories . Une catégorie inverse est simplement une catégorie dans laquelle tout morphisme f  : X → Y a un inverse généralisé g  : Y → X tel que fgf = f et gfg = g . Une catégorie inverse est autoduale . La catégorie des ensembles et bijections partielles en est le meilleur exemple.

Les catégories inverses ont trouvé diverses applications en informatique théorique .

Voir également

Remarques

Les références

• Clifford, AH ; Preston, GB (1967). La théorie algébrique des semi-groupes . Enquêtes mathématiques de l'American Mathematical Society. 7 . ISBN 978-0-8218-0272-4.
• Fontaine, JB (1979). "Semi-groupes adéquats" . Actes de la Société mathématique d'Édimbourg . 22 (2) : 113-125. doi : 10.1017/S0013091500016230 .
• Gołab, St. (1939). "Über den Begriff der "Pseudogruppe von Transformationen " ". Mathematische Annalen (en allemand). 116 : 768–780. doi : 10.1007/BF01597390 .
• Exel, R. (1998). « Actions partielles des groupes et actions des semi-groupes inverses ». Actes de la Société mathématique américaine . 126 (12) : 3481-4. arXiv : funct-an/9511003 . doi : 10.1090/S0002-9939-98-04575-4 .
• Gould, V. "(Faiblement) gauche E-ample semi-groupes" . Archivé de l'original (Postscript) le 2005-08-26 . Récupéré le 2006-08-28 .
• Howie, JM (1995). Fondements de la théorie des semi-groupes . Oxford : Clarendon Press. ISBN 0198511949.
• Lawson, MV (1998). Semi-groupes inverses : la théorie des symétries partielles . Scientifique du monde. ISBN 9810233167.
• McAlister, DB (1974a). « Groupes, semi-réseaux et semi-groupes inverses ». Transactions de l'American Mathematical Society . 192 : 227-244. doi : 10.2307/1996831 . JSTOR  1996831 .
• McAlister, DB (1974b). "Groupes, semi-réseaux et semi-groupes inverses II" . Transactions de l'American Mathematical Society . 196 : 351-370. doi : 10.2307/1997032 . JSTOR  1997032 .
• Petrich, M. (1984). Semi-groupes inverses . Wiley. ISBN 0471875457.
• Preston, GB (1954a). "Semi-groupes inverses". Journal de la Société mathématique de Londres . 29 (4) : 396-403. doi : 10.1112/jlms/s1-29.4.396 .
• Preston, GB (1954b). « Les semi-groupes inversés avec des idéaux justes minimaux ». Journal de la Société mathématique de Londres . 29 (4) : 404-411. doi : 10.1112/jlms/s1-29.4.404 .
• Preston, GB (1954c). « Représentations de semi-groupes inverses ». Journal de la Société mathématique de Londres . 29 (4) : 411-9. doi : 10.1112/jlms/s1-29.4.411 .
• Schein, BM (1981). « Nécrologie : Viktor Vladimirovitch Vagner (1908-1981) ». Forum semi-groupe . 28 : 189-200. doi : 10.1007/BF02676643 .
• Schein, BM (2002). "Révision de livre : "Semigroups inverses : La théorie des symétries partielles" par Mark V. Lawson". Forum semi-groupe . 65 : 149-158. doi : 10.1007/s002330010132 .
• Wagner, VV (1952). "Groupes généralisés". Actes de l'Académie des sciences de l'URSS (en russe). 84 : 1119-1122. Traduction en anglais (PDF)
• Wagner, VV (1953). « La théorie des tas généralisés et des groupes généralisés ». Matematicheskii Sbornik . Novaya Seriya (en russe). 32 (74) : 545-632.

Lectures complémentaires

• Pour une brève introduction aux semi-groupes inverses, voir Clifford & Preston 1967 , chapitre 7 ou Howie 1995 , chapitre 5.
• Des introductions plus complètes peuvent être trouvées dans Petrich 1984 et Lawson 1998 .
• Linckelmann, M. (2012). « Sur les catégories inverses et transfert en cohomologie » (PDF) . Actes de la Société mathématique d'Édimbourg . 56 : 187. doi : 10.1017/S0013091512000211 . Préimpression en libre accès