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 $P$ ; Clifford et Preston emploient la notation ${\mathcal {C}}$ ; les livres plus récents[4] tendent à utiliser $B$ . 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 $p$ et $q$ , par la congruence engendré par la relation $pq=1$ (voir « Présentation d'un monoïde (en) »). En d'autre termes, tout élément du demi-groupe est un mot sur $p$ et $q$ , avec la condition que le facteur $pq$ 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 $B$ est en fait de la forme $q^{a}p^{b}$ , pour des entiers naturels $a$ et $b$ . L'opération de composition admet alors l'expression :

(q^a p^b) (q^c p^d) = q^{a + c − min{b, c}} p^{d + 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 $p$ et $q$ peuvent être omis, ne laissant subsister que les opérations sur les exposants $a$ et $b$ . Ainsi, $B$ 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 $B$ , comme dans la première construction, sauf qu'ici, $B$ a les deux générateurs $(1,0)$ et $(0,1)$ , et l'élément neutre $(0,0)$ .

Comme sous-demi-groupe

Si trois éléments $p$ , $q$ et $e$ d'un demi-groupe $S$ vérifient les conditions suivantes :

$pe=ep=p$
$qe=eq=q$
$pq=e$
$qp\neq e$

alors le demi-groupe engendré par $p$ et $q$ est isomorphe au demi-groupe bicyclique[6].

La preuve demande des vérifications. Par exemple, prouvons que tous les $p^{k}$ sont distincts. Pour cela, supposons que $p^{k}+h=p^{h}$ pour un $h>1$ . Alors $p^{k}=e$ par multiplication à droite par $q^{h}$ . Il en résulte que

q=eq=p^{k}q=p^{k-1}e=p^{k-1}

et donc

qp=p^{k}=e

,

contrairement aux conditions. La preuve complète figure dans le livre de Clifford et Preston[7].

Exemple : demi-groupe engendré par deux applications

Soient $p$ , $q$ , et $e$ les trois éléments du demi-groupe des applications des entiers naturels dans eux-mêmes définis par :

$e(n)=n$ ;
$p(n)=n+1+1$ ;
$q(0)=0$ et $q(n)=n-1$ pour $n>0$ .

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 $B$ a la propriété suivante : l'image homomorphe $f(B)$ de $B$ dans un autre demi-groupe est soit une copie isomorphe de $B$ , soit un groupe cyclique. En effet, les images $f(p)$ et $f(q)$ des générateurs de $B$ vérifient les trois premières des conditions données ci-dessus parce que $f$ est un morphisme. Si $f(qp)\neq f(e)$ , alors l'image est bicyclique, et si $f(qp)=f(e)$ , l'image est le groupe cyclique engendré par $f(q)$ .

Idempotents

Les idempotents du demi-groupe bicyclique $B$ sont, dans la représentation par couples, les couples $(a,a)$ , où $a$ est un entier naturel. Le demi-groupe $B$ est régulier (pour tout $x$ , il existe $y$ tel que $xyx=x$ ). De plus, les idempotents commutent, et $B$ est donc un demi-groupe inversif. Ceci équivaut à dire que pour tout $x$ , il existe un unique $y$ tel que $xyx=x$ et $yxy=y$ .

Idéaux

Tout idéal de $B$ est principal: l'idéal à gauche et l'idéal à droite engendrés par $(a,b)$ sont respectivement

$B\,(a,b)=\{(c,d)\mid d\geq b\}$
$(a,b)\,B=\{(c,d)\mid c\geq a\}$

Chaque idéal principal en contient une infinité d'autres, donc $B$ 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 $B$ est composé d'une seule ${\mathcal {D}}$ -classe (il est appelé bi-simple) et donc est une seule ${\mathcal {J}}$ -classe. Les relations ${\mathcal {L}}$ et ${\mathcal {R}}$ sont données par

$(a,b){\mathcal {R}}(c,d)$ si et seulement si $a=c$ ;
$(a,b){\mathcal {L}}(c,d)$ si et seulement si $b=d$ [8].

Il en résulte que deux éléments sont ${\mathcal {H}}$ -équivalents si et seulement s'ils sont égaux. Les sous-groupes de $B$ sont donc tous triviaux, chacun correspondant à un idempotent.

Le diagramme en « boîte à œufs » des relations de Green pour $B$ 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 ${\mathcal {H}}$ -classe, les lignes sont les ${\mathcal {R}}$ -classes et les colonnes les ${\mathcal {L}}$ -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 ${\mathcal {R}}$ -classe et par ${\mathcal {L}}$ -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 $pq=1$ . 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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Bicyclic semigroup » (voir la liste des auteurs).

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 » (n^o 7), 1961, 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 » (n^o 193), 1995, xii+398 (ISBN 0-8247-9662-4, Math Reviews 2000g:20001, lire en ligne)
(en) John M. Howie, Fundamentals of Semigroup Theory, Oxford, Oxford University Press, coll. « London Mathematical Society Monographs. New Series » (n^o 12), 1995, x+351 (ISBN 0-19-851194-9, Math Reviews 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,‎ 1953, p. 45-54 (Math Reviews 0076775)
(en) Christopher D. Hollings, « Some first tantalizing steps into semigroup theory », Mathematics Magazine, vol. 80,‎ 2007, p. 331-344 (JSTOR 27643058)

Portail de l'informatique théorique
Portail de l’algèbre

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] 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.

[2] C'est le monoïde syntaxique de langage de Dyck, comme expliqué plus bas.

[3] Clifford et Preston 1961, p. 43.

[4] Par exemple Howie 1995 ou Grillet 1995.

[5] Voir par exemple Clifford et Preston 1961, p. 45, Hollings 2007, p. 332 ou Howie 1995, p. 32.

[6] Ceci est le Lemme 1.31 à la page 44 de Clifford et Preston 1961.

[7] Clifford et Preston 1961, p. 44-45.

[8] Howie 1995, p. 60.