théorème de Godel
Pour me faire pardonner de troller trop souvent ce forum, voici une suite d'arguments (mi-exo de maths, mi-exo de philo) qui s'enchainent qui vous amènent au théorème de Godel:
On se place dans une théorie $T$ dans laquelle il y a un prédicat binaire nommé $\in $ (mais qui sera utilisé dans un sens un tout petit peu différent de d'habitude) et un prédicat binaire aussi "dem".
On suppose aussi que tout texte $t$, quel qu'il soit, correspond univoquement à une constante $c_t$ du langage de la théorie $T$.
Un énoncé clos, en particulier, $P$ du langage de la théorie $T$ correspond donc à un $c_P$.
On suppose qu'il existe $e$ tel que pour tout $a: a\in e$ si et seulement s'il existe $d$ tel que $dem(d,c_{[a\notin a]})$
supposons que $e\in e$. Alors il existe $d$ tel que $dem(d,c_{[e\notin e]})$. Mais alors $e\notin e$.
Posons maintenant $t:=supposons que e\in e. Alors il exsite d tel que dem(d,c_{[e\notin e]}). Mais alors e\notin e$.
(Bon d'accord j'ai 3ans d'age mental... C'est pour ça que j'ai créé ce fil lol)
Supposons que $dem(t,c_{[e\notin e]})$ (supposition qui parait hautement raisonnable, non?). Alors, il existe bien d tel que $dem(d,c_{[e\notin e]})$. Et donc $e\in e$.
Et comme $dem([supposons que e\in e. Alors il existe d tel que dem(d,c_{[e\notin e]}). Mais alors e\notin e],c_{[e\notin e]})$
forcément $e\notin e$ (sauf s'il existe des trucs prouvés qui sont faux lol)
Ainsi, avec des axiomes acceptables, j'ai prouvé {\bf tout} (ie j'ai obtenu une contradiction)
{\it si vous vous ennuyez, Cherchez l'erreur... }
On se place dans une théorie $T$ dans laquelle il y a un prédicat binaire nommé $\in $ (mais qui sera utilisé dans un sens un tout petit peu différent de d'habitude) et un prédicat binaire aussi "dem".
On suppose aussi que tout texte $t$, quel qu'il soit, correspond univoquement à une constante $c_t$ du langage de la théorie $T$.
Un énoncé clos, en particulier, $P$ du langage de la théorie $T$ correspond donc à un $c_P$.
On suppose qu'il existe $e$ tel que pour tout $a: a\in e$ si et seulement s'il existe $d$ tel que $dem(d,c_{[a\notin a]})$
supposons que $e\in e$. Alors il existe $d$ tel que $dem(d,c_{[e\notin e]})$. Mais alors $e\notin e$.
Posons maintenant $t:=supposons que e\in e. Alors il exsite d tel que dem(d,c_{[e\notin e]}). Mais alors e\notin e$.
(Bon d'accord j'ai 3ans d'age mental... C'est pour ça que j'ai créé ce fil lol)
Supposons que $dem(t,c_{[e\notin e]})$ (supposition qui parait hautement raisonnable, non?). Alors, il existe bien d tel que $dem(d,c_{[e\notin e]})$. Et donc $e\in e$.
Et comme $dem([supposons que e\in e. Alors il existe d tel que dem(d,c_{[e\notin e]}). Mais alors e\notin e],c_{[e\notin e]})$
forcément $e\notin e$ (sauf s'il existe des trucs prouvés qui sont faux lol)
Ainsi, avec des axiomes acceptables, j'ai prouvé {\bf tout} (ie j'ai obtenu une contradiction)
{\it si vous vous ennuyez, Cherchez l'erreur... }
Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Réponses
-
{\bf précision:}
$dem(d,c_t)$ est une abréviation pour:
{\it le texte $d$ est une démonstration correcte de la phrase (si c'en est une) $t$}
en règle général, dans le post ci-dessus, je l'ai mise entre crochet...Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Messire, il eût été de bon aloi que vous utilisassiez les ressources du LaTeX pour espacer correctement les vocables que vous écrivîtes sans séparation aucune.
-
lol
Pour une fois, c'était fait exprès...Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Compte-tenu de certaines compulsions platoniciennes tout à fait respectables, je ferai remonter ce fil épisodiquement avec des illustrations différentes à chaque fois que les "godèleries" sont partout...
Today il est question de Ramsey et de certaines idées apparues pour la première fois chez Paris et Harrington dans les années 70
$C_n$ désigne l'ensemble des suites croissantes $a_1<a_2..a_n$ d'entiers.
On suppose, par exemple, $n$ pair.
Le problème de savoir si oui ou non $\forall x_1< a_1\exists y_2 < a_2\forall x_3< a_3...\exists y_n <a_n R(x_1,y_2,x_3...y_n)$ est assez simple, et calculable en un temps pas plus que exponentiel par rapport à $a:=(a_1..a_n)\in C_n$
On partitionne ainsi (**) $C_n$ en 2. D'une manière imagée, disons qu'on a colorié les éléments de $C_n$ en 2 couleurs. Le théorème de Ramsey dit que quelque soit une partition de $C_n$ en un nombre fini de couleurs, il existe un ensemble infini $T\subseteq \N$ tel que toutes les suites de $C_n$ formées avec les éléments de $T$ sont de la même couleur.
Il se trouve (exercice) qu'avec la partition (**) {\bf une seule couleur} seulement est possible!
Par ailleurs, s'il existe $T$ infini tel que pour toute suite $a_1<..a_n$ croissante d'éléments de $T$ il est vrai que
$\forall x_1< a_1\exists y_2 < a_2\forall x_3< a_3...\exists y_n <a_n R(x_1,y_2,x_3...y_n)$
{\bf alors }
$\forall x_1 \exists y_2 \forall x_3...\exists y_n R(x_1,y_2,x_3...y_n)$
Et réciproquement.
Conclusion, le fait de savoir, pour la coloration (**) {\it récursive} et même presque polynomiale (tout dépend comment on représente les entiers) laquelle des 2 couleurs est la bonne dans la conclusion de Ramsey {\bf suffit} à savoir si n'importe quel énoncé d'arithmétique est vrai ou non, et donc dépasse de très loin les questions de décidabilité.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Remarque du jour, comme promis:
$P:=$la phrase qui dit "je ne suis pas démontrable en moins de 1000000000 symboles"
Il existe une preuve* de $P$, et il y a consensus pour dire que toutes les preuves de $P$ contiennent plus de 1000000000 symboles.
*On traduit en preuve formelle l'argument (assez long, il faut l'avouer) suivant:
On écrit tous les textes qui contiennent moins de 1000000 symboles et on "constate" qu'aucun d'entre eux n'est une preuve de $P$. On en infère $P$.
\centerline{*****************************}
Voici une godèlerie qui montre un peu plus en détails comment les choses sont faites:
Soit $P:=$la phrase qui dit "je ne suis pas démontrable"
Ce n'est pas une phrase très longue. Soit $n$ un entier dont on est {\bf sûr} pour telle ou telle raison que toute preuve d'un énoncé de moins de 1000 lettres en français (c'est par exemple le cas de $P$) implique qu'il existe une telle preuve de moins de $n$ symboles.
On disposerait effectivement d'un tel $n$ si toutes les phrases étaient "décidables" (dans le théorie ambiante). Il suffirait en effet de prendre la plus longue démonstration parmi la plus courte de chaque phrase prouvable.
On obtient alors une "preuve" de $P$: on écrit toutes les preuves de moins de $n$ symboles. On "constate" qu'aucune n'est une preuve de $P$ et on en infère $P$.
Dès lors, il devrait exister une "autre" démonstration de $P$ qui elle occuperait moins de $n$ symboles...
Conclusion: l'entier $n$ ci-dessus avec les propriétés voulues n'existe pas -
Soit $P:=$la phrase qui dit "toute preuve $d$ de moi est telle qu'il existe une preuve $d_2$ du faux dans la théorie ambiante de longueur $<$ à 3 fois celle de $d$"
Manifestement, si la théorie ambiante est contradictoire alors $P$ est décidable dans n'importe quelle "autre" théorie ambiante raisonnablement expressive...
Si maintenant, il existe une preuve $d$ de $P$ alors forcément il existe une preuve du faux dans la théorie ambiante: en effet,
de 2 choses l'une: ou bien aucune preuve $d_2$ de longueur $<3long(d)$ du faux n'existe dans la théorie ambiante et alors, on peut "prolonger" $d$ en une preuve du faux. Ou bien...
Tout ceci prouve que toute preuve $d$ de $P$ (et dans tous les cas, sans hypothèse supplémentaire) entraine l'existence d'une preuve $d_2$ du faux.
Mais on ne parvient pas à prouver que $d_2$ ne dépasse pas 3 fois la longueur de $d$... -
Une godèlerie un peu différente des habituelles:
$P:=${\it il y a un couple de phrases $(P_1, P_2)$ tel qu'il n'y a pas de preuve de $P_1$ strictement plus courte que toute preuve de $P_2$ et je suis $P_1$. De plus, $P_2$ dit qu'il n'y a pas de preuve de $P_2$ strictement plus courte ou aussi courte que toutes celles de $P_1$}
Il semble que l'une des 2 au moins doivent être vrai et que ce soit prouvable, non?
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 165.1K Toutes les catégories
- 58 Collège/Lycée
- 22.1K Algèbre
- 37.5K Analyse
- 6.3K Arithmétique
- 58 Catégories et structures
- 1.1K Combinatoire et Graphes
- 13 Sciences des données
- 5.1K Concours et Examens
- 20 CultureMath
- 51 Enseignement à distance
- 2.9K Fondements et Logique
- 10.7K Géométrie
- 83 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 79 Informatique théorique
- 3.9K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 337 Mathématiques et Physique
- 5K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10.1K Probabilités, théorie de la mesure
- 801 Shtam
- 4.2K Statistiques
- 3.8K Topologie
- 1.4K Vie du Forum et de ses membres