La démonstration de l'incomplétude
Il me la faut...
Donc on pompe (1) et (2) et aussi (3).
Au préalable, rappelons que toutes ces démonstrations ne sont que des variantes de la "diagonalisation", l'archétype étant la démonstration de la grandeur du monde, la diagonale des entiers. Rangeons les réels par leur infinité de décimales en les numérotant. Chaque rangée de la matrice infinie est un réel. Soit alors le réel défini avec une infinité de décimales comme étant celui qui a pour chaque chiffre la valeur de la case diagonale de la matrice plus 1 modulo 10. Ce nombre n'est pas dans la matrice par définition et donc est hors du monde: où qu'il est ?
Gödel utilise une astuce de ce genre mais avec 3 degrés d'indirections. Au dessus du lot, Kurt, il est.
POINT UN : Un système formel
On a donc un système formel, ses objets, ses constantes et ses axiomes et formules. Les objets sont les entiers, de zéro à N, avec N aussi grand qu'on veut. Il faudra préciser cela un peu, on verra après.
Voyons tout de suite: un système du premier ordre, c'est quand on ne peut quantifier QUE sur les variables, pas sur les "relations", c'est à dire les objets paramétrés par des variables.
Les formules sont celles obtenues des axiomes par application des formules à une variable libre (fauvl) aux objets existants (seulement les entiers, pas les formules) et bien sur par le modus ponens qui utilise la constante d'implication.
POINT DEUX : on encode le système dans N
On encode alors tout dans N, les formules à n signes en multipliant les n premiers nombres premiers à l'exposant p, p étant le numéro d'ordre de la constance considérée... Toute formule f a donc un nombre de Gödel g(f). Il faut noter que toute formule a un nombre de Gödel calculable et que à partir de tout nombre de Gödel, on peut trouver la formule qui l'a. Soit la fonction g' inverse de g. Tout nombre de Gödel n a ainsi une formule associée g'(n).
POINT TROIS : on exprime le fait d'être démontrable
Soit une formule de cette sorte mais démontrable dans le système. On va coder par son nombre de Gödel la formule qui exprime la phrase "est démontrable". Dem(n) signifie ainsi: "la formule de nombre de Gödel "n" est démontrable". Dem(n) est une formule et donc a un nombre de Gödel. Well done.
Pour préciser un peu, comme on a les quantificateurs, la formule "la formule f est démontrable" est formée de la suite de formules déduites les unes des autres par ce qu'on a dit, et se terminant par la formule f elle même. Une démonstration, donc. On ajoute un "il existe g, nombre de Gödel tel que" et le tour est joué: on a tous les entiers qui sont nombres de Gödel des fauvl démontrables.
Pour préciser davantage, on va considérer la formule suivante, notée PP(y) :
Existe(x) Dem (g'(y)) = g'(x)
qui exprime précisément que la formule de nombre de Gödel y, démontrable, a pour démonstration une formule dont le nombre de Gödel est x, dans N.
On prend sa respiration.
POINT QUATRE : on numérote les expressions pour avoir un espace de diagonalisation
On va alors numéroter les fauvl (quelles soient démontrables ou non) en partant de zéro. Il suffit de les classer en additionnant les valeurs de leurs constantes avec un truc en plus astucieux à préciser, bref. fauvl(i)(x) sont ces formules, en quelquesorte des "lambda": lambda x, fauvl(i)(x).
Attention ! Ca va diagonaliser...
fauvl(n) (n) est l'application à l'entier n de la fauvl de numéro n. Cette formule a un nombre de Gödel x.
On notera alors NOT PP (x) l'affirmation : "la formule fauvl(n)(n) n'est pas démontrable". C'est une AUTRE formule. On progresse, mais ce n'est pas fini.
Car mieux que ça, elle a une variable libre, donc elle est numérotée dans la liste du point QUATRE et donc, tatatata IL EXISTE un numéro de fauvl, k tel que:
fauvl(k)(n) = NOT PP(x) avec x = g(fauvl(n)(n))
Cette égalité sur la variable n est valide pour tout n, donc aussi pour n = k et donc on a une formule vraie sans variables libres:
fauvl(k)(k) = NOT Dem ( fauvl(k)(k) )
Cette formule EST le monstre de Gödel. On peut l'écrire A = NOT Dem(A)
Il faut bien voir que sa véracité est liée au fait qu'on l'a trouvé, c'est-à-dire sortie du néant, grâce à un IL EXISTE DONC qui tire une formule de la liste indéfinie où elle se trouve ! C'est cela qui fait qu'elle n'est pas, en fait démontrable, même si elle existe...
POINT CINQ
D'abord elle dit bien, et c'est la LA chose à comprendre ""JE" ne suis pas démontrable". Cette réflexivité, que je ne voyais pas comment exprimer avant ce jour, est ici parfaitement caractérisée: une formule A se trouve égale à l'assertion de sa non démontrabilité. Non seulement elle EST (existe, a une identité) mais EST aussi non démontrable. Elle arrive donc à parler d'elle même. C'est possible et c'est une formule du système formel contenant l'arithmétique etc.
A) Le monstre comme formule est indémontrable, elle et son contraire, d'ailleurs.
En fait c'est A qui est indémontrable bien sûr. Si elle l'était, elle serait "vraie" (car notre système est consistant) et elle ne serait DONC pas démontrable d'après la formule qui la définit. Au passage, si on peut dire, comme A est indémontrable et affirme qu'elle (par la magie de l'autoréférence) l'est, elle est DONC, vraie.
Si c'est son contraire qui ne l'est pas (démontrable), alors il faut une hypothèse supplémentaire, il faut que la théorie soit omega consistante, car cela entraine qu'elle ne le serait pas (oméga consistante). En effet, et là on se lance,
POINT SIX : l'oméga consistance
Cette histoire d'omega consistance est tout à fait intéressante... D'abord elle fut introduite par Kurt lui même et n'est pas nécessaire. Rosser avec un autre type de monstre, arrive au même résultat sans elle. Bon. Elle a quand même comme caractéristique, pour ce monstre là (celui qu'on préfère) de parler de l'infini. En gros dans une théorie contenant l'arithmétique, il peut y avoir d'autres objets que les nombres entiers, enfin les objets qu'on identifie aux nombres entiers.
Et bien si la théorie est omega consistante, et bien si une propriété est vraie pour tous les entiers, et bien on ne peut pas démontrer la négation de l'extension du quelque soit à tout l'espace.
Dans le cas de la démonstration qui nous occupe, si le contraire de A est démontrable, alors la démontrabilité de A est démontrée, et donc il existerait un "x" nombre de Gödel de la démonstration, ce qui nie le fait que quelquesoit n, il n'y a pas de démonstration. Attention tour de magie: comme il y a une démonstration (on a dit "la démontrabilité de A est démontrée" juste avant), cela crée une oméga inconsistance, refusée à l'avance donc bang.
B) Le monstre comme formule est indécidable.
C'est ce qu'on vient de voir, et tous les arguments "rigoureux" reviennent à un raisonnement paradoxal à l'emporte pièce qui serait celui ci: d'abord elle est vraie. Si elle était fausse, elle serait démontrable (c'est ce qu'elle dit) et donc ne le serait pas, bang. Ensuite si elle était démontrable, elle serait vraie, et donc non démontrable donc bang. Bref, tout ce qu'on a dit précédemment plus le second théorème et l'irréfragabilité. Bref, la totale. L'essentiel est qu'on a (enfin presque) exprimé la magie de la chose.
La magie de la "vérité" de la chose est apparente et c'est ce que je voulais obtenir. Ce qui est "vrai" c'est qu'il existe un nombre de Gödel pour une formule qui est la démonstration d'une autre formule. C'est cela qui affirme la "vérité", comme distincte de la prouvabilité et c'est ce qu'on voulait démontrer et comprendre.
Pour conclure après coup, et pour clarifier, la seule généralité vague acceptable qu'on peut tirer de tout ça est que la mécanisation du discours a des limites. Pas le discours. Plus précisément, c'est le programme dit de Hilbert qui se trouve ainsi convaincu d'impossibilité: il s'agissait de permettre l'expression "élémentaire" (mécanisée) de tout résultat prouvé par des moyens "abstraits" dans des théories cohérentes assez larges.
(1) http://www.dirk-k-lange.de/documents/Goedel-simple.pdf
(2) https://mat.iitm.ac.in/home/asingh/public_html/papers/goedel.pdf
(3) http://www.math.mcgill.ca/rags/JAC/124/theorems.html