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 et un important exemple de monoïde syntaxique. 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, 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 $𝒞$ ; les livres plus récents 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 « Modèle:Lien »). 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 :

(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 :

1. $pe=ep=p$
2. $qe=eq=q$
3. $pq=e$
4. $qp\ne e$

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

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.

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$ ;
• $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)\ne 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\ge b\}$
• $(a,b)B=\{(c,d)\mid c\ge 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 $𝒟$-classe (il est appelé bi-simple) et donc est une seule $𝒥$-classe. Les relations $ℒ$ et $ℛ$ sont données par

• $(a,b)ℛ(c,d)$ si et seulement si $a=c$ ;
• $(a,b)ℒ(c,d)$ si et seulement si $b=d$.

Il en résulte que deux éléments sont $\mathscr{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 $\mathscr{H}$-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 $pq=1$. Le langage de Dyck, et donc aussi le monoïde bicyclique, est lié aux arbres binaires et aux algèbres associatives.

Voir aussi

Littérature

• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Ouvrage
• Modèle:Article
• Modèle:Article