Indécidable et vrai

AlainLyon · February 2022

J'ai lu sous la plume d'Alain Connes que pour les entiers et avec la théorie des ensembles on pouvait parler de proposition indécidables et vraies (ou fausses en prenant la proposition contraire). Prenons par exemple la conjecture des nombres premiers jumeaux : il se peut qu'un logicien prouve qu'elle est indécidable, pourtant en énumérant "on sent" qu'elle a une valeur de vérité vraie ou fausse. Ma question est donc : y a-t-il une preuve écrite qu'un théorème sur les entiers indécidable a une valeur de vérité (ce qui répond à l'intuition) ?

Médiat_Suprème · February 2022

Toute proposition indécidable dans une théorie (comme l'arithmétique de Peano) est soit vraie, soit fausse dans chacun des modèles, donc dans $\mathbb N$.
De plus il y a un théorème intéressant sur les formules $\Sigma_1$ et les modèles premiers

Maxtimax · February 2022

Un exemple de $\Sigma_1$ où ce que tu suggères a bel et bien lieu: la conjecture de Goldbach. Si elle est indécidable (dans Peano, disons) alors elle est vraie (dans $\mathbb N$). En effet, si ce n'était pas le cas il y aurait un entier pair qui ne s'écrit pas comme somme de deux premiers (plus petits !) et ce fait là serait prouvable dans Peano ("Preuve : on énumère toutes les paires d'entiers premiers plus petit que $n$ et on observe qu'aucune somme ne vaut $n$")

L'exemple des nombres premiers jumeaux ne rentre pas dans ce cadre (on parle de choses qui arrivent à l'infini: que ce soit la conjecture elle même ou sa négation, pour la prouver il faut prouver "infiniment de choses"- pour confirmer ou infirmer, il faut une infinité de vérifications). En particulier je ne connais pas de théorème général "si machin est indécidable, alors machin est vrai" qui ait pour cas particulier machin = conjecture des nombres premiers jumeaux.

Médiat_Suprème · February 2022

Maxtimax a dit : il y aurait un entier pair qui ne s'écrit pas comme somme de deux premiers (plus petits !) et ce fait là serait prouvable dans Peano ("Preuve : on énumère toutes les paires d'entiers premiers plus petit que $n$ et on observe qu'aucune somme ne vaut $n$")

Il manque un petit bout : prouvable dans Peano, car $\mathbb N$ étant un modèle premier, si cet entier pair existait dans $\mathbb N$ il existerait dans tous les modèles (le fait que les premiers sont plus petits est essentiel ici), donc serait prouvable dans Peano.

Martial · February 2022

@Médiat_Suprême : Qu'entends-tu exactement par par "modèle premier" ?

Si c'est "section initiale de tout modèle de Peano avec définition de l'ordre", je te suis. Si c'est au sens général de la théorie des modèles je ne me souviens plus de la définition.

Médiat_Suprème · February 2022

Bonjour Martial,
Au sens de la théorie des modèles (c'est ce qui rend le théorème vraiment puissant) : un modèle premier de T est un modèle de T (merci captain obvious) qui se plonge élémentairement dans tous les modèles de T.

Martial · February 2022

Merci, Médiat_Suprême, c'est ça qui me manquait.

Evidemment, maintenant que je connais la définition c'est facile de montrer que ça marche dans le cas de $\mathbb{N}$ avec Peano. Mais je n'arrivais pas à extrapoler dans l'autre sens.

Maxtimax · February 2022

Médiat : $\mathbb N$ ne se plonge pas élémentairement dans tout modèle de Peano, ce serait bien triste si Peano était complète. Je n'ai pas précisé, mais effectivement cela vient juste de ce que je peux toutes les preuves en questions peuvent s'exprimer en termes de $sssss...0$ et si une telle équation est vraie dans $\mathbb N$ elle l'est dans tout modèle (récurrence :-D )

Médiat_Suprème · February 2022

Est-ce que l'implication "il existe un modèle premier de T" ==> T est complète ne serait pas valable que si T est modèle complet ?

Martial · February 2022

@Médiat_Suprême : Je me souviens, lors d'un DM de théorie des modèles, avoir considéré à un moment donné que tout sous-modèle d'un modèle premier était premier. (Je n'avais aucune raison de le faire, mais je me suis laissé abuser par la terminologie). Avant que je ne rende ma copie mes potes m'ont signalé que c'était faux. Ils m'ont donné un contre-exemple dont je ne me souviens plus, sinon ce ne serait pas drôle.

Bref, s'il y avait vraiment un tel contre-exemple ça entraîne en particulier que l'existence d'un modèle premier n'entraîne pas la modèle-complétude.

Mais je viens de me rendre qu'il n'y a aucun rapport avec la question que tu poses ci-dessus, donc tu peux laisser tomber, sorry.

Martial · February 2022

Je crois que je viens de trouver la bonne réponse. Dire qu'une théorie est modèle-complète revient à dire que tous ses modèles sont premiers, OK ?

Et pourtant elle n'est pas nécessairement complète : par exemple la théorie des corps algébriquement clos est modèle-complète, mais elle n'est pas complète car on ne peut rien dire de la caractéristique.

Médiat_Suprème · February 2022

Le modèle premier d'une théorie, s'il existe, est unique et modèle complète n'entraine pas l'existence d'un modèle premier.

Martial · February 2022

Médiat_Suprème

Je ne comprends pas, ou alors c'est ta définition ci-dessus d'un modèle premier qui est incorrecte. Si une théorie T est modèle-complète, tout plongement entre deux modèles de cette théorie est élémentaire, donc (toujours au sens de ta définition ci-dessus) tout modèle de T est premier.

Médiat_Suprème · February 2022

Modèle complète= tout plongement est élémentaire (ce qui ne veut pas dire qu'il y a toujours un plongement)
Modèle premier = pour tout modèle, il existe un plongement élémentaire.

Martial · February 2022

" (ce qui ne veut pas dire qu'il y a toujours un plongement)".

OK merci, c'est cette subtilité qui m'a fait planter.

Maxtimax · February 2022

Soit T une théorie qui admet un modèle premier M, et phi un énoncé dans le langage de T. Je prétends que phi est décidable dans T (i.e. T est complète).

En effet, s'il est vrai dans M (resp. faux) alors il est prouvable (resp. réfutable). En effet, supposons qu'il est vrai dans M mais pas prouvable. Par le théorème de complétude il existe un modèle N qui nie phi. Mais alors, puisque phi est vrai dans M, il n'existe pas de plongement élémentaire M -> N (ils ne sont même pas élémentairement équivalents !!)

Je raconte des bêtises ?

Martial · February 2022

Bien joué, Max !

Toi, raconter des bêtises ? En soirée, peut-être, comme tout le monde, mais pas quand tu parles de maths !

Médiat_Suprème · February 2022

Désolé Maxtimax mais c'est faux, un plongement élémentaire n'est pas synonyme de élémentairement équivalent.
Il suffit d'une formule existentielle qui peut-être fausse dans le modèle qui se plonge et vraie dans le modèle dans lequel elle se plonge.

Martial · February 2022

Désolé Médiat_Suprême mais Maxtimax n'a jamais dit que "plongement élémentaire" est synonyme de "élémentairement équivalent". Il a dit que "pas élémentairement équivalent" implique "pas plongement élémentaire". Par contraposée, cela signifie que s'il existe un plongement élémentaire de $M$ dans $N$, alors en particulier $M$ et $N$ sont élémentairement équivalents. Et ça c'est trivial : il suffit d'appliquer l'élémentarité aux formules closes.

Médiat_Suprème · February 2022

Désolé, mais depuis 1945 (Tarski) on sait que le groupe libre non commutatif sur $n$ générateurs $F_n$ se plonge élémentairement dans $F_m$ (où $n \le m$), mais aujourd'hui encore on ne sait pas s'ils sont élémentairement équivalents, soit vous vous trompez, soit plusieurs générations de logiciens, dont Tarski, sont de fieffés imbéciles !

Regardez mon exemple précédent.

Martial · February 2022

Re-désolé, mais je pense qu'on n'a tout simplement pas la même définition de "plongement élémentaire".

Page 197 du tome 2 de Cori-Lascar (qui à ma connaissance ne sont pas de fieffés imbéciles), je lis

Définition : Soient $\mathscr M$ et $\mathscr N$ deux $L$-structures et $h$ une application de $M$ dans $N$ ; on dit que $h$ est une application élémentaire si, pour toute formule $F[v_1,v_2,...,v_n]$ de $L$ et tous éléments $a_1,a_2,...,a_n$ de $M$, on a :

$$\mathscr M \models F[a_1,a_2,...,a_n] \text{ si et seulement si } \mathcal{N} \models F[h(a_1),h(a_2),...,h(a_n)].$$

Ensuite les auteurs précisent qu'une application élémentaire est clairement injective, raison pour laquelle on l'appelle aussi plongement élémentaire.

Bas page 198 :

Corollaire : S'il existe une application élémentaire de $\mathscr M$ dans $\mathscr N$, alors $\mathscr M$ et $\mathscr N$ sont élémentairement équivalents.

Martial · February 2022

Par ailleurs, Gabriel Sabbagh (qui n'est pas non plus un fieffé imbécile) nous a dit un jour que quelqu'un avait écrit un livre de 1000 pages dont la conclusion était qu'il existe un isomorphisme de $F_2$ sur $F_3$... ce qui est encore mieux que "élémentairement équivalents"... et ce qui semble contredire légèrement ce que tu dis plus haut au sujet de $F_n$ et $F_m$.

Médiat_Suprème · February 2022

Quel est l'intérêt du théorème :

T modèle complète et a un modèle premier ==> T est complète

Si l'hypothèse "modèle complète" est inutile ?

Maxtimax · February 2022

Martial : mhm je suis d'accord avec tout ce que tu dis sauf l'iso entre $F_2$ et $F_3$, ça, ça n'existe pas (preuve : prendre l'abélianisé, et voir que $\mathbb Z^2$ n'est pas isomorphe à $\mathbb Z^3$).
Mais je suis d'accord que la source du problème doit être la définition de plongement élémentaire. C'est une évidence plate que dans la définition que je connais (pareil que Martial) un plongement élémentaire implique une équivalence élémentaire.
Il serait bon que Médiat nous communique sa définition de plongement élémentaire pour qu'on voie où est le binz (et qu'on se convainque qu'il y a une définition raisonnable pour laquelle $\mathbb N$ est effectivement un modèle premier en ce sens de Péano). Personnellement, je pense que toute définition de "plongement élémentaire" qui n'implique pas équivalence élémentaire est une mauvaise définition, (enfin, plus précisément, elle devrait changer de nom !!), mais bon, on n'est pas à l'abri de surprise.

(Pour ce qui est théorie des modèles, j'ai tout appris de Cori et Lascar et d'internet, et les deux semblent d'accord sur plongement élémentaire, c'est pour ça que j'étais surpris)

Maxtimax · February 2022

Ah j'ai trouvé le binz. Selon wikipedia, un modèle premier est un modèle qui se plonge élémentairement dans tout modèle avec lequel il est élémentairement équivalent, et non pas dans tout modèle. C'est une distinction très importante. Là je suis plus prêt à t'accorder que $\mathbb N$ est un modèle de Peano, ce n'est pas "évident", mais pas compliqué de s'en convaincre ($\mathbb N$ se plonge dans tout modèle de Peano, il s'agit alors de prouver que si $M$ est élémentairement équivalent à $\mathbb N$, ce plongement l'est. En l'occurrence, puisque tous les éléments de $\mathbb N$ sont des constantes du langage, cela se déduit de l'équivalence élémentaire)

Martial · February 2022

@Maxtimax : merci, tu me rassures, je commençais à me demander si par hasard je n'étais pas totalement à côté de mes pompes.

Ton esquisse de preuve du fait que $\mathbb{N}$ est modèle premier de Peano me paraît tout à fait convaincante. Je pense que Dehornoy donne tous les détails dans le chapitre consacré aux théorèmes de limitation... sauf qu'il n'emploie jamais l'expression "modèle premier", c'est pour ça que je ne me souvenais plus précisément de cette notion.

Concernant $F_2$ et $F_3$ je dois confondre, ça remonte à 2003...

Indécidable et vrai

Réponses

Lettre d'information