Pour ce qui est de ma propre opinion sur le sujet des formules qui « parlent d’elles-mêmes », vous la trouverez dans Comment la vérité et la réalité furent inventées (Gallimard 2009). J’ai reproduit récemment ici sur le blog le passage du livre qui s’intéresse spécifiquement aux propositions auto-référentielles.
Druuh :
Vous me demandiez d’expliciter cette fameuse formule qui dit d’elle même qu’elle n’est pas démontrable dans Peano. Je vais le faire et j’espère bien vous convaincre qu’il s’agit d’une vraie formule et non d’une illusion. Veuillez accepter de procéder en plusieurs étapes, en validant chaque étape avant de passer à la suivante afin de bien s’assurer qu’il n’y ait pas de malentendus.
Je ne me réfèrerai pas à l’article original de Gödel, mais au livre que je vous fourni en pièce jointe. Je pense qu’essentiellement le raisonnement est le même, mais comme je vous ai déjà dit le livre a la mérite de présenter les choses dans un langage plus moderne et plus épuré.
Avant de commencer, clarifions la problématique si vous le voulez bien : si j’ai bien compris, les critiques au théorème de Gödel que vous formulez avec Mr Jorion sont de 2 ordres :
le fait que « vrai et non démontrable » est un non sens.
2) le fait qu’une formule dans le langage de Peano ne peut pas dire d’elle meme qu’elle n’est pas démontrable dans Peano, et donc que la formule que présente Gödel n’est pas écrite dans le langage de Peano contrairement à ce qu’il affirme.
Yu LI：
1) le fait que « vrai et non démontrable » est un non sens.
Non, je n’ai pas dit ça.
En fait, « vrai et non démontrable » est une expression qu’il faut analyser de près. Justement j’ai cité le texte de Jean-Yves Girard pour en discuter (voir mon commentaire 6 Aout : https://www.pauljorion.com/blog/2022/04/09/what-makes-a-demonstration-worthy-of-the-name-by-paul-jorion-yu-li/)
2) le fait qu’une formule dans le langage de Peano ne peut pas dire d’elle même qu’elle n’est pas démontrable dans Peano, et donc que la formule que présente Gödel n’est pas écrite dans le langage de Peano contrairement à ce qu’il affirme.
Oui. Je veux précisément dire que, la formule dit d’elle même qu’elle n’est pas démontrable n’existe pas dans le langage de Peano.
Druuh :
En ce qui concerne le premier point : Partons des entiers relatifs Z comme groupe. Seriez vous d’accord pour dire que l’énoncé « pour tout x, pour tout y, x+y=y+x » est démontrable ? Que pensez vous de la réponse que vous a fait BasicRabbit le 7 aout à 14h17 ?
Le second point : tout d’abord, êtes vous convaincue du codage des formules et des démonstrations que l’on trouve par exemple a partir de la page 81 du livre en pièce jointe ?
Yu LI：
Puisque tu as lu la preuve du théorème d’incomplétude de Gödel dans ce livre, et que j’ai lu la preuve dans l’article de Gödel de 1931, je pense qu’il pourrait être intéressant de comparer les deux preuves.
Dans ton livre, on a parlé de la « fonction récursive », mais pas la « relation récursive ». Pourtant, la « relation récursive » est le concept central de la preuve de Gödel dans son article, car une formule est représentée par une relation récursive par Gödel.
Donc, je voudrai savoir：Comment la « relation récursive » est-elle représentée dans ton livre ?
Pour cela, je présente d’abord la « fonction récursive » et la « relation récursive » dans l’article de Gödel.
1, Les définitions de la « fonction récursive » et de la « relation récursive »
Gödel dit ([1], p.46-47) :
A number-theoretic function Φ(x1, x2, …xn) is said to be recursively defined by the number-theoretic functions Ψ(x1, x2, …xn-1) and μ(x1, x2, …xn + 1), if for all x2, … xn, k the following hold:
Φ(0, x2, …xn) = Ψ(x2, …xn)
Φ(k + 1, x2, …xn) = μ(k, Φ(k, x2, …xn), x2, …xn). (2)
A number-theoretic function Φ is called recursive, if there exists a finite series of number-theoretic functions Φ1, Φ2, … Φn which ends in Φ and has the property that every function Φk of the series is either recursively defined by two of the earlier ones, or is derived from any of the earlier ones by substitution, or, finally, is a constant or the successor function x + 1. The length of the shortest series of Φi that belongs to a recursive function Φ, is termed its degree.
A relation R(x1, x2, …xn) among natural numbers is called recursive, if there exists a recursive function Φ(x1, x2, …xn) such that for all x1, x2,… xn
R(x1, x2, …xn) ≡ [Φ(x1, x2, …xn) = 0]
2, Exemples
J’utilise deux exemples pour expliquer la signification de ces deux concepts.
Exemple 1 : Plus grand commun diviseur pgcd(a, b)
Définition récursive de pgcd(a, b), où a et b sont deux nombres naturels et a > b :
pgcd(a, b) = a, b=0
pgcd(a, b) = pgcd(b, mod(a, b)), b/=0
For exemple,
pgcd(12, 8) = pgcd(8, 4) = pgcd(4, 0) = 4, 12 et 8 ne sont pas des premiers entre eux.
pgcd(12, 5) = pgcd(5, 2) = pgcd(2, 1) = pgcd(1, 0) = 1, 12 et 5 sont donc des premiers entre eux.
Ainsi, la relation recursive peut être définie :
R(a, b) ≡ [pgcd(a, b) = 1] : décider si a et b sont des nombres premiers entre eux.
Conclusions : pgcd(a, b) est une fonction récursive, et aussi une fonction récursive primitive ; R(a, b) est une relation récursive, et R(a, b) est démontrable, car pgcd(a, b) lui-même peut être vu comme une démonstration par récurrence pour déterminer la valeur de vérité de R(a, b).
Exemple 2 : Conjecture de Collatz
Définition récursive de la séquence de Collatz :
fCollatz(n, i) = 1 (n=1)
fCollatz(n, i) = fCollatz(n/2, i+1) (n is pair)
fCollatz(n, i) = fCollatz(3n+1, i+1) (n is impair)
Par exemple,
fCollatz(5, 1) = fCollatz(16, 2) = fCollatz(8, 3) = fCollatz(4, 4) = fCollatz(2, 5) = fCollatz(1, 6) = 1
Cela correspond à une séquence de Collatz : 5, 16, 8, 4, 2, 1.
Ainsi, une relation recursive peut être définie :
R(n) = [fCollatz(n, 1) = 1] : décider si fCollatz(n, 1) peut s’arrêter à 1.
Conclusion : On ne sait pas si fCollatz(n, i) est la fonction récursive primitive, et si R(n) s’arrête à 1 pour toutes les n séquences, d’où la conjecture fCollatz.
[1]https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf
Druuh :
la définition de « récursif » pour Gödel dans son article est celle qu’on appelle aujourd’hui « récursif primitif », car on s’est apperçu depuis qu’il existe des fonctions récursives non récursives primitives telle la fameuse fonction d’Ackermann (mais je ne t’apprendrai rien puisque tu est informaticienne). La définition de Gödel est donc la meme que celle de fonction récursive primitive dans le livre pages 9 et 10.
Et page 11 la définition d’une relation récursive (primitive) est aussi la meme que celle que donne Gödel : fonction caractéristique récursive (primitive).
Mais ne perdons pas de vue notre fil : est tu donc d’accord avec le codage des formules et des démonstrations du chapitre p 81 du livre ? c’est le premier pas vers la formule qui pose problème
PS: n’oublies pas de répondre au premier point car c’est vraiment fondamental de se mettre d’accord là dessus et de clarifier ce point.
Yu LI :
Tu dis, « la définition de « récursif » pour Gödel dans son article est celle qu’on appelle aujourd’hui « récursif primitif », car on s’est apperçu depuis qu’il existe des fonctions récursives non récursives primitives telle la fameuse fonction d’Ackermann (mais je ne t’apprendrai rien puisque tu est informaticienne). La définition de Gödel est donc la même que celle de fonction récursive primitive dans le livre pages 9 et 10. »
Une fonction récursive primitive est prouvable, c’est-à-dire décidable. Étant donné que la définition de Gödel est donc la meme que celle de fonction récursive primitive, Gödel ne traite que « récursif primitif », en d’autres termes, il n’y a pas de « proposition indécidable » dans sa preuve !
Si c’est le cas, je me demande si tu te rends compte de la gravité du problème : l’article de Gödel n’est rien d’autre que les Habits neufs de l’empereur, …
Druuh :
Je ne comprends pas bien ce que tu dis, mais si tu veux bien, réservons ceci pour après nous pourrons en discuter. Je veux d’abord finir mon exposition pas à pas sans perdre de vue l’objectif. Si nous nous perdons en route nous n’arriverons jamais.
Donc avant de passer à l’étape suivante, est tu d’accord avec le codage des formules et des démonstrations présenté dans le chapitre de la page 81 du livre ?
Yu LI :
1. Concernant le codage des formules et des démonstrations
Tu dis, « Donc avant de passer à l’étape suivante, est tu d’accord avec le codage des formules et des démonstrations présenté dans le chapitre de la page 81 du livre ? »
Ce codage lui-même ne me pose pas de problème, ma vraie question est la suivante :
Quel est le but de ce codage ? Comment l’utiliser ?
2. Concernant la relation récursive (primitive)
Je suis d’accord que les relations récursives (primitives) dans l’article de Gödel sont représentées par les fonctions caractéristiques récursives (primitives) dans ton livre.
Puisqu’un ensemble est défini par sa fonction caractéristique, la décidabilité de la fonction caractéristique détermine alors l’existence de l’ensemble.
Ma question est : La preuve dans ton livre tient-elle compte de cette contrainte ?
Druuh :
Ta question en 2. : encore une fois je ne comprends pas bien ta question, mais gardons la pour après.
Tes questions en 1. : c’est l’objet de la suite : en page 94 on considère l’ensemble Dem = { (a,b) ; a est le numéro de Gödel d’une formule close F et b est le numéro de Gödel d’une démonstration de F dans T }. C’est un ensemble récursif. On lui applique le théorème de représentation de la page 77 pour obtenir une formule du langage de Peano DEM(x,y) qui la représente.
Est tu d’accord avec tout cela ?
Yu LI :
Dem = { (a,b) ; a est le numéro de Gödel d’une formule close F et b est le numéro de Gödel d’une démonstration de F dans T }.
Qu’est-ce qu’une formule close F?
Prenant l’exemple de la séquence de Collatz :
fCollatz(n, i) = 1 (n=1)
fCollatz(n, i) = fCollatz(n/2, i+1) (n est pair)
fCollatz(n, i) = fCollatz(3n+1, i+1) (n is impair)
Pourrais-tu expliquer quelle est la formule close F pour cet exemple ?
fCollatz(n, i) = 1 (n=1)
fCollatz(n, i) = fCollatz(n/2, i+1) (n est pair)
fCollatz(n, i) = fCollatz(3n+1, i+1) (n est impair)
Druuh :
Une formule close est une formule sans variables libres.
Par exemple, la formule Vx (x.y = 1) a la variable libre y (V= »pour tout »).
Une variable liée dans une formule du premier ordre est une variable qui est sous le champs d’un quantificateur. Une variable libre est une variable qui n’est pas liée.
Les formules closes sont celles auxquelles ont peut appliquer la théorie de la démonstration formelle de Hilbert qui est celle que Gödel prend en compte quand il parle d’énoncé « démontrable ».
On dit aussi « énoncé » pour « formule close ».
Je ne connaissais pas la séquence de Collatz, mais en regardant sur Wikipedia :
https://en.wikipedia.org/wiki/Collatz_conjecture
je me rend compte que tu l’as mal définie. La bonne définition est plutot :
https://en.wikipedia.org/wiki/Collatz_conjecture
fCollatz(n, 0) = k (un entier quelconque)
fCollatz(n, i+1) = fCollatz(n, i)/2 si fCollatz(n, i) est pair
fCollatz(n, i+1) = 3fCollatz(n, i) + 1 si fCollatz(n, i) est impair.
Ok donc quoi qu’il en soit, cette séquence est clairement récursive primitive en tant que fonction de N dans N. Pour savoir quelle est la formule de Peano qui la représente, il faudrait suivre pas à pas la preuve du théorème de représentation, ce qui serait très fastidieux.
Ta question « est ce que cette formule fait partie de Dem ? » n’a pas de sens, car Dem est un ensemble de couples d’entiers, pas un ensemble de formules. Et DEM (en lettres gotiques dans le livre) est une formule qui représente cet ensemble.
Mais je reviens à mon déroulement : est tu donc d’accord que la formule DEM(x,y) (lettres gothiques) est bien une formule du langage de Peano qui représente l’ensemble Dem au sens de la définition 2 p 76 ?
Yu LI :
Je trouve que nos discussions actuelles sont très constructives !
Tu dis：est tu donc d’accord que la formule DEM(x,y) (lettres gothiques) est bien une formule du langage de Peano qui représente l’ensemble Dem au sens de la définition 2 p 76 ?
Cette question est au cœur de la preuve de Gödel, alors ne me presse pas de répondre par oui ou par non, clarifions d’abord la signification de Dem et DEM(x,y).
Tu dis: Dem est un ensemble de couples d’entiers, pas un ensemble de formules. Et DEM (en lettres gotiques dans le livre) est une formule qui représente cet ensemble.
Une telle explication n’est pas suffisante pour illustrer la signification de Dem et DEM(x,y), le mieux est donc d’utiliser des exemples représentatifs pour l’illustrer. Je pense que la conjecture de Collatz en est un bon exemple.
D’abord, une clarification est nécessaire sur la définition de la séquence de Collatz :
Tu donne la définition du wiki :
fCollatz(n, 0) = n (un entier quelconque)
fCollatz(n, i+1) = fCollatz(n, i)/2 si fCollatz(n, i) est pair
fCollatz(n, i+1) = 3fCollatz(n, i) + 1 si fCollatz(n, i) est impair.
Cette définition est formellement une « fonction récursive », mais la génération effective de la séquence de Collatz se fait de manière itérative :
Par exemple, n = 5
fCollatz(5, 0) = 5
fCollatz(5, 1) = 3*fCollatz(n, 0)+1= 16
fCollatz(5, 2) = fCollatz(n, 1)/2 = 8
fCollatz(5, 3) = fCollatz(n, 2)/2 = 4
fCollatz(5, 4) = fCollatz(n, 3)/2 = 2
fCollatz(5, 5) = fCollatz(n, 4)/2 = 1
Par conséquent, j’utilise une définition alternative qui rend la génération effective de la séquence de Collatz par recurrence :
fCollatz(n, i) = 1 (n=1)
fCollatz(n, i) = fCollatz(n/2, i+1) (n is pair)
fCollatz(n, i) = fCollatz(3n+1, i+1) (n is impair)
Par exemple :
fCollatz(5, 1)
= fCollatz(16, 2)
= fCollatz(8, 3)
= fCollatz(4, 4)
= fCollatz(2, 5)
= fCollatz(1, 6)
= 1
Il existe également des variantes, telles que （https://skobki.com/en/c-language-recursion-and-the-collatz-conjecture/）:
collatz(n) = 0 (n=1)
collatz(n) = 1 + collatz(n/2) (n is pair)
collatz(n) = 1 + collatz(3n+1) (n is impair)
collatz(5)
= 1 + collatz(16)
= 2 + collatz(8)
= 3 + collatz(4)
= 4 + collatz(2)
= 5 + collatz(1)
= 5
Cette définition renvoie le nombre de pas nécessaires lorsque la séquence s’arrête à 1.
Par conséquent, tu ne peux pas dire : Ok donc quoi qu’il en soit, cette séquence est clairement récursive primitive en tant que fonction de N dans N.
Car si cette séquence est récursive primitive en tant que fonction de n dans N, cela signifie qu’on sait si pour tout n, la séquence s’arrête à 1 ou non, et la fonction récursive primitive elle-même est sa preuve. Dans ce cas, la conjecture de Collatz devient le théorème de Collatz, mais la conjecture de Collatz reste toujours conjecture jusqu’à maintenant !
Donc à mon avis, la fonction de la séquence de Collatz ne peut pas être exprimée dans Dem, car il n’existe pas (jusqu’à ce jour) de preuve que cette séquence s’arrête à 1.
Est-ce que tu es d’accord ?
Druuh :
Je ne comprends pas pourquoi tu veux faire rentrer la sequence de Collatz dans le cadre du theoreme de Gödel, mais encore une fois je propose d’en reparler une fois arrivés au bout de mon argumentation, ainsi que tes autres questions en suspens.
Quand tu dis « la fonction de la séquence de Collatz ne peut pas être exprimée dans Dem », je vois que tu n’as pas compris ce qu’est Dem car cette remarque n’a pas de sens. En effet, Dem est un ensemble de couples d’entiers et la sequence de Collatz est une fonction, donc que signifie qu’une fonction « ne peut pas etre exprimee » dans un ensemle de couples d’entiers ? Tu veux peut etre dire que la sequence de Collatz ne peut pas etre representée par une formule de Peano selon la definition 2 p 76 ?
Ensuite, tu dis « Tu dis: Dem est un ensemble de couples d’entiers, pas un ensemble de formules. Et DEM (en lettres gotiques dans le livre) est une formule qui représente cet ensemble.Une telle explication n’est pas suffisante pour illustrer la signification de Dem et DEM(x,y) »
Bien entendu que ce n’est pas suffisant, il faut te reporter aux definitions de Dem et de la formule DEM, mais je pensais que tu l’avais deja fait ! La definition de Dem comme ensemble de couples d’entiers utilise le codage des formules et des demonstrations, et tu m’as dis que tu n’avais pas de problemes avec ces codages. Je te la redonne :
Dem = { (a,b) ; a est le numéro de Gödel d’une formule close F et b est le numéro de Gödel d’une démonstration de F dans Peano }
Quant a la definition de DEM, elle utilise le theoreme de representation de la page 77. En effet, puisque Dem est un ensemble recursif, on peut lui appliquer le theorme de representation, et il existe une formule a deux variables libres DEM(x,y) qui represente l’ensemble recursif d’entiers Dem au sens de la definition 2 p 76.
Prend bien le temps de relire tout ceci dans le livre, et si tu as des questions ou des doutes parlons en. Une fois tout cela clair pour toi, il ne reste presque plus rien pour arriver au bout.
Enfin, ne pense pas pouvoir illustrer ceci avec des exemples non triviaux, car pour passer d’un ensemble recursif d’entiers a la formule qui le represente, il faut suivre pas a pas la preuve du theoreme de representation, et bien que cela soit possible en principe, cela serait beaucoup trop fastidieux, et cela ferait probablement rentrer en jeu des entiers beaucoup trop grands pour etre fait a la main.
C’est un peu comme si je disais « je ne te crois pas que le chiffre mille millards de millards existe : prouve le moi en comptant un par un jusque la ». Tu me repondrais « je ne peux pas compter jusque la, mais ce chiffre existe cependant pour des raisons evidentes ».
Yu LI :
« Je ne comprends pas pourquoi tu veux faire rentrer la sequence de Collatz dans le cadre du theoreme de Gödel, mais encore une fois je propose d’en reparler une fois arrivés au bout de mon argumentation, ainsi que tes autres questions en suspens. »
Ok, tu continues jusqu’au bout de ton argumentation, et pour l’instant nous laissons tomber mes questions, y compris la sequence de Collatz.
Druuh :
Ok mais avant de passer a l’etape suivante, je dois m’assurer que tu as bien compris Dem et DEM.
Est ce le cas ? est tu convaincue que DEM est une formule du language de Peano qui represente Dem ?
Yu LI :
Maintenant c’est moi qui ne comprends pas.
Tu as dit, « Je ne comprends pas pourquoi tu veux faire rentrer la sequence de Collatz dans le cadre du theoreme de Gödel, mais encore une fois je propose d’en reparler une fois arrivés au bout de mon argumentation, ainsi que tes autres questions en suspens. »
Donc, j’ai répondu, « tu continues jusqu’au bout de ton argumentation, et pour l’instant nous laissons tomber mes questions, y compris la sequence de Collatz »
Et maintenant, tu me demande : est tu convaincue que DEM est une formule du language de Peano qui represente Dem ?
Mais si je ne pose pas des questions sur Dem et DEM, et n’utilise pas des exemples pour concrétiser cette comprehension, comment je peux être sure que je suis convaincue que DEM est une formule du language de Peano qui represente Dem ?
Druuh :
Tu peux en etre convaincue en validant la demonstration du theoreme de representabilité. C’est le coeur de tout ceci. Soit tu as confiance que sa demonstration est correcte. Dans le cas contraire, tu dois verifier les details de la preuve pour t’assurer de la validité du theoreme.
Tu n’auras pas de formule explicite pour DEM. Tu sauras cependant que c’est bien une formule du langage de Peano grace au theoreme de representabilité.
Excuse moi d’etre un peu insistant, mais c’est presque la fin en ce qui concerne l’existence de la « formule qui dit d’elle meme qu’elle n’est pas demontrable dans Peano ».
Yu LI :
Est-ce que DEM peut être considéré comme la fonction caractéristique de l’ensemble Dem ?
Druuh :
C’est bien que tu poses ces questions car il est essentiel de bien avoir compris tout cela pour pouvoir comprendre le theoreme de Gödel.
Le théoreme de représentabilité : lis (ou relis) attentivement la définition d’une fonction et d’un ensemble représentable p 76 (définition 1 et définition 2). Fait de même pour l’énoncé du théoreme de représentation p 77.
Dis moi si il y a des choses que tu ne comprends pas bien dans ces définitions et dans l’énoncé du théoreme de représentation.
DEM n’est pas la fonction caractéristique de Dem, c’est une formule du langage de Peano, ce n’est pas une fonction. Tu est en train de faire des confusions, mais je vais m’efforcer d’éclaicir totu cela pour que tu finisses par y voir clair 🙂
Yu LI :
J’ai lu définition 1 et définition 2 ainsi que l’énoncé du théorème de représentation.
Je repose ma question : Est-ce que DEM est la formule représente la fonction caractéristique de l’ensemble Dem ?
Druuh :
Pas tout à fait : pour avoir la formule qui représente la fonction caractéristique de Dem il faut modifier un peu DEM(x,y) comme dans la remarque page 76.
Ce qui est vrai (et que met en évidence la meme remarque), c’est qu’un ensemble de tuples d’entiers est représentable si et seulement si sa fonction caractéristique l’est.
D’autres doutes ?
Yu LI :
Je pense que j’ai compris la signification de Dem et DEM(x,y).
Concernant Théorème de représentation, ça signifie qu’une « fonction récursive » peut être « représentée » en termes de formule (« relation récursive » dans l’article de Gödel), comme montré par quelques exemples donnés dans le livre :
– La fonction successeur est représentée par la formule v0 = Sv1
– L’addition lamda xy x+y est représentée par la formule v0 = v1+ v2
Druuh :
Oui c’est bien cela, un autre exemple simple et instructif de représentation d’une fonction récursive par une formule du language de Peano est le lemme 1 p 77, qui explicite quelle formule est utilisée pour représenter une composition de fonctions. Cette formule utilise des quantificateurs, elle est donc un peu plus élaborée que les exemples que tu as cité. Je t’invite à regarder la formule de ce lemme avec attention pour te convaincre qu’elle représente bien la composition des fonctions. Le reste de la preuve du théoreme de représentabilité est un peu moins triviale, elle consiste à vérifier que ça fonctionne aussi avec le schéma mu et le schéma de récurrence.
Je continue donc : maintenant qu’on à notre disposition la formule DEM(x,y), on peut d’ores de et déjà fabriquer très facilement une « formule qui dit qu’une AUTRE formule n’est pas démontrable dans Peano ». La dernière étape de la « formule qui dit d’ELLE MEME qu’elle n’est pas démontrable » sera une variante un peu plus élaborée de celle là.
Commençons donc par du très simple : je prends une formule close du langage de Peano (un énoncé) quelconque F. Je prends son numéro de Gödel a (un entier naturel). Je considère la formule close
G = ¬∃ v DEM(a_,v)
G est bien une formule du language de Peano puisque DEM(x,y) en est déjà une.
Enfin, G « dit » que F n’est pas démontrable dans Peano dans le sens suivant : G est satisfaite dans le modèle N si et seulement si F n’est pas démontrable dans Peano (par définition même de Dem et le fait que DEM représente Dem).
Est tu d’accord avec tout cela ?
Yu LI :
Merci beaucoup de ta patience pour toutes ces explications ! Sinon, je ne sais pas combien de temps il m’aurait fallu pour comprendre cette version académique de la preuve de Gödel. Je vais maintenant commenter cette preuve.
Tu dis, « maintenant qu’on à notre disposition la formule DEM(x,y), on peut d’ores de et déjà fabriquer très facilement une « formule qui dit qu’une AUTRE formule n’est pas démontrable dans Peano ». La dernière étape de la « formule qui dit d’ELLE MEME qu’elle n’est pas démontrable » sera une variante un peu plus élaborée de celle là ».
C’est-à-dire que la preuve de Gödel se porte sur la formule DEM(x,y) !
La formule DEM(x,y) est une représentation de l’ensemble Dem, et l’existence de l’ensemble Dem dépend de l’existence de la fonction caractéristique de Dem qui, étant donné une formule F (codée comme a) et une preuve de F (codée comme b), décide si (a,b) est un élément de l’ensemble Dem :
Dem = { (a,b) ; a est le numéro de Gödel d’une formule close F et b est le numéro de Gödel d’une démonstration de F dans Peano }
La détermination si (a,b) est un élément de l’ensemble Dem consiste à décider (ou de vérifier) si la preuve de F (codée comme b) est valide, c’est-à-dire à décider la validité d’une preuve donnée, ce qui est le vrai cœur du « problème indécidable » ！
Les travaux de Turing, Church montrent qu’il n’y a pas de méthode universelle de déterminer la validité d’une preuve donnée, c’est-à-dire que la fonction caractéristique de Dem n’existe pas! Par conséquence, Dem n’existe pas, DEM non plus, et finalement la « formule qui dit d’ELLE MEME qu’elle n’est pas démontrable » ne peut pas être construite comme Gödel dit.
En effet, la preuve du théorème d’incomplétude de Gödel n’est plus une preuve logique purement formelle, mais implique le problématique de l’ « existence » , …
Druuh :
Ta remarque revient a dire que si Dem n’est pas un ensemble recursif, alors toute l’argumentation s’effondre et la formule DEM n’existe pas.
Mais je te rassure : Dem est bel et bien un ensemble recursif. Pour t’en convaincre, regarde la proposition p 90 dont l’objet est precisement de demontrer que Dem est recursif.
Essentiellement, il se passe la chose suivante : il n’existe en effet pas d’algorithmes (de machine de Turing) qui permette de savoir si une formule F est demontrable. C’est ce que tu dis dans ta remarque et tu as raison. En revanche, on peut verifier en un temps fini si une pretendue preuve (formelle au sens de Hilbert) d’une formule en est bien une : il suffit de verifier si toutes les etapes de la preuve sont correctes, et de verifier si la derniere etape conclue a la formule F. C’est essentiellement la peruve de la proposition p 90.
Yu LI :
« Ta remarque revient a dire que si Dem n’est pas un ensemble recursif, alors toute l’argumentation s’effondre et la formule DEM n’existe pas. »
Non. Ce que je voulais dire : la formule DEM existe si Dem est un « ensemble récursif primitif » ; cependant, l’existence d’un ensemble récursif primitif dépend de la détermination de la fonction récursive primitive, ce qui est indécidable.
Ce qui est important à noter est que, la « fonction récursive » et la « fonction récursive primitive » sont deux notions de deux niveaux complètement différents, comme montre la fonction fCollatz(n) impliquée dans la conjecture de Collatz :
fCollatz(n) = 1 (n=1)
fCollatz(n) = fCollatz(n/2) (n is pair)
fCollatz(n) = fCollatz(3n+) (n is impair)
(Note : j’ai légèrement modifié fCollatz(n) en supprimant la variable i)
fCollatz(n) est une fonction récursive, mais jusqu’à présent elle n’a pas été reconnue comme une fonction récursive primitive. Cet exemple illustre que la détermination de la fonction récursive primitive est indécidable.
« Essentiellement, il se passe la chose suivante : il n’existe en effet pas d’algorithmes (de machine de Turing) qui permette de savoir si une formule F est demontrable. C’est ce que tu dis dans ta remarque et tu as raison. En revanche, on peut verifier en un temps fini si une pretendue preuve (formelle au sens de Hilbert) d’une formule en est bien une : il suffit de verifier si toutes les etapes de la preuve sont correctes, et de verifier si la derniere etape conclue a la formule F. C’est essentiellement la peruve de la proposition p 90. »
Non. Cette conclusion ne vaut que pour les preuves de formes spéciales, comme le raisonnement par recurrence ; mais Gödel discute des preuves de toute formule dans un système formel.
Par exemple, la fonction recursive fCollatz(n), en tant que preuve de la conjecture de Collatz, nous ne savons pas s’il s’agit d’une preuve valide, c’est-à-dire, si la séquence de Collatz s’arrête à 1 pour tout n.
La chose primordiale concernant le « problème indécidable » est que, la détermination de la validité d’une preuve donnée revient en fait à identifier les raisonnements fallacieux, ce qui ne peut être entièrement formalisé ; il s’agit d’une connaissance de bon sens connue depuis l’époque d’Aristote,…
Druuh :
»la formule DEM existe si Dem est un « ensemble récursif primitif » » :
non, il suffit que Dem soit un ensemble récursif. Si tu reprends la preuve du théoreme de représentation dans le livre, tu verras qu’il prouve que toute fonction récursive est représentable par une formule du language de Peano. C’est grace à la possibilité de representer le « schéma mu », qui est la seule chose qui différencie récursif et récursif primitif.
Je réserve tes autres remarques et questions pour plus tard, mais je ne les évacue pas.
Yu LI :
Ce dont nous discutons actuellement est en fait similar à la question a posé par Zermelo quand l’article de Gödel vient sortir. Malheureusement, Gödel n’a pas répondu directement à cette question et a rapidement mis fin à ce qui aurait été une conversation extrêmement intéressante !
Un passage de la lettre de Zermelo (https://www.sciencedirect.com/science/article/pii/0315086085900709) :
While I was engaged in preparing a short abstract of my Elster lecture, in the course of which I had also to refer to yours, I came subsequently to the clear realization that your proof of the existence of undecidable propositions exhibits an essential gap. In order to produce an “undecidable” proposition, you define on page 178 a “class sign” (a propositional function of one free variable) S = R(q), and then you show that neither [R(q);q] = A nor its negation ¬A would be “provable.” But does
S = ¬Bew[R(n);n]
really belong to your “system,” and are you justified in identifying this function with R(q), just because it is a “class sign “?
Druuh :
Ok là tu est en train de parler de la démonstration originale de Gödel, que je n’ai pas encore lue par manque de temps. Je vais essayer de m’y mettre, mais finissions d’abord avec la démonstration du livre.
Est tu d’accord que Dem est un ensemble récursif comme démontré dans la proposition p 90 ?
Qu’on peut donc lui appliquer le théoreme de representation pour obtenir une formule DEM(x,y) exprimée dans le language de Peano ?
Qu’on peut facilement à partir de là obtenir l’énoncé G présenté dans un mail precedent qui dit qu’un autre énoncé F n’est pas démontrable dans Peano (« dit » dans le sens que j’ai précisé dans le meme mail) ?
Yu LI :
Représenter une » fonction récursive » comme une formule exprimée dans le langage de Peano ne change pas son existence, c’est-à-dire, si cette » fonction récursive » existe dans le système, elle y existe toujours après on lui appliquer le théoreme de representation.
Par exemple.
– La fonction successeur est représentée par la formule v0 = Sv1
– L’addition lamda xy x+y est représentée par la formule v0 = v1+ v2
Cependant, une formule paradoxale tel que « dit d’elle qu’elle est indémontrable », bien que formellement elle est représentable, n’existe pas réellement dans le système de Peano.
En d’autres termes, la représentation et l’existence sont deux concepts de deux niveaux complètement différents. Le théoreme de representation ne concerne que la représentation, mais l’essence du « problème indécidable » met l’accent sur l’existence, plutôt que sur la représentation.
Druuh :
Le théoreme de représentabilité dit que pour toute fonction récursive, IL EXISTE une formule du language qui la représente.
Je ne comprends ta distinction entre représentabilité et existence.
Yu LI :
« Est tu d’accord que Dem est un ensemble récursif comme démontré dans la proposition p 90 ? »
Non, je ne suis pas d’accord.
Regarde encore l’exemple de la conjecture de Collatz :
Etant donné la suite de formules :
fCollatz(n) = 1 (n=1)
fCollatz(n) = fCollatz(n/2) (n is pair)
fCollatz(n) = fCollatz(3n+1) (n is impair)
On ne sait pas jusqu’à maintenant si la séquence de Collatz s’arrête à 1, c’est-à-dire, si cette suite est une démonstration est effectif.
Comment peut-on dire (p 90) :
– Il suffit de se reporter à la définition d’une démonstration (chapitre 4, 1.3) et de se rendre compte que le procédé permettant de vérifier si une suite de formules est une démonstration est effectif.
J’ai dit :
– La chose primordiale concernant le « problème indécidable » est que, la détermination de la validité d’une preuve donnée revient en fait à identifier les raisonnements fallacieux, ce qui ne peut être entièrement formalisé ; il s’agit d’une connaissance de bon sens connue depuis l’époque d’Aristote,…
Malheureusement ce sujet primordiale a été ignoré par Gödel et la quasi-totalité de la communauté scientifique !
Druuh :
Ok, alors a ce stade de notre discussion je propose de faire une pause sur mon exposition et de revenir aux questions en suspens que tu as posées au cours de notre échange. Il faut clarifier tout cela car il y a des choses que tu dis depuis le debut et que je ne comprends pas.
Tout d’abord, quelle est ta definition d’un ensemble (et d’une fonction) récursif primitif et d’un ensemble (et d’une fonction) récursif ?
Ensuite, peut tu m’expliquer le lien que tu fait entre la sequence de Collatz et le théorème de Gödel ?
Et aussi : qu’entends tu par le « problème indécidable » associé a Church et Turing auquel tu as fait reference plusieurs fois ?
****
Annexe
Des extraites cités dans nos dialogues du livre :
Logique Mathématiques
Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles
Réné Cori, Daniel Lascar
P. 76-77
2. Les Fonctions Représentables
Rappelons que Fp désigne l’ensemble des fonctions totales de NP dans N.
Définition 1 : Soient f dans Fp et F[v0,v1,v2,…,vp] une formule de L0 qui n’a pas de variables libres en dehors de v0,v1,v2,…,vp. On dit que F[v0,v1,v2,…,vp] représente f si, pour tout p-uple d’entiers (n1,n2,…,np), on a :
P0 ⊢ ∀ v0 (F[v0,v1,v2,…,vp] ↔ v0 = f(n1,n2,…,np))
On dit que la fonction f est représentable s’il existe une formule qui la représente.
Définition 2 : Soient A inclus NP et F[v1,v2,…,vp] une formule qui n’a pas de variables libres en dehors de v1,v2,…,vp. On dit que F représente A si, pour tout p-uple d’entiers (n1,n2,…,np), on a :
si (n1,n2,…,np) in A alors P0 ⊢ F[n1,n2,…,np]
si (n1,n2,…,np) non in A alors P0 ⊢ ¬F[n1,n2,…,np]
On dit que l’ensemble A est représentable s’il existe une formule qui le représente.
Remarque : Un ensemble A inclus NP est représentable si et seulement si sa fonction caractéristique l’est : on vérifiera que, si F représente A, la formule
(F[n1,n2,…,np] ∧ v0=1) ∨ (¬F[n1,n2,…,np] ∧ v0=0)
représente la fonction caractéristique de A; réciproquement, si G[v0, v1,v2,…,vp] représente la fonction caractéristique de A, alors G[1, v1,v2,…,vp] représente A.
Exemples :
La fonction successeur est représentée par la formule v0 = Sv1
L’addition lxy x+y est représentée par la formule v0 = v1+ v2
…
En fait, toutes les fonctions récursives sont représentables :
Théorème de représentation : Toute fonction récursive (totale) est représentable.
Laisser un commentaire