Répondre à la discussion
Affichage des résultats 1 à 27 sur 27

Précisions sur le théorème d'incomplétude de Gödel...



  1. #1
    LPTheKiller

    Précisions sur le théorème d'incomplétude de Gödel...


    ------

    Salut à vous,

    Je poste ici parce qu'une question me taraude depuis un certain temps à propos du deuxième théorème de Gödel :

    (J'ai lu divers textes à ce propos, dont celui-ci : http://membres.multimania.fr/godel/t...plus_pres.html)

    Gödel a montré, d'après ce que j'en ai compris, qu'il existe des propositions qui ne peuvent pas être prouvées au sein d'un formalisme comme l'arithmétique, mais qui pourtant sont "vraies".
    J'aimerais savoir plus précisément ce qu'il entend par "vraies". Puisque ce n'est pas une vérité démontrée (il a montré que cela est impossible), alors s'agit-il d'une vérité intuitive ? De quelque chose qui est reconnu vrai par le bon sens, mais pas par le formalisme ?
    Ou est-ce bien toujours démontré, mais dans un formalisme de "niveau supérieur" ?

    Ensuite, j'ai peut-être d'autres questions à propos de tout ça, mais il faut que j'arrive à bien les formuler en attendant...

    Merci pour vos éclairages !

    -----

  2. Publicité
  3. #2
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par LPTheKiller Voir le message
    J'aimerais savoir plus précisément ce qu'il entend par "vraies". Puisque ce n'est pas une vérité démontrée (il a montré que cela est impossible), alors s'agit-il d'une vérité intuitive ? De quelque chose qui est reconnu vrai par le bon sens, mais pas par le formalisme ?
    Bonjour, et merci ()

    Merci, parce que je combats ce vocabulaire (l'usage de "vraies" dans le cas présent) depuis fort longtemps.

    Dans le cas de l'arithmétique "vraie" signifie "vraie dans le modèle standard de l'arithmétique" (une proposition n'est jamais indécidable dans un modèle).

    Une "proposition indécidable mais vraie" (vocabulaire inutilement source de confusion) signifie que la proposition est indécidable dans la théorie étudiée (Peano par exemple), mais vraie dans le modèle standard (mais donc forcément fausse dans d'autres modèles).

    L'origine de ce mauvais vocabulaire vient d'un excès de platonisme : pour un platonicien (ce que je ne suis pas) l'ensemble des entiers (le modèle standard) existe la théorie essayant de décrire ce modèle, "vrai" fait alors référence à "l'objet" que l'on veut étudier.

    Je parle d'excès de platonisme (ce qui fait que ce n'est pas une critique du platonisme), car pour moi cette façon de voir n'est pas nécessaire, même pour un platonicien convaincu (il suffit d'ajouter "dans le modèle standard" pour éliminer tout risque de confusion), et que cela laisse entendre que les modèles non-standard "n'existent pas", et personnellement, je ne vois pas comment on peut dire que certains modèles existent et pas d'autres.

    Citation Envoyé par LPTheKiller Voir le message
    Gödel a montré, d'après ce que j'en ai compris, qu'il existe des propositions qui ne peuvent pas être prouvées au sein d'un formalisme comme l'arithmétique, mais qui pourtant sont "vraies".
    J'aime mieux : Dans toute théorie du premier ordre récursivement axiomatisable et pouvant formaliser l'arithmétique, il existe des propositions indécidables.

    Une formule f est indécidable dans la théorie T si et seulement si :
    T U {f} est consistante
    T U {non f} est consistante.

    Avec cette formulation, on ne parle jamais de modèle, jamais de vrai ou de faux, et, à mon sens il n'y a rien qui puisse créer une confusion.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Bonjour,

    Citation Envoyé par Médiat Voir le message
    "vraie dans le modèle standard de l'arithmétique" (une proposition n'est jamais indécidable dans un modèle).
    Donc si j'ai bien compris la notion de "vraie" dans le modèle standard, c'est la notion intuitive de vérité : cela correspond dans le cas de l'arithmétique à une proposition qui est indécidable ?

  5. #4
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Bonjour
    Citation Envoyé par jreeman Voir le message
    Donc si j'ai bien compris la notion de "vraie" dans le modèle standard, c'est la notion intuitive de vérité
    Je me méfie d'une expression comme "notion intuitive de vérité", déjà que je me méfie du mot "vérité" ; ce que l'on peut dire sans risque, c'est que le modèle standard (dans le cas de l'arithmétique en particulier) est le modèle auquel tout le monde pense quand on ne précise pas plus.


    Citation Envoyé par jreeman Voir le message
    cela correspond dans le cas de l'arithmétique à une proposition qui est indécidable ?
    Une proposition vraie dans le modèle standard peut être démontrable dans la théorie (d'ailleurs : laquelle ?).

    J'ai un peu développé ces notions dans : http://forums.futura-sciences.com/ma...ml#post1980944
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  6. A voir en vidéo sur Futura
  7. #5
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    J'ai lu dans wikipédia http://fr.wikipedia.org/wiki/Mod%C3%A8le_non_standard

    ceci :

    Les propositions qui sont vraies dans le modèle standard sont vraies dans le modèle non standard.

    Malgré qu'on ait employé l'expression "vrai dans le modèle standard", je ne peux que comprendre que c'est encore employé dans le sens "démontrable", non ?

  8. #6
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    Bonjour
    Je me méfie d'une expression comme "notion intuitive de vérité", déjà que je me méfie du mot "vérité"
    Oui mais si dans une discussion, on emploie le terme "vrai", difficile de ne pas parler "un peu" de "vérité".


    Une proposition vraie dans le modèle standard peut être démontrable dans la théorie (d'ailleurs : laquelle ?).
    Peut être l'arithmétique du second ordre ?

  9. Publicité
  10. #7
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par jreeman Voir le message
    J'ai lu dans wikipédia http://fr.wikipedia.org/wiki/Mod%C3%A8le_non_standard

    ceci :

    Les propositions qui sont vraies dans le modèle standard sont vraies dans le modèle non standard.

    Malgré qu'on ait employé l'expression "vrai dans le modèle standard", je ne peux que comprendre que c'est encore employé dans le sens "démontrable", non ?
    L'article est intégralement faux, en particulier la phrase que vous avez extraite !

    Dans le pdf que j'ai cité, il y a une explication concernant cette confusion (je voulais écrire "immense c**nerie").

    Citation Envoyé par jreeman Voir le message
    A partir du moment où on est d'accord pour partir dans une discussion, où le terme "vrai" est employé, il faut bien accepter de parler de vérités pour rester cohérant.
    Certes, mais c'est justement le mot "vrai" ou "vérité" qui crée la confusion. De plus, ma remarque concernait aussi le mot "intuitif".

    Citation Envoyé par jreeman Voir le message
    Peut être l'arithmétique du second ordre ?
    Je ne comprends pas : 1 + 1 = 2 est démontrable dans AP et donc vraie dans le modèle standard, sans avoir à faire appel à la logique du 2nd ordre.

    Je réagissais à :
    Citation Envoyé par jreeman Voir le message
    Malgré qu'on ait employé l'expression "vrai dans le modèle standard", je ne peux que comprendre que c'est encore employé dans le sens "démontrable", non ?
    et j'ai dû mal me faire comprendre, donc je précise : "vrai dans le modèle standard" peut concerner des propositions démontrables, ou des propositions indécidables (mais évidemment pas des propositions réfutables).
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #8
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Certes, mais c'est justement le mot "vrai" ou "vérité" qui crée la confusion.
    D'après ce que j'ai compris de ces messages, c'est que "vrai dans le modèle standard de l'arithmétique" peut être compris par :
    - soit démontrable dans le modèle standard de l'arithmétique
    - soit indécidable dans le modèle standard de l'arithmétique

    De plus, ma remarque concernait aussi le mot "intuitif".
    Parceque, je ne conçois la notion de vérité que comme intuitive. Pour moi 1+1=2 est une vérité intuitive.

    Je ne comprends pas : 1 + 1 = 2 est démontrable dans AP et donc vraie dans le modèle standard, sans avoir à faire appel à la logique du 2nd ordre.
    Je ne comprends pas trop non plus, c'est surement du à un probleme anodin de vocabulaire.
    Dernière modification par invite7863222222222 ; 14/04/2010 à 12h46. Motif: effacement d'une imprécision

  12. #9
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par jreeman Voir le message
    D'après ce que j'ai compris de ces messages, c'est que "vrai dans le modèle standard de l'arithmétique" peut être compris par :
    - soit démontrable dans le modèle standard de l'arithmétique
    - soit indécidable dans le modèle standard de l'arithmétique
    Indécidable dans un modèle ne veut rien dire, indécidable fait référence à une théorie.

    Une proposition est "vraie dans le modèle standard de l'arithmétique" veut dire ... qu'elle est vraie dans le modèle standard de l'arithmétique (désolé, mais je ne vois rien d'autres à dire (en fait on peut dire qu'elle n'est pas réfutable dans la théorie, et pour certaines classes de propositions on peut en dire plus, cf. le document déjà cité).


    Citation Envoyé par jreeman Voir le message
    Parceque, je ne conçois la notion de vérité que comme intuitive. Pour moi 1+1=2 est une vérité intuitive.
    Personnellement, je ne vois aucune différence de nature entre la "vérité" 1 + 1 = 2, et la "vérité" baptisée "paradoxe de Banach-Tarski (on peut découper une boule de IR3 et reconstruire deux boules identiques à la première avec les morceaux)", et pourtant, je ne serais pas étonné, que vous n'ayez pas la même approche intuitive de ces deux "vérités".
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  13. #10
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    désolé, mais je ne vois rien d'autres à dire
    Il me semble qu'on peut donc dire qu'elle n'est pas réfutable.

    pourtant, je ne serais pas étonné, que vous n'ayez pas la même approche intuitive de ces deux "vérités".
    Ca c'est sûr, car je ne classifie pas la seconde "vérité" dans les vérités.

    Où voyez vous une incohérance dans mes propos (si vous en voyez) ?

  14. #11
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par jreeman Voir le message
    Il me semble qu'on peut donc dire qu'elle n'est pas réfutable.
    C'est bien ce que j'ai dit ; on peut même dire plus pour les propositions purement existentielles


    Citation Envoyé par jreeman Voir le message
    Ca c'est sûr, car je ne classifie pas la seconde "vérité" dans les vérités.
    Ce qui a l'air de vouloir dire que pour vous "vérité" réfère à l'intuition et non aux mathématiques, ce qui illustre bien ma méfiance vis à vis de l'expression "notion intuitive de vérité" quand on fait des mathématiques.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  15. #12
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    Ce qui a l'air de vouloir dire que pour vous "vérité" réfère à l'intuition et non aux mathématiques
    Si. 1 +1 est selon moi, une vérité intuitive et mathématique.

    De votre coté, vous n'excluez donc pas que l'on puisse parler de vérités en se référant aux mathématiques ? Dans quel mesure est-ce possible dans une position non platonicienne ?

  16. Publicité
  17. #13
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par jreeman Voir le message
    Si. 1 +1 est selon moi, une vérité intuitive et mathématique.
    Oui mais, pour vous, le paradoxe de Banach-Tarski, n'est pas une "vérité" alors que du point de vue mathématique, c'est un théorème, "comme les autres".

    Citation Envoyé par jreeman Voir le message
    De votre coté, vous n'excluez donc pas que l'on puisse parler de vérités en se référant aux mathématiques ? Dans quel mesure est-ce possible dans une position non platonicienne ?
    Je l'ai déjà dit, je n'aime pas le vocabulaire vrai/faux que l'on soit platonicien ou formaliste, peu importe, cela génère des confusions, donc c'est un mauvais vocabulaire (essentiellement à cause de "l'intuition" que l'on peut avoir du mot "vérité").

    En tout état de cause dire : "la proposition f est vraie dans le modèle standard de l'arithmétique" ne me pose pas de problème car la signification de "vraie" y est parfaitement définie. Par contre, jamais je ne dirais "la proposition f est vraie (ou fausse)" pour signifier qu'elle est vraie (ou fausse) dans le modèle standard, mais fausse (ou vraie) dans d'autres.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  18. #14
    LPTheKiller

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    jreeman : Les maths, c'est tout SAUF l'intuition !
    Peu importe qu'intuitivement tu retrouve certains trucs que les maths ont démontré, on peut affirmer que c'est plus "par hasard" qu'autre chose. Parce que tu n'aurais jamais trouvé intuitivement le truc de Banach-Tarski, qui pourtant est vrai, et parce que l'intuition peut aussi bien faire dire des choses qui sont fausses !
    C'est pourquoi le but des théories fondamentales est de poser les concepts de base pour que 1+1=2 ne soit plus de l'ordre de l'intuitif, mais bel et bien une chose démontrée et donc absolument certaine.

    edit : désolé d'avoir encore utilisé le mot "vrai" ^^
    Par "vrai", moi j'entends un raisonnement juste.
    Dernière modification par LPTheKiller ; 14/04/2010 à 14h40.

  19. #15
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    Oui mais, pour vous, le paradoxe de Banach-Tarski, n'est pas une "vérité" alors que du point de vue mathématique, c'est un théorème, "comme les autres".
    Je revendique le droit d'avoir une définition des mathématiques qui exclut ce genre de théorème comme une vérité ou comme théorème "comme les autres".
    Que vous pensiez que ca m'exclut des mathématiciens j'en ai rien à faire (et je vous le concède volontiers), pas pour être buté ou parceque je n'aime pas les mathématiciens ou les mathématiques, mais parceque je pense être dans mon droit.

    Je l'ai déjà dit, je n'aime pas le vocabulaire vrai/faux que l'on soit platonicien ou formaliste, peu importe, cela génère des confusions, donc c'est un mauvais vocabulaire (essentiellement à cause de "l'intuition" que l'on peut avoir du mot "vérité").
    Non mais vous admettez que le terme vérité bien employé soit justifié ? Oui ou non ?

    En tout état de cause dire : "la proposition f est vraie dans le modèle standard de l'arithmétique" ne me pose pas de problème car la signification de "vraie" y est parfaitement définie.
    Parfaitement définie mais vous êtes d'accord que le mot "vraie" n'a pas été choisi au hasar, qu'il a quelque chose à voir avec la notion habituelle que l'on a du vrai, non ? Si oui comment est-ce possible d'un point de vue non platonicien. Si non, pourquoi, continuer à utiliser ce terme ?

  20. #16
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par LPTheKiller Voir le message
    jreeman : Les maths, c'est tout SAUF l'intuition !
    Peu importe qu'intuitivement tu retrouve certains trucs que les maths ont démontré, on peut affirmer que c'est plus "par hasard" qu'autre chose. Parce que tu n'aurais jamais trouvé intuitivement le truc de Banach-Tarski, qui pourtant est vrai, et parce que l'intuition peut aussi bien faire dire des choses qui sont fausses !
    C'est pourquoi le but des théories fondamentales est de poser les concepts de base pour que 1+1=2 ne soit plus de l'ordre de l'intuitif, mais bel et bien une chose démontrée et donc absolument certaine.
    Par l'usage de ! et de mots en majuscule vous venez de vous disqualifiez d'office d'avoir des réponses aux différents points de votre message.

  21. #17
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par jreeman Voir le message
    [...]
    Par votre ton, vous venez de vous disqualifiez d'office d'avoir des réponses aux différents points de votre message.


    @ LPTheKiller : si ma réponse à votre question initiale n'est pas complète de votre point de vue, n'hésitez pas à me relancer, je vous répondrai avec plaisir.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  22. #18
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    Par votre ton, vous venez de vous disqualifiez d'office d'avoir des réponses aux différents points de votre message.
    C'est bien trop facile...

  23. Publicité
  24. #19
    LPTheKiller

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    Par votre ton, vous venez de vous disqualifiez d'office d'avoir des réponses aux différents points de votre message.


    @ LPTheKiller : si ma réponse à votre question initiale n'est pas complète de votre point de vue, n'hésitez pas à me relancer, je vous répondrai avec plaisir.
    Merci pour al réponse.
    Je suis d'accord pour la question du "vrai", qui fait plutôt sens à mes yeux. Mais à ce moment-là, beaucoup personnes se trompent et n'interprètent pas bien le théorème !
    D'ailleurs : Est-ce que Gödel lui-même parlait de "vérité" ?

    Sinon, un autre point est pour moi assez obscure : Soit n le nombre de Gödel qui dit, en gros "on ne peut pas démontrer n".
    Comment ce nombre peut-il faire référence à lui-même sans faire de boucle du genre : "on ne peut pas démontrer "on ne peut pas démontrer "on ne peut pas démontrer "on ne peut pas démontrer "on ne peut pas démontrer ... " " " " " ?
    Ce que je veux dire, c'est que si n est une séquence de chiffre, pour qu'il s'auto-réfère, il faudrait qu'il comprenne sa propre séquence... à moins de s'y référer de manière détournée... ?

  25. #20
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par LPTheKiller Voir le message
    Mais à ce moment-là, beaucoup personnes se trompent et n'interprètent pas bien le théorème !
    C'est un fait malheureusement avéré

    Citation Envoyé par LPTheKiller Voir le message
    D'ailleurs : Est-ce que Gödel lui-même parlait de "vérité" ?
    Le texte original est en allemand, langue que je ne parle pas, le titre parle de "unentscheidbare", traduit généralement par indécidable ...

    Citation Envoyé par LPTheKiller Voir le message
    Sinon, un autre point est pour moi assez obscure : Soit n le nombre de Gödel qui dit, en gros "on ne peut pas démontrer n".
    Comment ce nombre peut-il faire référence à lui-même sans faire de boucle du genre : "on ne peut pas démontrer "on ne peut pas démontrer "on ne peut pas démontrer "on ne peut pas démontrer "on ne peut pas démontrer ... " " " " " ?
    Ce que je veux dire, c'est que si n est une séquence de chiffre, pour qu'il s'auto-réfère, il faudrait qu'il comprenne sa propre séquence... à moins de s'y référer de manière détournée... ?
    En fait le "n" est le nombre de Gödel d'une proposition a une variable libre, ce que n code ne contient donc pas la constante n, mais la variable x.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  26. #21
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Je vais essayer d'être plus clair en donnant un exemple :
    Soit la formule f(x) : 1 + x = x + 1
    1) le problème n'est pas de savoir si cette formule est vraie dans le modèle standard, si elle est démontrable ou non ..., il s'agit simplement de la coder.
    2) "1" n'est pas un élément du langage, la première chose à faire est donc d'écrire cette formule en utilisant exclusivement les éléments du langage
    f(x) : s(0) + x = x + s(0)
    3) en utilisant le codage décrit dans le document déjà cité (s -> 49, ( -> 3, 0 -> 15, ) -> 5, + -> 97, x -> 21, = -> 99), la formule se code :
    249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415
    4) rien n'interdit de coder la formule f(12) : laissé en exercice, car il faut écrire 12 sous la forme s(s(s ... s(0) ... ), avec 12 fois s)
    5) on peut aussi coder f(249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415
    ) (bon courage ), mais dans ces deux derniers cas la formule n'est plus la même, donc les codes sont différents !
    6) il n'est pas possible de coder f(n), car "n" ne fait pas partie du langage (comment écrire s(s(s ... s(0) ... )) sans savoir combien de s il faut écrire, le but est d'obtenir un nombre, pas une formule contenant des variables)
    7) bien sur je peux me demander si la formule de code 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415 est démontrable ou non pour x = 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415, sans que 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415 "contienne" 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  27. #22
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par LPTheKiller Voir le message
    D'ailleurs : Est-ce que Gödel lui-même parlait de "vérité" ?
    Je viens de parcourir le texte de Gödel en anglais, le mot "True" n'y apparaît me semble-t-il que dans le sens "vrai dans tous les modèles", donc prouvable grace au théorème de complétude, et dans un seul paragraphe.

    Le théorème original s'écrit :
    Citation Envoyé par Gödel
    For every -consistent primitive recursive class of formulae there is a primitive recursive class-sign r such that neither forall(v; r) nor not(forall(v; r)) belongs to Conseq( ) (where v is the free variable of r).
    On est loin des formulations "marketing" .
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  28. #23
    invite7863222222222
    Invité

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Avec la réserve que cette source http://www.philo5.com/Les%20philosop...eme.htm#_ftn22 soit fiable, voici une version "digeste" générale et de Gödel lui-même :


    Grâce à certains travaux qui ont suivi cet article, notamment ceux de A.M. Turing, nous disposons désormais d'une définition sûre, précise et adéquate du concept de système formel, il est possible de donner une version tout à fait générale des théorèmes VI et XI. On peut démontrer rigoureusement que dans tout système formel consistant contenant une théorie des nombres finitaire relativement développée, il existe des propositions arithmétiques indécidables et que, de plus, la consistance d'un tel système ne saurait être démontrée à l'intérieur de ce système.

  29. #24
    LPTheKiller

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par Médiat Voir le message
    Je vais essayer d'être plus clair en donnant un exemple :
    Soit la formule f(x) : 1 + x = x + 1
    1) le problème n'est pas de savoir si cette formule est vraie dans le modèle standard, si elle est démontrable ou non ..., il s'agit simplement de la coder.
    2) "1" n'est pas un élément du langage, la première chose à faire est donc d'écrire cette formule en utilisant exclusivement les éléments du langage
    f(x) : s(0) + x = x + s(0)
    3) en utilisant le codage décrit dans le document déjà cité (s -> 49, ( -> 3, 0 -> 15, ) -> 5, + -> 97, x -> 21, = -> 99), la formule se code :
    249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415
    4) rien n'interdit de coder la formule f(12) : laissé en exercice, car il faut écrire 12 sous la forme s(s(s ... s(0) ... ), avec 12 fois s)
    5) on peut aussi coder f(249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415
    ) (bon courage ), mais dans ces deux derniers cas la formule n'est plus la même, donc les codes sont différents !
    6) il n'est pas possible de coder f(n), car "n" ne fait pas partie du langage (comment écrire s(s(s ... s(0) ... )) sans savoir combien de s il faut écrire, le but est d'obtenir un nombre, pas une formule contenant des variables)
    7) bien sur je peux me demander si la formule de code 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415 est démontrable ou non pour x = 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415, sans que 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415 "contienne" 249.33.55.715.1197.1321.1799.1921.2397.2949.313.3715.415
    Merci, je comprends mieux comment ça marche maintenant.

    J'aurais une autre petite question, pas vraiment liée à tout ça et moins formelle.
    C'est sur ce "paradoxe" :
    Le plus petit nombre qui ne peut pas être défini par moins de dix-neuf mots en français

    Comme cette définition est incohérente, autant dire que ce mot n'existe pas, et puis c'est tout, non ? Où est le paradoxe ?
    Ce n'est pas parce que je donne une définition qu'il existe bien un objet qui y répond...

    Par exemple, "soit x le réel qui est tel que x² = -1"
    Eh bien, ce réel n'existe pas, simplement... Me trompé-je ?

  30. Publicité
  31. #25
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Citation Envoyé par LPTheKiller Voir le message
    J'aurais une autre petite question, pas vraiment liée à tout ça et moins formelle.
    C'est sur ce "paradoxe" :
    Le plus petit nombre qui ne peut pas être défini par moins de dix-neuf mots en français

    Comme cette définition est incohérente, autant dire que ce mot n'existe pas, et puis c'est tout, non ? Où est le paradoxe ?
    Ce n'est pas parce que je donne une définition qu'il existe bien un objet qui y répond...

    Par exemple, "soit x le réel qui est tel que x² = -1"
    Eh bien, ce réel n'existe pas, simplement... Me trompé-je ?
    C'est un tout petit plus compliqué que cela.
    L'ensemble IN, muni de la relation d'ordre habituelle est un bon ordre, c'est à dire que tout sous ensemble non vide possède un plus petit élément, donc si l'ensemble défini par "l'ensemble des nombres qui ne peuvent pas être défini par moins de dix-neuf mots en français" est bien un ensemble, alors il doit avoir un plus petit élément, ce qui est contradictoire, la conclusion s'impose : ce n'est pas un ensemble !

    Pour creuser un peu plus, il faudrait savoir pourquoi ce n'est pas un ensemble : la définition n'est pas formelle, et que si on devait la rendre formelle, il faudrait quantifier sur les formules, ce qui n'est pas possible en logique du premier ordre, et qui plus est, une quantification qui inclut l'auto-référence (ce qui est une façon très simple de créer des "paradoxes").

    Il faudrait aussi introduire la notion de longueur d'une formule dans la logique, ce qui poserait quelques problèmes supplémentaires (définition de IN et de quelques unes de ses propriétés en amont de la définition de IN).

    Personnellement, je n'appelle pas cela un paradoxe, mais une erreur de raisonnement.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  32. #26
    LPTheKiller

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Re-bonjour, j'ai une nouvelle question

    Le nombre de Gödel n qui code "n n'est pas prouvable", on a donc montré qu'il correspond à une proposition qui n'est pas prouvable dans la théorie.
    Mais on a codé la prouvabilité des formules représentées par les nombres de Gödel à partir d'opérations arithmétiques de base.
    Cela signifierait qu'il existe un certain entier, pour lequel on ne peut pas (enfin, la théorie ne peut pas) conclure quant à certaines opérations arithmétiques de base qu'on lui ferait subir ?
    Par exemple, que "tel nombre est divisible par tel nombre" puisse ne pas être prouvable ?
    Dans ce cas, est-ce qu'on a concrètement (explicitement) n, et les opérations arithmétiques que telle théorie ne peut pas prouver à son propos ?

    (Je sens que ce n'est toujours pas tout à fait clair dans ma tête )

  33. #27
    Médiat

    Re : Précisions sur le théorème d'incomplétude de Gödel...

    Bonjour,

    Une discussion sur ce sujet a déjà eu lieu : http://forums.futura-sciences.com/ma...thmetique.html.

    J'ajoute une remarque : l'arithmétique n'est pas décidable, c'est dire qu'il n'existe pas d'algorithme capable, quand on lui donne une formule en entrée, de répondre en un temps fini si cette formule est démontrable ou non.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

Discussions similaires

  1. théorème de Gödel
    Par treborliryc dans le forum Mathématiques du supérieur
    Réponses: 37
    Dernier message: 05/12/2009, 16h38
  2. Théorème d'incomplétude
    Par AimericB dans le forum Mathématiques du supérieur
    Réponses: 14
    Dernier message: 16/09/2009, 04h49
  3. Théorème d'imcomplétude de Gödel
    Par AutreMichel dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 09/09/2006, 18h13
  4. Théorème de Gödel
    Par GottferDamnt dans le forum Lectures scientifiques
    Réponses: 5
    Dernier message: 13/01/2006, 02h07
  5. Theorème de Gödel
    Par Fufu dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 23/04/2004, 11h14