Logique Gödel

bonjour

essayer de démontrer l'indécidabilité de la conjecture de Goldbach est un effort vain, inutile et désespérant
un chercheur mathématique doit être clair et affirmatif : soit la conjecture est vraie, soit elle est fausse

le second terme de l'alternative est démontré par un contre-exemple flagrant
le premier terme de l'alternative est forcément plus long et plus exigent à prouver
comme cela était déjà le cas dans la démonstration du dernier théorème de Fermat (qui était en fait une conjecture)

que les chercheurs évitent de perdre leur temps avec l'indécidabilité
qui rend la mathématique obscure, oiseuse et absconse !

cordialement

Salut Christophe,
Mais peut-être que c'est la mode ? Je veux dire de s'exprimer. Sur n'importe quoi. En n'étant pas toujours (sic) au fait de .. A se demander si ``les gens'' ont entendu parler du dixième problème de Hilbert. Et des noms tels que Davis, Putnam, Robinson & Matiasevich. Du problème du mot dans les groupes ou semi-groupes (Markov, Post). Du petit monoïde redoutable de Céjtin, de l'algorithme de Knuth-Bendix, du problème de mortalité des matrices $3 \times 3$. Et j'en passe ...

Confus mes propos ? Pas plus que ceux d'une certaine personne ayant écrit dans le fil ``Est ce que 1 est un nombre premier'' un post affirmant que des technocrates, dans les années 1970 (si je me souviens bien) avaient changé le statut de la primalité de 1 (avant non, après oui). Edit : je voulais dire ``avant oui, après non''.

@Poirot: bah ZF est contradictoire, ou bien la conjecture de Riemann peut être vraie (comprenons: personne ne pourra trouver de contre-exemple) et prouvable, ou vraie et improuvable (et les gens vont chercher en vain pendant longtemps) sans qu'on le sache...

De mon téléphone : je crois que CQ une information qu'il a déjà donnée récemment: l'ensemble des ensembles finis F de matrices 3 fois 3 à coefficients dans Z tel qu'il existe un produit d'éléments de F qui est nul n'est pas récursif.

@Krokop
Pour compléter ce que dit cc : un pointeur, il s'agit de la section 5.1 de https://arxiv.org/pdf/1204.0299.pdf

Une variante (en des termes probablement naïfs car j'aurai du mal à formaliser) : étant donné un ensemble fini de matrices $3 \times 3$ à coefficients dans $\Z$, peut-on décider s'il existe un produit de ces matrices dont le coefficient en position $(3,2)$ est nul. J'ai mis $(3,2)$ pour faire concret mais on pourrait mettre $(i,j)$. Et bien ce problème est indécidable et la démonstration se fait par réduction du problème de correspondance de Post.

En fait, j'ai mentionné la position $(3,2)$ car un jour (en suivant P.N.), j'ai étudié le problème de réduction. Et appris ainsi que dans $M_3(\Z)$, il y avait du monde ``du point de vue semi-groupes''. Tu verras que pour $n=2$, Bjorn Poonen, dans la section 5.1, dit (en 2014) que le probléme est ouvert. Y'en a qui feraient bien de se mettre au boulot.
Fais un petit tour des problèmes abordés par Poonen, tu ne le regretteras pas.

Merci, Claude, je n'avais pas compris la description de l'ensemble non-récursif.

@Claude Quitté.

On a une matrice $3\times3$. Son rang se calcule facilement: il est nul si la matrice est nulle. Sinon, il est un si la matrice adjointe est nulle. Sinon, il est trois si le déterminant est non nul. Sinon, il est deux.

Dans le problème de mortalité, on peut virer toutes les matrices de rang 3. Et donc un sous problème est le suivant: on a un ensemble fini de matrices $3\times 3$ de rang $2$. Le problème de savoir s'il existe un produit de rang $1$ est-il décidable ?

Cordialement, Pierre.

Bonsoir,

je profite de ce fil pour poser une question qui me taraude. Les phrases suivantes sont peut-être grammaticalement (au sens mathématique) incorrectes, et si elles ne le sont pas, elles sont peut-être fausses... J'espère que vous me corrigerez s'il le faut !

L'énoncé $G$ de la conjecture de Goldbach est un "énoncé de la logique du premier ordre dans le langage de l'arithmétique de Peano".

Quel sens donnez-vous à "$G$ est vrai" ?

Le seul sens mathématique que je connais du mot "vrai" est celui de "vérité dans un domaine d'interprétation du langage de l'arithmétique de Peano". De ce point de vue-là, si $G$ et $nonG$ ne sont pas démontrables, alors $G$ n'est ni vrai ni faux, sommes-nous d'accord ?

Cependant, dans un modèle de l'arithmétique de Peano, si on considère l'ensemble de tous les objets qui sont des successeurs de successeurs de successeurs... de $0$, alors on obtient un modèle de l'arithmétique de Peano qui est le même, peu importe à partir de quel modèle on est parti, et c'est celui-là (ou sa classe d'isomorphie, disons) qu'on appelle "modèle standard".

Alors, $G$ est vrai, ou faux, dans ce modèle dit standard. En l'occurrence, s'il est faux, c'est qu'il existe un $n$, successeur de successeur de successeur... de $0$ (un nombre pair de "successeur") qui n'est pas somme de deux nombres premiers. La phrase précédente peut s'écrire dans le langage de l'arithmétique de Peano (ce qui donnerait un énoncé $P$), et serait d'ailleurs démontrable, puisqu'on pourrait extraire de la liste (finie) des sommes de nombres premiers inférieurs à $n$ une "démonstration formelle" de $P$.

En outre, comme évidemment, $P \Rightarrow nonG$, $nonG$ serait démontrable dans l'arithmétique de Peano.

Bref, si $G$ est faux dans le modèle standard, alors $nonG$ est démontrable, et donc $G$ ne peut être à la fois indécidable et faux dans le modèle standard. C'est bien ça, ce dont vous parliez ?

Et enfin, tout ceci vaut pour les énoncés qui commencent par $\forall$, j'imagine ?

Merci bien !

EDIT : Et à en croire le message de Foys, il existe des énoncés $P$ qui sont vrais dans le modèle standard, mais non démontrables (dans l'arithmétique de Peano) ? Le théorème de Goodstein, par exemple ?

La hiérarchie logique des énoncés se fait par le nombre d'alternances de quantificateurs et en fusionnant 2 quantificateurs égaux qui se suivent. Celui qui commence déterminé si l'énoncé est un "pi" ou un "sigma" (c'est juste du vocabulaire). Sur les entiers les quantificateurs bornes comptent pour du beurre.

Je detaillerai d'un PC. On peut meme prouver que cette hiérarchie est la bonne et que c'est un bon ordre (bon pré ordre).

Par exemple AAAEAEE est de même complexité que AEAE (A:=forall, E:= exists).

Et ouii @GA : les énoncés " A " qui sont indécidables sont automatiquement vrais.

Pour tenir ma promesse, mais j'ai un peu la flemme, et j'ai aussi la flemme de chercher où le lien vers mon ancien post, je rappelle "assez rapidement" pourquoi même des groupes commutatifs de matrices sont "indécidables".

1/ D'après Matiyasevic, l'ensemble des équations diophantiennes qui ont des solutions n'est pas récursif.

2/ Une équation diophantienne est un truc de la forme $P=0$ où $P$ est un polynome à plusieurs indéterminées, à coefficients dans $\Z$ et où on cherche un uplet de solutions qui sont des éléments de $\Z$.

2.bis/ Remarque: chercher des solutions dans $\Z$ ou dans $\N$ ne change rien à la difficulté, vu que tout entier positif est somme de 4 carrés et dans l'autre sens, chercher une solution dans $\Z$, c'est chercher un entier positif n vérifiant $P(n)\times P(-n)=0$

3/ Un polynôme est une somme de monômes

4/ Parfois..., et même souvent :-D, il arrive qu'une variable apparaisse à plusieurs endroits (on dit qu'elle a plusieurs occurrences)

5/ Pour remédier partiellement à cette "multi-occurencerie", on peut mettre des petits numéros pour différencier chaque occurence, de sorte qu'on se retrouve avec un polynôme où chaque variable n'apparait qu'une seule fois. Evidemment il faut "se rappeler" qui a le devoir d'être égal à qui. Pour ça, on complète LA SEULE équation $P=0$ par des équations de la forme $x=y$, le tout formant un système d'équations et non plus une seule équation

5bis/ remarque: $x_1=x_2=...x_9$ suffit à remédier à 9 occurrences d'une même variable $x$ (le système comportera donc les équations $x_1=x_2$; $x_2=x_3$; etc).

5ter/ HS pour la culture on remarquera que chaque variable apparaît ainsi au plus 3 fois. Je n'ai aucune idée de la complexité des systèmes où chaque variable apparaît au plus 2 fois, mais m'est avis qu'ils ont été étudiés (on est 7 10^9 sur Terre, s'il n'y a pas un matheux qui s'est intéressé à ça...)

6/ Je décris maintenant comment je transforme ça en un problème de petites matrices qui commutent 2 à 2. Mais comme j'ai la flemme, je vous invite à deviner ce qui est un peu trop résumé.

6.1/ Les variables vont rester de pures lettres du début à la fin. Chercher une solution ne va plus consister à leur attribuer une valeur à chacune

6.2/ Notre système est donc composé d'une somme de monômes à qui on demande de valoir $0$ et d'une liste d'équations très simples de la forme $ax+by+c=0$ (à l'état intial, ces équations sont $1x+(-1)y+0=0$), $a,b,c$ sont des coefficients connus et effectifs qui caractérisent le système

6.3/ Au lieu de "chercher une valeur pour une variable $x$", on s'amuse à plutôt changer le système de manière qu'il devienne équivalent à l'ancien en remplaçant $x$ par $x+1$. Apuuyer sur LA LETTRE $x$ va donc effectuer le changement de variable $x\to x+1$ en changeant tout bêtement les coefficients du systèmes (les nombres devant chaque monôme de la grosse équation et les $a,b,c$ précédents.)

6.4/ Par exemple si le polynôme qui forme la "grosse" équation est de la forme $.... + axm + bm+...$, où $m$ est un mot composé de lettres et $a,b$ des coefficients, le changement de var va provoquer le changement suivant pour "les mémoires" a,b: $a$ va rester $a$ mais $b$ va devenir $a+b$. Dans les équations de la forme $ax+by+c=0$, $a,b$ ne bougent pas, mais $c$ devient $a+c$.

6.5/ Je vous laisse vous amuser à traduire ça en matrices. Pourquoi c'est commutatif? Bin la réponse est très simple: $x\to x+1$ suivi de $y\to y+1$, c'est pareli que $y\to y+1$ suivi de $x\to x+1$

7/ Et pour finir, pour voir si le lecteur a suivi :-D , vous l'aurez compris, l'équation initial a une solution ssi en tapant un certain nombre de fois sur les touches qui font les changements $var\to var+1$ on finit par mettre tous les coefficients constants à $0$.

Pardon pour le retard, mais j'ai tenu (une fois n'est pas coutume) une de mes promesses plus haut dans le fil).

J'ai lu mais je ne comprends pas bien où tu veux aller. Tu veux démontrer que le problème de savoir si en multipliant des matrices données entre elles, on peut tomber sur la matrice nulle est indécidable, même lorsque les matrices commutent ?

Bon j'essaie d'être courageux :-D

L'exemple que j'ai choisi est peu inspiré, il vient de ce qu'il n'y a pas d'entiers $n$ tels que $n(n+1)$ est impair. Initialement, l'état du système est le suivant. Je mets les coefficients en rouge:

1 XY+0X+0Y+1 Z + (-2) T + (-1)=0

1X + (-1) Y + 0 = 0

1X + (-1) Z + 0 = 0

On se retrouve avec 12 coefficients, que je vais nommer avec les 12 premières lettres de l'alphabet.

a XY+kX+mY+b Z + c T + d = 0
eX + f Y + g = 0
hX + i Z + j = 0

Les coefficients "constants" (non multipliés par un monôme) sont : d;g;j

L'appui sur la touche X fait passer le vecteur
$$(a,b,c,d,e,f,g,h,i,j,k,m)$$ au vecteur $$(a,b,c,d+k,e,f,g+e,h,i,j+h,k,m+a)$$


L'appui sur la touche Y fait passer le vecteur $$(a,b,c,d,e,f,g,h,i,j,k,m)$$ au vecteur $$(a,b,c,d+m,e,f,g+f,h,i,j,k+a,m)$$

Je laisse le lecteur compléter la suite et produire les matrices correspondantes.