Problème indécidable ?
Bonjour,
Le monoïde engendré par l'ensemble fini de mots $G$ est-il un sous-groupe du groupe libre engendré par $a,b$ :
$$G=\{b^{-1}a^{-1}ba,ab^{-1}a^{-2}b,ab^{-1}a,ba,a^{-1}ba,bab^{-1},bab,b^{-1}a\}$$
PS : indécidabilité ici
Bonne journée.
Le monoïde engendré par l'ensemble fini de mots $G$ est-il un sous-groupe du groupe libre engendré par $a,b$ :
$$G=\{b^{-1}a^{-1}ba,ab^{-1}a^{-2}b,ab^{-1}a,ba,a^{-1}ba,bab^{-1},bab,b^{-1}a\}$$
PS : indécidabilité ici
Bonne journée.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si oui, l'exhiber, si non expliquer pourquoi.
(Je ne parle pas de l'oublie des définitions de $a$ et $b$ sûrement éléments d'un magma dont la loi est notée multiplicativement. Ces deux éléments étants inversibles. ).
Tout énoncé qui commence par "le monoïde engendré par A..." décrit un monoïde et donc contient le neutre.
Peut-être qu'il faut reformuler autrement.
Est-ce que l'on ne demande pas plutôt de savoir si le neutre est produit d'un nombre fini d'éléments de G ?
[ S'agissant d'Emil Post, on s'efforcera d'écrire son nom avec une majuscule, comme il se doit. jacquot ]
En effet je peux me tromper et me trompe souvent.
Bonne journée.
pour que l'on me dise si je suis ou non complètement à côté de la plaque:
$b^{-1}a$ et $a^{-1}ba$ sont dans $G$; donc $a$ (i.e.leur concaténé $b^{-1}a a^{-1}ba$) est dans le monoïde engendré par $G$. Si ce monoïde engendré par $G$ est un sous-groupe alors, vu qu'il contient $a$, il contient $a^{-1}$. Or ce monoïde contient $ba$ puisque $G$ lui-même le contient. S'il est un sous-groupe alors, vu qu'il contient $ba$ et $a^{-1}$, il contient $baa^{-1}$ , i.e $b$ et donc aussi $b^{-1}$.
Ainsi, de deux choses l'une: ou bien le monoïde engendré par $G$ n'est pas un sous-groupe, ou bien il est le groupe engendré par $a$ et $b$.
Cordialement
Paul
Joli.
Bilan : si le monoïde est un sous-groupe alors il pourrait engendrer n'importe qu'elle élément du groupe libre.
Bonne journée.
pour prouver que le monoïde $M$ engendré par $G$ n'est pas un sous-groupe du groupe engendré par $a$ et $b$, il suffit désormais d'exhiber des éléments du groupe engendré par $a$ et $b$ qui ne sont pas dans le monoïde.
Montrons qu'aucun élément de $M$ ne commence par $a^{-1}b^{-1}$:
Initialisation: aucun élément de $G$ ne commence par $a^{-1}b^{-1}$.
Hérédité: Soit $n$, naturel non nul, tel qu'aucun élément de $G^n$ ne commence par $a^{-1}b^{-1}$.
Supposons qu'il existe $x$ dans $G^{n+1}$ ( on a donc $x=gm_n$ avec $g$ dans $G$ et $m_n$ dans $G^n$) qui commence par $a^{-1}b^{-1}$, autrement dit $x=a^{-1}b^{-1}y$.
On a donc: $gm_n=a^{-1}b^{-1}y$.
Or le seul élément de $G$ qui commence par $a^{-1}$ est $a^{-1}ba$
Donc $g=a^{-1}ba$, puis $a^{-1}bam_n=a^{-1}b^{-1}y$, enfin $m_n=a^{-1}b^{-1}b^{-1}y$,
Contradiction
Cordialement
Paul
Edit: à prouver!
$eba=a^{-1}b^{-1}baba$ est dans le monoïde engendré par G, $e$ l'élément neutre.
Bonne journée.
mais, de toute façon, j'ai un gros doute sur ma démonstration comme signifié par mon edit. Bref, c'est plus compliqué que je l'ai cru!
Cordialement, en espérant que d'autres s'y mettent
Paul
Mais même ainsi (sous forme réduite) : $a^{-1}b^{-1}x$ les 2 premiers lettres peuvent utiliser beaucoup plus qu'un mot de G pour pouvoir être écrit.
En fait c'est ensemble G est tel que tout sous ensemble non vide de G a la même propriété (que le monoïde engendré ne soit pas un sous groupe).
Bonne journée.
Y a-t-il une belle astuce ou un théorème bien connu de non-moi derrière tout ça ?
J'ai réduit de $8$ à $4$ le cardinal, mais ça ne m'avance pas: $\{b^{-1},a,a^
{-1},b\}$ n'est pas la seule partie de cardinal $4$ qui engendre le $2$-groupe $D$.
$H:=\{ab^{-1}a^{-2}b,a^{-1}ba,bab,b^{-1}\}$ engendre un monoïde $Y$ qui contient $G:=\{b^{-1}a^{-1}ba,ab^{-1}a^{-2}b,ab^{-1}a,ba,a^{-1}ba,bab^{-1},bab,b^{-1}a\}$ et donc le monoïde engendré par $G$.
Yapluka prouver que $Y$ n'est pas $D$.
Un coup de main serait très apprécié.
Amicalement
Paul
Indice : La construction de G est basée sur une astuce qui permet de construire un ensemble aussi gros que l'on veut ayant la même propriété que G.
Bonne journée.
Je m'en vais donc essayer de trouver l'astuce; je "vois" bien que le semi-groupe engendré par $G$ et celui engendré par $G^{-1}$ sont disjoints et que leur réunion est le groupe privé du neutre, mais "voir" n'est pas démontrer!
J'en avais marre cette nuit.
Si quelqu'un donne la solution, il serait gentil de l'écrire à l'encre sympathique;-)
Cordialement
Paul
Solution en blanc :
en se plaçant dans le groupe des fonctions affines (munies de la composition), on prend $a(x)=3x+1$ et $b(x)=2x$
donc $a^{-1}(x)=(x-1)/3$ et $b^{-1}(x)=x/2$ et l'on voit alors pourquoi ce monoïde ne peut être un groupe.
Bonne journée.