Demi-groupe bicyclique
En mathématiques, et en informatique théorique, le demi-groupe bicyclique est un demi-groupe particulier. Cet objet est important dans la théorie structurelle des demi-groupes[1] et un important exemple de monoïde syntaxique[2]. Même s'il est appelé demi-groupe bicyclique, c'est en fait un monoïde. La première description dans la littérature en a été donnée par Evgenii Sergeevich Lyapin en 1953. Alfred H. Clifford et Gordon Preston, dans leur livre[3], disent que l'un d'entre eux avait découvert ce monoïde avant 1943, en collaboration avec David Rees, mais n'avait pas publié le résultat.
Construction
Il existe plusieurs méthodes de construction du demi-groupe bicyclique, et plusieurs notations pour le désigner. Lyapin le note ; Clifford et Preston emploient la notation ; les livres plus récents[4] tendent à utiliser . C'est cette notation qui est adoptée ici.
À partir d'un demi-groupe libre
Le demi-groupe bicyclique est le quotient du demi-groupe libre sur deux générateurs et , par la congruence engendré par la relation (voir « Présentation d'un monoïde (en) »). En d'autre termes, tout élément du demi-groupe est un mot sur et , avec la condition que le facteur n'apparaît pas dans le mot. L'opération du demi-groupe est la concaténation de mots, suivie d'une réduction par la relation si nécessaire ; elle est clairement associative. On peut montrer que tout élément de est en fait de la forme , pour des entiers naturels et . L'opération de composition admet alors l'expression :
- (qa pb) (qc pd) = qa + c − min{b, c} pd + b − min{b, c}.
À partir de couples d'entiers naturels
Dans la construction précédente, l'opération s'exprime sur les exposants des éléments. Ceci suggère que les symboles et peuvent être omis, ne laissant subsister que les opérations sur les exposants et . Ainsi, s'identifie à l'ensemble des couples d'entiers naturels (y compris zéro) avec l'opération suivante[5] :
- (a, b) (c, d) = (a + c − min{b, c}, d + b − min{b, c}).
Ceci définit , comme dans la première construction, sauf qu'ici, a les deux générateurs et , et l'élément neutre .
Comme sous-demi-groupe
Si trois éléments , et d'un demi-groupe vérifient les conditions suivantes :
alors le demi-groupe engendré par et est isomorphe au demi-groupe bicyclique[6].
La preuve demande des vérifications. Par exemple, prouvons que tous les sont distincts. Pour cela, supposons que pour un . Alors par multiplication à droite par . Il en résulte que
et donc
- ,
contrairement aux conditions. La preuve complète figure dans le livre de Clifford et Preston[7].
Exemple : demi-groupe engendré par deux applications
Soient , , et les trois éléments du demi-groupe des applications des entiers naturels dans eux-mêmes définis par :
- ;
- ;
- et pour .
Le demi-groupe engendré par ces trois fonctions vérifie les conditions de la caractérisation donnée ci-dessus, donc engendre le demi-groupe bicyclique.
Propriétés
- Morphisme
Le demi-groupe bicyclique a la propriété suivante : l'image homomorphe de dans un autre demi-groupe est soit une copie isomorphe de , soit un groupe cyclique. En effet, les images et des générateurs de vérifient les trois premières des conditions données ci-dessus parce que est un morphisme. Si , alors l'image est bicyclique, et si , l'image est le groupe cyclique engendré par .
- Idempotents
Les idempotents du demi-groupe bicyclique sont, dans la représentation par couples, les couples , où est un entier naturel. Le demi-groupe est régulier (pour tout , il existe tel que ). De plus, les idempotents commutent, et est donc un demi-groupe inversif. Ceci équivaut à dire que pour tout , il existe un unique tel que et .
- Idéaux
Tout idéal de est principal: l'idéal à gauche et l'idéal à droite engendrés par sont respectivement
Chaque idéal principal en contient une infinité d'autres, donc n'a pas d'idéal à gauche ou à droite minimal.
- Relations de Green
En ce qui concerne les relations de Green, les propriétés sont les suivantes : Le demi-groupe bicyclique est composé d'une seule -classe (il est appelé bi-simple) et donc est une seule -classe. Les relations et sont données par
- si et seulement si ;
- si et seulement si [8].
Il en résulte que deux éléments sont -équivalents si et seulement s'ils sont égaux. Les sous-groupes de sont donc tous triviaux, chacun correspondant à un idempotent.
Le diagramme en « boîte à œufs » des relations de Green pour est un rectangle infini dans les deux directions. Son coin supérieur gauche est le suivant :
(0, 0) | (1, 0) | (2, 0) | ... |
(0, 1) | (1, 1) | (2, 1) | ... |
(0, 2) | (1, 2) | (2, 2) | ... |
... | ... | ... | ... |
Chaque entrée représente une -classe, les lignes sont les -classes et les colonnes les -classes. Les idempotents de B sont sur les éléments sur la diagonale. Ceci illustre la propriété d'un demi-groupe régulier de contenir exactement un idempotent par -classe et par -classe.
Lien avec la combinatoire
Le monoïde bicyclique intervient en combinatoire et en théorie des langages, comme monoïde syntaxique du langage de Dyck sur une paire de parenthèses. Plus précisément, le langage de Dyck est l'image homomorphe inverse de l'élément neutre du monoïde bicyclique, puisque c'est l'ensemble des mots qui se réduisent au mot vide par la relation . Le langage de Dyck, et donc aussi le monoïde bicyclique, est lié aux arbres binaires et aux algèbres associatives.
Notes et références
- ↑ C'est en effet l'exemple le plus simple de quotient d'un demi-groupe libre, à savoir par une seule relation, elle-même réduite à sa plus simple expression.
- ↑ C'est le monoïde syntaxique de langage de Dyck, comme expliqué plus bas.
- ↑ Clifford et Preston 1961, p. 43.
- ↑ Par exemple Howie 1995 ou Grillet 1995.
- ↑ Voir par exemple Clifford et Preston 1961, p. 45, Hollings 2007, p. 332 ou Howie 1995, p. 32.
- ↑ Ceci est le Lemme 1.31 à la page 44 de Clifford et Preston 1961.
- ↑ Clifford et Preston 1961, p. 44-45.
- ↑ Howie 1995, p. 60.
Voir aussi
Article connexe
Classes particulières de demi-groupes (en)
Littérature
- (en) Alfred H. Clifford et Gordon B. Preston, The Algebraic Theory of Semigroups, Providence, R.I., AMS, coll. « Mathematical Surveys » (no 7), , 224 p. (ISBN 978-0-8218-0271-7, lire en ligne)
- (en) Pierre Antoine Grillet, Semigroups: An Introduction to the Structure Theory, New York, Marcel Dekker, coll. « Monographs and Textbooks in Pure and Applied Mathematics » (no 193), , xii+398 (ISBN 0-8247-9662-4, MR 2000g:20001, lire en ligne)
- (en) John M. Howie, Fundamentals of Semigroup Theory, Oxford, Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (no 12), , x+351 (ISBN 0-19-851194-9, MR 1455373)
- (ru) Evgenii Sergeevich Lyapin, « Canonical form of elements of an associative system given by defining relations », Leningrad. Gos. Ped. Inst. Uč. Zap., vol. 89, , p. 45-54 (MR 0076775)
- (en) Christopher D. Hollings, « Some first tantalizing steps into semigroup theory », Mathematics Magazine, vol. 80, , p. 331-344 (JSTOR 27643058)
Portail de l'informatique théorique
Portail de l’algèbre