Problème indécidable ?

Ce n'est pas parce que tu as mis un lien vers le célèbre théorème de Post que ça te dispense de formuler une question particulière de manière compréhensible. L'indécidabilité dont il est question dans le lien est synonyme de non récursivité (d'un ensemble) et non pas d'indécidabilité d'un énoncé.

[ S'agissant d'Emil Post, on s'efforcera d'écrire son nom avec une majuscule, comme il se doit. jacquot ]

Les lecteurs ne comprendront toujours pas ta question puisque tu ne précises pas qui sont $a,b$ et le groupe ambiant sous-entendu.

Ton premier post est maintenant à mon avis tout à fait compréhensible, bravo!

Bonjour,

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

Bonjour,

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!

D'accord! Je sous-entendais qu'aucune forme réduite ne commence par $a^{-1}b^{-1}$, et j'aurais dû le dire!
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

Je suppose que tu me souffles que si un mot non vide est dans le monoïde son inverse n'y est pas...

Bonsoir, je sèche lamentablement !
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

Merci

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