Indécidabilité par le choix d'un élément

Adrien_ · July 2019

Bonsoir ! :-)
Alors voilà, la paire {0, 1} est habitée (en effet 0 en est élément), donc je peux choisir l'un de ses éléments, que je vais appeler x.
La formule x = 0 est-elle indécidable ?

Merci de m'éclairer ^^

Maxtimax · July 2019

Si tu veux elle est indécidable au sens suivant (sous réserve de cohérence etc.):

Il n'y a pas de preuve de la formule $x=0$ à partir de $x\in \{0,1\}$, ni de $\neg (x=0)$ avec les mêmes hypothèses.

Le problème étant ta formulation "je peux choisir $x$ dedans" qui n'est pas formelle et donc laisse à interprétation. En effet, on peut l'interpréter comme "je prends $x=0$ ou je prends $x=1$ mais je ne vous dis pas lequel" auquel cas bah $x=0$ est ou prouvable (si tu as choisi $x=0$) ou réfutable (si tu as choisi $x=1$).

Donc ça dépend du sens précis que tu donnes à te formulation imprécise.

Martial · July 2019

@adrien_ :
Je pense que tu peux formaliser les choses de la façon suivante :
Soit L le langage réduit à 2 symboles de constante c et c', et T la théorie des ensembles naïve à deux éléments (je te laisse le soin d'écrire les axiomes de T).
M={0,1} est bien un modèle de T.
La question que tu te poses est : la théorie T démontre-t-elle la formule c=c' ou son contraire ?
Là tu vois bien que non, puisqu'on peut interpréter c et c' par 0, ou bien c par 0 et c' par 1, ce qui signifie que l'énoncé c=c' est bien indécidable dans la théorie T.

@Max : n'hésite pas à me corriger si j'ai dit des conneries.
Martial

Adrien_ · July 2019

Merci beaucoup pour vos réponses !

Maxtimax, je ne pensais pas que ma formulation pourrait porter à confusion : je voulais bien sûr éliminer la phrase existentielle $\exists x,\ x \in \{0, 1\}$ et non faire un choix au sens du langage courant.
En fait je peux même "simplifier" mon raisonnement : si l'univers est habité, je choisis $ x \ $ puis je choisis $y$, et je demande si $x=y$ (ou encore si $x \in y \ $) par exemple.
Si des formules aussi simples sont indécidables, pourquoi ne sont-elles jamais données en exemple ?

Martial, je ne suis pas sûr de comprendre ce qu'est un modèle. Est-ce qu'il représente un univers possible de la théorie ? Dans ce cas, soit le modèle est trop petit pour supporter la plupart des axiomes de ZFC, soit mes axiomes sont très limités (il y a à tout casser $\forall x,\ x = 0 \vee x = 1$ et $0 = 1 \rightarrow \bot$).
Je me demande finalement si une théorie change chaque fois que l'on élimine une phrase existentielle.

Ps : Excusez-moi, je n'arrive pas à rentrer les symboles logiques.
Edit 2 : Ajout du Latex

Maxtimax · July 2019

Ok pour ta reformulation (ta question initiale n'aurait pas causé de confusion si je savais que tu étais capable de dire "élimination du quantificateur existentiel" :-D )
Elles ne sont pas choisies en exemple parce qu'elles ne sont pas indécidables pour "les bonnes raisons". Ici ta phrase "$x=0$" a une variable libre elle est donc peu intéressante. Dans toute théorie cohérente qui contient un symbole de constante $c$ et qui ne prouve pas que l'univers est réduit à un point, la phrase "$x=c$" est indécidable, mais peu intéressante. Ce qui intéresse vraiment les gens, ce sont les énoncés, aussi appelés formules closes ou sans variables libres. En fait l'indécidabilité de "$x=0$" n'est pas intéressante parce qu'elle concerne un énoncé qui parle de quelque chose dont on se fiche éperdument : $x$ (il t'intéresse toi ? Moi pas), tandis que l'indécidabilité de (par exemple) l'axiome du choix est intéressante parce que AC est un énoncé qui parle de quelque chose qui nous intéresse : "l' "univers des ensembles.

Si tu veux un exemple très simple d'indécidabilité mais qui reste quand même plus intéressant tu peux prendre $\forall x,\forall y, xy=yx$ dans la théorie des groupes (c'est indécidable parce qu'il y a des groupes commutatifs et des groupes non commutatif). Là c'est pareil : c'est un énoncé qui parle de quelque chose qui nous intéresse (le groupe), alors que "$x=e$" parle d'un $x$ que je ne connais ni d'Eve ni d'Adam et dont je me fiche.

(pour les symboles mathématiques il faut les mettre entre deux symboles dollar ; ensuite connaître le bon code : le quantificateur universel sera \forall : le code dollar \forall dollar donne $\forall$, existentiel ce sera \exists, etc. Pour découvrir des codes etc. tu peux cliquer droit sur le rendu et ensuite sur Show math as puis sur Tex Commands, tu auras un petit onglet avec le code qui s'ouvrira)

Adrien_ · July 2019

Je vois, effectivement dans la théorie des groupes (supposée cohérente), $x=e$ est indécidable quel que soit x fixé (sans autre indication), mais ce n'est pas très intéressant, par contre, le phrase $\forall x,\ x=e$ (par exemple) est elle aussi indécidable, mais davantage intéressante : la phrase caractérise les groupes triviaux.
Merci pour cette réponse éclairante (et pour l'astuce des dollars :-D).

Maxtimax · July 2019

(la théorie des groupes, on n'a pas à la supposer cohérente, elle l'est : voilà un modèle $\{e\}$)

Math Coss · July 2019

Est-ce que cela prouve que la théorie est cohérente ou seulement qu'elle n'est pas plus incohérente que la théorie des ensembles nécessaire pour décrire ce modèle ?

Maxtimax · July 2019

MathCoss : attention il y a plusieurs niveaux : philosophiquement tu as évidemment raison et d'ailleurs un.e philosophe sceptique n'acceptera jamais aucune preuve de cohérence.
Mais là on fait des maths, et officiellement les maths se font dans ZF(C). Donc l'énoncé "la théorie des groupes est cohérente" est prouvable, via le modèle en question; c'est une situation oh combien différente de l'énoncé "la théorie des ensembles est cohérente" qui (on l'espère) n'est pas prouvable. C'est ce que j'entendais par "on n'a pas à la supposer cohérente" (alors que pour ZFC, on a à la supposer cohérente)

Indécidabilité par le choix d'un élément

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 30