Commutativité indécidable dans la théorie des groupes?

[invitecd39b2fc]

Bonjour à tous,

je me permet d'ouvrir un nouveau topic, comme un fork d'un autre topic, et en particulier ce post de Médiat.

En fait je ne comprends pas la phrase suivante:

La théorie des groupes se résume à un langage (un symbole d'opération) et ses axiomes (associativité, élément neutre et élément symétrique), ces axiomes ne permettent pas de démontrer la commutativité, ni la non commutativité d'ailleurs (la commutativité est indécidable dans la théorie des groupes).

Ce que je ne comprends pas, c'est que je me souviens de mes cours d'algèbre de DEUG où l'on démontrait, justement, la commutativité ou non-commutativité d'un groupe. Je me souviens notamment du groupe dont les éléments sont des matrices (4x4 par exemple) et la relation est la multiplication matricielle. Groupe qui n'est pas commutatif, et nous avions démontré qu'il ne l'était pas.

Je ne comprends donc pas pourquoi vous dites que "la commutativité est indécidable dans la théorie des groupes". Si vous avez un peu de patience pour m'expliquer, je vous serai éternellement reconnaissant de combler cette terrible lacune dans un domaine que je pensais pourtant bien comprendre.

Merci
-----

[invitec317278e]

Si j'ai bien compris :


Si tu prends un groupe en particulier, on peut dire si oui ou non il est commutatif, mais en revanche, dans le cas général, se donner une structure munie d'une loi de composition interne associative, d'un élément neutre, et tel que tout élément soit inversible ne suffit pas pour dire que les éléments commutent. Donc la commutativité est indécidable.

Si on cherche une proposition décidable, on peut par exemple (je pense), penser à celle de l'unicité de l'élément neutre.
"il existe un unique élément neutre" est démontrable simplement à partir de la définition générale de groupe, si on a un groupe, peu importe lequel, son élément neutre sera unique.

[invitebe0cd90e]

L'idée c'est que les axiomes de groupe definissent (ca a une definition precise en logique) une theorie. cad qu'on peut abstraitement utiliser ces axiomes et les regles de logique pour demontrer des choses.

Chaque groupe est ce qu'on appelle un modele de cette theorie. Cad que c'est une "realisation concrete" des axiomes : les axiomes ne font intervenir que des symboles sans siginifcation, et prendre un groupe c'est donner un sens a ces symboles.

Tout ce que tu demontres a partir des axiomes est vrai dans n'importe quel groupe.

D'une maniere generale, on dit d'une proposition qu'elle est indecidablde dans une theorie, si il existe des modeles ou elle est vraie, et des modeles ou elle est fausse. Ca revient a dire que la theorie seule n'est pas "assez complete" pour prouver cette proposition ou son contraire.

Le fait meme qu'il existe des groupes commutatifs et d'autre qui ne le sont pas prouve que cette proposition est indecidable dans la theorie des groupes.

Des que tu as une proposition indecidable, tu peux l'ajouter ou ajouter sa negation a la theorie. Par exemple tu peux ajouter l'axiome de commutativité et obtenir une nouvelle theorie (qui possede "moins" de modeles), qui te permettra de demontrer abstraitement des choses vraies pour tout groupe commutatif.

Evidemment en general on ne raisonne pas comme ca. On se contente de dire "Soit G un groupe commutatif". Mais il se trouve que la notion de proposition indecidable, avec les fantasmes sur Gödel, l'hypothese du continu, etc.. laissent penser que la notion de prop. indecidable est tres mysterieuse. Les groupes fournissent un exemple tres simple de theorie logique en un sens rigoureux qui permet d'illustrer pas mal de choses.

[Médiat]

Si vous avez un peu de patience pour m'expliquer

Thorin et jobherzt ont tout dit, mais je reste à ta disposition (depuis le temps que l'on se connaît ).

[A voir en vidéo sur Futura]

[invitebe0cd90e]

Mon avant derniere phrase est un peu casse gueule. J'espere qu'on comprend quand meme

[invite7863222222222]

Le fait meme qu'il existe des groupes commutatifs et d'autre qui ne le sont pas prouve que cette proposition est indecidable dans la theorie des groupes.

Bonjour,

concernant par exemple l'indécidabilité de certaines équations diophantiennes dans l'arithmétique, existe-t-il, des modéles de l'arithmétique satisfaisant les axiomes de Peano mais dans lesquelles pour certains ces équations diophantiennes auraient des solutions alors que dans d'autres, il n'y en aurait pas ?

[Médiat]

concernant par exemple l'indécidabilité de certaines équations diophantiennes dans l'arithmétique, existe-t-il, des modéles de l'arithmétique satisfaisant les axiomes de Peano mais dans lesquelles pour certains ces équations diophantiennes auraient des solutions alors que dans d'autres, il n'y en aurait pas ?

Salut,
Par définition d'une p proposition indécidable dans une théorie T consistante :
T U {p} est consistante
T U {non p} est consistante

Par le théorème de complétude de Gödel une théorie consistante a des modèles.

La réponse est donc oui (à la consistance de l'arithmétique de Peano près, bien sur).

[invitec317278e]

Peux tu donner un exemple concret de ce qu'est un modèle de l'arithmétique de Péano, s'il te plait ?

[Médiat]

Peux tu donner un exemple concret de ce qu'est un modèle de l'arithmétique de Péano, s'il te plait ?

Peux-tu me démontrer qu'elle est consistante ?

[invitec317278e]

Je sais même pas ce que ça veut dire XD
Je veux juste comprendre ce qu'est un modèle

[Médiat]

Je sais même pas ce que ça veut dire XD
Je veux juste comprendre ce qu'est un modèle

N'importe quel groupe est un modèle de la théorie des groupes.

Tu peux regarder le petit document du message #33 : http://forums.futura-sciences.com/ma...ssiques-2.html

Ou chercher sur le net "Théorie des modèles".

[invite7863222222222]

Salut,
Par définition d'une p proposition indécidable dans une théorie T consistante :
T U {p} est consistante
T U {non p} est consistante

Par le théorème de complétude de Gödel une théorie consistante a des modèles.

La réponse est donc oui (à la consistance de l'arithmétique de Peano près, bien sur).

donc en supposant la consistance de l'arithmétique de Peano, il existe un modèle satisfaisant les axiomes de peano dans lequel une équation diophantienne n'a pas de solutions (alors que d'autres elle en a) ? A-t-on réussi à en exhiber un ?

[invité576543]

Bonjour,

Avertissement:

Ce qui suit est le fruit d'une "libre-pensée". Cela n'est pas dans le document de Médiat, ou dans un quelconque texte que j'ai pu lire sur la théorie des modèles. (Traduction : ne me demandez pas de références!)

En conséquence, c'est peut-être du franc n'importe quoi. Je prends le risque de raconter ce qui peut se révéler n'importe quoi, entre autres parce que, si on me l'explique d'une manière que je comprends, je serais très content d'avoir progressé.

Je ne prétend pas comprendre ou maîtriser la théories des modèles, au contraire. Sur cette théorie j'alterne régulièrement entre "la notion de modèle est triviale" et "je n'y comprends rien", sans arriver à me stabiliser sur aucun de ces extrêmes, ni quelque part au milieu (ce qui devrait être la bonne place!).

Mais peut-être, paradoxalement, justement cette non maîtrise me permet-elle d'apporter quelque chose à ceux qui découvrent le domaine.

Texte :

Prenons une équation diophantienne indécidable. Deux extensions des axiomes de Peano sont alors envisageables:

- avec une solution p : on affirme axiomatiquement que p existe, sans le décrire comme un entier (e.g., successeur de successeur etc. ou écriture décimale); l'ensemble des axiomes obtenu est non contradictoire, et il existe des modèles pour le nouveau jeu d'axiomes.

- sans solution : on affirme axiomatiquement qu'aucun élément ne respecte l'équation; l'ensemble des axiomes obtenu est non contradictoire, et il existe des modèles pour le nouveau jeu d'axiomes..

Pourquoi sans le décrire? Parce que la description explicite d'un entier se fait avec le langage des axiomes de Peano, et que cela implique que l'équation devient calculable, ce qui contredit l'indécidabilité.

Un modèle est un ensemble plus une association (la "sémantique") entre cet ensemble (et des ensembles construit à partir de lui) et les axiomes. C'est peut-être là une difficulté de la théorie des modèles quand on l'aborde : dans le cursus usuel on commence par apprendre que l'on construit les entiers à partir des axiomes. En théorie des modèles c'est d'une certaine manière inversé : on considère les axiomes d'abord par eux-mêmes, en tant que relations indépendantes de tout ensemble, et on regarde ensuite quels ensembles (construits exclusivement à partir des axiomes de la théorie des ensembles) respectent ces relations.

N, construit à partir des axiomes ensemblistes, respecte les axiomes de Peano. Mais il n'est pas le seul.

Par contre N ne peut pas être un modèle du cas "avec p" (faudrait donner explicitement la valeur de p pour avoir la sémantique). Ce qui n'empêche pas l'existence de modèles pour le cas "avec p" , le théorème de complétude permettant même d'affirmer l'existence de tels modèles.

Mais, tous les modèles vont tomber dans le pb de N? Non. Parce que le langage étant dénombrable, pour tout modèle de cardinal non dénombrable, il existe des éléments non descriptibles dans le langage.

Autrement dit, on peut affirmer l'existence d'un modèle, i.e., un ensemble respectant les axiomes de Peano plus l'axiome d'existence d'une solution, mais en aucun cas la solution ne peut-elle être exprimée comme un entier en écriture décimale par exemple. Mais on peut l'associer à un symbole, et ensuite travailler sur les formules dans lesquelles apparaît le symbole, sans (a priori, en acceptant que les axiomes de Peano soient non contradictoires) risquer de démontrer quelque chose et son contraire. Notons qu'on peut s'attendre à ce que de nombreuses formules avec p soient indécidables...

Réflexion plus philosophique:

Tout vient des limites physiques, selon ma compréhension. Les mathématiques des humains sont, par contrainte physique, basées sur un langage dénombrable; mais notre imagination permet une sémantique, la théorie des ensembles, avec des objets strictement plus "grands" que le dénombrable, donc non descriptibles exhaustivement et ce même avec un temps infini. (Deux limitations physiques sont à l'oeuvre : la dénombrabilité de l'ensemble des formules mathématiques construites à partir d'un ensemble fini ou dénombrable de symboles, et la finitude de l'espace-temps.)

Nul besoin d'invoquer des cas compliqués : R est non dénombrable, et il existe nécessairement des réels qui ne seront jamais décrits par les mathématiques humaines telles qu'elles sont maintenant. (En fait, le sous-ensemble des réels qui ont été ou seront dans un futur quelconque décrits individuellement par le langage mathématique en usage par les humains est de mesure nulle dans les réels!)

Il y a derrière tout cela la notion d'infini actuel. Les résultats de la théorie des modèles peuvent être vus comme des conséquences du postulat de l'infini actuel.

Cordialement,

[Médiat]

Sous réserve que je sache bien ce qu'est une équation diophantienne :
La proposition qui affirme que telle équation diophantienne admet une ou des solutions est une formule , sa négation est donc , donc vérifie le corollaire 1 du théorème 17 de mon document sur l'arithmétique (que je vais re-publier bientôt en ayant tenu compte des nombreuses remarques de Gwyddon (merci encore)).
Si l'existence d'une solution pour une équation diophantienne est indécidable dans l'arithmétique de Peano, alors cette solution ne peut appartenir au modèle standard.

[invitebe0cd90e]

Si l'existence d'une solution pour une équation diophantienne est indécidable dans l'arithmétique de Peano, alors cette solution ne peut appartenir au modèle standard.

Et donc ironiquement, pour certain probleme d'arithmetique, le fait qu'il soit indecidable.. Donne la reponse au probleme.

Exemple type : La conjecture de Goldbach. Si elle est indecidable... alors elle est "vraie", puisque si on pouvait trouver un contre exemple avec nos "bons vieux entiers qu'on connait", elle serait decidable (il "suffirait" d'exhiber le contre exemple).

[Médiat]

Exemple type : La conjecture de Goldbach. Si elle est indecidable... alors elle est "vraie", puisque si on pouvait trouver un contre exemple avec nos "bons vieux entiers qu'on connait", elle serait decidable (il "suffirait" d'exhiber le contre exemple).

C'est exactement l'exemple que j'ai pris dans le document cité ci-dessus, en expliquant pourquoi le vocabulaire indécidable/vraie provoque ma colère (heureusement tu as mes des guillemets )

[invite7863222222222]

C'est exactement l'exemple que j'ai pris dans le document cité ci-dessus, en expliquant pourquoi le vocabulaire indécidable/vraie provoque ma colère (heureusement tu as mes des guillemets )

Oui car ce vocabulaire peut vraiment porter à confusion, je m'en rends compte (enfin ).

[invite7863222222222]

Et donc ironiquement, pour certain probleme d'arithmetique, le fait qu'il soit indecidable.. Donne la reponse au probleme.

Exemple type : La conjecture de Goldbach. Si elle est indecidable... alors elle est "vraie", puisque si on pouvait trouver un contre exemple avec nos "bons vieux entiers qu'on connait", elle serait decidable (il "suffirait" d'exhiber le contre exemple).

En fait, il faut peut-être préciser elle est "vraie" dans un autre modèle que le modèle standard.

Car sinon on pourrait croire que ce que tu veux dire, c'est qu'elle est vraie dans une autre théorie, par exemple Zermelo Frankel quand on sait justement que dans cette théorie, on a justement démontré cette conjecture.

Mais la question intéressante est : peut-on se placer dans un autre modèle que le modèle standard sans changer de théorie ?

[invite7863222222222]

Oups petite erreur pour moi, j'ai confondu la conjecture de Goldbach avec le théorème de Goldstein.

[invitebe0cd90e]

[effacé car sans objet, malentendu avec jreeman CF message au dessus ]

[Médiat]

En fait, il faut peut-être préciser elle est "vraie" dans un autre modèle que le modèle standard.

Pour la conjecture de Golbach (qui est ), si elle est indécidable alors elle est vraie dans le modèle standard (je ne mets pas de guilemets à "vraie" puisque j'ai précisé dans quel modèle je me plaçais, et bien que je méfie toujours de ce vocabulaire, dans ce cadre précis, au moins a-t-il une signification),

Mais la question intéressante est : peut-on se placer dans un autre modèle que le modèle standard sans changer de théorie ?

Oui, puisqu'un modèle non standard de PA est un modèle de PA.
Non, puisque, si les modèles ne sont pas élémentairement équivalents, leurs théories complètes sont différentes (par exemple telle équation diophantienne admet des solutions dans un modèle et pas dans un autre).
Donc tout dépend de ce que l'on appelle théorie ici, la théorie de départ, ou les théories complètes des modèles...

[invite7863222222222]

Oui, puisqu'un modèle non standard de PA est un modèle de PA.

C'était bien à cela que je faisais allusion.

Donc tout dépend de ce que l'on appelle théorie ici, la théorie de départ, ou les théories complètes des modèles...

Je faisais allusion à la théorie de départ (d'ailleurs je ne sais ce qu'est une théorie complète des modèles).
Et donc si dans le modèle non standard telle équation diophantienne n'admet pas plus de solution que dans le modèle standard, cela répondrait aussi à ma question de départ.

[Médiat]

Je faisais allusion à la théorie de départ (d'ailleurs je ne sais ce qu'est une théorie complète des modèles).

C'est l'ensemble des formules du premier ordre (nous ne parlons que de cela ici puisque nous parlons de Peano) vraies dans ce modèle.

Et donc si dans le modèle non standard telle équation diophantienne n'admet pas plus de solution que dans le modèle standard, cela répondrait aussi à ma question de départ.

Supposons PA consistante :
Soit p une formule disant qu'une équation diophantienne admet des solutions, si p est indécidable, alors
1) PA U {p} est consistante et a des modèles.
2) PA U {non p} est consistante et a des modèles (dont le modèle standard).
Par le théorème d'incomplétude de Gödel : ni la théorie 1 ni la théorie 2 ne sont complètes, il est donc possible de trouver des formules q₁ et q₂ telles que :

11) PA U {p, q₁ } est consistante et a des modèles.
12) PA U {p, non q₁ } est consistante et a des modèles.
21) PA U {non p, q₂ } est consistante et a des modèles.
21) PA U {non p, non q₂ } est consistante et a des modèles.

Ces quatres théories sont différentes, mais tous les modèles envisagés sont des modèles de PA (mais pas élémentairement équivalents deux à deux).

[invite7863222222222]

1) PA U {p} est consistante et a des modèles.

Oui mais pour revenir à l'exemple de la commutativité des groupes, on est pas obligé de poser pour axiome, directement la proposition qui nous intéresse. On peut ajouter d'autres axiomes qui aboutiront à des groupes soit commutatifs, soit non commutatifs.

Je me disais juste comme cela en passant que c'était sur ce point que la comparaison entre l'indécidabilité de la commutativité et de l'existence de solution à une équation diophantienne, atteignait ses limites, non toujours pas ?

[invité576543]

Oui mais pour revenir à l'exemple de la commutativité des groupes, on est pas obligé de poser pour axiome, directement la proposition qui nous intéresse. On peut ajouter d'autres axiomes qui aboutiront à des groupes soit commutatifs, soit non commutatifs.

Je me disais juste comme cela en passant que c'était sur ce point que la comparaison entre l'indécidabilité de la commutativité et de l'existence de solution à une équation diophantienne, atteignait ses limites, non toujours pas ?

A mon sens, les deux cas diffèrent à cause de l'intervention de l'infini.

Le cas des groupes reste traitable avec une approche constructiviste. On peut construire explicitement des groupes commutatifs et d'autres non commutatifs. En particulier des groupes finis.

Le cas des diophantiennes est différent selon un point de vue constructiviste.

Mais cette différence n'a pas grand chose à voir avec la théorie des modèles.

L'intérêt du cas des groupes est de comprendre la notion de modèle. Mais elle ne permet en rien de comprendre le malaise qui apparaît dans le cas des diophantiennes.

Simplement parce que le point d'achoppement n'est pas dans la théorie des modèles, mais a à voir avec l'infini.

Cordialement,

[invite4ef352d8]

Peux-tu me démontrer qu'elle est consistante ?

>>> Oui : elle admet un modèle ( N qu'on peut définir dans ZF) donc elle est consistante. à partir de la on sait qu'il existe plein d'autre modèle (qui sont normalement constructible dans ZF... à moins que Löwenheim-Skolem ne requiert l'axiome du choix, j'ai toujours un doute la dessus...)... et donc on doit quand même pouvoir donner une réponse satisfaisante à la question de Thorin en construisant d'autre modèle de Peano que N dans ZF... (construction qui m'interesserait beaucoup ! )

Sauf erreur, j'ai déja vu qu'un modèle non standard dénombrable de Peano est forcement isomorphe (en tant qu'ensemble ordoné) à N +Q*Z (c'est à dire N suivit d'une infinité indéxé par Q de copie de Z...). mais je n'en ai jamais vu un pour de vrai... ( notement voir ce que vaudrait l'addition et la multiplication dessus... ou encore comment le principe de récurence fonctionnerait dessus... )

[invite7863222222222]

A mon sens, les deux cas diffèrent à cause de l'intervention de l'infini.

Le cas des groupes reste traitable avec une approche constructiviste. On peut construire explicitement des groupes commutatifs et d'autres non commutatifs. En particulier des groupes finis.

Le cas des diophantiennes est différent selon un point de vue constructiviste.

Mais cette différence n'a pas grand chose à voir avec la théorie des modèles.

L'intérêt du cas des groupes est de comprendre la notion de modèle. Mais elle ne permet en rien de comprendre le malaise qui apparaît dans le cas des diophantiennes.

Simplement parce que le point d'achoppement n'est pas dans la théorie des modèles, mais a à voir avec l'infini.

Cordialement,

Merci, je comprends effectivement mieux ainsi.

[Médiat]

>>> Oui : elle admet un modèle ( N qu'on peut définir dans ZF) donc elle est consistante. à partir de la on sait qu'il existe plein d'autre modèle (qui sont normalement constructible dans ZF... à moins que Löwenheim-Skolem ne requiert l'axiome du choix, j'ai toujours un doute la dessus...)... et donc on doit quand même pouvoir donner une réponse satisfaisante à la question de Thorin en construisant d'autre modèle de Peano que N dans ZF... (construction qui m'interesserait beaucoup ! )

Tu repousses le problème : peux-tu démontrer que ZF est consistante ?

Sauf erreur, j'ai déja vu qu'un modèle non standard dénombrable de Peano est forcement isomorphe (en tant qu'ensemble ordoné) à N +Q*Z (c'est à dire N suivit d'une infinité indéxé par Q de copie de Z...). mais je n'en ai jamais vu un pour de vrai... ( notement voir ce que vaudrait l'addition et la multiplication dessus... ou encore comment le principe de récurence fonctionnerait dessus... )

Tu devrais lire mon document sur l'arithmétique .
La forme des modèles non standard y est démontré, et est cité (mais non démontré) le théorème de Tennenbaum qui dit que dans un modèle non standard l'addition et la multiplication ne peuvent être récursives (autrement dit on ne sait pas les définir).

[Médiat]

Je me disais juste comme cela en passant que c'était sur ce point que la comparaison entre l'indécidabilité de la commutativité et de l'existence de solution à une équation diophantienne, atteignait ses limites, non toujours pas ?

Pour moi la vraie limitation est que pour PA il existe un modèle standard avec pas mal de propriétés intéressantes cf. la remarque sur Goldbach, par exemple.

[invite4ef352d8]

En effet... je devrait le lire !


"Tu repousses le problème : peux-tu démontrer que ZF est consistante ?" >>> certe je ne peux pas, mais tu peux répondre cela à n'importe qui, qui démontre n'importe qu'elle théorème.
de toute facon "Peano admet un modèle" est un énoncé de ZF (Peano, un modèle... tous sa c'est des ensembles), donc si ZF n'est pas cohérente il est "vrai"