Incomplétude de Gödel

Je viens de regarder tes anciens posts sur le forum, et j'espère que ma réponse te satisfera, il me semble à cette vue en tout cas. Mais lis-la doucement.

Pour éviter ce genre de confusion, je pense que le mieux serait que tu lises un cours de logique mathématique. La notion de vérité n'a pas de sens en mathématiques (théorème de Tarski), on peut seulement parler de vérité dans un modèle (ou un univers si tu préfères) donné. Par contre la notion de démontrabilité (à partir d'un jeu d'axiomes donné) a un sens bien précis.

Un énoncé démontrable est vrai dans tout modèle (et la réciproque est vraie, c'est le théorème de complétude de Gödel), mais un énoncé peut être vrai dans certains modèles et faux dans d'autres. Par exemple l'énoncé $\forall x,\ \forall y,\ x*y=y*x$ dans le langage de la théorie des groupes est vrai dans tout groupe abélien, faux dans tout groupe non abélien, et n'est par conséquent pas démontrable à partir des axiomes de la théorie des groupes.

Il en est de même de l'énoncé de Gödel, à partir des axiomes de Peano.

Bonjour.

On peut prouver qu'une assertion n'est pas vraie, cela revient à prouver qu'elle est fausse.

C'était, je crois, le dixième problème de Hilbert qui demandait s'il existait toujours un moyen de trouver des solutions à une équation diophantienne.
Il a été prouvé que ce n'était pas le cas.

À bientôt.

C'est bien un paradoxe du menteur mais avec des détails techniques élaborés (nécessaires mais très fastidieux à mettre en place: il s'agit des passages en bleu foncé ci-dessous ainsi que de la définition d'une preuve en arithmétique telle qu'évoquée au 5°: ils se trouvent dans les livres habituels sur le sujet).

Donnons l'idée générale (qui ressert et qui sert de guide pour comprendre les objectifs de ce genre de théorème).

1°) On se place dans un système formel (i.e. des listes de symboles et des règles pour les manipuler) où il y a, parmi les listes de symboles (on va les appeler des "termes"):
-un ensemble $Ph$ de termes appelé "phrases"
-un ensemble $Pr$ de termes appelé "propriétés"
-un ensemble $E$ de termes appelés "Entiers"
-une application $\alpha$ qui à partir d'une propriété $f$ et d'un entier $t$, forme une phrase "$\alpha(f;t)$" (qui se lit mettons "$t$ possède la propriété $f$", $t$ satisfait $f$ etc)
-une notion d'équivalence entre phrases (signifiant qu'elles veulent dire la même chose: "$p\equiv q$" abrégeant "$p$ équivaut à $q$")

2°) On suppose aussi donnée une "numérotation de Gödel" qui est un procédé associant à chaque terme $t$ un entier (numéro) unique de façon transparente (par exemple si tous les termes sont des listes finies de symboles pris parmi un ensemble fini à $d$ éléments de symboles $s_1,s_2,...s_d$ fixé à l'avance, on peut définir pour un terme $x=s_{u(1)}s_{u(2)}...s_{u(k)}$ le numéro $\#[x]$ de $x$ par $\sum_{i=1}^k d^{i-1} k_i$ en exploitant l'écriture d'un nombre en base $d$).
NB: dans la littérature on trouve très souvent la notation $\ulcorner y \urcorner$ au lieu de $\#(y)$ pour tout terme $y$.


3°) Enfin on suppose que dans le système où on se place, il existe un moyen de former, pour toute propriété $q$, une propriété $q^*$ telle que pour toute propriété $r$, il y a équivalence entre les phrases $\alpha(q^*; \#[r])$ et $\alpha \left( q; \# \left [\alpha (r; \#[r]) \right ]\right)$ (en arithmétique, dans le cadre de 2°, il s'agit surtout de décrire la fonction arithmétique $\varphi$ qui écrit un nombre $\rho$ en base $d$, obtenant une liste $\ell$ de symboles, concatène les listes de symboles "$\alpha($", $\ell$, "$;$", $\rho$, "$)$"; calcule la phrase correspondant à $\alpha(\ell,\rho)$ et renvoie le nombre dont la liste obtenue est l'écriture en base $d$ autrement dit $\#[$cette liste$]$. On a alors "$n$ satisfait $q^*$" qui équivaut à $\varphi(n)$ satisfait $q$ pour tout entier $n$).

Dans ces conditions on a le théorème de point fixe suivant, dont le théorème de Gödel est un cas particulier:

Pour toute propriété $p$, il existe une phrase $e$ équivalente à $\alpha(p; \#[e])$
Cette phrase n'est rien d'autre que $\alpha(p^*, \#[p^*])$ (le vérifier ce qui est immédiat d'après la définition de 3°)!!

Cette phrase dit intuitivement "mon numéro vérifie $p$".

*************************

N'importe quelle théorie contenant l'arithmétique est basée sur la logique (!) et permet de former des négations de propriétés.

4°) On déduit de ce qui précède le théorème de Tarski: sauf dans le cas où le système est contradictoire, il n'existe aucune propriété (au sens formel de ce texte: c'est-à-dire un élément de $P_r$ évoqué au 1° )$v$ exprimant la vérité d'une formule (i.e. telle que pour toute phrase $f$, $\alpha(v,\#[f])$ équivaut à $f$). En effet considérons alors la négation $\overline v$ de $v$: c'est une propriété telle que pour toute phrase $f$, $\alpha \left (\overline v; \#[f] \right)$ équivaut au contraire de $f$. Appliquons le théorème de point fixe à $\overline v$; on obtient une phrase $e_v$ qui équivaut au contraire de $e_v$ autrement dit elle-même, fournissant immédiatement une contradiction.

5°) Dans le premier théorème de Gödel la situation est un peu différente: il est possible de définir la démontrabilité d'une formule en arithmétique: une phrase $f$ est prouvable si et seulement si il existe une suite finie de phrases $f_1,...,f_m$ telles que $f_m=f$ et telles que certaines règles entièrement descriptibles par des moyens arithmétiques sont satisfaites.
Bref il y a une propriété $d$ telle que pour tout $n$, $\alpha(d;n)$ signifie "$n$ est le numéro de Gödel d'une phrase démontrable", sa négation $\overline d$, et enfin la phrase $e_d:= \alpha \left ( \overline d^* ; \# \left [\overline d^* \right ]\right)$
qui est une phrase exprimant "mon numéro de Gödel n'est pas celui d'une phrase démontrable" (dit plus succintement: "je ne suis pas démontrable").

Tes questions "d'impression" deviennent trop vagues.

la phrase de Godel existe autant que la phrase $47=88$.

c'est vrai que j'aurais bien aimé qu'on prouve en premier lieu que la phrase de Godel existe en tant que proposition réelle

Dans l'arithmétique c'est long à cause de l'implémentation du théorème chinois. Je te signale que dans l'arithmétique il est tout aussi long de définir $a=factorielle(b)$ puisque ça passe aussi par le théorème chinois qui implémente les suites finies.

Mais sinon, je te l'ai donnée. une fois implémenté ce que veut dire "prouvable" (et ce, comme tu veux), tu prends la phrase:



Tu lances ton programme (informatique).

- S'il la reconnait comme prouvable, elle est donc à la fois fausse et prouvable (et qui plus est si ton système est un tant soit peu ce qu'on attend de lui, elle est même prouvablement fausse).

- S'il ne la reconnaita pas comme telle, alors elle est vraie et pas prouvable.

Ca n'a rien de "mystérieux".

Bon évidemment, comme je te parle en français, ça te parait bizarre, mais une phrase en français est un cas particulier de suites de caractères. Certaines sont prouvables d'autres non. Les prouvables sont celles qui font sonner un programme quand on let met en paramètre (ie le programme tourne, tourne, puis à un moment dit "Eureka").

C'est la différence entre prouvable et vrai. Tu n'as pas de programme qui te dit quelles phrases sont vraies.

Concernant ton "interrogation" sur le fait que ce qui est prouvable est vrai, idem, on ne pourra jamais le prouver. Voici pourquoi.

Soit $T$ l'idée que tout ce qui est prouvable est vrai.

Soit $A$ la phrase telle que A = "il est prouvable que non(T et A)"

Supposons T et A. Alors il est prouvable que T => nonA.

Puisque T, étant prouvable, c'est vrai donc T=> nonA, contradiction.

Ce que je viens de prouver est que non(T et A). Il suit donc qu'on a A. Donc T est faux.

Je n'ai pas lu exprès ce passage avant de te répondre (si tu me donnes la page, je le ferai).

Mais c'est un logicien professionnel, donc il ne risque pas de s'insurger contre une définition. Il s'insurge peut-être contre la poésie du mot.

Il y a néanmoins des choses à préciser et je le fais ci-dessus:

1/ indécidable ne veut rien dire en arité 1. C'est un adjectif d'arité 2 : $P$ est indécidable dans $T$.

2/ En maths, ces abus de langage sont souvent tacites. Ils peuvent conduire à de graves malentendus, dont on retrouve d'ailleurs des dégâts collatéraux à l'exétérieur de la science, je prends un exemple que j'ai dû corriger 100 fois depuis 1an:

"musulman" ne veut rien dire, ce n'est pas un adjectif d'arité 1. La phrase "X est musulman" ne veut rien dire. C'est TRES EXACTEMENT la même chose:

- l'abus de langage corrigé donne "X est musulman à la date t".

- Ceci étant bien sûr à partir de la définition religieuse (et non pas culturelle) suivante: "X est musulman à l'instant t" étant une abréviation de "X affirme à l'instant t que Dieu a dicté le coran".

3/ Il en va de même pour les adjectifs, indécidables, MAIS AUSSI PROUVABLE, REFUTABLE, etc.
$P$ est prouvable ne veut rien dire. Ce qui a un sens est la phrase "P est prouvable dans T"

4/ Je tiens à dire que MOI MEME je commets (exprès) cet abus de langage par PURE PARESSE. Mais il faut rester conscient qu'on le commet.

5/ Par exemple "je ne suis pas prouvable" est un abus pour dire "je ne suis pas prouvable dans T", et le fait d'omettre $T$ est dû au fait qu'on la considère comme fixée par le contexte du discours. (Ici en l'occurrence c'était une des théories universelles (ie capable de calculer tous les récursivement énumérables de manière définissables) qu'on utilise "banalement" dans les maths : entre Peano et ZFC, avec dépassement parfois, ie ZFC+ autres axiomes.

Merci, je vais la visionner!

Médiat a écrit:

Les travaux de Woodin sur le sujet consistent justement à chercher des axiomes "intuitifs" (quoi que cela veuille dire) à ajouter à ZFC pour que l'on puisse, dans cette nouvelle théorie, démontrer HC ou non HC

On rajoute HC lui-même et hop le tour est joué :-D.

Ou alors on rajoute V=L (mais j'ai l'impression que ce choix est impopulaire alors que dans la vie courante un ensemble est basiquement un cas particulier de phrase avec une variable libre dédiée, avec quelques limitations pour éviter les contradictions immédiates).

@Médiat : je ne suis pas sûr que les axiomes proposés par Woodin soient franchement "intuitifs". Que ce soit $V=Ultimate-L$, qui entraîne $HC$, ou la $\Omega$-conjecture, qui entraîne $\neg HC$.

Sociologico-psycholigueqment, il y a des petits potins à connaitre:

1/ HW est un genre "d'espion" grassement payé aux USA et tenu probablement à tout plein de secrets défense.

2/ Il est très largement au dessus de tous dans la maitrise de ces choses (je ne sais pas pourquoi, je ne connais pas son évolution)

3/ Il a entrepris, par gentillesse conviviale, à la fois de collecter et retravailler en temps réel toutes les découvertes des spécialistes mondiaux. Je dis par convivialité car son choix initial de titres dans lesquels figurait "hypothèse du continu" faisaient se tordre de rire les spectateurs conviés à aller l'écouter, et il le savait, il se mettait au service du rire et de la bonne humeur.

4/ Il ne faut "pas trop prendre au sérieux" l'évolution (devenue cossue) de cette thématique, qui in fine s'est épaissie d'archives pointues, mais s'est fondée sur du rire.

5/ HW a lui-même évolué puisque le match mené actuellement par HC a longtemps été mené au score et de beaucoup par non(HC). Mais comme il fait une fixette sur L-ultimate, il déplace le focus favorablement vers HC pour l'instant.

6/ Ne pas négliger la potentialité d'un prochain épisode surprenant

7/ Ne pas oublier (ou savoir que) beaucoup de ses arguments sont les plus terriblement fautifs et éthiquement graves qui soient sur le plan scientifiques puisqu'ils sont de la forme "je suppose ça car le supposer donne du jus", ce qui est, même s'il n'est pas le seul coupable de ce grave crime anti-science objective, "définitivement disqualifiant" pour l'aspect qui intéresserait scienteux et philosopheux qui se demanderaient "Mme Vérité, dites-moi comment est fait le monde".