Discussion Utilisateur:Proz

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

Si tu as d'autres questions, tu peux voir cette page ou me contacter :  Le gorille Houba 6 avril 2006 à 11:31 (CEST)

Sommaire 1 Logique mathématique 2 Portail de logique 3 Portail de logique 4 Théorème d'incomplétude de Gödel 4.1 Partie I 4.1.1 Conditions d'application 4.1.2 Csqces du premier théorème 4.1.3 Csqces du second théorème 4.2 Partie II 4.2.1 Sur la notion de vérité, plus en détail 4.2.2 Vérité et démonstrabilité 4.3 Conclusion provisoire 5 théorie axiomatique des ensembles 6 Même article, autre remarque 7 Bandeau de logique 8 Proposition de réorganisation 9 Prouver ou démontrer 10 Pas d'AdQ 11 Théorème de complétude de Gödel 12 Décidabilité 13 Fonction logique 14 Paradoxe du menteur et mathématiques 15 Démonstration et absurde 16 Acquit de conscience 17 Georg Cantor 18 Décidable vs complet 19 Application 20 Georg Cantor 21 Incomplétude ontologique 22 Principles / Principia

[modifier] Logique mathématique

Le meilleur lieu pour discuter de l'état de l'ensemble de la logique mathématique est États des articles sur la logique. Il y a d'ailleurs déjà un début de discussion.. Pierre de Lyon 26 avril 2006 à 14:53 (CEST)

[modifier] Portail de logique

Il existe un portail de logique auquel tu peux participer si cela te tente. Bien a toi. Pierre

Apierrot 19 juillet 2006 à 14:57 (CEST)

[modifier] Portail de logique

Bonjour Proz, tu indiques dans la page de discussion du Portail de logique qu'il existe une section logique dans Projet:Mathématiques. Quitte à poser une question bête, où se trouve cette section? J'ai cherché sans rien trouver. Je te remercie par avance pour tes indications. Bien à toi

Apierrot 11 août 2006 à 13:04 (CEST)

[modifier] Théorème d'incomplétude de Gödel

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.

[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.

• 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.

• 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.

• 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?

• 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.

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.

[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] théorie axiomatique des ensembles

Réponse à la question "pourquoi supprimer l'axiome de l'infini ?" dans la boite de résumé : je crois que Cantor n'avait pas du tout cherché à axiomatiser la th. des ensembles, donc ce qui est appellée "théorie naïve" dans l'article est une fiction historico-pédagogique, pas de l'histoire (que je ne connais pas ou mal). Je répond sur un plan de "logique interne". Pour l'axiome de l'infini : je ne vois pas pourquoi il serait nécessaire. On construit facilement une infinité d'ensembles distincts par compréhension. Si on a l'axiome de compréhension généralisé, l'ensemble de tous les ensembles est infini. Bien-sûr, comme il s'agit d'une théorie contradictoire, tout cela n'a pas grand sens (tout est démontrable). Mais je ne vois pas nécessité de mentionner un axiome de l'infini. Ceci dit ça ne me gêne pas plus que ça : puisqu'il y a question posée je répond. Proz 14 août 2006 à 02:52 (CEST)

Oui il est très peu probable que Cantor ait voulu axiomatiser la th. des ensembles vu la manière dont il s'y est pris. Tes arguments sont justes, il faudra sans doute revoir quelques passages mais pour l'heure l'axiome de l'infini est effectivement non nécessaire. Merci d'avoir éclairé ma lanterne. BenduKiwi [ | φ] - 14 août 2006 à 03:08 (CEST)

[modifier] Même article, autre remarque

J'ai fait une petite remarque dans la section Dieu? de la page de discussion de l'article. je t'invite à y jeter un coup d'œil.Salle 14 août 2006 à 23:21 (CEST)

[modifier] Bandeau de logique

Salut Proz, tu sais peut-être que nous avons eu un problème de copyvio avec le bandeau du portail de logique. Une discussion a lieu ici pour qu'on en fasse un nouveau. Si tu veux participer, tu es naturellement le bienvenu. Amicalement Apierrot 16 août 2006 à 13:34 (CEST)

[modifier] Proposition de réorganisation

Bonjour, je te propose une réorganisation de la partie Vérité et démontrabilité, sur cette page, dans le but de mieux structurer le discours. Les différences essentielles :

• deux sous-sections qui permettent de mieux voir la structure du discours ; ce qui s'accompagne d'une interversion du matériau.

d'accord, j'avais préféré annoncé la couleur tout de suite, mais c'est l'ordre logique. je vais ajouter un ou deux mots d'intro pour expliquer l'intérêt du §.

• La suppression d'un paragraphe qui me semblait faire doublon.

s'il s'agit bien de la note où il est précisé que la vérité se définit math. : c'est une précaution utile, pour certaines personnes qui pourraient penser que c'est une notion "meta-physique". J'essaye de trouver un équivalent en introduction.

• Tout à la fin, tu trouveras une ligne en gras ; tu avais fait une reformulation après une de mes remarques, qui ne me semblait pas vraiment satisfaisante ; j'en propose une autre ; d'ailleurs, je pense que ce que j'ai écrit est faux, donc je te demande juste de regarder la formulation.

effectivement c'est tout à fait faux, je vois une façon de dire les choses plus clairement, effectivement ce que j'avais écris n'est aps très compréhensible, à ce point de l'article.

• Au début de la première sous-section, j'ai fait un paragraphe en italique pour dénoncer un lien qui me semble apporter de la confusion au discours.Salle 20 août 2006 à 14:36 (CEST)

Je recopie le § en question :

Problème de lien : modèle standard de l'arithmétique pointe non pas vers une page qui explique le modèle, mais vers une page qui décrit les diverses théories vérifiant (est-ce le bon terme?) ce modèle. C'est vraiment dommageable, et ça a bien participé à ma confusion entre modèle et théorie, etc...

c'est plutôt un modèle qui vérifie une théorie. Effectivement l'article parle du modèle standard, mais de façon peu explicite et un peu technique. Je propose de supprimer le lien. Je ferai une reformulation dans l'intro du § vérité à la démontrabilité, insistant sur la différence entre vrai dans un modèle/démontrable dans une théorie. La confusion devant être commune pour un mathématicien non logicien, je vais essayer de rédiger quelquechose pour expliquer ce point. Proz 21 août 2006 à 09:20 (CEST)

Je n'ai aucune prévention contre ce que tu proposes ; j'ai juste fait deux modifications mineures. En particulier, la suppression du lien, et la reformulation de la dernière phrase me conviennent. L'intro aussi. Seulement, maintenant, j'ai l'impression d'avoir compris, et je ne peux plus avoir le regard naïf que j'avais au départ, et je n'ai évidemment pas assez bien compris pour avoir du recul. Donc, j'encourage la substitution, sans trop savoir, à toi de choisir.Salle 22 août 2006 à 10:29 (CEST)

[modifier] Prouver ou démontrer

Je vois que tu utilises souvent le verbe «prouver» pour le verbe «démontrer» et le nom «preuve» pour le nom «démonstration». Je n'y sois pas favorable pour deux raisons.

1. C'est une anglicisme.
2. En français, une preuve est un fait qui intervient dans l'établissement d'une conviction, alors qu'une démonstration est un suite d'étapes de raisonnement. En mélangeant les deux concepts on appauvrit le français.

A ce propos, j'ai vu au cours d'un voyage le très beau film Proof qui doit plaire aux matheux, mais je crains qu'il ne sorte pas en France. Pierre de Lyon 28 août 2006 à 19:56 (CEST)

Je suis sensible à l'argument numéro 2. Je reconnais volontiers n'y pas faire attention. Ceci dit cet usage du mot preuve est très commun chez les mathématiciens et logiciens, et, sur un site [1] que je viens de découvrir et qui met en ligne le Littré de 1872 (ça a l'air d'un excellent travail au passage), cette définition [2] (voir en particulier 6° et 7°) me laisse penser que cela ne date pas d'hier, et que ce n'est pas apparu sous l'influence de l'anglais. Voir aussi la définition du terme prouver [3] qui donne clairement les deux sens que tu indiques, me semble-t-il. Proz 28 août 2006 à 21:11 (CEST)

Je ne vais pas mourrir pour cela, mais je me dis que si on veut écrire quelque chose de propre, on peut y prêter un peu attention, ça ne mange pas de pain. Pierre de Lyon 31 août 2006 à 13:17 (CEST)

[modifier] Pas d'AdQ

Bon, voilà, le verdict est tombé ; c'est un peu rageant quand on voit que Problème du sac à dos, qui est nettement moins bon à tous points de vue, a eu le label, mais c'est les aléas des votes Wikipedia. En tout cas, je te félicite du travail effectué, et je te remercie de ta patience devant mes questions.Salle 2 septembre 2006 à 11:50 (CEST)

Pour moi, le but d'un AdQ, c'est de dire aux gens bon, Wikipedia n'est pas une source fiable en général, mais là, on a fait du bon boulot ; avantage annexe : la procédure attire des gens vers l'article, permet d'entendre des critiques, et donc d'améliorer. Donc, je ne crois pas qu'il faille renoncer à ce genre d'articles pour des AdQ. En revanche, tu as raison sur les critiques sur les lectures. Ce qu'il y a, c'est qu'on a plein de procédures AdQ et PàS, et qu'il faut faire du chiffre ; donc, sur les domaines qui ne nous tiennent pas vraiment à cœur, on essaie de se faire un avis vite fait, et parfois, on se plante (va voir Wikipedia:Proposition articles de qualité/Stephen Hawking, que j'ai du mal à digérer :)).

Sur cet article en particulier, il est vrai qu'en plus, ne pas parler des applications plus ou moins farfelues, c'était tendre le bâton pour se faire battre. Qu'on le veuille ou non, cette matière fait partie du folklore autour du théorème, et même si ça ne fait que montrer le manque de rigueur intellectuelle de certains "philosophes", c'est instructif - ou du moins, ça existe.

Enfin, il y a un utilisateur de 17 ans qui a compris le théorème grâce à l'article, c'est déjà une belle satisfaction, non?Salle 3 septembre 2006 à 00:02 (CEST)

[modifier] Théorème de complétude de Gödel

Bonjour,

Sur l'article homonyme (lien), dans la section « Le théorème de Löwenheim et le paradoxe de Skolem », 3ème (ou 4ème selon la base du compte) paragraphe, on peut lire : "Cela résulte" sans autre suite. Il semble que ce début de phrase ait été ajouté lors de votre contribution datée du 10 mai dernier (2006). Peut-être est-ce simplement un bout de phrase qui a échappé à votre attention. ;-)

Si vous en avez le temps et l'occasion, je vous remercierais de nous faire profiter de votre relecture sur ce point. Bravo et encore merci pour le reste et la clarté de votre contribution.

Cordialement --nha de Lyon 6 septembre 2006 à 12:13 (CEST)

Merci pour les rectifications apportées et pour l'information sur l'action. L'article étant relativement volumineux, la relecture générale que vous proposez se fera sans doute à petits pas mais à pas "sûrs". ;-) Amicalement --nha de Lyon 7 septembre 2006 à 00:32 (CEST)

[modifier] Décidabilité

En fait, ma modification était motivée par la volonté de ne pas laisser apparaître le fait qu'il y ait deux sens distincts du même mot dans deux domaines très voisins comme une incongruité de terminologie, mais au contraire comme finalement quelque chose de très justifié au regard de l'équivalence que je mentionnais.

de plus il faudrait mentionner que l'ensemble des axiomes doit être récursif Il me semble que récursivement énumérable suffit — on peut énumérer toutes les démonstrations si l'ensemble des axiomes est récursivement énumérable, sauf confusion de ma part.

Le théorème de complétude intervient ainsi:

• les énoncés décidables au sens de la logique sont ceux qui sont soit vrais dans tout modèle, soit faux dans tout modèle;
• par le théorème de complétude, c'est équivalent à dire que ce sont ceux qui sont démontrables ou de négation démontrable;
• si l'ensemble des axiomes est r.e., alors l'ensemble des énoncés démontrables et celui des énoncés de négation démontrable sont r.e.;
• au final, on peut donc décider au sens algorithmique la vérité (au sens de "vrai vs faux dans tous les modèles") des énoncés décidables au sens logique.

Ceci dit, je ne suis sans doute pas d'une grande clarté... David.Monniaux 15 septembre 2006 à 19:27 (CEST)

[modifier] Fonction logique

Bonjour, tu as récemment modifié les catégorisations de fonction récursive, fonction calculable et logique combinatoire. Pour les deux premiers il s'agit bien de calculabilité, et plutôt de logique mathématique, ou d'informatique, pas de fonction logique au sens de l'article en tout cas. Pour le dernier, il s'agit d'une théorie généralisée des fonctions, ayant des rapports étroits avec le lambda-calcul, donc rien à voir a priori non plus. Par ailleurs, la sous-catégorie fonction logique a peut-être un sens en électronique, mais pas à mon avis en logique mathématique (une catégorie naturelle serait plutôt de calcul propositionnel). Proz 15 octobre 2006 à 19:42 (CEST)

Salut ! Ben à la base je voulais essayer de regrouper toutes les fonctions logiques dans une catégorie spécifique, pour pouvoir l'intégrer dans Catégorie:électronique. Je n'ai supprimé aucune catégorie, car j'ai intégré la catégorie Fonction logique dans Logique mathématique, Théorie des types, Calculabilité, Algorithmique. Mais j'avoue que j'ai eu la tronçonneuse un peu leste (j'ai fait un gros trou dans la haie !), il est vrai que Calculabilité et Algorithmique sont des notions peut être plus abstraites que les fonctions logiques, même si un algorithme pourrait être considérée comme une fonction logique séquentielle... Par contre pour Logique combinatoire et logique séquentielle ça rentre dans la définition de fonction logique. Es-tu d'accord avec cette définition ? --Zedh msg 15 octobre 2006 à 20:51 (CEST)

La catégorisation était c'est vrai un peu anarchique. Pour fonctions récursives et calculabilité c'est bien la catégorie calculabilité qui devrait être une sous-catégorie de logique mathématique. Là je crois que nous sommes d'accord. Je peux m'en occuper.

Pour logique combinatoire : est-ce bien celle-ci (La logique combinatoire de Curry, des fonctionnelles d'ordre supérieur) à laquelle tu penses ? Je ne connais pas le sens que ça a en électronique, je suis surpris que ce soit celui là. Je pense que cela devrait de toute façon rester comme sous-catégorie de théorie des types et logique mathématique. Pour la catégorisation en fonction logique : je te laisse apprécier vu le contenu actuel, mais j'aimerai quand même bien en savoir plus.

Pour logique séquentielle : je ne sais pas ce que c'est, hors de ce que je lis sur wikipedia (honnêtement, j'en apprends plus en allant voir l'article bascule qui est cité, je n'ai pas l'habitude d'utiliser le mot logique dans ce sens là). Mais j'ai toujours l'impression que l'on y parle de logique combinatoire dans un autre sens.

Est-ce que cela a vraiment un sens d'avoir fonction logique comme sous-catégorie de théorie des types, voire de calculabilité ? Proz 15 octobre 2006 à 22:35 (CEST)

Ben pour moi (cad pour l'electronicien le plus basique), la logique combinatoire c'est quand à tout moment on peut décrire la sortie comme une fonction de l'entrée, tandis que la logique séquentielle est fonction de l'entrée mais aussi de l'état précédent du système. C'est ce qu'on retrouve par exemple dans les FPGA. C'est pour ça que je voulais que la notion soit accessible depuis la catégorie:Circuit intégré logique. Mais c'est vrai que quand on regarde de plus près l'article logique combinatoire/logique séquentielle, y a bien quelque chose qui cloche (je comprend pas grand chose en fait .. surtout logique combinatoire). D'ailleurs c'est quand même un comble pour un article encyclopédique !

Quant à Calculabilité, Algorithmique et Théorie des types, laisse moi un peu de temps de réflexion, je suis un peu perdu là ; ) Bonne nuit ! --Zedh msg 16 octobre 2006 à 00:17 (CEST)

On en a confirmation en lisant la version anglaise [en:Combinatory_logic], il s'agit de deux choses différentes. Malheureusement, on ne dispose pas de la même variété d'adjectifs. Il faudrait probablement créer un article [logique combinatoire (électronique)], mettre comme dans la version anglaise un chapeau alertant sur la différence des notions dans chaque version.On peut aussi renommer également la version actuelle (plus lourd). En attendant on peut rétablir l'ancienne catégorisation de la page actuelle et supprimer le lien sur logique séquentielle (qui devrait aller dans l'autre version). Proz 16 octobre 2006 à 10:35 (CEST)

Effectivement il semble que nos amis anglais sont plus avancés sur ce point. J'ai supprimé les liens de fonction logique et de logique séquentielle vers calculabilité, algorithmique et théorie des types. Désolé pour le dérangement. --Zedh msg 16 octobre 2006 à 21:50 (CEST)

[modifier] Paradoxe du menteur et mathématiques

Voir Discussion Utilisateur:Circular et paradoxe du menteur

La solution trouvée, qui coïncide avec l'intuition que cet énoncé ne peut être accepté, est tout de même que ce n'est pas un énoncé du langage des mathématiques.

Que veux-tu dire par "la solution trouvée" ?

Personnellement, je ne suis pas d'accord que ce genre d'énoncé ne soit pas acceptable et qu'on le qualifie d'énoncé non mathématique. Pour moi, c'est un peu pour les mathématiques de ne pas reconnaitre ses propres contradictions. Un énoncé ni vrai ni faux... et alors? Cela me semble être une catégorisation que l'on fait a posteriori, parce que cela dérange.

Dis-moi si je me trompe, mais le codage des propositions dans l'arithmétique consiste en une sorte de mise en abîme, comme à l'opposé l'est le fait d'utiliser un métalangage. L'un est un peu comme un mirroir de l'autre. Pour aller plus loin, on pourrait dire que c'est un phénomène un peu fractal.

Fractal, honnêtement, je ne crois pas. Il y a un rapport au moins formel avec un combinateur de point fixe, mais cela reste fini.

Cela est-il bien sûr? Je m'explique. Au langage, on ajoute un métalangage. Ce métalangage peut être à son tour décrit par un métamétalangage etc. Et de l'autre côté, le langage permet de coder des propositions, donc dans un "sous-langage". Dans ce sous-langage, on peut coder de nouveau des propositions d'un autre langage etc. Comment cela pourrait-il avoir de fin?

--Circular 6 novembre 2006 à 11:36 (CET)

solution trouvée : la méthode formelle disons.

le paradoxe du menteur est une antinomie : "vrai et faux", et non "ni vrai, ni faux". On peut tout en déduire. Une théorie formelle qui démontre un tel énoncé est sans intérêt (par ailleurs vrai et faux peuvent prendre des sens précis en logique, "ni vrai ni faux" : c'est une question de définition, si "faux" est la négation de "vrai", ça n'est pas possible classiquement).

pour le combinateur de point fixe : je voulais parler du lemme de diagonalisation de la preuve du th. d'incomplétude, pas du codage de la syntaxe en général. Sinon ces histoires de meta-langages emboîtés à l'infini sont parfois évoquées, rien n'en est jamais sorti a ma connaissance (théorèmes ou autre). Enfin le codage de la syntaxe dans l'arithmétique, c'est effectivement exactement prendre le langage de l'arithmétique (pas très commode) comme meta-langage pour l'arithmétique. Proz 8 novembre 2006 à 19:40 (CET)

Ok pour les méta(^n)langages.

Je comprends à présent ta réaction par rapport aux paradoxes. Si avec eux on peut tout déduire, c'est comme si toutes les maths tombaient à l'eau, ce n'est pas rien. Cependant, j'ai le sentiment que les paradoxes ne sont pas dangeureux pour les mathématiques. Est-ce que tu peux m'expliquer comment on peut tout démontrer avec une proposition paradoxale? Y a-t-il un article à ce sujet? Cela se baserait-il sur le principe du tiers exclu?

Au fait, merci pour tes réponses.

--Circular 9 novembre 2006 à 08:42 (CET)

[modifier] Démonstration et absurde

règle logique valide déjà en logique intuitionniste, donc ne se fondant pas sur le tiers exclu. Justification informelle, si on peut prouver l'absurde, qui n'a pas de règle ou d'axiome permettant de l'"introduire", c'est que l'on peut prouver n'importe quoi. Proz 10 novembre 2006 à 20:36 (CET)

Et concrètement, comment fait-on pour prouver n'importe quoi à partir d'un énoncé paradoxal ?

NB: Je pense qu'un énoncé paradoxal n'est ni vrai, ni faux, ni les deux à la fois. Sa valeur de vérité est différente du vrai et du faux. Si l'on pose qu'une proposition ne peut avoir qu'une seule valeur de vérité, alors pour les énoncés paradoxaux il y en a une troisième, qu'on pourrait appeler paradoxal, tout simplement. On aurait alors trois possibilités : vrai, faux et paradoxal.

Table de vérité du "non" logique :

Non	Vrai	Faux	Paradoxal
=	Faux	Vrai	Paradoxal

Le problème de la proposition "A = non A" a alors une solution.

Circular 11 novembre 2006 à 10:43 (CET)

Pardonne-moi d'insister, mais comment fait-on concrètement pour prouver n'importe quoi à partir d'un énoncé paradoxal ? Parce que je ne vois pas.

Détermination de la valeur de vérité de l'énoncé paradoxal

Si on part de l'énoncé A disant que A n'est pas vrai. Si on suppose qu'il est vrai, cela entraine qu'il est faux, donc il n'est pas simplement vrai. De même, il n'est pas simplement faux. Il a donc une 3ème valeur de vérité : pardoxale ou indéterminé.

Je préfère la notion de paradoxale car il ne s'agit pas d'un énoncé dont on ne sait pas grand chose, qui aurait des inconnues qui ferait qu'il n'est pas déterminé. On sait qu'il est vrai et faux, ou bien ni vrai ni faux, ou plus simplement qu'il est paradoxal.

Conséquences

Table du "ou logique" avec la valeur paradoxale

A ou B	B vrai	B faux	B paradoxal
A vrai	Vrai	Vrai	Vrai
A faux	Vrai	Faux	Paradoxal
A paradoxal	Vrai	Paradoxal	Paradoxal

Ensuite, si (A=>B) est comme ( (non A) ou B) alors on a la table d'implication suivante

Table de l'implication avec la valeur paradoxale

A => B	B vrai	B faux	B paradoxal
A vrai	Vrai	Faux	Paradoxal
A faux	Vrai	Vrai	Vrai
A paradoxal	Vrai	Paradoxal	Paradoxal

Et après ?

[modifier] Acquit de conscience

C'est un détail. Mais c'est bien "acquit de conscience" (du verbe "acquitter", sens comptable) et non pas "acquis" (référence : Robert). Cordialement. Vivarés 23 novembre 2006 à 01:14 (CET)

[modifier] Georg Cantor

Merci pour ton intervention. J'ai abandonné la traduction en cours de route à un moment où je me suis rendu compte que j'accordais plus de temps à wikipédia qu'à mes études, d'où mon arrêt brutal. Depuis que j'ai repris mon activité sur wiki, je me dis qu'il faut que je finisse ce texte, mais j'ai pas prévu de m'y remettre, m'étant engagé dans le développement des articles portant sur (rien à voir) le Tyrol.

Thedreamstree 20 janvier 2007 à 17:06 (CET)

Je copie mon message sur la page de discussion de l'article Georg Cantor. Thedreamstree 20 janvier 2007 à 17:59 (CET)

[modifier] Décidable vs complet

Houla j'ai craqué quand j'ai écrit ça... Bonne rectification. Ce que je voulais dire c'est que quand une théorie est décidable au sens algorithmique (il existe un algo qui réponde vrai vs faux) alors elle n'admet pas d'énoncés indécidables.

En fait tout ceci vient d'un problème de vocabulaire. Il y a en fait deux problèmes qualifiés de "complétude":

• tout énoncé vrai dans tous les modèles est-il démontrable?
• tout énoncé est-il soit vrai dans tous les modèles, soit faux dans tous les modèles?

David.Monniaux 22 janvier 2007 à 09:59 (CET)

[modifier] Application

Bonsoir, Pourquoi enlever la définition formelle ? Oxyde 8 février 2007 à 21:12 (CET)

La forme de l'article me convient. Mais la notion de fonction n'y est plus abordée et je me souviens qu'ils avaient fusionné les articles fonction et application... Il n'y a plus qu'à en recréer intitulé fonction. :-) Oxyde 8 février 2007 à 23:02 (CET)

J'ai plutôt l'impression que tu veux faire à ta façon. Quand on construit une application de R dans R, le problème se pose souvent puisqu'il faut choix parmi une infinité de réels une image de chaque élément de l'ensemble de définition. Oxyde 8 février 2007 à 23:43 (CET)

Je te retourne la question, tu penses que ces fonctions polynômes, ... sont les seules fonctions qui existent? Oxyde 9 février 2007 à 00:11 (CET)

[modifier] Georg Cantor

J'ai copié votre remarque dans Discuter:Georg Cantor, ainsi que ma réponse. Tous les contributeurs intéressés pourront s'exprimer. Amicalement, ▪ Sherbrooke (✎✎) 8 mars 2007 à 10:39 (CET)

[modifier] Incomplétude ontologique

Je suis pour la suppression de l'article Incomplétude ontologique:

1. parce que l'article n'a pas beaucoup de sens et de consistance (peut-être même de cohérence),
2. parce son(es) auteur(s) a (ont) disparu de Wikipédia et il n'y aura personne pour discuter,
3. maintenant qu'il na plus de catégorie, il devient article orphelin.

Pierre de Lyon 14 mars 2007 à 08:31 (CET)

[modifier] Principles / Principia

La confusion est facile, vu les titres, mais les "principles of mathematics" (1903) et les "principia mathematica" (1910 pour le 1er volume) sont deux oeuvres différentes de Russell. La première (entre autre) décrit les paradoxes (donc celui de Russell), fait connaître Frege aux mathématiciens etc. Proz 16 mars 2007 à 23:52 (CET)

Désolé, il faudrait alors dire par une note qu'il ne faut pas confondre. Pierre de Lyon 17 mars 2007 à 14:22 (CET)