Discuter:Théorème d'incomplétude de Gödel

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Théorème d'incomplétude de Gödel fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
A Cet article a été classé comme d'Avancement A selon le Tableau d'évaluation du projet. (Voir les statistiques)
Élevée Cet article a été classé comme d'Importance élevée selon le Tableau d'évaluation du projet.
Projet WP1
 La version actuelle de Théorème d'incomplétude de Gödel a été sélectionnée par le comité de sélection du projet Wikipédia 1.0. En discuter...

Sommaire

[modifier] Indécidabilité

Note : le texte ci-dessous a été déplacé depuis le Bistro de Wikipédia. Aoineko 18 fév 2004 à 02:50 (CET)

Dans la page Discuter:Athéisme, Stuart évoque le principe d'indécidabilité de Cantor. C'est apparemment un sujet qui touche à la fois les mathématiques (par son origine) et la philosophie (par ses applications). J'aimerais en savoir plus là-dessus, c'est pourquoi j'ai lancé une offre sur Wikipédia:WikiMonnaie. Et à la réflexion, 4 ψ c'est pas assez pour un sujet aussi costaud, je vais remonter ça. Φido 11 fév 2004 à 11:15 (CET)

Je n'y connais pas grand chose (juste quelques mots de la part d'un prof d'algèbre en prépa) mais je donne quand même mon avis. Le principe d'une bonne théorie est d'expliquer le maximum de choses avec le minimum d'hypothèses. Pour réduire le nombre d'hypothèses on essaie de montrer qu'une hypothèse peut se démontrer à partir d'autres qui ont déjà été posées. En revanche il y a des résultats qu'on ne peut absolument pas démontrer à partir d'autres. L'exemple le plus célèbre est constitué par les tentatives de démontrer que l'axiome des parallèles en géométrie euclidienne pourrait se déduire des autres axiomes (je ne me souviens plus lesquels). Or, grâce à ce cher Cantor on sait maintenant que cet axiome n'est pas démontrable. Donc les trois solutions (deux parallèles ne se coupent jamais; se coupent en un point; se coupent en une infinité de points) sont toutes aussi valables et sont chacune à la base d'un type de géométrie. Dans le cas de Dieu, son existance ou sa non existance n'étant pas démontrable, chacune des réponses est valables. S'il y avait un matheux dans la salle pour corriger mes erreurs ce ne serait pas de refus. /me préfère la Physique aux maths ;) Med 11 fév 2004 à 11:30 (CET)


Non, cette théorie là, c'ets le rasoir d'Ockham. Stuart Little 11 fév 2004 à 17:36 (CET)


Pour moi, le principe d'indécidabilité est de Gödel (en s'inspirant de Cantor)), qui a publié le Théorème d'Incomplétude. D'ailleurs, Stuart Little a écrit : "C'est ce qu'explique le principe d'indécidabilité de Goeddel à partir des travaux sur les grands cardinaux de Cantor.". Ceci dit, c'est bien au-dessus de mon niveau, on verra ca dans quelques années. Ceux que ca intéresse peuvent aussi lire les livres de Raymond Smullyan ("Le livre qui rend fou" et "Ca y est, je suis fou"), ca commence par des énigmes et ca finit par ca... je me suis arrêté un peu avant Koxinga 11 fév 2004 à 13:20 (CET)

C'est exactement cela que j'aimerais qu'on expose proprement. Parce que moi, si je l'expose, je sors de mon domaine de compétence et je n'exposerai que des salades.

Je suis pas au courãnt du wikimonnaie. Mais c'est sûr que j'en mettrais bien pour avoir un exposé clair et cohérent. Stuart Little 11 fév 2004 à 17:36 (CET)


J'ai lu un bouquin la dessus il y a quelque temps qui expliquait qu'il fallait faire très attention as l'application de ce théorème hors du champs des mathématiques (il prenait justement le cas de l'existence de Dieu). En effet les indécidables de Goëdel (comme tout résultat mathématique) ne le sont que pour un système formel (une collection d'hypothèse de départs: les axiomes) donné. Il ne prédisent en aucun cas qu'il ne sera pas possible de trouver un système formel ou il ne seront plus indécidable (tout ce que prédit ce théorème c'est que ce nouveau système formel sera toujours incomplet car il contiendra encore d'autre indécidables). Pour reprendre l'axiome de parallèle: il est tout à fait possible de le remplacer par un autre axiome (la somme des angles d'un triangle vaut 180° devrait marcher ???) qui permettra de démontrer l'axiome des parallèles. Par ailleurs il existe des systèmes formels complets (c'est à dire des théories sans indécidables): par exemple la logique du premier ordre (tout est vrai ou faux) est axiomatisable. Donc si quelqu'un qui vous dit "l'existence de Dieu est indécidable" demandez lui "en prenant quelles hypothèses de départ?" ;-) ske 11 fév 2004 à 13:49 (CET)

OK. Mais si tu prends la question de Cantor sur les grands cardinaux (cel de l'aleph 1 et de l'aleph 0) tu comprends parfaitement ce dont on parle à propos de l'indécidabilité de l'existence de Dieu. Laquelle question des grands cardinaux ne dépend que d'un axiome : toute grandeur est mesurable. Stuart Little 11 fév 2004 à 17:36 (CET)



Coucou, coucou ! Voilà un matheux ! Gödel a démontré deux théorèmes sur le sujet de l'indécidabilité : ① tout système formel contenant les nombres entiers (donc pas mal de choses) contient une proposition indécidable (ie qu'on ne peut peut démontrer vraie ou fausse avec les axiomes initiaux) et ② que cette proposition est vraie en ajoutant un axiome. Ensuite il ne faut pas faire sortir ce théorème mathématique des mathématiques sinon on raconte n'importe quoi comme Debray et son principe bidon de Gödel-Debray (cf. la partie là-dessus du livre de Sokal et Bricmont Impostures intellectuelles). ℓisllk 11 fév 2004 à 16:32 (CET)

Bon, c'est incompréhensible. Mais l'interdit de Sokal et Briquement est clairement documenté par des exemples et, dans le cas présent, cela ne s'applique pas.

C'est marrant comme les matheux peuvent être dogmatiques, parfois ? On croirait entendre un croyant démontrer l'existence de Dieu dans le langage qui lui est propre et, quand on veut lui montrer un glissement sémantique qui sert de raisonnement, il répond ah, mais tu peux pas comprendre. :-)))

Stuart Little 11 fév 2004 à 17:36 (CET)


Relis lentement, tu devrais comprendre : ce n'est pas si dur que ça. De plus le problème de א0 et de א1 n'est pas indécidable au sens de mon intervention ci-dessus parce que le problème de Cantor (est-ce qu'il existe un cardinal entre א0 et א1 ?) est un postulat, c'est-à-dire qu'on peut y répondre « oui » ou « non », cela produira juste des théories différentes, en aucun cas des contradicitons. Notons que mon intervention (comme la précédente) n'est pas dogmatique, ce que je dis sont des théorèmes démontrés (pas par moi bien entendu). ℓisllk 11 fév 2004 à 20:40 (CET)

[modifier] Création de l'article

J'ai réalisé deux articles sur le Théorème d'incomplétude de Gödel et l'Hypothèse du continu de Cantor. Je pense que c'était le sujet de vos demandes ? Ils sont par contre à completer, notamment pour la demonstration du théorème d'incompletude et le rapport avec la philosophie et dieu. OsMoSe 29 fév 2004 à 19:13 (CET)

Je pense que la page devrait s'appeler Théorèmes d'Incomplétude vu que Gödel en a pondu deux. Sinon je ne vois pas ce que dieu vient faire là dedans. Ces théorèmes existent et sont prouvés mathématiquements. La philosophie qui vient se greffer dessus ce n'est que des discussions. --Tom 15 sep 2004 à 23:15 (CEST)

CD J'ai créé le titre "création de l'article", et ce serait bien que quelqu'un fasse des séparations avec des "modifier" parce que la page commence à être bien longue - c'est hors de ma portée pour le moment. Je viens de faire un peu de "cosmétique" dans le texte et je m'apprétais à pondre mes observations ici, et, oh surprise, ce n'est pas comme pour tous les théorèmes que j'ai visités ces derniers jours, on a déjà beaucoup discuté ! J'allais commencer en disant : bon article, mais cela peut être un article phare pour le projet mathématiques dans la mesure où la population intéressée dépasse largement le cadre des plus ou moins initiés à la logique (sauf erreur, il n'y a aucun article de mathématique non élémentaire parmi la centaine de fleurons de wikipédia) ; de ce point de vue je crois que l'article n'est pas encore à la hauteur, mais je me doute combien la tâche est difficile. Avant d'écrire quelques réflexions sur l'article, je suggérerai une méthode pour apporter des idées : il est clair, si j'ai bien compris la discussion, qu'il y a eu un bon débat sur le sujet avant la création de l'article, mais qu'il s'est éteint après la création ; ne pourrait-on pas relancer le débat sur une arène plus fréquentée (bistro, ?, et pourquoi pas, tâche de la semaine) en demandant aux gens de dire ce qu'ils pensent de la rédaction actuelle ?


Je termine par quelques remarques au fil de la lecture de l'article. Je vais parfois essayer de dire des choses précises du point de vue logique formelle, mais je risque ainsi de sortir de mon domaine de compétence, bref de dire des conneries.
1) Au sujet de « échapper ». Pour bien exposer la problématique il faudrait en dire un peu plus sur les systèmes formels. Goedel (comme Hilbert) s'intéresse à des systèmes où en un certain sens, qui peut être rendu précis, l'ensemble des axiomes est décidable : on a un algorithme qui permet de décider si oui ou non un énoncé est un axiome. Mais on peut très bien définir une théorie fromelle des entiers en prenant un modèle de la théorie précédente et en prenant comme axiomes tous les énoncés vrais dans le modèle ; on n'a là une théorie complète (tout aussi consistante que celle départ), mais à part cela sans grand intérêt pratique.
2) Il faudrait quelques mots ici ou là sur l'ordinal mystérieux de Gentzen.
3) La date 1868 est aussi mystérieuse ; et puis ce n'est pas tout à fait juste pour Bolyai et Lobatchewski.
4) Ici encore il faudrait que le lecteur puisse comprendre qu'un indecidable dans un système à la Peano (et jamais précisé dans l'article) peut ne pas l'être dans les entiers de la théorie des ensembles. De plus on a un exemple amusant d'une telle chose avec Hercule coupant les têtes de l'hydre (je ne sais plus exactement ce que c'est, mais je peux retrouver). Par contre je ne connais pas du tout l'exemple en théorie des matrices, et j'aimerais bien avoir une référence.
5) enfin, le dernier paragraphe n'a à mon avis rien à faire dans un article de mathématique ; par contre il suggère qu'il devrait y avoir un article sur l'exploitation de résultats scientifiques (th. de Goedel, mais aussi principe d'incertitude, etc. ; en fouillant les archives de l'affaire Sokal, on peut trouver beaucoup de sujets) en sciences humaines, avec quelques beaux problèmes de neutralité de point de vue... CD 22 jan 2005 à 19:41 (CET)


Personnellement, je verrai bien l'évolution de l'article vers 2 articles différents :
  • Je pense qu'il faudrait crée sur une autre page un article totalement mathématique présentant rigoureusement les théorèmes d'incomplétude de Gödel, avec un modèle de démonstration.
  • Quand à cette page, elle pourrait rester dans le même esprit qu'actuellement, une page de vulgarisation qui présenterai également les aspects extra-mathématiques. Qu'en pensez vous ?
Concernant les têtes de l'hydre, c'est un très bon exemple en effet, très clair, j'essayerai de le rajouter (à moins que vous préfériez le faire ?). Concernant "l'ordinal mystérieux de Gentzen" par contre, je pense voir grosso-modo de quoi il s'agit, mais je ne pense avoir les connaissances pour en parler, je vous laisse donc faire :).
Concernant la date de 1868, elle correspond à la démonstration due à Eugenio Beltrani.
OsMoSe 23 jan 2005 à 19:27 (CET)


Content de te "rencontrer" (comme je suis sans doute le plus vieux, je me permets de proposer le tutoiement, qui me semble habituel dans ces lieux). Je suis entièrement de ton avis, c'est très bien d'avoir, comme on a maintenant, une bonne base de départ (pas trop formalisée, mais pas trop floue non plus) et de continuer par les aspects extra-mathématiques. Mais il faut alors, comme tu le dis, un article vraiment mathématique et je n'ai pas l'impression qu'on a parmi nous quelqu'un d'apte à le faire ex nihilo ; si le texte anglais est bon (je ne l'ai pas regardé) je peux en faire la traduction (avec les afférents : système formel, etc. ; dans quoi je me lance !). Pour l'hydre, c'est un souvenir, je ne sais plus où j'ai lu (ou entendu) cela, et je te la laisse bien volontiers. Je me doutais que 1868 était l'apparition d'un modèle intérieur à la géométrie euclidienne ; il faut ajouter Beltrami etc. ou dans l'article ou dans 1868. Je m'occupe du epsilonn de Gentzen (je ne sais pas bien ce que c'est, mais j'ai de la documentation - de manière générale j'ai à ma disposition beaucoup de documentation, ne pas hésiter à me demander). CD 23 jan 2005 à 21:58 (CET)

[modifier] Modification de l'article

  • Quelques modifs mineures :
    • remplacer consistant par cohérent. C'est tout aussi précis (aucune contradiction prouvable) et c'est plus parlant.
    • date de communication de la preuve (1930), publication écrite 1931.
    • mentionner que la terminologie n'est pas très bien fixée, ni ici, ni par les logiciens. Le théorème d'incomplétude de Gödel est appelé parfois le premier théorème d'incomplétude pour le distinguer du second (l'énoncé qui affirme la cohérence d'une théorie T est un indécidable de T). Comme les deux vont ensemble, que la preuve du second suit directement celle du premier, qu'ils ont été exposés par Gödel dans le même article fondateur de 1931, il me semble qu'ils doivent être présentés dans un même article de l'encyclopédie.
  • modifs plus importantes
    • mentionner l'existence d'une preuve naturelle de la Cohérence des axiomes de l'arithmétique formelle, dont la validité n'est pas contestable, mais qui est difficile à formaliser et qui présuppose notre capacité à connaître les ensembles infinis.
    • Introduire les notions de représentation d'une formule par un nombre (arithmétisation de Gödel) et par un objet quelconque de la théorie, et de prédicat de prouvabilité.
    • Prouver le théorème de Gödel sous l'hypothèse de l'existence d'un prédicat de prouvabilité et d'un prédicat de substitution. La preuve est facile et peut être exposée même dans un article destiné à tout public. La construction de l'énoncé indécidable de Gödel est identique à la construction du nombre AT dans le théorème d'incomplétude de Tarski. Il suffit de remplacer le prédicat de vérité par un prédicat de prouvabilité. C'est une application directe du paradoxe du menteur, comme tous (?, je crois que oui, mais c'est peut-être un peu tiré par les cheveux. Peut-on voir les théorèmes de Cantor comme une application directe du paradoxe du menteur ?) les théorèmes sur l'incomplétude mathématique. On peut aussi déduire le théorème de Gödel du théorème de Tarski.
    • La partie difficile de la preuve de Gödel consiste bien sûr à prouver l'existence des prédicats de prouvabilité et de substitution. Je ne sais pas si CD a avancé sur cette partie très mathématique. De mon côté je laisse cela pour l'instant. Je prépare une révision de l'article système formel qui donnera quelques préliminaires.
    • Donner l'argument de la preuve du second théorème d'incomplétude. Insister, comme cela a déjà été dit sur le caractère relatif de ce théorème : T ne permet pas de prouver la cohérence de T, mais cela ne veut pas dire que la cohérence de T n'est pas prouvable.
    • Je trouve que la discussion sur formalisme et logicisme est trop courte.
      • Pour que les conclusions soient recevables il faudrait qu'elles soient précisées. Il y a des façons d'interpréter le formalisme et le logicisme tout à fait respectables, même aujourd'hui. Ce sont des tentatives de réponse à la question de la nature de la vérité mathématique. C'est toujours une question d'actualité pour laquelle les propos de Frege, Hilbert, Whitehead, Russell et beaucoup d'autres sont toujours pertinents, même s'ils doivent être révisés à la lumière des résultats obtenus par Gödel.
      • mentionner que la terminologie sur la différence entre principes logiques et principes mathématiques n'est pas très bien fixée, ni ici, ni par les logiciens. Frege considérait les principes de sa théorie (contradictoire) des ensembles comme des principes logiques. Il me semble qu'aujourd'hui, le mieux est de considérer les principes de la logique du premier ordre (sans théorie des ensembles donc, ni explicitement, ni implicitement) comme le noyau dur de la logique.
    • la partie philosophie pourrait être mieux exploitée.
      • Dire que l'existence de Dieu est un indécidable, c'est dire qu'on n'a pas choisi d'axiomes pour répondre à cette question. De ce point de vue, on peut rappeler que chacun est libre de choisir les axiomes qu'il veut, et que c'est à lui de montrer alors leur valeur.
      • Discuter les notions de puissance et d'impuissance de la raison. Montrer que le théorème d'incomplétude est lié à la puissance de l'imagination mais qu'il ne met pas en doute notre capacité à donner des preuves et à connaître, en un sens, tous les principes logiques.(voir théorème de complétude de Gödel.
  • Tout ceci est en préparation. J'en mettrai en ligne une partie dès que ce sera prêt (quelques jours), en tenant compte de vos objections.--Thierry Dugnolle 19 fev 2005 à 11:08 (CET)
J'ai lu, apprécié, mais je n'ai pas le temps d'écrire ma réponse aujourd'hui. J'écris aujourd'hui surtout pour te signaler ce qui me semble une coquille dans tes premières lignes. Tu as écrit "théorème de complétude" pour "théorème d'incomplétude" me semble-t-il. Trois théorèmes de Goedel : l'un, de complétude, le suivant d'incomplétude (1er) et le dernier d'inconsistance si je puis dire (incomplétude 2ème). CD 19 fev 2005 à 12:11 (CET)
Désolé pour la coquille. J'avais pourtant relu deux ou trois fois.--Thierry Dugnolle 19 fev 2005 à 14:30 (CET)

[modifier] Maturité de l'article

Très bel article, maintenant ! Encore un peu de wikification et de corrections typographiques (pour les formules mathématiques) et je serais pour en faire un "article de qualité" ! --Aldoo / ✉ 25 fev 2005 à 10:12 (CET)
J'avais aussi fait des éloges et quelques remarques, mais tout a disparu à la sauvegarde ! Avant d'avoir le courage de recommencer, deux petites choses que je pourrais faire moi-même un peu plus tard : sauf erreur, on n'écrit pas "Türing" mais "Turing", et il faut un lien diophantien quelque part. CD 25 fev 2005 à 11:17 (CET)

Reprises de quelques remarques.

  • Il manque un pont entre "incomplétude" qui paraît dans le titre mais peu ailleurs (sf reprise du titre) et "indécidabilité" et autres utilisés abondamment.
  • Je suis d'accord que "cohérent" est meilleur que "consistant", mais il est tellement fait usage de "consistant" ou "inconsistant" qu'il faut à mon avis que le mot paraisse dans le début de l'article (je ne sais si Dugnolle voit ici une différence "technique" entre "cohérent" et "consistant", aussi je m'abstiens de corriger moi-même).
Est-ce que "consistant", bien que fréquemment utilisé dans ce contexte-là, ne serait pas un anglicisme, au fait ? --Aldoo / ✉ 1 mar 2005 à 09:17 (CET)
Oh là bonne question, moi qui défends "récurrence" contre "induction"... C'est sans doute un anglicisme (et j'ai appris la logique dans des livres en anglais). J'ai été voir dans mes références en français. Dans "théorie des ensembles", Krivine donne "non contradictoire", "cohérent" et "consistant" comme synonymes [il serait bon aussi de citer "non contradictoire"] ; dans "Logique mathématique", Cori et Lascar prenne "cohérent" dans le sens syntaxique (on ne peut démontrer formellement un énoncé et son contraire) et "consistant" dans le sens sémantique (théorie ayant au moins un modèle). CD 1 mar 2005 à 10:46 (CET)
  • Le paragraphe "Relativité de l'indécidabilité..." et plus précisément dans l'alinéa "On pourrait penser "s'échapper" du théorème...", qui date d'avant Dugnolle, ne me satisfait pas. Il manque une référence à quelque chose comme "théorie finiment axiomatisée", introduit bien plus tard.
  • Toujours dans ce paragraphe, pourrait-on rendre moins mystérieux l'ordinal de Gentzen ?
  • Le paragraphe "Des exemples... d'indécidables", qui date aussi d'avant Dugnolle, contient une distorsion historique : l'exploration de la géométrie hyperbolique par Lobatschevski ou Bolyai date de bien avant le modèle de Beltrami auquel la date 1868 fait sans doute référence.
  • Dans le même paragraphe, je suis toujours preneur de l'exemple d'indécidable concernant les produits de matrices (je ne vois pas du tout à quoi cela fait allusion). Je me souviens (imprécisément) d'autre part d'un exemple où Hercule a à couper des tetes de l'hydre selon certaines règles : on ob tient un indécidable de la théorie de Peano mais un théorème pour les entiers en théorie des ensembles.
  • Au début de "Argument de la preuve et...", le paragraphe "On sait aujourd'hui... temps de calcul". Cela donne l'impression qu'une théorie décidable n'a pas grand intérêt, et c'est faux : par exemple, d'après Tarski, la géométrie d'Euclide est décidable, etc. D'autre part, le temps de calcul, pour un énoncé de taille raisonnable, peut être plus long que ce que permet l'univers (voir travaux de Stockmeyer et Meyer). CD 28 fev 2005 à 17:41 (CET)

Il y a beaucoup à répondre.

  • Sur Gentzen je suis un peu embêté. Je n'ai pas lu ses travaux sur la cohérence, ou consistance, ou non-contradiction, de l'arithmétique, je ne connais que le chapitre donné par Lorenzen (Métamathématique) sur ce sujet, et je ne connais pas les développements de la théorie de la preuve. J'aimerais bien aller plus loin mais je manque de temps et de documentation.
  • On a parfois besoin de distinguer plusieurs notions de consistance (syntaxique ou sémantique, oméga-consistance,...) mais je ne crois pas qu'il faille introduire ici ces distinctions. Le même flou terminologique existe aussi en anglais.
  • Oui pour changer le ton du paragraphe sur les théories décidables. Il serait même souhaitable de répertorier les théories décidables "intéressantes" et de donner (dans d'autres articles) des algorithmes de décision.

Sur les autres points, j'y réfléchis.--Thierry Dugnolle 1 mar 2005 à 15:00 (CET)

Petite réponse. Je suis (et serai) beaucoup en voyage ces temps-ci. Sur Gentzen, tu n'as pas à te sentir embêté ; je ne pense pas qu'il faille en dire beaucoup ssur son ordinal, juste une petite chose pour qu'il soit moins mystérieux (c'est sans doute un "petit" ordinal dénombrable, je n'ose pas le mettre parce que je n'ai pas retrouvé de référence, sinon je pense que c'est la seule chose à mettre). Je suis tout à fait d'accord pour ne pas chercher à distinguer dans l'article les différents sens donnés à consistance, cohérence, etc. Mais je réitère ma remarque : il faut que le mot "consistance" (ou "consistant") apparaisse au moins une fois pour que le lecteur qui a lu quelque part "consistance" n'ait pas de doute qu'on parle de la même chose. Enfin, il y a un article décidable qui a été créé, et aussi une discusssion de savoir si on le garde (dans PàS). J'ai proposé de garder, et de mettre là des exemples intéressants de théories décidables. CD 4 mar 2005 à 10:02 (CET)

J'ai supprimé les deux phrases suivantes. Je suis pour les réintégrer mais comme je ne sais pas de quoi il s'agit j'aimerais des précisions

  • Mais depuis l'arrivée de la théorie du calcul, on a pu créer de nouveaux indécidables, touchant par exemple des propriétés élémentaires concernant des produits de matrices.

--Thierry Dugnolle 4 mar 2005 à 22:08 (CET)

Pour ce qui est des "...produit de matrices...", c'est un mystère pour moi. Peut-être que "Osmose", qui s'est beaucoup occupé de la première rédaction, sait. Pour le problème de Whitehead je crois que j'ai lu un article dessus dans la version anglaise de Wikipédia et j'y ai compris un petit quelque chose. Cependant, il s'agit d'un problème sur les groupes abéliens, la théorie des groupes abéliens est décidable... et là je flotte. CD 4 mar 2005 à 23:23 (CET)

[modifier] Dieu ?

La partie Le théorème d'incomplétude en philosophie est assez surprenante. Il est dit que le théorème est souvent cité en philosophie. On aimerait bien des exemples. Quant à Dieu, on se demande bien ce qu'il vient faire dans cet article et quel rapport il peut bien avoir avec un théorème d'ordre mathématique. Mêler Dieu au théorème d'incomplétude de Gödel est aussi absurde que de le lier à la non-existence de solution réelle à l'équation x2+1=0 ou au contraire à l'existence d'une solution complexe. Theon 9 mars 2006 à 18:15 (CET)

Je suis globablement d'accord. L'existence de Dieu n'a rien a faire là. En ce qui concerne les citations en philosophie : ce n'est pas parce que certains "philosophes" ont utilisé le théorème de Gödel de façon extravagante que c'est l'habitude en philosophie. La philosophie peut s'occuper de mathématiques, de la logique et du théorème de Gödel sans sortir ce dernier de son contexte. A ce sujet, quelques lignes plus loin dans l'article, une phrase comme "Ces théorèmes montrent que l'imagination déborde tous les cadres" fait quand même un peu penser aux citations décriés au dessus. Est-il besoin dans un article sur le théorème de Gödel de parler des mauvais usages de celui-ci ? Si oui il faudrait intituler le paragraphe autrement et effectivement donner des exemples. je pense plutôt que l'on peut supprimer cette partie. Proz 7 avril 2006 à 01:30 (CEST)

En fait, je pense que les utilisations plus ou moins délirantes du Théorème de Gödel font partie de la matière encyclopédique concernant ledit théorème. Le but, c'est de rester neutre (donc, je retire plus ou moins délirantes:)), et de garder à cette partie des proportions raisonnables. Pour la neutralité, on peut utiliser cette phrase introductive : Le théorème de Gödel porte sur une propriété des systèmes formels d'axiomes dans la théorie des prédicats. Certains ouvrages ont prétendu lui donner une portée plus étendue que son champ d'application naturel. (peut-être certains trouveront prétendu non neutre, on peut changer). Après, il faudrait faire une vraie recherche pour donner quelques exemples significatifs, n'en développer aucun, et renvoyer sur les pages dédiées aux auteurs ou aux ouvrages en questions pour plus de précision, puis citer au moins l'existence d'une réaction à la Sokal-Bricmont, avec à nouveau lien vers ailleurs. La question existe, on dit ainsi cette existence, sans entrer dans la polémique.Salle 14 août 2006 à 23:20 (CEST)

Je ne suis guère enthousiaste, mais on peut faire quelquechose effectivement. Finalement je ne citerais pas forcément d'exemple précis. On peut se contenter d'une phrase sur la fascination exercée par le th. qui a produit quelques extrapolations contestables. Le livre de Sokal-Bricmont (qui peut être cité) a sa cohérence propre. C'est le fonctionnement d'un milieu qui est dénoncé, à travers ce genre de dérive sur le th. de Gödel (entre autres). Maintenant faire une vraie recherche pour etc. (ne pas se contenter de seconde main), c'est du boulot, et est-ce vraiment intéressant ? Si quelqu'un a envie de le faire, pourquoi pas ? L'écueil c'est un peu ce qui existait encore un avril 2006 (voir l'historique) : un paragraphe qui dénonce de façon vague, et qui fait vite prétentieux. Tout ça peut s'intégrer à un paragraphe d'intro, (dans lequel il y a des choses plus urgentes à dire). Proz 15 août 2006 à 22:57 (CEST)

Moi non plus, ça ne me passionne pas ; disons que l'idée, c'est de ne pas tomber dans un consensus entre matheux pour dire que tout ça n'a pas sa place. Puisque personne n'a envie de faire les recherches nécessaires, il vaut mieux effectivement ne rien faire pour le moment ; mais en se disant que le jour où quelqu'un voudra le faire bien, ça vaudra un petit paragraphe.Salle 18 août 2006 à 10:55 (CEST)

[modifier] refonte de l'article ?

Après avoir parcouru l'article il me semble que quelques modifications seraient utiles. D'une part il y a des imprécisions, voire erreurs. Par exemple la partie sur la preuve partielle du théorème est vraiment douteuse. Le théorème de Gödel ne se déduit pas du théorème de Tarski (sauf dans une version beaucoup plus faible que celle de Gödel, puiqu'il faut supposer que la théorie à pour modèle les entiers usuels) et de toute façon celui-ci date de 1933 (2 ans après Gödel), l'énoncé dit équivalent au th. de Gödel dans cette partie n'est de toute façon pas clair (que veut dire vrai ?) etc.[corrigé] Il faut de toute façon parler des hypothèses de cohérence pour comprendre le problème [à faire].

Je commence quelques modifications dans ce sens, très graduellement, et en débutant sous wikipedia. Mais une refonte serait peut être utile :

- la partie sur les preuves de cohérence de l'arithmétique devrait être dans un autre article

- les considérations sur les théories complètes devraient faire partie d'un autre article

- l'existence de théories incomplètes est en soit une trivialité, donc je ne suis pas sûr que le passage sur la géométrie, qui est bien-sûr intéressant (preuve de cohérence relative) soit à sa place.


Proz 5 avril 2006 à 22:19 (CEST)

Petit ajout : j'ai commencé quelques modifications. J'en justifie une qui n'était pas annoncée ci-dessus. L'énoncé du second théorème d'incomplétude n'était pas correct : sous les hypothèses usuelles, la cohérence d'une théorie est non démontrable dans cette théorie, mais pas forcément indécidable, comme on le déduit d'ailleurs justement du théorème lui-même. Je rajouterai d'ailleurs probablement quelquechose à ce sujet dans l'article [Fait].

Proz 7 avril 2006 à 01:40 (CEST)


J'ai restructuré le premier paragraphe, éliminé la reférence à une preuve en 1930 dont je n'ai pas trouvé trace [il semble que le résultat ait été annoncé en 1930, je laisse la date de parution de l'article, ce qui est le plus usuel] essayé de simplifier ou d'éclaircir certains points. Je ne considère pas du tout l'article dans un état satisfaisant. La suite est souvent encombrée de considérations qui me semblent hasardeuses par exemple sur les preuves de cohérence, et difficile à reprendre. Je compte réécrire pas mal de choses. Proz 25 avril 2006 à 20:38 (CEST)

Création d'un article théorie axiomatique, déplacement des développement sur les théories récursivement axiomatisable dans cet article, qui contiendra également une partie sur les liens entre complétude et décidabilité.[Fait]

Proz 26 avril 2006 à 22:19 (CEST)

L'article présent pointe sur l'article Diophantien qui semble précis et bien documenté, on peut donc réduire le paragraphe à ce sujet de l'article présent. En fait le paragraphe "Des exemples de systèmes incomplets et d'indécidables" est à restructurer. Le paragraphe "La relativité de l'indécidabilité des énoncés" également.

Par ailleurs la bibliographie est dans un grand désordre, et je doute qu'elle soit très utile. Il faudrait structurer, un peu dans le style de l'article de la version anglaise (qui est dans un meilleur état que celui-ci), je séparerais les livres de vulgarisation, des livres plus scientifiques, et/ou J'ajouterais des commentaires très courts, pour décrire le livre, essentiellement le public à qui il s'adresse. Mais je n'ai pas lu, et ne compte pas lire, tout ce qui est cité actuellement ... j'espère des indications. [Fait partiellement] Proz 27 avril 2006 à 20:45 (CEST)

Ajout d'un paragraphe sur "vérité et démontrabilité" [Fait].

Je commence aussi de restructurer la suite : "La relativité de l'indécidabilité des énoncés", suppression à terme de ce paragraphe, ce qui correspond au titre est déjà décrit plus précisément dans le paragraphe "conséquences directes du 1er th. de G.", il y a aussi des choses dans "vérité et démontrabilité".[Fait]

  • Goodstein à recaser (dans un paragraphe "énoncés indécidables de l'arithmétique" ?)[Fait]
  • preuves de cohérence : on peut en parler brièvement dans le paragraphe sur le formalisme qui est à reprendre également, voir la partie sur le programme de Hilbert dans fondements des mathématiques.[Fait]

On peut dire un mot sur la preuve de cohérence sémantique dans le paragraphe sur "vérité et démontrabilité", dans le sens communément admis : c'est une trivialité, c'est une preuve de cohérence relativement à une théorie au moins aussi forte en le sens le plus naïf (contient l'arithmétique), plus forte par le 2nd Th. d'inc.

Suppression du paragraphe "TH. de G. en philo." prévue, si pas d'opposition (voir discussion précédente).[Fait]

Proz 4 mai 2006 à 20:25 (CEST)

J'ai, entre autres, restructuré le paragraphe sur "théorie incomplètes et énoncés indécidables", et supprimé à l'occasion le paragraphe sur la géométrie. Parler de l'axiome des parallèles à propos du théorème d'incomplétude est un peu tiré par les cheveux. Mais surtout ça ne semblait pas correct sur le plan historique. Voir les articles géométrie euclidienne, géométrie non euclidienne, axiomes de Hilbert et google : l'apport de Beltrami semble concerner la géométrie hyperbolique, le paragraphe décrivait un modèle de Riemann.

paragraphe créé "Théorèmes d'incomplétude et indécidabilité algorithmique" : à compléter [Fait] (renommé ... et calculabilité)

Proz 17 mai 2006 à 22:42 (CEST)

Restructuration du paragraphe "Une preuve partielle du premier théorème d'incomplétude": à poursuivre, fonction beta ... [Fait]

Considérations purement gratuites sur le "pythagoricisme" supprimées.

A faire (dans un autre paragraphe): citer le Th. de Löb [Fait, mais article à écrire].

Proz 26 mai 2006 à 02:01 (CEST)

A faire : ce qui était appelé "indécidable absolu" a disparu : donner la position de Hilbert ( / Ignorabimus)

Harmoniser et compléter le dernier paragraphe (2nd Th) [Fait] Proz 30 mai 2006 à 20:49 (CEST)

A faire : réordonner les paragraphes de l'article, en particulier, il faut parler plus tôt du programme de Hilbert, un peu plus d'aspects historiques (Von Neumann) [proposition sous le titre "Introduction à l'article", dans la suite].

Proz 19 juin 2006 à 22:52 (CEST)


[modifier] Bibliographie

Que contient (en rapport avec le sujet) ? Est-ce une référence à maintenir ?

  • Jean-Marc Alliot, Thomas Schiex, Pascal Brisset, Frédérik Garcia, Intelligence artificielle & informatique théorique - Cepadues, 2002 - ISBN 2854285786

Je déplace ici cette référence, qui est plus à sa place dans la discussion, que comme référence de l'article lui même, me semble-t-il

Références "Autres" à commenter. Proz 30 mai 2006 à 21:21 (CEST)

[modifier] Rapport avec :le théorème de complétude ?

Quelqu'un pourrait-il indiquer ici (ou dans l'article cousin "Théorème de complétude de Gödel", le rapport exact des deux théorèmes, c'est à dire indiquer ce qui relève de l'un ou de l'autre ? L'idéal serait que ce fût sous forme de tableau, afin de bien fixer les idées. D'avance merci à qui en aura le courage ! 81.64.199.181 8 juillet 2006 à 16:47 (CEST)

[modifier] Félicitation

J'ai étudié ce théorème à l'université, et je tiens à vous féliciter pour son explication claire et concise ;-) Ce qui permet à terme un décloisonnement des personnes.

Merci à tous. Bonne continuation.

[modifier] Lecture de Salle, questions posées à Proz, recopiées ici pour mémoire

Bonjour, l'article devant passer AdQ, en tant que contributeur en maths, j'ai tenté de ma lancer dans la lecture. Pour le moment, je n'ai lu que les deux premières parties, et je n'ai pas compris grand-chose, j'ai peur. Je ne sais pas si ça sera utile, mais j'essaie (et ça va forcément être flou, étant donné mon incoompétence avérée en logique) quand même d'expliquer ce qui me bloque, et peut-être pourras-tu en tirer quelque chose pour améliorer l'article ; sinon, tant pis ; et je m'excuse d'avance pour toutes les remarques débiles que je vais faire (plutôt qu'à chaque fois que je ne serai pas sûr de ne pâs dire n'importe quoi), ainsi que toutes celles se référant à des notions présentes ailleurs : j'ai juste jeté un coup d'œil aux liens.Salle 11 août 2006 à 19:28 (CEST)

Merci pour tes réponses et reformulations, cela me semble plus clair. Il reste deux ou trois points obscurs. Pour la suite de l'article, je n'ai pas le temps de le lire en ce moment, mais dès que je peux, j'essaie de m'y mettre.

[modifier] Partie I

[modifier] Conditions d'application

  • Il est dit qu'on se place dorénavant dans la logique classique, mais que le théorème reste vrai en logique intuitionniste. Or, il est fait usage constant de raisonnement par l'absurde ; si j'ai compris la page sur logique intuitionniste (mais il y a des notations fractionnaires bizarres qui me troublent), on n'y a pas droit. Le problème est-il délicat à surmonter? QUi l'a fait? Gödel lui-même?
Les démonstrations des deux théorèmes n'utilisent pas le raisonnement par l'absurde. Donc il n'y a rien à faire. La suite utilise parfois le raisonnement par l'absurde pour des conséquences des théorèmes, pas pour les preuves. Ce qui m'inquiète, c'est que l'article donne l'impression de faire un usage constant du raisonnement par l'absurde : peux-tu expliquer ? Par ailleurs il est commode de se placer en logique classique pour la notion de modèle et de vérité dans un modèle.
Je répète que ma lecture de l'article s'est limitée pour le moment au deux premières parties. Ta réponse réduit il est vrai mon objection : faire du raisonnement par l'absurde pour les conséquences, c'est OK. Cependant, par curiosité, j'ai regardé les premières lignes de la preuve du théorème 1. A vue de nez, Il est vrai dans N, car s'il était faux, il serait prouvable. Or cet énoncé est de complexité logique suffisamment simple pour que sa prouvabilité dans une théorie cohérente capable de coder l'arithmétique entraîne sa vérité dans N (on n'a pas besoin de supposer que N est modèle de la théorie). Il est donc vrai dans N. ressemble à du raisonnement par l'absurde, mais je ne suis pas bien sûr.Salle 12 août 2006 à 08:24 (CEST)
Effectivement l'article utilise la notion de vérité dans un modèle qui est classique, et tel que rédigé le raisonnement que tu soulignes est bien un raisonnement par l'absurde (tiers-exclu, soit vrai, soit faux). Tu as raison. Mais il s'agit de montrer qu'un énoncé n'est pas prouvable : il n'existe pas d'entier qui code une preuve de l'énoncé. Pour un tel énoncé négatif, les intuitionnistes acceptent ce qu'un mathématicien appelle habituellement raisonnement par l'absurde ("introduction de la négation" en jargon théorie de la démonstration). On pourrait reformuler le raisonnement directement, sans parler de vérité. Mais je n'ai pas du tout cherché à être intuitionniste, et je m'aperçois qu'effectivement je ne le suis pas. Par ailleurs même si la preuve n'était pas intuitionniste (mais elle l'est ou peut l'être), le résultat reste forcément valide pour la prouvabilité intuitionniste, qui est moins forte que la prouvabilité classique. J'ajoute une note à ce sujet dans l'article.
Ca me va.
  • Les axiomes de Peano conviennent. Je comprends : les axiomes de Peano constituent une théorie qui vérifie les hypothèses du théorèmes. Est-ce bien ça? Si oui, ne faudrait-il pas plutôt le dire ainsi?
ok, je vais reformuler.
Ok

[modifier] Csqces du premier théorème

  • Là est démontrée une pté importante : dans la théorie T une pté G est démontrable si et seulement si T et nonG est contradictoire. L'implication directe me convient ; en revanche, je ne comprends pas l'implication réciproque j'essaie de reconstituer : supposons T et non G contradictoire. Par déf, cela signifie que G est vraie dans (T et nonG) ; donc G est vraie dans T ; donc G est démontrable dans T. Des deux donc, le premier me semble acceptable même si je serais incapable de le démontrer, n'étant pas logicien. En revanche, le deuxième me semble confondre vérité et démontrabilité, ce que la partie II nous enjoint à ne pas faire. Quid?
Il n'y a pas à parler de vérité. C'est de la démonstration, et c'est à peu près le raisonnement par l'absurde usuel en math, mais sous une forme tellement abstraite, qu'on ne le reconnait pas je suppose. Je rerédige dans l'article, en tentant d'être plus clair.
Là, je ne comprends pas ; j'essaie de dire plus loin.
  • Le théorème de Gödel est reformulé en utilisant cette pté ; mais il l'est deux fois (avant et après la démo de ladite pté), et ça ne facilite pas la lecture.
En fait après la preuve, ça n'est pas exactement une reformulation, et ça permet d'enchaîner avec la suite. J'ajoute un mot avant pour expliquer la suite, rien de mieux ne me vient rapidement à l'esprit pour le moment. N'hésite pas à modifier si tu vois mieux.
A la relecture, ça ne me pose plus de problème ; donc, ça va.
  • Pour la dernière remarque de ce chapitre (en gros : l'énoncé indécidable obtenu est exprimable dans le langage de l'arithmétique ; et c'est de plus un énoncé assez simple) : il n'est pas clair si cette précision sur le théorème esst une trivialité qu'on devrait savoir faire seul, ou si c'est dur.
ce n'est pas une trivialité. C'est parce que les codages sont arithmétiques. J'ai un peu modifié la formulation dans l'article. D'autre part logiquement assez simple ne signifie pas vraiment simple, je précise également.
Ca me paraît plus clair.
  • Bonjour. En relisant la démonstration, et bien qu'il soit mentionné que l'on présume que la théorie T considérée dans le contexte satisfait les hypothèses « utiles », il ne me semblerait pas inutile d'expliciter une propriété-clé de T impliquée dans la déduction ici : la cohérence. Actuellement, on peut lire que : « T augmentée de non G est contradictoire » conduit à « non G est source de contradiction dans T » ; cela est valide bien entendu dans l'hypothèse implicite que T est non contradictoire — autrement, on ne pourrait pas, à mon sens, conclure (décider) sur la source contradictoire (non G ? S une sous-théorie de T ?). Merci pour votre avis sur la pertinence de l'explicitation proposée. --nha de Lyon 26 janvier 2007 à 00:10 (CET)
Ta formulation « non G est source de contradiction dans T » est trompeuse. Pense que T est l'arithmétique de Peano, tu fais ce genre de raisonnement sans invoquer la cohérence de l'arithmétique. "T+non G contradictoire" signifie de "T+non G on déduit l'absurde", ce qui est quasiment pareil que "dans T de non G on déduit l'absurde" (quand on formalise la preuve, ça dépend du choix du formalisme, mais c'est en général complètement évident). C'est du même ordre que (A et B) => Absurde équivaut à A => (B => Absurde), pour donner une idée (mais attention : T peut être infinie). On a besoin que ce soit non G pour la suite bien-sûr, mais ce bout de raisonnement serait tout aussi valide en prenant à la place une formule de T. La cohérence de T n'est pas nécessaire pour ce raisonnement. Ca marche très bien si T est incohérente (mais ça n'a pas grande signification puisqu'alors T démontre n'importe quoi). Par contre G indécidable dans T n'est pas possible si T incohérente. C'est là qu'a déjà servi l'hypothèse de cohérence, pour le résultat que l'on cherche à démontrer. J'avais pensé à mettre un avertissement pour dire que ces démonstrations sont effectivement très simples mais non usuelles, et, par expérience, il n'est pas si simple de se rendre compte qu'elles le sont ! Ceci dit je ne dis pas qu'il n'y a pas moyen de mieux expliquer. Proz 26 janvier 2007 à 01:37 (CET)

[modifier] Csqces du second théorème

  • Dans la petite pruve, il y a une utilisation de la pté du parag précédent, non? Peut-être le dire explicitement faciliterait la lecture.
c'est ce que j'entendais par "d'après ce qui précède", je précise.
D'accord
  • Pourquoi la preuve est-elle qualifiée d'esquisse? Elle m'a semblé complète.
Il y a du codage. L'énoncé non coh(T) , c'est "il existe un entier qui code une preuve de l'absurde dans T". De même dans T' . Donc " non cohT a pour conséquence non cohT' " demande de fait un peut d'arithmétique, même si c'est intuitivement tellement évident que personne ne prendra la peine d'en dire plus. J'ai reformulé pour que ce soit plus clair.
D'accord.
  • En revanche, le résultat une théorie qui démontre un énoncé exprimant qu'elle n'est pas cohérente, peut très bien ne pas être contradictoire, comme on le déduit du second théorème d'incomplétude lui-même ! est super choquant aux yeux du profane que je suis, infiniment plus que les théorèmes dans leur forme courante. J'imagine qu'étant conséquence immédiate des théorèmes eux-mêmes, il n'a pas fait l'objet de suite particulière ; mais peut-on quand même trouver un exemple, le plus accessible possible, où ce genre de phénomène se produit réellement? Ou dire au moins où on ne risque pas de le rencontrer? Ou, au contraire, si on est susceptible de le rencontrer n'importe où? En gros, j'ai du mal à le croire sans le voir.
L'exemple est quasiment donné : Peano+non coh(Peano). fort heureusement c'est pathologique. Je précise dans l'article.
Précisions rassurantes.

[modifier] Partie II

  • Je ne comprends pas très bien l'enchaînement entre les deux assertions en gras ; d'ailleurs, je crois que je ne comprends pas la deuxième assertion :T est une théorie récursivement axiomatisable qui permet de formaliser "suffisamment d'arithmétique", et dont tous les axiomes sont vrais dans N Que signifie que les axiomes de T sont vrais dans N? Que ce sont des théorèmes de l'arithmétique classique? Mais dans ce cas, juste pour pouvoir exprimer, ces axiomes/théorèmes, il faut déjà disposer d'une construction de l'arithmétique, non? Ca ne doit pas être ça, car on demande ensuite à T, précisément de fonder l'arithmétique. De mon point de vue de profane, on est en train de parler d'une théorie qui doit fonder l'arithmétique, mais qui s'exprime dans, ou au moyen de, l'arithmétique. C'est troublant, et une explication pourrait être éclairante.
J'essayerai (plus tard) de trouver qqchose. La vérité dans N, c'est ce que j'essaye d'expliquer ensuite. Je propose de revenir sur ce point après avoir répondu à "sur la notion de vérité, plus en détail". Quand j'essaye de préciser, ça introduit des redondances. Par ailleurs, la vérité dans N se définit, disons en théorie des ensembles. Il n'est pas question de fondation. Il n'y a pas de raison de se restreindre mathématiquement pour étudier les théories arithmétiques.
Je ne vois pas précisément de qelles théories on parle ; je suis assez convaincu que l'axiomatique de Peano rentre là-dedans ; mais par exemple la théorie ZF? Elle modélise suffisamment d'arithmétique ; mais ses axiomes ne sont ni vrais ni faux dans N? Qu'en fait-on? L'impression que j'ai c'est qu'on est en train de parler d'une théorie qui en définitive modélise l'arithmétique, et rien d'autre (et qui a le bon goût de ne pas introduire d'énoncé faux, mais c'est la moindre des choses). Si tu arrives à voir ce qui bloque, je serai content.
Il y a effectivement une précision à apporter, vis à vis des énoncés du début. Là je suis passé sans le dire dans le langage de l'arithmétique. Pour ZF il faudrait parler des énoncés arithmétiques conséquences de ZF et vrais. Mais je préfère restreindre le langage pour simplifier. Je précise dans l'article.
  • Pour l'enchaînement que je ne comprends pas, je pense qu'il s'éclairera tout seul si je sais de quoi on parle.
j'ai ajouté un mot dont je ne suis pas sûr qu'il éclaire.
Ca me paraît clair.
  • Une parenthèse contient deux remarques : il s'applique à moins de théories, on ne peut le formaliser dans l'arithmétique, pour en déduire le second théorème d'incomplétude.. J'ai réussi à me convaincre de la première tout seul, en revanche pas de la deuxième. On pourrait dire, pour ce genre de remarques, soit c'est facile, pour le lecteur, soit c'est un nouveau théorème que je ne vous démontre pas. Enfin, trouver un moyen que les trucs triviaux et les trucs difficiles ne soient pas mis sur un même plan.
ok, c'est le th. de Tarski. Je mettrai une note. [fait]
Très bien
  • on pourra ne supposer que la vérité dans N des théorèmes de cette complexité logique, et on obtiendra un théorème équivalent au premier théorème d'incomplétude tel que démontré par Gödel. Pour moi, cela signifie qu'en prenant la théorie précédente à laquelle on ajoute comme axiomes tous les théorèmes de cette complexité logique, et en réécrivant le théorème de type 1 pour toutes ces théories, on a évidemment un énoncé plus fort (au sens large) que celui mis en gras ici ; évidemment moins fort (au sens large) que Gödel ; et, non évidemment, aussi fort que Gödel. Si c'est ça, je pense que cela pourrait être reformulé de façon plus explicite ; et qu'on pourrait dire pourquoi l'assertion non évidente est vraie, ou sur quoi repose la démo (c'est peut-être la fonction de la parenthèse, dont je n'arrive pas à voir précisément la fonction, justement).
c'est la fin de l'article, je mettrai un lien.
en fait l'indication y est déjà. Je reformule un peu le tout. On pourrait aussi remplacer le paragraphe, par un renvoi à la fin de l'article sans tenter d'explication.
Le bout d'explication me paraît intéressant, et rassurant, donc pas à enlever. Ce sur quoi je veux insister, c'est en fait le on peut supposer (...), que je comprends comme : on considère une théorie qui a au moins comme axiomes (...). Le problème du terme supposer, c'est qu'il peut vouloir dire, on fait une hypothèse, ou on choisit un axiome, ce qui n'est pas tout à fait la même chose ; il me semble que c'est ce second sens ici, et qu'une reformulation pourrait éviter l'éventuelle ambiguïté et rendre les choses plus claires.
reformulation dans l'article : j'espère que c'est plus clair. si je trouve mieux je reformulerai (On choisit les axiomes de façon à satisfaire l'hypothèse si la théorie est cohérente).
  • Voilà comment je comprends la fin de cette partie : on fait quelques considérations (que je ne cerne pas bien) historiques et épistémologiques sur la notion de vérité, plus la déf de la vérité dans N. Je ne vois pas ce que ce développement apporte à la compréhension de l'article (mais comme je n'ai pas lu la suite...). S'il est superflu, peut-être en faire un article lié?
il n'est pas superflu : l'article utilise la vérité dans N. Les reformulations du 1er th. de Gödel en terme de vérité (du genre "il existe une formule vraies non démontrable") sont courantes. Sans en parler on comprend mal la dissymétrie dans l'indécidabilité, et le théorème lui-même (Gödel n'a pas, je crois, parlé de vérité, mais l'avait en tête, d'après des lettres ultérieures). Je souhaiterais que ce § permette, entre autre, de comprendre ce qu'est la vérité dans N.
Je réponds plus loin.
Je corrigerai la seconde partie selon les remarques ci-dessus [fait].

[modifier] Sur la notion de vérité, plus en détail

  • La notation bien connue avec les petits bâtons, ça m'a longtemps troublé... Peut-être faire mieux ressortir le terme unaire, et abandonner ces remarques seraient plus productif.
j'espérai que ce serait plus clair. Pour moi il s'agit de faire comprendre que la syntaxe ne fait que refléter l'idée très intuitive d'entier, que l'on utilise, par exemple quand on compte des votes avec des bâtonnets. je pense que je me suis mal exprimé, s'il faut abandonner, j'abandonnerai, mais avant peux-tu expliquer ce qui trouble ?
C'est peut-être juste le fait de passer de but en blanc de considérations sur des formules atomiques closes à une remarque, assez naïve sur un système de numération. Je ne sais pas trop quel lecteur n'ayant pas au moins une idée de ce qu'est un système de numération arrivera ici, et donc je ne vois pas trop le public pour cette remarque.
ok, je supprime (bien que pas tout à fait sûr qu'il soit si clair que ça que pour quiconque en arrive là, sss0, et ||| c'est "pareil").
  • On utilise le terme polynôme. Est-ce dans le sens mathématique courant? Si oui, il faudrait un lien, je pense.
ok;, lien + précision ajoutés
Ok
  • Le terme formule atomique close. Close est expliqué, mais pas atomique, il n'y a pas non plus de lien, donc je n'ai pas compris ; je pense que cela doit se ramener aux formules du type (avec notations habituelles) 2=2, 2=3, 1<4 et 4<2, et tout ça...
j'ajoute une explication et un lien. les formules atomiques que tu écris sont closes. On a aussi x + yz = 1+ 2x etc.
Lien utile.
  • J'ai l'impression qu'il y a équivalence entre sans quantificateur et sans variable ; si c'est le cas, il faudrait le dire.
non ce n'est pas équivalent.
Pareil avec le lien précédent ; ne faudrait-il pas dire qu'une formule close, c'est sans variable libre?
pour les formules atomiques toutes les variables sont libres ; ça m'a semblé plus simple de ne pas préciser.
  • je ne suis pas sûr que le paragraphe où on parle du quantificateur universel ne pourrait pas être mieux rédigé ; peut-être rajouter, un a priori dans cela demande une infinit" de varififcations ; et préciser Les énoncés universels qu'on parvient à démontrer le sont souvent au moyen d'une récurrence, à la place de la phrase actuelle qui pourrait laisser l'impression que tous ces énoncés peuvent être démontrés, et que le habituellement ne porte que sur le mode de démo utilisé.
ok, c'est justement ce que je voulais dire par la phrase relevée ensuite, qui n'a pas l'air claire. Je reformule.
Ok
  • Je ne comprends pas ce que cette phrase  : Au passage on a perdu quelque chose, comme l'énonce précisément le théorème de Gödel. signifie ; elle pourrait être explicitée.
reformulé
Je crois que de toutes les modifs, c'était la plus nécessaire. Bien plus clair comme ça.
  • au sens informel de cette notion, je pense que ça porte sur preuve. Je pense que ça fait référence à la notion de preuve formelle telle qu'expliquée en méthode formelle (informatique). Si c'est ça, il faudrait un lien, ou même supprimer l'incise, car je pense que pour la majorité des gens, preuve ne signifie pas a priori preuve formelle.
j'ai exprimé les choses autrement, le vocabulaire était probablement mal choisi.
Pour cette remarque et la suivante, c'est Ok.
  • Dans les cas abordés ci-dessus, ces preuves sont effectivement formalisables dans les théories pour lesquelles on démontre les théorèmes de Gödel. Encore une fois, on part sur quelque chose d'assez éloigné des considérations initiales, pour ce que j'en comprends. J'imagine encore que formalisable est employé dans le sens précédent. Et ça soulève plus de questions queça n'en résout, j'ai l'impression : une peurve formalisable, j'imagine que c'est encore plus dur à avoir qu'une preuve tout court? Est-ce que c'est la même chose que d'avoir un moyen mécanique de décider la vérité? Où est-ce que ça se situe par rapport à intuitionnisme/logique classique?
idem
remarque : une preuve formelle : c'est la vérification du fait que c'est une preuve qui est mécanique, pas la recherche qui correspond au "moyen mécanique de décider la vérité". Ce serait une preuve au sens mathématique usuel où l'on aurait absolument tout explicité.

[modifier] Vérité et démonstrabilité

Les remarques pour lesquelles j'ai renvoyé ici sont toutes liées à ce point. Quelle différence entre vérité et démontrabilité? J'en suis là, surtout après cette phrase : L'énoncé de Gödel, qui est vrai et non démontrable est justement un énoncé universel, appellons le ∀ x H(x). Prenons le cas de l'arithmétique de Peano. Quand on définit précisément l'énoncé, on montre que pour chaque entier n, H(n) est prouvable dans l'arithmétique de Peano. Mais on ne peut pas démontrer ∀ x H(x). : tout énoncé clos dans une théorie (satisfaisant les hypothèses utiles?) a une valeur de vérité. Parmi les énoncés vrais, certains ne sont pas démontrables. Car en fait, dans une démonstration, on ne peut faire qu'un nombre fini d'étapes, et même si la récurrence permet de pallier ce problème pour certaines classes d'énoncés, il y en a certains où elle échoue ; le théorème de Gödel exhibe ces énoncés H(n), qui sont démontrables et donc vrais ; donc, par définition ∀ x H(x) est vrai ; en revanche (pour des raisons de complexité logique, je crois?) il n'est pas démontrable.

H(n) est vraie et donc démontrable pour des raisons de complexité logique, mais je ne pense pas qu'il faille préciser à cet endroit. Pour ∀ x H(x) n'est pas démontrable, il faut le bon énoncé et il y a une preuve à faire. Là j'essaye d'expliquer ce qui fait que le th. de Gödel peut être vrai, je ne donne aucune idée de la démonstration.

Mais ceci reste obscur :Étant donné un énoncé G, notons non G sa négation. On montre facilement qu'un énoncé G n'est pas démontrable dans T si et seulement si la théorie T + non G (la théorie T à laquelle on ajoute l'axiome non G) est cohérente. En effet, si G est démontrable dans T, T + non G est évidemment contradictoire. Réciproquement, supposons T + non G contradictoire. Cela signifie que, dans la théorie T, on peut déduire de non G une contradiction. On en déduit que G est conséquence de T (c'est un raisonnement par l'absurde).. Pour la dernière phrase, je la comprends par G est démontrable dans T, parce que c'est ce qu'on voulait obtenir. Maintenant, voilà mon problème : je considère deux classes d'énoncés dans T : celle des démontrables et celle des vrais, la première étant incluse dans la seconde, et même strictement. Le problème, c'est que si je prends dans cet exemple G=(∀ x H(x)) de tout à l'heure, ben G est vrai dans T, donc G+non T est contradictoire, et donc On en déduit que G est conséquence de T ? donc que G est démontrable dans T, Ce qui n'est pas le cas.

Vrai dans une théorie n'a pas de sens. C'est vrai dans un modèle : ici toujours N. Ce sont les axiomes de la théorie, qui peuvent être vrais dans N, et dans ce cas tous les théorèmes le sont. Pour l'énoncé de Gödel pour T, justement T+non G n'est pas contradictoire, mais n'a pas N pour modèle (bien que vérifiant la récurrence, si T est Peano, ce qui peut être contre-intuitif). N'étant pas contradictoire cette théorie a quand même des modèles (non-standards). Je pense que ton problème c'est en partie que tu interprètes "contradiction" en terme de vérité. Mais c'est juste une proposition absurde, disons la conjonction d'une proposition et de sa négation, ou 0=1 dans l'arithmétique de Peano. Dire que Peano+non G est contradictoire, c'est dire que l'on démontre 0=1 dans Peano+non G. J'ai précisé dans l'article. Je ne sais pas si c'est suffisant.
Non, ce n'est pas très convaincant. Tu dis juste ce qu'est une contradiction sur un exemple, et le problème n'était pas là. J'ai enlevé, ça me paraissait d'un niveau un peu trop inégal à ce qu'il y a avant et après. Je pense que ta première phrase (Vrai dans une théorie n'a pas de sens.) m'a éclairé, et je propose une réorganisation de la section en conséquence sur cette page.Salle 20 août 2006 à 14:47 (CEST)


Excusez-moi de m'immiscer dans votre discussion. Je voudrais distinguer trois concepts : validité (satisfaction dans tout modèle), démontrabilité et vérité (un concept philosophique, très important, approché par les deux autres). On notera que j'introduis un quatrième concept la satisfaction et que seuls les deux premiers concepts sont mathématiques. Personnellement, je commençais mon cours d'introduction à la logique par l'explication de ces concepts avant d'attaquer le corps du débat. En conséquence, j'appellerais validité ce que vous appelez vérité. Pierre de Lyon 28 août 2006 à 08:43 (CEST)
Je suis bien-sûr d'accord pour la distinction entre ces 4 concepts. Dans l'article, vérité fait le plus souvent référence à "satisfaction dans le modèle standard de l'arithmétique". C'est assez usuel quand on parle du th. de Gödel (une formule vraie mais non démontrable). Le but du § est de faire comprendre dans le cas particulier de l'arithmétique la différence entre "vraie dans N (au sens de Tarski) et démontrable disons dans Peano. Ca me semble un exemple où les choses sont particulièrement claires, et il ne faudrait pas que le § devienne un "cours d'introduction à la logique" en général. Je souhaiterais, que la majeure partie de l'article soit lisible par un mathématicien non-logicien. Je me suis laissé aller récemment à parler de modèle non standard, et c'est peut-être déjà faire trop de logique. Je suis d'accord que "vérité" est un terme très chargé, j'avais pris d'ailleurs quelques précautions à ce sujet dans une version antérieure, mais la phrase a récemment disparu lors de remaniements. J'aurai tendance à garder tout de même vérité, qui est quand même aussi utilisé dans ce sens, qui me semble plus parlant que validité et satisfaction, et qui est plus en phase avec les énoncés plus ou moins vulgarisés du th. de Gödel que l'on peut rencontrer. Je propose plutôt une phrase expliquant que la vérité Tarskienne n'est qu'une définition mathématique, pas "la" vérité (dit autrement bien-sûr). Proz 28 août 2006 à 10:54 (CEST)
Je propose plutôt une phrase expliquant que la vérité Tarskienne n'est qu'une définition mathématique, pas "la" vérité (dit autrement bien-sûr). D'accord, mais en gardant à l'ersprit ce que Jean-Yves Girard fait dire à Gödel répondant à Monsieur Homais (in Le théorème de Gödel ou une soirée avec M. Homais, Sciences et Avenir, Janvier 2000 ) « la principale force du tarskisme c'est sa platitude ».
Ah oui, c'est moi qui avais râlé contre les précautions prises initialement par Proz sur le terme vérité. Disons que je ne vois pas ce que ça vient faire là. Il me semble clair que cet article parle de maths et pas de philo, et dire que le terme vérité prend d'autres sens ailleurs ne me paraît pas nécessaire. Un peu comme si à chaque fois qu'on dit corps, il fallait préciser <<Attention, en médecine, ça a un sens différent.>>.Salle 28 août 2006 à 11:41 (CEST)
Je défends faiblement le point de vue de Pierre de Lyon sur le remplacement systématique de «vrai» par «valide», tout en soulignant que le mot «vrai» est couramment utilisé par les mathématiciens comme un synonyme de «valide». Je pense comme lui que l'usage de ce mot est un peu trompeur. Néanmoins je ne me battrai pas comme un chiffonier, priorité à l'avis de celui qui a travaillé sur l'article et lui a donné sa cohérence ! Cela étant et pour dire du bien plutôt que du mal, le plan choisi (une partie 1 qui ignore complètement la théorie des modèles suivi d'une partie 2 centrée sur celle-ci) est très judicieux -- les sources confuses sont typiquement celles qui font des allers-retours permanents entre les deux points de vue. Touriste * (Discuter) 28 août 2006 à 12:08 (CEST)
Oui, mais valide dans N ça ne se dit pas trop, il faudrait dire plutôt satisfait dans N. L'usage de "vrai" ou "faux" sans préciser (j'ai essayé d'éviter tant que ce peut, mais il en traîne forcément, et de toute façon c'est courant dans ce contexte) fait clairement référence au fait qu'il y a un modèle standard, et que c'est vrai dans ce modèle. Le remplacement ne peut être aussi simple, et ça n'améliorera pas la lisibilité de mon point de vue. Proz 28 août 2006 à 12:26 (CEST)
Surtout il ne faut pas rentrer dans les débats entre logiciens sur Tarski, et la vérité tarskienne. Mathématiquement son efficacité, par exemple en théorie des ensembles pour ne pas prendre la théorie des modèles, ne fait aucun doute. Je pense quand même rétablir les "précautions", qu'on le veuille ou non un article sur le th. de Gödel doit affronter ce genre de problèmes, plus qu'un article sur la théorie des corps. Proz 28 août 2006 à 12:11 (CEST)
Bon, je n'ai pas d'argument contre ; j'imagine que c'est mon goût personnel qui est trop personnel sur ce coup.Salle 28 août 2006 à 12:19 (CEST)


Comme Touriste et j'ai un point de vue globalement positif sur l'article. je suis d'accord avec le plan. Je reviens sur ce que que dit Salle à savoir (je paraphrase) que les mathématiciens n'ont rien à faire de concepts des philosophes, erreur suivant que vous êtes plantonicien ou réaliste, les objets existeront ou n'existeront pas (je simplifie) et la vérité qui leur est attachée aura tel sens ou tel autre. En revanche, la validité sera la même (du moins je l'espère) pour tout le monde. Pierre de Lyon 28 août 2006 à 12:22 (CEST)
Ah non! Je n'ai pas du tout dit ça, même avec la précaution paraphrase. J'ai juste dit que c'était une autre question.Salle 28 août 2006 à 12:27 (CEST)
J'ai rétabli sans trop le modifier un texte précédent dans l'introduction de la partie "vérité et démontrabilité". Je ne suis pas sûr que ça réponde suffisamment aux critiques émises. Proz 28 août 2006 à 13:03 (CEST)


Je ne suis pas sûr d'avoir bien compris la phrase «  on sait le prouver dans une théorie plus forte que celle de départ ». Ou plus précisément, je devrais dire que je pense qu'elle est ambigüe. Il faut me semble-t-il dire qu'elle est plus « forte » au point de vue de sa puissance logique (induction au delà d'ε0) mais pas parce qu'on y a ajouté des axiomes qui font que l'on peut maintenant démontrer un théorème que l'on ne pouvait pas auparavant. Pierre de Lyon 28 août 2006 à 13:09 (CEST)
Je ne fais pas référence forcément à la preuve de Gentzen. Je pensais plutôt d'ailleurs à une preuve de cohérence en théorie des ensembles ou plus précisément en logique du second ordre, en donnant le modèle, puisque l'on parle de sémantique. Passer à la logique du second ordre, ce n'est pas exactement ajouter des axiomes mais pas loin. Pour la preuve de Gentzen, qui est bien plus instructive, c'est effectivement plus subtil qu'ajouter des axiomes, puisqu'il utilise un schéma de récurrence plus fort que celui de Peano, mais sur des formules de faible complexité. Donc cela revient bien me semble-t-il à ajouter, mais aussi à enlever des axiomes. On prouve des th. que l'on ne prouvait pas auparavant, mais on n'en prouve plus que l'on prouvait. D'accord pour l'ambiguïté : on utilise "plus fort" dans les deux sens, plus d'axiomes, et la phrase est quand même correcte, ou prouve la cohérence et la phrase devient tautologique. Je ne pense pas qu'il faille rentrer dans ce genre de subtilités dans cet article, en tout cas pas dans ce §. Enfin, exemple artificiel certes, Peano+coh(Peano) prouve la cohérence de Peano, donc ça marche bien en ajoutant des axiomes !
Ce que j'essaye de dire, en fait, et dont l'expression peut sûrement être amélioré, c'est quelquechose comme la vérité (tarskienne) dans N est une notion "idéale", que concrètement les mathématiciens approximent en choisissant (implicitement d'ailleurs) une théorie suffisamment puissante (dit comme ça c'est trop simplificateur mais c'est l'idée, je préfère le dire sur un exemple). Proz 28 août 2006 à 15:49 (CEST)
J'ai conscience que nous planons assez haut (du moins pour le lecteur lambda). Ce que je voulais mettre en évidence, c'était dans l'optique du lecteur lambda précisément qui dirait crûment (-: « Eh bien sûr, l'ami, si tu ajoutes les bons axiomes, tu vas pouvoir le prouver ton théorème! » Pierre de Lyon 28 août 2006 à 17:12 (CEST)

[modifier] Une remarque (qui est en même temps une question à haute voix)

C'est au sujet de : "la vérité dans le modèle standard de l'arithmétique, les entiers que «tout le monde connaît»" - En qualité de personne formée mathématiquement mais pas spécialiste en logique, j'ai plusieurs fois été intrigué par cette inévitable apparition des "entiers standard" dans la plupart des exposés sur ce genre de questions. Me trompè-je en croyant comprendre que ce qui est important chez eux ce n'est pas que «tout le monde les connaisse» mais surtout que ce soient les mêmes que ceux qui ont été utilisés en amont pour définir des concepts comme "cohérent", "récursivement axiomatisable" voire tout simplement "formule" ? Je ne suis pas assez expert pour exposer ça précisément, mais si je ne suis pas à côté de la plaque, je trouve que c'est clarificateur - ça intrigue vraiment de voir les entiers «les plus familiers» se mettre en trompeuse apparence à jouer un rôle particulier alors qu'ils sont en fait intevenus mais un peu cachés tout au long de la première partie. Touriste * (Discuter) 28 août 2006 à 12:41 (CEST)

C'est une remarque assez subtile. Je ne suis pas sûr de donner une réponse pertinente. Effectivement les entiers interviennent dès que l'on définit le langage. Dans un modèle non standard, les entiers non standards, on ne peut justement pas en parler dans le langage de la théorie, donc il n'est pas question de les utiliser pour les définitions des formules, de la cohérence etc. C'est effectivement indispensable que les notions de formule, preuve, etc. se codent par des entiers (forcément standards). Il est effectivement important que les prédicats "récursivement axiomatisable", "prouvable", etc. veuille bien dire, via les codages par les entiers, donc interprétés dans N, ce que l'on veut. Ceci dit tout ceci sera démontrable, donc vrai dans un modèle non-standard. La phrase "les entiers que «tout le monde connaît»" est très abusive, mais évite de donner des détails. On peut introduire une remarque dans le sens de ce que tu proposes. Proz 28 août 2006 à 13:48 (CEST)
Merci de ta réponse, inutile de mettre une remarque si personne ne se sent sûr. Il est aussi possible qu'il soit essentiel que le N qu'on utilise soit bien ordonné, et encore plus plausible qu'il y ait un peu des deux à la fois ; il faudrait lire pas à pas, vraiment très pas à pas, les démonstrations notamment dans les sections 6-1-2 et 6-1-3 pour se faire une opinion. Donc n'y touchons pas tant que nous ne sommes sûrs de rien, c'est certainement plus prudent. Touriste * (Discuter) 28 août 2006 à 13:56 (CEST)
Je ne proposais qu'une remarque sur le fait que la connaissance des entiers est déjà implicite. Sinon, à la réflexion, je pense que ce que tu dis corresponds au fait que, la vérité dans N est utilisé comme biais commode pour montrer que ce que l'on définit dans la théorie (prédicat de prouvabilité) correspond bien à la "vraie" prouvabilité, que le codage est fidèle finalement (on parle parfois de "réflexion" de la théorie dans elle-même). Il faudrait peut-être plus insister dans la partie codage. Proz 29 août 2006 à 21:40 (CEST)

[modifier] Conclusion provisoire

Je ne demande pas de réponse à mes questions une par une (ni ne les refuse, d'ailleurs). L'idée est juste que la perception d'un profane peut aider le rédacteur à voir où il peut clarifier son article. Je serai absent pendant plusieurs jours, donc je ne pourrai pas préciser tout de suite mes questions si tu le demandes. En revanche, après mon retour, je veux bien essayer de lire la suite, si certaines de mes remarques ont pu aider, et revenir sur celles qui auront été obscures. Merci.Salle 11 août 2006 à 21:29 (CEST)

cela m'intéresse que ce soit compréhensible par des non-spécialistes, donc ce sera avec plaisir. De toute façon, tout texte de ce genre devrait être relu. Par ailleurs ne faudrait-il pas reporter cette discussion dans la page de discussion de l'article ? Proz 14 août 2006 à 20:08 (CEST)
Aucun souci pour recopier en page de discussion de l'article. Je vais opérer. Encore quelques jours d'absence, et j'espère finir de lire. Merci.Salle 14 août 2006 à 23:06 (CEST)

[modifier] Introduction à l'article

J'ai écrit un brouillon pour une introduction : Utilisateur:Proz/Gödel. Bien-sûr la partie du présent article concernant le programme de Hilbert, qui est largement reprise dans cette intro, disparaitrait. Quelques modifications très cosmétiques seraient aussi nécessaires. C'est un peu long. Qu'en pensez-vous ? Proz 29 août 2006 à 21:22 (CEST)

J'ai fait quelques modifications cosmétiques. Pierre de Lyon 31 août 2006 à 13:14 (CEST)

ok, théorie arithmétique ne me gêne pas, mais bon. J'ai juste modérer par un conditionnel l'affirmation finale sur l'intuitionnisme. Je peux opérer la substitution, auf avis contraire. Proz 31 août 2006 à 18:10 (CEST)

Je peux me tromper, mais j'ai l'impression que toutes les allusions à l'intuitionnisme devraient être abandonnées : ce texte doit servir d'intro à l'article sur le théorème de Gödel, et j'ai l'impression que l'intuitionnisme n'a pas de lien direct avec ce théorème, le schéma étant le théorème de Gödel a un lien avec le programme de Hilbert, et ah oui, il y aussi un lien entre le programme de Hilbert et l'intuitionnisme ; pour moi, cela délaie l'information. En définitive, cette intro telle quelle me semblerait plus adaptée à un article Programme de Hilbert. Mais je peux me tromper.

Un autre détail : je ne suis pas convaincu par la formulation des théorèmes ; j'ai l'impression qu'il y a eu tentative d'explication avec les mains, mais qu'en définitive, c'est fait à moitié en langage simplifié, mais pas complètement : il faudrait trouver une vraie formulation en langage simplifié - je sais, c'est dur, et là, je n'ai pas d'idée.Salle 31 août 2006 à 18:20 (CEST)

Pour les allusions à l'intuitionnisme : ça explique le contexte de l'époque, et donne un éclairage sur le programme de Hilbert, mais bien-sûr le tout est à la limite du hors sujet. Un article annexe sur le programme de Hilbert serait probablement la solution (il faudrait alors un peu mieux expliquer d'ailleurs). C'est plus ou moins la raison pour laquelle j'hésite à l'incorporer comme introduction de l'article.
Pour la formulation des théorèmes, pas facile de simplifier sans tomber dans le contre-sens. J'ai trouvé par hasard sur le web cette citation de Ian Stewart que j'aime bien : "Godel showed that there are true statements in arithmetic that can never be proved, and that if anyone finds a proof that arithmetic is consistent, then it isn't!", mais pourtant c'est déjà limite. Peut-être faut-il aller quand même dans cette voie ? [réponse intercalée, je lis la suite] Proz 31 août 2006 à 18:45 (CEST)
Pour l'intuitionnisme, je suis bien conscient de cet avantage. Je dis juste que, pour moi, l'inconvénient (risque de confusion) dépasse l'avantage.Salle 31 août 2006 à 19:01 (CEST)
Grossièrement, le premier théorème énonce qu'une théorie suffisante pour faire de l'arithmétique est nécessairement incomplète, au sens où il existe forcément des énoncés qui ne sont pas démontrables et dont la négation n'est pas non plus démontrable : c'est-à-dire qu'il existe des énoncés sur lesquels on sait qu'on ne pourra jamais rien dire dans le cadre de cette théorie. Sous le même genre d'hypothèses sur les théories considérées, le second théorème affirme qu'il existe un énoncé exprimant la cohérence de la théorie - le fait qu'elle ne permette pas de démontrer tout et donc n'importe quoi - et que cet énoncé ne peut pas être démontré dans la théorie elle-même : il faudrait donc renoncer à ce qu'un discours mathématique ait une valeur de vérité universelle, puisqu'on ne peut même pas savoir s'il est cohérent. Outre les restrictions sur les théories envisagées dues aux hypothèses des théorème, il faut noter que ces deux renonciations (énoncés dont la vérité est inaccessible, cohérence du discours) sont seulement relatives, comme la suite de l'introduction l'indiquera.
Voilà, je tente une reformulation vraiment avec les mains. Je pense que c'est pas mal d'introduire dès maintenant les renoncements auxquels les théorèmes conduisent - avec la réserve d'usage (cf dernière phrase). J'y vais, donc si mon truc est mauvais, n'en tenez pas compte sans discussion, c'est juste un essai de profane.Salle 31 août 2006 à 18:38 (CEST)

C'est pas mal, mais sur la cohérence, ça ne me semble pas tout à fait exact. Je reformule de façon plus interrogative :

Grossièrement, le premier théorème énonce qu'une théorie suffisante pour faire de l'arithmétique est nécessairement incomplète, au sens où il existe forcément des énoncés qui ne sont pas démontrables et dont la négation n'est pas non plus démontrable : c'est-à-dire qu'il existe des énoncés sur lesquels on sait qu'on ne pourra jamais rien dire dans le cadre de cette théorie. Sous le même genre d'hypothèses sur les théories considérées, le second théorème affirme qu'il existe un énoncé exprimant la cohérence de la théorie - le fait qu'elle ne permette pas de démontrer tout et donc n'importe quoi - et que cet énoncé ne peut pas être démontré dans la théorie elle-même. A cause des hypothèses des théorèmes, toute théorie qui prétend formaliser l'ensemble des mathématiques, comme la théorie des ensembles, est concernée. Faut-il pour autant renoncer à ce qu'un discours mathématique ait une valeur de vérité universelle ? Sur quoi se fonder pour savoir s'il est cohérent, puisqu'il semble que l'on ne puisse y arriver par des moyens purement internes aux mathématiques ? Les théorèmes de Gödel ne donnent pas de réponse mais permettent d'écarter celles qui sont trop simples. Il faut déjà noter que ces deux limitations (énoncés dont la vérité est inaccessible, cohérence du discours) sont seulement relatives, comme la suite de l'article l'indiquera.

Proz 31 août 2006 à 19:06 (CEST)

[modifier] Autre proposition pour l'introduction

Je propose de reprendre le paragraphe de Salle, que j'ai un peu modifié, de le faire suivre du second paragraphe (plus historique) du chapeau de l'introduction que je proposais, de créer un article "ébauche" sur le programme de Hilbert en recopiant le contenu du brouillon d'introduction, de placer un pointeur dans le présent article du genre : pour mieux comprendre le contexte historique voir ... à propos des preuves de cohérence voir ... (pour le moment le même article, mais ça pourrait changer).

J'éliminerais alors tout ce qui concerne le programme de Hilbert et les preuves de cohérence du présent article.

Ca donnera quelquechose d'améliorable (par d'autres éventuellement ;)), mais ça fera une intro à peu près honnête, me semble-t-il ? Proz 31 août 2006 à 19:24 (CEST)

Ca me va!Salle 31 août 2006 à 19:45 (CEST)

J'ai procédé, c'est effectivement mieux que ce que je proposais. Proz 31 août 2006 à 21:58 (CEST)

[modifier] Proposition d'article de qualité refusée le 2 septembre 2006

Cet article a été proposé comme article de qualité mais a été rejeté car ne satisfaisait pas les critères de sélection dans sa version du 2 septembre 2006 (historique).
Si vous désirez reprendre l'article pour l'améliorer, vous trouverez les remarques que firent les wikipédiens dans la page de vote.

Quelques remarques, ou pointeurs, au sujet de certaines critiques de ce vote, et pour éviter de lancer sur de fausses pistes ceux qui souhaiteraient améliorer l'article.

  • une introduction, dont l'absence est déplorée pas de nombreux intervenants, est déjà présente dans la version du 2 septembre (ajoutée le 1er), voir discussion ci-dessus.
  • Sur "l'utilisation abusive du th. de Gödel", voir aussi la discussion ci-dessus, sous le titre "Dieu ?".
  • Il ya un parti-pris dans l'article, sûrement discutable, qui est d'expliquer comment déduire le 1er théorème de Gödel, du théorème de Matiiassevitch, plutôt que de l'indécidabilité du problème de l'arrêt, via un codage par les formules ∑1. J'ai pensé que l'énoncé du théorème de Matiiassevitch était plus simple à comprendre pour un non spécialiste (ça évite de parler de ∑1 et donc de formule), même si la démonstration du th. de Matiiassevitch lui même, qui n'est pas abordée, est bien plus difficile (rmq : le théorème de Gödel est démontré ainsi dans un livre sur le sujet de Yuri Manin). J'ai ajouté une note dans à la partie "codage" expliquant comment déduire le th. de Gödel de l'indécidabilité du pb de l'arrêt. Je pense que ça répond à la critique sur "déduire le 1er th. du th. de Rice".
  • Usage du mot "vérité" : voir aussi discussion sur cette page à la fin de "vérité et démontrabilité".
  • enfin je signale que je n'ai pas de témoignage d'une relecture scrupuleuse de l'article à partir de la partie 4.

Proz 2 septembre 2006 à 22:11 (CEST)

[modifier] typographie

[déplacé ici pour éviter les confusions]

J'ai commencé le travail de correction typographique, qui pourrait à mon avis améliorer grandement la lisibilité de l'article. N'hésitez pas à continuer, car ce travail risque de prendre un certain temps si je m'y attèle seul ! Grob / ? 31 déc 2006 à 13:08 (CET)

Je suis désolé de dire ça, car ça représente sûrement du temps passé si c'est fait à "à la main", mais franchement, je ne crois pas que de changer le gras typographique en gras "tableau noir" améliore la lisibilité. De plus, les lettres deviennent des images (tant qu'il n'y en a qu'une isolée comme ce que tu as fait ça va). Il y a à certe à améliorer, systématiser la typographie des notations mathématiques par ex. (italique pour les variables ...), mais je ne pense pas qu'il faille passer en TeX, ça peut être lourd à charger à la fin, d'autant que l'article est long. (Par ailleurs là on s'intercale dans une vieille discussion sur une version antérieure de l'article, je propose de reporter l'ensemble du dialogue à la fin, quand tu auras lu ceci). Proz 31 décembre 2006 à 13:52 (CET)
Je pense qu'il faut laisser Proz jouer le rôle de chef d'orchestre, car il s'est pas mal investi dans l'article et le connait bien. En ce qui me concerne, je pense qu'il faut encore travailler sur le fond avant d'attaquer la forme. Et si nous décidons d'attaquer la forme, faisons le de façon concertée en se donnant des objectifs acceptés par tous. Pierre de Lyon 31 décembre 2006 à 16:41 (CET)
merci pour ce rôle (mais l'orchestre est bien réduit je crains). Pour l'aspect typographie : sans nouvelles après une semaine, je suis revenu à la version antérieure qui est plus cohérente. Je n'ai pas d'attachement excessif à une certaine typographie, celle actuelle est imparfaite. Sur le travail de fond : eh bien tirons déjà au clair les désaccords (en dehors des questions de vocabulaire). Proz 7 janvier 2007 à 19:40 (CET)

Sur le fond, je pense qu'il faut relire la deuxième partie. Je vais m'y atteler dès que j'ai du temps. Pas pour l'instant.Pierre de Lyon 8 janvier 2007 à 13:53 (CET)

[modifier] Remarque d'ordre syntaxique

Sous le même genre d'hypothèses sur les théories considérées, le second théorème affirme qu'il existe un énoncé exprimant la cohérence de la théorie : l'expression sous le me semble maladroite, et à mon humble avis la première partie de cette phrase devrait être reformulée. Des avis ? DocteurCosmos - ✉ 22 mai 2007 à 19:27 (CEST)

Sous des hypothèses voisines ? Proz 22 mai 2007 à 19:57 (CEST)
Et pourquoi pas selon des ... ? DocteurCosmos - ✉ 22 mai 2007 à 19:59 (CEST)
selon des hypothèses ? Il me semble que ça n'a pas exactement le même sens, on interprète machin selon l'hypothèse truc, on a l'impression de pouvoir faire d'autres hypothèses ; sous ces hypothèses, c'est de la déduction. Peut-être est-ce du jargon de mathématicien (mais courant) ? Est-ce sous + hypo = sous qui gêne ? Proz 22 mai 2007 à 20:11 (CEST)
Oui c'est ça mais c'est pas très grave. « En partant de ces mêmes hypothèses » peut-être... DocteurCosmos - ✉ 22 mai 2007 à 20:26 (CEST)

[modifier] Base 1 ?

Une question probablement idiote, le texte mentionne « Les algorithmes en jeu sont essentiellement ceux de l'addition et de la multiplication en base 1. » Ne serait-ce pas plutôt base « 2 » ? Vincent Lextrait (d) 12 avril 2008 à 08:51 (CEST)

Je ne suis pas certain, mais je ne pense pas. Je pense qu'on parle d'une notation à la Peano, avec un seul symbole numérique et une notation en successeur (0 = 0, s(0) = 1, s(s(0)) = 2...), équivalente (au zéro près) à une notation en bâtons (I, II, III), donc en base 1. Ceci dit le terme de base 1 est sans doute abusif, car ce ne peut pas être une numération de position comme en base > 1. - Eusebius [causons] 12 avril 2008 à 11:46 (CEST)
C'est bien la base 1, une suite de "petits bâtons" par exemple, additionner c'est mettre bout à bout (éventuellement déplacer un à un), une représentation très proche de l'idée intuitive de nombre entier, et qui est celle choisie dans l'axiomatisation de Peano. J'ajoute (j'ai répondu en même temps qu'Eusebius, je ne l'avais pas lu) que le terme s'emploie et n'est pas vraiment abusif parce que par ex. |||= 3 = 1*1°+1*1¹+1*1². Bon je suis d'accord que c'est un peu limite, parce que la position n'a plus d'importance. Proz (d) 12 avril 2008 à 11:59 (CEST)
3 = 1*1°+1*1¹+1*1², je l'a connaissais pas celle là (ni le contexte), mais j'en ai un grand sourire au lèvre depuis 5 minutes depuis que je l'ai lu; ça me fait penser à la blague éculée : il y a 10 sortent de personnes, ceux qui connaissent le binaire et les autres --Epsilon0 ε0 12 avril 2008 à 12:25 (CEST)
On avait eu un grand débat dans mon labo pour savoir si ça méritait l'appellation de numération de position ou pas. Notre argument principal pour conclure à la négative était la non-unicité de la décomposition en facteurs (si l'on a bien un seul symbole et pas de zéro). - Eusebius [causons] 12 avril 2008 à 15:12 (CEST)
Je n'ai pas compris l'argument mais je suis d'accord que ce n'est pas une numération de position (à dire le contraire, on risquerait de se faire mal voir des enseignants de CP :) ), puisqu'il n'est pas pas besoin d'attribuer une signification à la position. Proz (d) 12 avril 2008 à 18:32 (CEST)
Je crois que l'écriture "3 = 1*1°+1*1¹+1*1²" m'a surpris, non car ce ne peut être une représentation de la base un, mais parce qu'elle n'est pas homogène avec les écritures uselles en bases 2,3, etc ... vu que l'on pourrait considérer que l'unique chiffre en base un est le nombre zéro (et non pas le nombre un). Mais là bien sûr avec la décomposition 0*1°+0*1¹+0*1²... on ne va pas très loin. Bien sûr la réponse a toute question est 42 A00042 où le chiffre utilisé est "1" --Epsilon0 ε0 12 avril 2008 à 22:20 (CEST)