Juste une question
Bonjour,
Est ce que c’est possible que pour un énoncé il soit indécidable qu’il soit indécidable ?
Merci d’avance
Est ce que c’est possible que pour un énoncé il soit indécidable qu’il soit indécidable ?
Merci d’avance
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
On ne peut alors pas réfuter que "il existe des cardinaux inaccessibles" est indépendante de ZF(C), même sous réserve de cohérence de ZF(C)(parce que sous réserve de ma supposition, c'est vrai), mais on ne peut pas non plus le prouver, parce que si on pouvait le prouver alors en particulier on pourrait prouver que "il existe des cardinaux inaccessibles" est relativement cohérente, et ça on sait que ce n'est pas possible.
En résumé, sous réserve de ma supposition (qui est faite chaque jour par la plupart des théoricien.ne.s des ensembles), "il existe des cardinaux inaccessibles" est un exemple (et naturel en plus, je ne l'ai pas créé pour qu'il marche !)
Bon maintenant un truc sans supposition additionnelle, il doit y en avoir, même en arithmétique - mais ça doit sûrement se créer artificiellement. Je n'ai pas d'idée sur le coup, si j'ai le temps j'y réfléchirai.
Ou ça stagne?
Il peut être pour un énoncé d’etre Indécidable qu’il soit indécidable qu’il soit indécidable... et même à l’infini?
Donc un énoncé va être 2 s'il est indécidable qu’il soit indécidable qu’il soit prouvable (c’est la description).
On fait la somme dès indécidables (qui apparaissent dans la description) en remarquant que prouvable qu’il soit X qu’il soit prouvable c’est X qu’il soit prouvable.
Où on remplace X par prouvable ou indécidable.
La structure algébrique associée serait les p-anneaux (anneau où x^p=x et px=0)
C’est les suites de p-1 termes décroissantes d’éléments d’une algèbre de Boole.
superpower: je ne comprends pas ton dernier message mais pour ton avant dernier je ne vois pas de raison a priori que ça stagne.
Indécidable n'a pas de sens "tout seul". On parle d'indécidabilité dans une théorie T. Si on exclut les théories peu usuelles, tu as:
1/ si E est une équation diophantienne sans solution alors ou bien ce point est prouvable dans T ou bien ce point est indécidable dans T. Dans ce cas, T ne peut pas prouver que c'est indécidable dans T ', puisque T peut prouver que son indécidabilité dans T' entraine que E n'a pas de solution.
2/ En gros, tu as tout plein de situations en tout genre, mais ce que tu proposes n'a pas vraiment de pertinence. Par exemple, j'ai prouvé que certains énoncés sont "définitivement indécidables dans toute théorie raisonnable", mais j'ai la flemme de te les lister, d'autant qu'il faut des prérequis.
3/ D'une manière générale, ça dépend de la complexité des énoncés. Les grands infinis permettent d'avoir une variété importante alors que le diophantien limite les possibilités (Si Goldbach est indécidable dans T alors Goldbach est "vrai" ou "T déconne"), et ce fait là est non seulement prouvable, mais évident).
4/ Rien n'empêche de prouver un jour que Goldbach vrai =>Goldbach non prouvable dans T, mais attention à ne pas confondre indécidable et non prouvable dans un sens seulement).
1/ il y a d'abord eu les indécidables de Godel. Ils ont une tendance à être "intuitivement décidés" (je ne dis pas décidable, ça peut paraitre bizarre, en fait, on les décide "tous dans le même sens" par volonté platonicienne)
2/ Ensuite, il y a eu un bond avec les indécidables de Cohen, d'une nature très différente. Ceux-ci ne sont pas accessibles à l'intuition en ce sens, qu'on "sent bien" que la plupart du temps, $P$ comme $nonP$, vont bel et bien VRAIS dans des univers (tout aussi authentiques) différents.
Ceux de Godel par exemple sont très assymétriques: $P$ ne pourra être vraie que dans des modèles mal fondés, alors qu'on va croire au fait que $nonP$ elle sera vrai dans les "authentiques" (donc à minima bien fondés) univers.
Bon, ça c'est une présentation un peu introductive. en fait, on peut aller plus loin, mais ça devient technique. Et surtout, on admet de + en + d'axiomes très forts.
Par ailleurs, avec la découverte de ZF, on a progressé et découvert que les univers qui en sont des modèles "voient à l'extérieur d'eux" de beaucoup de manières, ce qui est paradoxal (et même plus) compte-tenu qu'ils ont été découverts avec l'espoir de "tout contenir".
Par exemple, il est "évident" une fois qu'on est plongé dans la technique qu'il existe une injection de la collection des ordinaux dans $P(\mathbb{R})$, l'ensemble des parties de $\R$, mais ZF en a décidé autrement et ne gère donc pas encore très bien ses trous de serrure (ceux qui permettent de regarder à l'extérieur).
Par exemple la paradoxe de Banach-Tarski n'est rien d'autre que la trouvaille de zones où il manque des réels, cependant on a du mal à définir correctement et de manière unique un réel manquant, on voit juste qu'il y en a plein à tels et tels endroits qui sont hors de l'univers.
Les indécidables en termes d'énoncés qui en résultent ne sont pas des indécidables mais des indéterminations en un sens très fort, à savoir juste des signalements clairs de bifurcations du type "bon, vous choisissez quel restaurant, là on ne fait pas de poisson, mais ici, on est spécialiste du beurre blanc"
Par exemple l'axiome du choix permet de maintenir à l'extérieur de l'univers les stratégies gagnantes à certains jeux apparents en construisant des ensembles symétriques (par exemple en mettant une notion de paire/impair sur les ensembles infinis) de la même manière que gonfler un ballon réduit le ratio de sa surface sur son volume.
Cela dit, je te donne un exemple de machinerie très simple qui "sort de l'accessible" et te donne des "indécidables définitifs". Quand tu as un ensemble $S$ de suites finies dont les termes sont des éléments de $\N\times 2$. une question "définitivement indécidable" dans le cas général (aussi qu'on puisse monter) est celle de savoir s'il existe un élément $a$ de $2^\N$ tel que pour tout $b\in \N^\N$, il existe $n\in \N$ tel que $((b_0,a_0),\dots , (b_n,a_n))\notin S$.
Cette question n'offre strictement aucune prise aux maths. Bien entendu, la plupart du temps tu te trouves dans un univers où un tel $a$ n'existe pas du point de vue de cet univers, mais c'est seulement dû au fait qu'il n'est pas assez haut, ie au fait que les seuls $a$ qui pourraient marcher sont tels que la hauteur de l'arbre bien fondé constitué des suites finie $u$ à termes dans $\N$ telles que $((u_0,a_0),\dots, (u_k,a_k))\in S$ est un ordinal dénombrable strictement plus haut (de beaucoup) que $ON$ (l'ordinal "ensemble" des ordinaux de l'univers).
L'univers ne perçoit alors pas ces $a$ qui le rendraient non seulement dénombrable, mais "détricotant sa complexité non aléatoire"
Comme tu peux facilement dessiner ce genre d'arbre dans un carré, c'est équivalent pour un ensemble intersection d'un ouvert et d'un fermé $X$ très simple et un ensemble $T$ récursif simple de partie finies de $\Q^2$ à chercher s'il existe ou pas un connexe $C\subset X$ qui va de $(0,0)$ à $(1,1)$ et qui ne contient aucun ensemble de $T$. Le fait que ton univers ne contiennent pas de tel connexe ne veut strictement rien dire car il n'est peut-être pas assez haut. On sait juste prouver que ce n'est qu'une question de hauteur et non de largeur (ie que ça ne dépend que de ses ordinaux et pas de ses ensembles d'ordinaux).
En bref, t'as de quoi t'amuser à te torturer l'esprit si tu digères tout ça :-D