Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
171 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Problème indécidable ?

Envoyé par pourexemple 
Problème indécidable ?
il y a quatre années
avatar
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.



Edité 3 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Dom
Re: Problème indécidable ?
il y a quatre années
Je ne suis pas spécialiste mais un monoïde ne contient-il pas nécessairement un élément neutre ?
Re: Problème indécidable ?
il y a quatre années
avatar
Oui, la question est : celui ci contient-il l'élément neutre ?

Si oui, l'exhiber, si non expliquer pourquoi.
Dom
Re: Problème indécidable ?
il y a quatre années
Alors je crois que la question est mal posée.
(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 ?
Re: Problème indécidable ?
il y a quatre années
avatar
Le problème de correspondance avec l'identité consiste à déterminer si un ensemble fini de paires de mots (sur un alphabet formé de lettres et de leurs inverses, autrement dit d'éléments du groupe libre à n générateurs) peut engendrer la paire identité par concaténations, autrement dit si le monoïde engendré par un ensemble fini de couples de mots est un groupe ; ce problème est indécidable. (source : wiki)
Re: Problème indécidable ?
il y a quatre années
avatar
Oui, tu as raison je corrige.
Re: Problème indécidable ?
il y a quatre années
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 ]

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par jacquot.
Re: Problème indécidable ?
il y a quatre années
avatar
J'ai corrigé, si tu as d'autres remarques sur une éventuelle mauvaise formulation de cette énoncé n'hésite pas.

En effet je peux me tromper et me trompe souvent.



Edité 2 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Re: Problème indécidable ?
il y a quatre années
Les lecteurs ne comprendront toujours pas ta question puisque tu ne précises pas qui sont $a,b$ et le groupe ambiant sous-entendu.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Problème indécidable ?
il y a quatre années
Si tu veux ne pas avoir à travailler pour corriger ça, tu peux juste ajouter "est-ce que dans tout groupe, l'ensemble suivant ..... est un sous-groupe?".

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Problème indécidable ?
il y a quatre années
avatar
C'est corrigé, si tu as d'autres remarques n'hésite pas, en effet un énoncé incompris est sans intérêt.
Re: Problème indécidable ?
il y a quatre années
Bin toujours pas! C'est bizarre que tu aies tant de mal à être complet confused smiley (je t'avais même suggéré un simple ajout à faire dans mon post précédent). Les gens ne sont pas trop ignorants du fait que $a^{-1}$ désigne l'inverse de $a$ dans un groupe. Le problème est que tu ne précises pas quel groupe. Par exemple, la réponse à ta question est "oui" dans un groupe trivial à un élément.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Problème indécidable ?
il y a quatre années
avatar
J'ai corrigé, mais je peux me tromper et comme tu peux le constater je me trompe souvent.
Re: Problème indécidable ?
il y a quatre années
avatar
Merci, pour ta lecture attentive.

Bonne journée.
Re: Problème indécidable ?
il y a quatre années
Ton premier post est maintenant à mon avis tout à fait compréhensible, bravo!

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Dom
Re: Problème indécidable ?
il y a quatre années
Par contre les messages qui suivent s'en trouvent incompréhensibles winking smiley
Re: Problème indécidable ?
il y a quatre années
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
Re: Problème indécidable ?
il y a quatre années
avatar
Bonjour,

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.
Re: Problème indécidable ?
il y a quatre années
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!



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par depasse.
Re: Problème indécidable ?
il y a quatre années
avatar
Bonjour,

$eba=a^{-1}b^{-1}baba$ est dans le monoïde engendré par G, $e$ l'élément neutre.

Bonne journée.



Edité 2 fois. La dernière correction date de il y a quatre années et a été effectuée par contrexemple.
Re: Problème indécidable ?
il y a quatre années
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
Re: Problème indécidable ?
il y a quatre années
avatar
Merci pour l’intérêt que tu portes à ce fil.

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.
Re: Problème indécidable ?
il y a quatre années
Je suppose que tu me souffles que si un mot non vide est dans le monoïde son inverse n'y est pas...
Re: Problème indécidable ?
il y a quatre années
avatar
La propriété que tu énonces est, me semble-t-il, correcte.
Re: Problème indécidable ?
il y a quatre années
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



Edité 1 fois. La dernière correction date de il y a quatre années et a été effectuée par AD.
Re: Problème indécidable ?
il y a quatre années
avatar
Bonsoir,

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.
Re: Problème indécidable ?
il y a quatre années
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 sympathiquewinking smiley

Cordialement
Paul
Re: Problème indécidable ?
il y a quatre années
avatar
Bonjour,


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.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 341, Messages: 1 508 964, Utilisateurs: 27 697.
Notre dernier utilisateur inscrit J-Maths.


Ce forum
Discussions: 2 539, Messages: 18 896.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page