![\"\"](\"https:\/\/www.pauljorion.com\/blog\/wp-content\/uploads\/kurt-go\u0308del-232x300.png\")
<\/p>\n<\/p>\n
Pour ce qui est de ma propre opinion sur le sujet des formules qui \u00ab parlent d\u2019elles-m\u00eames \u00bb<\/strong>, vous la trouverez dans Comment la v\u00e9rit\u00e9 et la r\u00e9alit\u00e9 furent invent\u00e9es<\/b> (Gallimard 2009). J’ai reproduit r\u00e9cemment ici sur le blog<\/a> le passage du livre qui s’int\u00e9resse sp\u00e9cifiquement aux propositions auto-r\u00e9f\u00e9rentielles<\/strong>.<\/em><\/p>\n Druuh :<\/p>\n Vous me demandiez d’expliciter cette fameuse formule qui dit d’elle m\u00eame qu’elle n’est pas d\u00e9montrable dans Peano. Je vais le faire et j’esp\u00e8re bien vous convaincre qu’il s’agit d’une vraie formule et non d’une illusion. Veuillez accepter de proc\u00e9der en plusieurs \u00e9tapes, en validant chaque \u00e9tape avant de passer \u00e0 la suivante afin de bien s’assurer qu’il n’y ait pas de malentendus. Je ne me r\u00e9f\u00e8rerai pas \u00e0 l’article original de G\u00f6del, mais au livre que je vous fourni en pi\u00e8ce jointe. Je pense qu’essentiellement le raisonnement est le m\u00eame, mais comme je vous ai d\u00e9j\u00e0 dit le livre a la m\u00e9rite de pr\u00e9senter les choses dans un langage plus moderne et plus \u00e9pur\u00e9.<\/p>\n Avant de commencer, clarifions la probl\u00e9matique si vous le voulez bien : si j’ai bien compris, les critiques au th\u00e9or\u00e8me de G\u00f6del que vous formulez avec Mr Jorion sont de 2 ordres :<\/p>\n le fait que \u00ab\u00a0vrai et non d\u00e9montrable\u00a0\u00bb est un non sens. Yu LI\uff1a<\/p>\n 1) le fait que \u00ab\u00a0vrai et non d\u00e9montrable\u00a0\u00bb est un non sens.<\/p>\n Non, je n\u2019ai pas dit \u00e7a.<\/p>\n En fait, \u00ab vrai et non d\u00e9montrable \u00bb est une expression qu\u2019il faut analyser de pr\u00e8s. Justement j\u2019ai cit\u00e9 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\/)<\/p>\n 2) le fait qu’une formule dans le langage de Peano ne peut pas dire d’elle m\u00eame qu’elle n’est pas d\u00e9montrable dans Peano, et donc que la formule que pr\u00e9sente G\u00f6del n’est pas \u00e9crite dans le langage de Peano contrairement \u00e0 ce qu’il affirme.<\/p>\n Oui. Je veux pr\u00e9cis\u00e9ment dire que, la formule dit d\u2019elle m\u00eame qu\u2019elle n\u2019est pas d\u00e9montrable n\u2019existe pas dans le langage de Peano.<\/p>\n Druuh :<\/p>\n En ce qui concerne le premier point : Partons des entiers relatifs Z comme groupe. Seriez vous d’accord pour dire que l’\u00e9nonc\u00e9 \u00ab\u00a0pour tout x, pour tout y, x+y=y+x\u00a0\u00bb est d\u00e9montrable ? Que pensez vous de la r\u00e9ponse que vous a fait BasicRabbit le 7 aout \u00e0 14h17 ?<\/p>\n Le second point : tout d’abord, \u00eates vous convaincue du codage des formules et des d\u00e9monstrations que l’on trouve par exemple a partir de la page 81 du livre en pi\u00e8ce jointe ?<\/p>\n Yu LI\uff1a<\/p>\n Puisque tu as lu la preuve du th\u00e9or\u00e8me d’incompl\u00e9tude de G\u00f6del dans ce livre, et que j’ai lu la preuve dans l’article de G\u00f6del de 1931, je pense qu\u2019il pourrait \u00eatre int\u00e9ressant de comparer les deux preuves.<\/p>\n Dans ton livre, on a parl\u00e9 de la \u00ab fonction r\u00e9cursive \u00bb, mais pas la \u00ab relation r\u00e9cursive \u00bb. Pourtant, la \u00ab relation r\u00e9cursive \u00bb est le concept central de la preuve de G\u00f6del dans son article, car une formule est repr\u00e9sent\u00e9e par une relation r\u00e9cursive par G\u00f6del.<\/p>\n Donc, je voudrai savoir\uff1aComment la \u00ab relation r\u00e9cursive \u00bb est-elle repr\u00e9sent\u00e9e dans ton livre ?<\/p>\n Pour cela, je pr\u00e9sente d\u2019abord la \u00ab fonction r\u00e9cursive \u00bb et la \u00ab relation r\u00e9cursive \u00bb dans l\u2019article de G\u00f6del.<\/p>\n 1, Les d\u00e9finitions de la \u00ab\u00a0fonction r\u00e9cursive\u00a0\u00bb et de la \u00ab\u00a0relation r\u00e9cursive \u00bb<\/p>\n G\u00f6del dit ([1], p.46-47) : A number-theoretic function \u03a6 is called recursive, if there exists a finite series of number-theoretic functions \u03a61, \u03a62, \u2026 \u03a6n which ends in \u03a6 and has the property that every function \u03a6k 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\u202f+\u202f1. The length of the shortest series of \u03a6i that belongs to a recursive function \u03a6, is termed its degree.<\/p>\n A relation R(x1,\u202fx2,\u202f\u2026xn) among natural numbers is called recursive, if there exists a recursive function \u03a6(x1,\u202fx2,\u202f\u2026xn) such that for all x1, x2,\u2026 xn<\/p>\n R(x1,\u202fx2,\u202f\u2026xn) \u2261 [\u03a6(x1,\u202fx2,\u202f\u2026xn) = 0]<\/p>\n 2, Exemples<\/p>\n J’utilise deux exemples pour expliquer la signification de ces deux concepts.<\/p>\n Exemple 1 : Plus grand commun diviseur pgcd(a, b)<\/p>\n D\u00e9finition r\u00e9cursive de pgcd(a, b), o\u00f9 a et b sont deux nombres naturels et a > b : For exemple, Ainsi, la relation recursive peut \u00eatre d\u00e9finie :<\/p>\n R(a, b) \u2261 [pgcd(a, b) = 1] : d\u00e9cider si a et b sont des nombres premiers entre eux.<\/p>\n Conclusions : pgcd(a, b) est une fonction r\u00e9cursive, et aussi une fonction r\u00e9cursive primitive ; R(a, b) est une relation r\u00e9cursive, et R(a, b) est d\u00e9montrable, car pgcd(a, b) lui-m\u00eame peut \u00eatre vu comme une d\u00e9monstration par r\u00e9currence pour d\u00e9terminer la valeur de v\u00e9rit\u00e9 de R(a, b).<\/p>\n Exemple 2 : Conjecture de Collatz<\/p>\n D\u00e9finition r\u00e9cursive de la s\u00e9quence de Collatz :<\/p>\n fCollatz(n, i) = 1 (n=1) Par exemple, Cela correspond \u00e0 une s\u00e9quence de Collatz : 5, 16, 8, 4, 2, 1.<\/p>\n Ainsi, une relation recursive peut \u00eatre d\u00e9finie : Conclusion : On ne sait pas si fCollatz(n, i) est la fonction r\u00e9cursive primitive, et si R(n) s’arr\u00eate \u00e0 1 pour toutes les n s\u00e9quences, d\u2019o\u00f9 la conjecture fCollatz.<\/p>\n [1]https:\/\/monoskop.org\/images\/9\/93\/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf<\/p>\n Druuh :<\/p>\n la d\u00e9finition de \u00ab\u00a0r\u00e9cursif\u00a0\u00bb pour G\u00f6del dans son article est celle qu’on appelle aujourd’hui \u00ab\u00a0r\u00e9cursif primitif\u00a0\u00bb, car on s’est apper\u00e7u depuis qu’il existe des fonctions r\u00e9cursives non r\u00e9cursives primitives telle la fameuse fonction d’Ackermann (mais je ne t’apprendrai rien puisque tu est informaticienne). La d\u00e9finition de G\u00f6del est donc la meme que celle de fonction r\u00e9cursive primitive dans le livre pages 9 et 10.<\/p>\n Et page 11 la d\u00e9finition d’une relation r\u00e9cursive (primitive) est aussi la meme que celle que donne G\u00f6del : fonction caract\u00e9ristique r\u00e9cursive (primitive).<\/p>\n Mais ne perdons pas de vue notre fil : est tu donc d’accord avec le codage des formules et des d\u00e9monstrations du chapitre p 81 du livre ? c’est le premier pas vers la formule qui pose probl\u00e8me<\/p>\n PS: n’oublies pas de r\u00e9pondre au premier point car c’est vraiment fondamental de se mettre d’accord l\u00e0 dessus et de clarifier ce point.<\/p>\n Yu LI :<\/p>\n Tu dis, \u00ab\u00a0la d\u00e9finition de \u00ab\u00a0r\u00e9cursif\u00a0\u00bb pour G\u00f6del dans son article est celle qu’on appelle aujourd’hui \u00ab\u00a0r\u00e9cursif primitif\u00a0\u00bb, car on s’est apper\u00e7u depuis qu’il existe des fonctions r\u00e9cursives non r\u00e9cursives primitives telle la fameuse fonction d’Ackermann (mais je ne t’apprendrai rien puisque tu est informaticienne). La d\u00e9finition de G\u00f6del est donc la m\u00eame que celle de fonction r\u00e9cursive primitive dans le livre pages 9 et 10. \u00bb<\/p>\n Une fonction r\u00e9cursive primitive est prouvable, c’est-\u00e0-dire d\u00e9cidable. \u00c9tant donn\u00e9 que la d\u00e9finition de G\u00f6del est donc la meme que celle de fonction r\u00e9cursive primitive, G\u00f6del ne traite que \u00ab\u00a0r\u00e9cursif primitif\u00a0\u00bb, en d’autres termes, il n’y a pas de \u00ab\u00a0proposition ind\u00e9cidable\u00a0\u00bb dans sa preuve !<\/p>\n Si c\u2019est le cas, je me demande si tu te rends compte de la gravit\u00e9 du probl\u00e8me : l\u2019article de G\u00f6del n’est rien d’autre que les Habits neufs de l\u2019empereur, \u2026<\/p>\n Druuh :<\/p>\n Je ne comprends pas bien ce que tu dis, mais si tu veux bien, r\u00e9servons ceci pour apr\u00e8s nous pourrons en discuter. Je veux d’abord finir mon exposition pas \u00e0 pas sans perdre de vue l’objectif. Si nous nous perdons en route nous n’arriverons jamais.<\/p>\n Donc avant de passer \u00e0 l’\u00e9tape suivante, est tu d’accord avec le codage des formules et des d\u00e9monstrations pr\u00e9sent\u00e9 dans le chapitre de la page 81 du livre ?<\/p>\n Yu LI :<\/p>\n 1. Concernant le codage des formules et des d\u00e9monstrations<\/p>\n Tu dis, \u00ab Donc avant de passer \u00e0 l’\u00e9tape suivante, est tu d’accord avec le codage des formules et des d\u00e9monstrations pr\u00e9sent\u00e9 dans le chapitre de la page 81 du livre ? \u00bb<\/p>\n Ce codage lui-m\u00eame ne me pose pas de probl\u00e8me, ma vraie question est la suivante : 2. Concernant la relation r\u00e9cursive (primitive)<\/p>\n Je suis d\u2019accord que les relations r\u00e9cursives (primitives) dans l\u2019article de G\u00f6del sont repr\u00e9sent\u00e9es par les fonctions caract\u00e9ristiques r\u00e9cursives (primitives) dans ton livre.<\/p>\n Puisqu’un ensemble est d\u00e9fini par sa fonction caract\u00e9ristique, la d\u00e9cidabilit\u00e9 de la fonction caract\u00e9ristique d\u00e9termine alors l’existence de l\u2019ensemble.<\/p>\n Ma question est : La preuve dans ton livre tient-elle compte de cette contrainte ?<\/p>\n Druuh :<\/p>\n Ta question en 2. : encore une fois je ne comprends pas bien ta question, mais gardons la pour apr\u00e8s.<\/p>\n Tes questions en 1. : c’est l’objet de la suite : en page 94 on consid\u00e8re l’ensemble Dem = { (a,b) ; a est le num\u00e9ro de G\u00f6del d’une formule close F et b est le num\u00e9ro de G\u00f6del d’une d\u00e9monstration de F dans T }. C’est un ensemble r\u00e9cursif. On lui applique le th\u00e9or\u00e8me de repr\u00e9sentation de la page 77 pour obtenir une formule du langage de Peano DEM(x,y) qui la repr\u00e9sente.<\/p>\n Est tu d’accord avec tout cela ?<\/p>\n Yu LI :<\/p>\n Dem = { (a,b) ; a est le num\u00e9ro de G\u00f6del d’une formule close F et b est le num\u00e9ro de G\u00f6del d’une d\u00e9monstration de F dans T }.<\/p>\n Qu\u2019est-ce qu\u2019une formule close F?<\/p>\n Prenant l\u2019exemple de la s\u00e9quence de Collatz : Pourrais-tu expliquer quelle est la formule close F pour cet exemple ?<\/p>\n fCollatz(n, i) = 1 (n=1) Druuh :<\/p>\n Une formule close est une formule sans variables libres.<\/p>\n Par exemple, la formule Vx (x.y = 1) a la variable libre y (V=\u00a0\u00bbpour tout\u00a0\u00bb).<\/p>\n Une variable li\u00e9e 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\u00e9e.<\/p>\n Les formules closes sont celles auxquelles ont peut appliquer la th\u00e9orie de la d\u00e9monstration formelle de Hilbert qui est celle que G\u00f6del prend en compte quand il parle d’\u00e9nonc\u00e9 \u00ab\u00a0d\u00e9montrable\u00a0\u00bb.<\/p>\n On dit aussi \u00ab\u00a0\u00e9nonc\u00e9\u00a0\u00bb pour \u00ab\u00a0formule close\u00a0\u00bb.<\/p>\n Je ne connaissais pas la s\u00e9quence de Collatz, mais en regardant sur Wikipedia : je me rend compte que tu l’as mal d\u00e9finie. La bonne d\u00e9finition est plutot : fCollatz(n, 0) = k (un entier quelconque) Ok donc quoi qu’il en soit, cette s\u00e9quence est clairement r\u00e9cursive primitive en tant que fonction de N dans N. Pour savoir quelle est la formule de Peano qui la repr\u00e9sente, il faudrait suivre pas \u00e0 pas la preuve du th\u00e9or\u00e8me de repr\u00e9sentation, ce qui serait tr\u00e8s fastidieux.<\/p>\n Ta question \u00ab\u00a0est ce que cette formule fait partie de Dem ?\u00a0\u00bb 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\u00e9sente cet ensemble.<\/p>\n Mais je reviens \u00e0 mon d\u00e9roulement : est tu donc d’accord que la formule DEM(x,y) (lettres gothiques) est bien une formule du langage de Peano qui repr\u00e9sente l’ensemble Dem au sens de la d\u00e9finition 2 p 76 ?<\/p>\n Yu LI :<\/p>\n Je trouve que nos discussions actuelles sont tr\u00e8s constructives !<\/p>\n Tu dis\uff1aest tu donc d’accord que la formule DEM(x,y) (lettres gothiques) est bien une formule du langage de Peano qui repr\u00e9sente l’ensemble Dem au sens de la d\u00e9finition 2 p 76 ?<\/p>\n Cette question est au c\u0153ur de la preuve de G\u00f6del, alors ne me presse pas de r\u00e9pondre par oui ou par non, clarifions d’abord la signification de Dem et DEM(x,y).<\/p>\n 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\u00e9sente cet ensemble.<\/p>\n 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\u00e9sentatifs pour l’illustrer. Je pense que la conjecture de Collatz en est un bon exemple.<\/p>\n D\u2019abord, une clarification est n\u00e9cessaire sur la d\u00e9finition de la s\u00e9quence de Collatz :<\/p>\n Tu donne la d\u00e9finition du wiki : Cette d\u00e9finition est formellement une \u00ab\u00a0fonction r\u00e9cursive\u00a0\u00bb, mais la g\u00e9n\u00e9ration effective de la s\u00e9quence de Collatz se fait de mani\u00e8re it\u00e9rative :<\/p>\n Par exemple, n = 5 Par cons\u00e9quent, j’utilise une d\u00e9finition alternative qui rend la g\u00e9n\u00e9ration effective de la s\u00e9quence de Collatz par recurrence : Par exemple : Il existe \u00e9galement des variantes, telles que \uff08https:\/\/skobki.com\/en\/c-language-recursion-and-the-collatz-conjecture\/\uff09: collatz(5) Cette d\u00e9finition renvoie le nombre de pas n\u00e9cessaires lorsque la s\u00e9quence s’arr\u00eate \u00e0 1.<\/p>\n Par cons\u00e9quent, tu ne peux pas dire : Ok donc quoi qu’il en soit, cette s\u00e9quence est clairement r\u00e9cursive primitive en tant que fonction de N dans N.<\/p>\n Car si cette s\u00e9quence est r\u00e9cursive primitive en tant que fonction de n dans N, cela signifie qu’on sait si pour tout n, la s\u00e9quence s’arr\u00eate \u00e0 1 ou non, et la fonction r\u00e9cursive primitive elle-m\u00eame est sa preuve. Dans ce cas, la conjecture de Collatz devient le th\u00e9or\u00e8me de Collatz, mais la conjecture de Collatz reste toujours conjecture jusqu’\u00e0 maintenant !<\/p>\n Donc \u00e0 mon avis, la fonction de la s\u00e9quence de Collatz ne peut pas \u00eatre exprim\u00e9e dans Dem, car il n’existe pas (jusqu’\u00e0 ce jour) de preuve que cette s\u00e9quence s’arr\u00eate \u00e0 1.<\/p>\n Est-ce que tu es d\u2019accord ?<\/p>\n Druuh :<\/p>\n Je ne comprends pas pourquoi tu veux faire rentrer la sequence de Collatz dans le cadre du theoreme de G\u00f6del, mais encore une fois je propose d’en reparler une fois arriv\u00e9s au bout de mon argumentation, ainsi que tes autres questions en suspens.<\/p>\n Quand tu dis \u00ab\u00a0la fonction de la s\u00e9quence de Collatz ne peut pas \u00eatre exprim\u00e9e dans Dem\u00a0\u00bb, 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 \u00ab\u00a0ne peut pas etre exprimee\u00a0\u00bb dans un ensemle de couples d’entiers ? Tu veux peut etre dire que la sequence de Collatz ne peut pas etre represent\u00e9e par une formule de Peano selon la definition 2 p 76 ?<\/p>\n Ensuite, tu dis \u00ab\u00a0Tu 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\u00e9sente cet ensemble.Une telle explication n’est pas suffisante pour illustrer la signification de Dem et DEM(x,y)\u00a0\u00bb<\/p>\n 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 :<\/p>\n Dem = { (a,b) ; a est le num\u00e9ro de G\u00f6del d’une formule close F et b est le num\u00e9ro de G\u00f6del d’une d\u00e9monstration de F dans Peano }<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n C’est un peu comme si je disais \u00ab\u00a0je ne te crois pas que le chiffre mille millards de millards existe : prouve le moi en comptant un par un jusque la\u00a0\u00bb. Tu me repondrais \u00ab\u00a0je ne peux pas compter jusque la, mais ce chiffre existe cependant pour des raisons evidentes\u00a0\u00bb.<\/p>\n Yu LI :<\/p>\n \u00ab Je ne comprends pas pourquoi tu veux faire rentrer la sequence de Collatz dans le cadre du theoreme de G\u00f6del, mais encore une fois je propose d’en reparler une fois arriv\u00e9s au bout de mon argumentation, ainsi que tes autres questions en suspens. \u00bb Druuh :<\/p>\n Ok mais avant de passer a l’etape suivante, je dois m’assurer que tu as bien compris Dem et DEM.<\/p>\n Est ce le cas ? est tu convaincue que DEM est une formule du language de Peano qui represente Dem ?<\/p>\n Yu LI :<\/p>\n Maintenant c\u2019est moi qui ne comprends pas.<\/p>\n Tu as dit, \u00ab Je ne comprends pas pourquoi tu veux faire rentrer la sequence de Collatz dans le cadre du theoreme de G\u00f6del, mais encore une fois je propose d’en reparler une fois arriv\u00e9s au bout de mon argumentation, ainsi que tes autres questions en suspens. \u00bb<\/p>\n Donc, j\u2019ai r\u00e9pondu, \u00ab tu continues jusqu\u2019au bout de ton argumentation, et pour l\u2019instant nous laissons tomber mes questions, y compris la sequence de Collatz \u00bb<\/p>\n Et maintenant, tu me demande : est tu convaincue que DEM est une formule du language de Peano qui represente Dem ?<\/p>\n Mais si je ne pose pas des questions sur Dem et DEM, et n\u2019utilise pas des exemples pour concr\u00e9tiser cette comprehension, comment je peux \u00eatre sure que je suis convaincue que DEM est une formule du language de Peano qui represente Dem ?<\/p>\n Druuh :<\/p>\n Tu peux en etre convaincue en validant la demonstration du theoreme de representabilit\u00e9. 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\u00e9 du theoreme.<\/p>\n 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\u00e9.<\/p>\n Excuse moi d’etre un peu insistant, mais c’est presque la fin en ce qui concerne l’existence de la \u00ab\u00a0formule qui dit d’elle meme qu’elle n’est pas demontrable dans Peano\u00a0\u00bb.<\/p>\n Yu LI :<\/p>\n Est-ce que DEM peut \u00eatre consid\u00e9r\u00e9 comme la fonction caract\u00e9ristique de l\u2019ensemble Dem ?<\/p>\n Druuh :<\/p>\n 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\u00f6del.<\/p>\n Le th\u00e9oreme de repr\u00e9sentabilit\u00e9 : lis (ou relis) attentivement la d\u00e9finition d’une fonction et d’un ensemble repr\u00e9sentable p 76 (d\u00e9finition 1 et d\u00e9finition 2). Fait de m\u00eame pour l’\u00e9nonc\u00e9 du th\u00e9oreme de repr\u00e9sentation p 77.<\/p>\n Dis moi si il y a des choses que tu ne comprends pas bien dans ces d\u00e9finitions et dans l’\u00e9nonc\u00e9 du th\u00e9oreme de repr\u00e9sentation.<\/p>\n DEM n’est pas la fonction caract\u00e9ristique 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’\u00e9claicir totu cela pour que tu finisses par y voir clair \ud83d\ude42<\/p>\n Yu LI :<\/p>\n J\u2019ai lu d\u00e9finition 1 et d\u00e9finition 2 ainsi que l’\u00e9nonc\u00e9 du th\u00e9or\u00e8me de repr\u00e9sentation.<\/p>\n Je repose ma question : Est-ce que DEM est la formule repr\u00e9sente la fonction caract\u00e9ristique de l\u2019ensemble Dem ?<\/p>\n Druuh :<\/p>\n Pas tout \u00e0 fait : pour avoir la formule qui repr\u00e9sente la fonction caract\u00e9ristique de Dem il faut modifier un peu DEM(x,y) comme dans la remarque page 76.<\/p>\n Ce qui est vrai (et que met en \u00e9vidence la meme remarque), c’est qu’un ensemble de tuples d’entiers est repr\u00e9sentable si et seulement si sa fonction caract\u00e9ristique l\u2019est.<\/p>\n D’autres doutes ?<\/p>\n Yu LI :<\/p>\n Je pense que j\u2019ai compris la signification de Dem et DEM(x,y).<\/p>\n Concernant Th\u00e9or\u00e8me de repr\u00e9sentation, \u00e7a signifie qu’une \u00ab fonction r\u00e9cursive \u00bb peut \u00eatre \u00ab repr\u00e9sent\u00e9e \u00bb en termes de formule (\u00ab relation r\u00e9cursive \u00bb dans l\u2019article de G\u00f6del), comme montr\u00e9 par quelques exemples donn\u00e9s dans le livre : Druuh :<\/p>\n Oui c’est bien cela, un autre exemple simple et instructif de repr\u00e9sentation d’une fonction r\u00e9cursive par une formule du language de Peano est le lemme 1 p 77, qui explicite quelle formule est utilis\u00e9e pour repr\u00e9senter une composition de fonctions. Cette formule utilise des quantificateurs, elle est donc un peu plus \u00e9labor\u00e9e que les exemples que tu as cit\u00e9. Je t’invite \u00e0 regarder la formule de ce lemme avec attention pour te convaincre qu’elle repr\u00e9sente bien la composition des fonctions. Le reste de la preuve du th\u00e9oreme de repr\u00e9sentabilit\u00e9 est un peu moins triviale, elle consiste \u00e0 v\u00e9rifier que \u00e7a fonctionne aussi avec le sch\u00e9ma mu et le sch\u00e9ma de r\u00e9currence.<\/p>\n Je continue donc : maintenant qu’on \u00e0 notre disposition la formule DEM(x,y), on peut d’ores de et d\u00e9j\u00e0 fabriquer tr\u00e8s facilement une \u00ab\u00a0formule qui dit qu’une AUTRE formule n’est pas d\u00e9montrable dans Peano\u00a0\u00bb. La derni\u00e8re \u00e9tape de la \u00ab\u00a0formule qui dit d’ELLE MEME qu’elle n’est pas d\u00e9montrable\u00a0\u00bb sera une variante un peu plus \u00e9labor\u00e9e de celle l\u00e0.<\/p>\n Commen\u00e7ons donc par du tr\u00e8s simple : je prends une formule close du langage de Peano (un \u00e9nonc\u00e9) quelconque F. Je prends son num\u00e9ro de G\u00f6del a (un entier naturel). Je consid\u00e8re la formule close<\/p>\n G = \u00ac\u2203 v DEM(a_,v)<\/p>\n G est bien une formule du language de Peano puisque DEM(x,y) en est d\u00e9j\u00e0 une.<\/p>\n Enfin, G \u00ab\u00a0dit\u00a0\u00bb que F n’est pas d\u00e9montrable dans Peano dans le sens suivant : G est satisfaite dans le mod\u00e8le N si et seulement si F n’est pas d\u00e9montrable dans Peano (par d\u00e9finition m\u00eame de Dem et le fait que DEM repr\u00e9sente Dem).<\/p>\n Est tu d’accord avec tout cela ?<\/p>\n Yu LI :<\/p>\n 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\u00e9mique de la preuve de G\u00f6del. Je vais maintenant commenter cette preuve.<\/p>\n Tu dis, \u00ab maintenant qu’on \u00e0 notre disposition la formule DEM(x,y), on peut d’ores de et d\u00e9j\u00e0 fabriquer tr\u00e8s facilement une \u00ab\u00a0formule qui dit qu’une AUTRE formule n’est pas d\u00e9montrable dans Peano\u00a0\u00bb. La derni\u00e8re \u00e9tape de la \u00ab\u00a0formule qui dit d’ELLE MEME qu’elle n’est pas d\u00e9montrable\u00a0\u00bb sera une variante un peu plus \u00e9labor\u00e9e de celle l\u00e0 \u00bb.<\/p>\n C’est-\u00e0-dire que la preuve de G\u00f6del se porte sur la formule DEM(x,y) !<\/p>\n La formule DEM(x,y) est une repr\u00e9sentation de l’ensemble Dem, et l’existence de l’ensemble Dem d\u00e9pend de l’existence de la fonction caract\u00e9ristique de Dem qui, \u00e9tant donn\u00e9 une formule F (cod\u00e9e comme a) et une preuve de F (cod\u00e9e comme b), d\u00e9cide si (a,b) est un \u00e9l\u00e9ment de l’ensemble Dem :<\/p>\n Dem = { (a,b) ; a est le num\u00e9ro de G\u00f6del d’une formule close F et b est le num\u00e9ro de G\u00f6del d’une d\u00e9monstration de F dans Peano }<\/p>\n La d\u00e9termination si (a,b) est un \u00e9l\u00e9ment de l’ensemble Dem consiste \u00e0 d\u00e9cider (ou de v\u00e9rifier) si la preuve de F (cod\u00e9e comme b) est valide, c’est-\u00e0-dire \u00e0 d\u00e9cider la validit\u00e9 d\u2019une preuve donn\u00e9e, ce qui est le vrai c\u0153ur du \u00ab probl\u00e8me ind\u00e9cidable \u00bb \uff01<\/p>\n Les travaux de Turing, Church montrent qu’il n’y a pas de m\u00e9thode universelle de d\u00e9terminer la validit\u00e9 d’une preuve donn\u00e9e, c’est-\u00e0-dire que la fonction caract\u00e9ristique de Dem n’existe pas! Par cons\u00e9quence, Dem n’existe pas, DEM non plus, et finalement la \u00ab\u00a0formule qui dit d’ELLE MEME qu’elle n’est pas d\u00e9montrable\u00a0\u00bb ne peut pas \u00eatre construite comme G\u00f6del dit.<\/p>\n En effet, la preuve du th\u00e9or\u00e8me d’incompl\u00e9tude de G\u00f6del n’est plus une preuve logique purement formelle, mais implique le probl\u00e9matique de l\u2019 \u00ab existence \u00bb , \u2026<\/p>\n Druuh :<\/p>\n 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.<\/p>\n 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.<\/p>\n 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.<\/p>\n Yu LI :<\/p>\n \u00ab 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. \u00bb<\/p>\n Non. Ce que je voulais dire : la formule DEM existe si Dem est un \u00ab\u00a0ensemble r\u00e9cursif primitif\u00a0\u00bb ; cependant, l’existence d’un ensemble r\u00e9cursif primitif d\u00e9pend de la d\u00e9termination de la fonction r\u00e9cursive primitive, ce qui est ind\u00e9cidable.<\/p>\n Ce qui est important \u00e0 noter est que, la \u00ab\u00a0fonction r\u00e9cursive\u00a0\u00bb et la \u00ab\u00a0fonction r\u00e9cursive primitive\u00a0\u00bb sont deux notions de deux niveaux compl\u00e8tement diff\u00e9rents, comme montre la fonction fCollatz(n) impliqu\u00e9e dans la conjecture de Collatz :<\/p>\n fCollatz(n) = 1 (n=1) (Note : j’ai l\u00e9g\u00e8rement modifi\u00e9 fCollatz(n) en supprimant la variable i)<\/p>\n fCollatz(n) est une fonction r\u00e9cursive, mais jusqu’\u00e0 pr\u00e9sent elle n’a pas \u00e9t\u00e9 reconnue comme une fonction r\u00e9cursive primitive. Cet exemple illustre que la d\u00e9termination de la fonction r\u00e9cursive primitive est ind\u00e9cidable.<\/p>\n \u00ab 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. \u00bb<\/p>\n Non. Cette conclusion ne vaut que pour les preuves de formes sp\u00e9ciales, comme le raisonnement par recurrence ; mais G\u00f6del discute des preuves de toute formule dans un syst\u00e8me formel.<\/p>\n 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\u2019est-\u00e0-dire, si la s\u00e9quence de Collatz s\u2019arr\u00eate \u00e0 1 pour tout n.<\/p>\n La chose primordiale concernant le \u00ab\u00a0probl\u00e8me ind\u00e9cidable\u00a0\u00bb est que, la d\u00e9termination de la validit\u00e9 d’une preuve donn\u00e9e revient en fait \u00e0 identifier les raisonnements fallacieux, ce qui ne peut \u00eatre enti\u00e8rement formalis\u00e9 ; il s’agit d’une connaissance de bon sens connue depuis l’\u00e9poque d’Aristote,\u2026<\/p>\n Druuh :<\/p>\n \u00bbla formule DEM existe si Dem est un \u00ab\u00a0ensemble r\u00e9cursif primitif\u00a0\u00bb\u00a0\u00bb : Je r\u00e9serve tes autres remarques et questions pour plus tard, mais je ne les \u00e9vacue pas.<\/p>\n Yu LI :<\/p>\n Ce dont nous discutons actuellement est en fait similar \u00e0 la question a pos\u00e9 par Zermelo quand l\u2019article de G\u00f6del vient sortir. Malheureusement, G\u00f6del n\u2019a pas r\u00e9pondu directement \u00e0 cette question et a rapidement mis fin \u00e0 ce qui aurait \u00e9t\u00e9 une conversation extr\u00eamement int\u00e9ressante !<\/p>\n Un passage de la lettre de Zermelo (https:\/\/www.sciencedirect.com\/science\/article\/pii\/0315086085900709) : S = \u00acBew[R(n);n]<\/p>\n really belong to your \u201csystem,\u201d and are you justified in identifying this function with R(q), just because it is a \u201cclass sign \u201c?<\/p>\n Druuh :<\/p>\n Ok l\u00e0 tu est en train de parler de la d\u00e9monstration originale de G\u00f6del, 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\u00e9monstration du livre.<\/p>\n Est tu d’accord que Dem est un ensemble r\u00e9cursif comme d\u00e9montr\u00e9 dans la proposition p 90 ?<\/p>\n Qu’on peut donc lui appliquer le th\u00e9oreme de representation pour obtenir une formule DEM(x,y) exprim\u00e9e dans le language de Peano ?<\/p>\n Qu’on peut facilement \u00e0 partir de l\u00e0 obtenir l’\u00e9nonc\u00e9 G pr\u00e9sent\u00e9 dans un mail precedent qui dit qu’un autre \u00e9nonc\u00e9 F n’est pas d\u00e9montrable dans Peano (\u00ab\u00a0dit\u00a0\u00bb dans le sens que j’ai pr\u00e9cis\u00e9 dans le meme mail) ?<\/p>\n Yu LI :<\/p>\n Repr\u00e9senter une \u00a0\u00bb fonction r\u00e9cursive \u00a0\u00bb comme une formule exprim\u00e9e dans le langage de Peano ne change pas son existence, c\u2019est-\u00e0-dire, si cette \u00a0\u00bb fonction r\u00e9cursive \u00a0\u00bb existe dans le syst\u00e8me, elle y existe toujours apr\u00e8s on lui appliquer le th\u00e9oreme de representation.<\/p>\n Par exemple. Cependant, une formule paradoxale tel que \u00ab\u00a0dit d\u2019elle qu’elle est ind\u00e9montrable\u00a0\u00bb, bien que formellement elle est repr\u00e9sentable, n’existe pas r\u00e9ellement dans le syst\u00e8me de Peano.<\/p>\n En d’autres termes, la repr\u00e9sentation et l’existence sont deux concepts de deux niveaux compl\u00e8tement diff\u00e9rents. Le th\u00e9oreme de representation ne concerne que la repr\u00e9sentation, mais l\u2019essence du \u00ab\u00a0probl\u00e8me ind\u00e9cidable\u00a0\u00bb met l’accent sur l’existence, plut\u00f4t que sur la repr\u00e9sentation.<\/p>\n Druuh :<\/p>\n Le th\u00e9oreme de repr\u00e9sentabilit\u00e9 dit que pour toute fonction r\u00e9cursive, IL EXISTE une formule du language qui la repr\u00e9sente.<\/p>\n Je ne comprends ta distinction entre repr\u00e9sentabilit\u00e9 et existence.<\/p>\n Yu LI :<\/p>\n \u00ab Est tu d’accord que Dem est un ensemble r\u00e9cursif comme d\u00e9montr\u00e9 dans la proposition p 90 ? \u00bb<\/p>\n Non, je ne suis pas d\u2019accord.<\/p>\n Regarde encore l\u2019exemple de la conjecture de Collatz :<\/p>\n Etant donn\u00e9 la suite de formules : On ne sait pas jusqu\u2019\u00e0 maintenant si la s\u00e9quence de Collatz s\u2019arr\u00eate \u00e0 1, c\u2019est-\u00e0-dire, si cette suite est une d\u00e9monstration est effectif.<\/p>\n Comment peut-on dire (p 90) : J\u2019ai dit : Malheureusement ce sujet primordiale a \u00e9t\u00e9 ignor\u00e9 par G\u00f6del et la quasi-totalit\u00e9 de la communaut\u00e9 scientifique !<\/p>\n Druuh :<\/p>\n 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\u00e9es au cours de notre \u00e9change. Il faut clarifier tout cela car il y a des choses que tu dis depuis le debut et que je ne comprends pas.<\/p>\n Tout d’abord, quelle est ta definition d\u2019un ensemble (et d’une fonction)\u00a0 r\u00e9cursif primitif et d’un ensemble (et d’une fonction) r\u00e9cursif ?<\/p>\n Ensuite, peut tu m’expliquer le lien que tu fait entre la sequence de Collatz et le th\u00e9or\u00e8me de G\u00f6del ?<\/p>\n Et aussi : qu’entends tu par le \u00ab\u00a0probl\u00e8me ind\u00e9cidable\u00a0\u00bb associ\u00e9 a Church et Turing auquel tu as fait reference plusieurs fois ?<\/p>\n **** Des extraites cit\u00e9s dans nos dialogues du livre : P. 76-77<\/p>\n 2. Les Fonctions Repr\u00e9sentables<\/p>\n Rappelons que Fp d\u00e9signe l\u2019ensemble des fonctions totales de NP dans N.<\/p>\n D\u00e9finition 1 : Soient f dans Fp et F[v0,v1,v2,\u2026,vp] une formule de L0 qui n\u2019a pas de variables libres en dehors de v0,v1,v2,\u2026,vp. On dit que F[v0,v1,v2,\u2026,vp] repr\u00e9sente f si, pour tout p-uple d\u2019entiers (n1,n2,\u2026,np), on a :<\/p>\n P0 \u22a2 \u2200 v0 (F[v0,v1,v2,\u2026,vp] \u2194 v0 = f(n1,n2,\u2026,np))<\/p>\n On dit que la fonction f est repr\u00e9sentable s\u2019il existe une formule qui la repr\u00e9sente.<\/p>\n D\u00e9finition 2 : Soient A inclus NP et F[v1,v2,\u2026,vp] une formule qui n\u2019a pas de variables libres en dehors de v1,v2,\u2026,vp. On dit que F repr\u00e9sente A si, pour tout p-uple d\u2019entiers (n1,n2,\u2026,np), on a : On dit que l\u2019ensemble A est repr\u00e9sentable s\u2019il existe une formule qui le repr\u00e9sente.<\/p>\n Remarque : Un ensemble A inclus NP est repr\u00e9sentable si et seulement si sa fonction caract\u00e9ristique l\u2019est : on v\u00e9rifiera que, si F repr\u00e9sente A, la formule repr\u00e9sente la fonction caract\u00e9ristique de A; r\u00e9ciproquement, si G[v0, v1,v2,\u2026,vp] repr\u00e9sente la fonction caract\u00e9ristique de A, alors G[1, v1,v2,\u2026,vp] repr\u00e9sente A.<\/p>\n Exemples :<\/p>\n La fonction successeur est repr\u00e9sent\u00e9e par la formule v0 = Sv1 En fait, toutes les fonctions r\u00e9cursives sont repr\u00e9sentables :<\/p>\n Th\u00e9or\u00e8me de repr\u00e9sentation : Toute fonction r\u00e9cursive (totale) est repr\u00e9sentable.<\/p>\n","protected":false},"excerpt":{"rendered":" Pour ce qui est de ma propre opinion sur le sujet des formules qui \u00ab parlent d\u2019elles-m\u00eames \u00bb<\/strong>, vous la trouverez dans Comment la v\u00e9rit\u00e9 et la r\u00e9alit\u00e9 furent invent\u00e9es<\/b> (Gallimard 2009). J’ai reproduit r\u00e9cemment ici sur le blog<\/a> le passage du livre […]<\/em><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7313,4965,16],"tags":[7182,8004,5335,693],"class_list":["post-133754","post","type-post","status-publish","format-standard","hentry","category-comment-la-verite-et-la-realite-furent-inventees","category-logique","category-mathematiques","tag-comment-la-verite-et-le-realite-furent-inventees","tag-fondements-des-mathematiques","tag-kurt-godel","tag-second-theoreme-de-godel"],"_links":{"self":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/133754","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/comments?post=133754"}],"version-history":[{"count":6,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/133754\/revisions"}],"predecessor-version":[{"id":133761,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/posts\/133754\/revisions\/133761"}],"wp:attachment":[{"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/media?parent=133754"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/categories?post=133754"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pauljorion.com\/blog\/wp-json\/wp\/v2\/tags?post=133754"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n<\/p>\n
\n2) le fait qu’une formule dans le langage de Peano ne peut pas dire d’elle meme qu’elle n’est pas d\u00e9montrable dans Peano, et donc que la formule que pr\u00e9sente G\u00f6del n’est pas \u00e9crite dans le langage de Peano contrairement \u00e0 ce qu’il affirme.<\/p>\n
\nA number-theoretic function \u03a6(x1,\u202fx2,\u202f\u2026xn) is said to be recursively defined by the number-theoretic functions \u03a8(x1,\u202fx2,\u202f\u2026xn-1) and \u03bc(x1,\u202fx2,\u202f\u2026xn\u202f+\u202f1), if for all x2, \u2026 xn, k\u202f the following hold:
\n\u03a6(0,\u202fx2,\u202f\u2026xn) = \u03a8(x2,\u202f\u2026xn)
\n\u03a6(k\u202f+\u202f1,\u202fx2,\u202f\u2026xn) = \u03bc(k,\u202f\u03a6(k,\u202fx2,\u202f\u2026xn),\u202fx2,\u202f\u2026xn). (2)<\/p>\n
\npgcd(a, b) = a, b=0
\npgcd(a, b) = pgcd(b, mod(a, b)), b\/=0<\/p>\n
\npgcd(12, 8) = pgcd(8, 4) = pgcd(4, 0) = 4, 12 et 8 ne sont pas des premiers entre eux.
\npgcd(12, 5) = pgcd(5, 2) = pgcd(2, 1) = pgcd(1, 0) = 1, 12 et 5 sont donc des premiers entre eux.<\/p>\n
\nfCollatz(n, i) = fCollatz(n\/2, i+1) (n is pair)
\nfCollatz(n, i) = fCollatz(3n+1, i+1) (n is impair)<\/p>\n
\nfCollatz(5, 1) = fCollatz(16, 2) = fCollatz(8, 3) = fCollatz(4, 4) = fCollatz(2, 5) = fCollatz(1, 6) = 1<\/p>\n
\nR(n) = [fCollatz(n, 1) = 1] : d\u00e9cider si fCollatz(n, 1) peut s’arr\u00eater \u00e0 1.<\/p>\n
\nQuel est le but de ce codage ? Comment l’utiliser ?<\/p>\n
\nfCollatz(n, i) = 1 (n=1)
\nfCollatz(n, i) = fCollatz(n\/2, i+1) (n est pair)
\nfCollatz(n, i) = fCollatz(3n+1, i+1) (n is impair)<\/p>\n
\nfCollatz(n, i) = fCollatz(n\/2, i+1) (n est pair)
\nfCollatz(n, i) = fCollatz(3n+1, i+1) (n est impair)<\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture<\/p>\n
\nhttps:\/\/en.wikipedia.org\/wiki\/Collatz_conjecture<\/p>\n
\nfCollatz(n, i+1) = fCollatz(n, i)\/2 si fCollatz(n, i) est pair
\nfCollatz(n, i+1) = 3fCollatz(n, i) + 1 si fCollatz(n, i) est impair.<\/p>\n
\nfCollatz(n, 0) = n (un entier quelconque)
\nfCollatz(n, i+1) = fCollatz(n, i)\/2 si fCollatz(n, i) est pair
\nfCollatz(n, i+1) = 3fCollatz(n, i) + 1 si fCollatz(n, i) est impair.<\/p>\n
\nfCollatz(5, 0) = 5
\nfCollatz(5, 1) = 3*fCollatz(n, 0)+1= 16
\nfCollatz(5, 2) = fCollatz(n, 1)\/2 = 8
\nfCollatz(5, 3) = fCollatz(n, 2)\/2 = 4
\nfCollatz(5, 4) = fCollatz(n, 3)\/2 = 2
\nfCollatz(5, 5) = fCollatz(n, 4)\/2 = 1<\/p>\n
\nfCollatz(n, i) = 1 (n=1)
\nfCollatz(n, i) = fCollatz(n\/2, i+1) (n is pair)
\nfCollatz(n, i) = fCollatz(3n+1, i+1) (n is impair)<\/p>\n
\nfCollatz(5, 1)
\n= fCollatz(16, 2)
\n= fCollatz(8, 3)
\n= fCollatz(4, 4)
\n= fCollatz(2, 5)
\n= fCollatz(1, 6)
\n= 1<\/p>\n
\ncollatz(n) = 0 (n=1)
\ncollatz(n) = 1 + collatz(n\/2) (n is pair)
\ncollatz(n) = 1 + collatz(3n+1) (n is impair)<\/p>\n
\n= 1 + collatz(16)
\n= 2 + collatz(8)
\n= 3 + collatz(4)
\n= 4 + collatz(2)
\n= 5 + collatz(1)
\n= 5<\/p>\n
\nOk, tu continues jusqu\u2019au bout de ton argumentation, et pour l\u2019instant nous laissons tomber mes questions, y compris la sequence de Collatz.<\/p>\n
\n– La fonction successeur est repr\u00e9sent\u00e9e par la formule v0 = Sv1
\n– L\u2019addition lamda xy x+y est repr\u00e9sent\u00e9e par la formule v0 = v1+ v2<\/p>\n
\nfCollatz(n) = fCollatz(n\/2) (n is pair)
\nfCollatz(n) = fCollatz(3n+) (n is impair)<\/p>\n
\nnon, il suffit que Dem soit un ensemble r\u00e9cursif. Si tu reprends la preuve du th\u00e9oreme de repr\u00e9sentation dans le livre, tu verras qu’il prouve que toute fonction r\u00e9cursive est repr\u00e9sentable par une formule du language de Peano. C’est grace \u00e0 la possibilit\u00e9 de representer le \u00ab\u00a0sch\u00e9ma mu\u00a0\u00bb, qui est la seule chose qui diff\u00e9rencie r\u00e9cursif et r\u00e9cursif primitif.<\/p>\n
\nWhile 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 \u201cundecidable\u201d proposition, you define on page 178 a \u201cclass sign\u201d (a propositional function of one free variable) S = R(q), and then you show that neither [R(q);q] = A nor its negation \u00acA would be \u201cprovable.\u201d But does<\/p>\n
\n– La fonction successeur est repr\u00e9sent\u00e9e par la formule v0 = Sv1
\n– L\u2019addition lamda xy x+y est repr\u00e9sent\u00e9e par la formule v0 = v1+ v2<\/p>\n
\nfCollatz(n) = 1 (n=1)
\nfCollatz(n) = fCollatz(n\/2) (n is pair)
\nfCollatz(n) = fCollatz(3n+1) (n is impair)<\/p>\n
\n– Il suffit de se reporter \u00e0 la d\u00e9finition d\u2019une d\u00e9monstration (chapitre 4, 1.3) et de se rendre compte que le proc\u00e9d\u00e9 permettant de v\u00e9rifier si une suite de formules est une d\u00e9monstration est effectif.<\/p>\n
\n– La chose primordiale concernant le \u00ab\u00a0probl\u00e8me ind\u00e9cidable\u00a0\u00bb est que, la d\u00e9termination de la validit\u00e9 d’une preuve donn\u00e9e revient en fait \u00e0 identifier les raisonnements fallacieux, ce qui ne peut \u00eatre enti\u00e8rement formalis\u00e9 ; il s’agit d’une connaissance de bon sens connue depuis l’\u00e9poque d’Aristote,\u2026<\/p>\n
\nAnnexe<\/p>\n
\nLogique Math\u00e9matiques
\nFonctions r\u00e9cursives, th\u00e9or\u00e8me de G\u00f6del, th\u00e9orie des ensembles, th\u00e9orie des mod\u00e8les
\nR\u00e9n\u00e9 Cori, Daniel Lascar<\/p>\n
\nsi (n1,n2,\u2026,np) in A alors P0 \u22a2 F[n1,n2,\u2026,np]
\nsi (n1,n2,\u2026,np) non in A alors P0 \u22a2 \u00acF[n1,n2,\u2026,np]<\/p>\n
\n(F[n1,n2,\u2026,np] \u2227 v0=1) \u2228 (\u00acF[n1,n2,\u2026,np] \u2227 v0=0)<\/p>\n
\nL\u2019addition lxy x+y est repr\u00e9sent\u00e9e par la formule v0 = v1+ v2
\n\u2026<\/p>\n<\/p>\n