La vérité d'une proposition de Gödel
Réponses
-
Je confirme que ce n'est pas du tout l'approche classique, c'est une approche "forum" pour les débutants.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Ben, merci christophe c, effectivement, je ne savais pas qu'on postulait l'existence de théories complètes "hors axiomatique". C'est un truc bizarre ça, et je me demande si on en connaît, à part des cas avec des ensembles finis et des structures "simples".
Je pensais que la seule façon de parler d'objets abstraits, et donc mathématiques, consistait à postuler qu'ils "étaient" ce qu'on en postulait dans un système axiomatique, et cette définition de cet objet n'ayant rien de plus "en-dehors" (contrairement à une théorie physique, par exemple, qui a aussi accès à des observations physiques), alors tout ce qu'on a dit concernant cet objet est ce qui découle par démonstration de sa définition. Ce qui ne découle donc pas d'une démonstration, on ne l'a pas "décidé" pour cet objet dans sa définitioin. On peut toujours changer d'avis, et le décider, mais de deux façons (vrai ou faux), et on fabrique alors deux variantes de cet objet, qui "coïncident" avec l'objet-mère pour tout ce qui était déjà vrai ou faux. Il en découle alors quand-même que pour cet objet-mère, un énoncé qui est non-prouvable (et dont on pourra donc choisir quel objet-fille on voudrait en faire) ne peut pas avoir "un statut de vérité" puisqu'on sera libre de le choisir et on ne l'a pas (encore) fait.
Et je pensais que hors cette façon de faire, aucun objet mathématique puisse exister. Je ne comprends donc pas d'où viennent ces "modèles", sauf si on dit quelque part qu'un modèle, c'est un objet mathématique comme je le décris, mais où on a quelque part "jeté une pièce au hasard pour choisir entre vrai et faux" chaque fois qu'on serait tombé sur un énoncé pour lequel l’axiomatique du dit objet (et les jets précédents) n'avait pas encore décidé sur la vérité ou la fausseté du dit énoncé ?
Un modèle serait alors un jeu d'énoncés de telle façon que chaque énoncé possède, d'une façon ou d'une autre, une valeur de vérité, et en plus, les règles de déduction logique qui peuvent jouer entre ces énoncés pour "propager" la vérité ne font jamais "collision" (la théorie reste quand-même cohérente) ? Donc une axiomatique qui est donnée par tous les énoncés vrais, de telle façon que ceux qui restent sont seulement des négations d'énoncés vrais, mais qu'on n'a quand-même pas des contradictions ? (et donc une axiomatique "infinie" dans beaucoup de cas).
C'est un truc du genre ?
Mais alors peut-être qu'ils "existent", mais on en connaît très peu, alors (sauf des cas finis ou simples) ? -
@GaBuZoMeu:
désolé de paraître "borné", c'est ma façon d'illustrer une incompréhension, à partir de laquelle, tu peux, si tu veux, tenir un discours plus pédagogique. Si c'est pour me dire "tu ne comprends pas", eh bien, je le savais déjà, sinon je n'en discuterais pas.
Tu dis qu'un modèle n'a pas de "théorie", mais alors je ne sais pas ce que cela pourrait être. Depuis le début du fil, on me répète que je ne sais pas ce que c'est, un modèle. On est d'accord. Je dis que je ne comprends pas ce que vous entendez par "modèle" et tu répètes que je ne le sais pas. Ben oui. Mais ce n'est pas en répétant cela que ça risque de changer. Il faut "déminer" mes incompréhensions en m'expliquant quelle idée est erronée, pourquoi, et comment il faut la remplacer par quelque chose qui marche. Je présente mon exposé "borné" pour que tu puisse y voir exactement ce qui coince, car si je le savais moi-même, je ne bloquerais pas.
Comme je dis ci-dessus, les seuls objets mathématiques dont je pensais qu'on pouvait "parler", sont des objets introduits par une axiomatique. Avec tout ce que je comprends de ce qu'on me dit d'un objet "modèle", on semble dire qu'on part du principe qu'il n'a pas d'axiomatique pour un modèle. J'en dis alors que je ne sais pas ce que c'est. Ce n'est pas une critique, j'explique ce que je ne comprends pas. Je ne comprends pas la définition de "modèle", quand on dit en même temps que "les nombres entiers naturels" seraient un modèle pour Péano, par exemple. Car les nombres entiers naturels sont définis par un système axiomatique dont on sait qu'il n'est pas complet. On ne peut donc pas vouloir parler de CES entiers naturels, mais alors desquels ?
Si la définition de modèle est "pour tout énoncé, il y a une valeur de vérité" je ne sais pas trop bien ce que cela veut dire dans le cadre d'un objet défini par axiomatique (sauf dire que cette axiomatique serait complète, mais ça, c'est justement une propriété très particulière d'une axiomatique qui est loin d'être satisfaite dans la plupart des cas). Et si on parle d'assigner des valeurs de vérité "hors axiomatique", je ne sais pas comment on le fait, alors. -
Bravo Christophe, Patrick123 est désormais encore plus dans le flou qu'avant. Ça fait aussi plaisir de voir que mes messages passent complètement inaperçus, ça valait bien la peine de se décarcasser, je sors.
-
:-D je n'ai vraiment pas cherché à t'embeter Poirot. Patrick en écrit trop long et trop philo vague de toute façon.
Je ne suis pas sur que son flou résulte de la précision complet/non complet que j'ai donné. Ses derniers msg que je me suis forcé à lire malgré absence de saut de ligne montrent plutôt qu'il ignore que tout est fait dans ZFC et qu'il réclame une axiomatique racine. Mais je peux me tromper c'est à lui de dephilosopher ses posts.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
@Patrick123 ,
Note : dans ce qui suit, il y a peut-être pas mal de bêtises écrites, merci d'avance à quiconque m'aidera à balayer mes fausses conceptions ...
Il faut accepter d'utiliser la théorie des ensembles pour définir le concept de modèle (avec l'axiome du choix pour le théorème de complétude ? : à vérifier) même si on l'applique à la logique. Contrairement à une vision purement syntaxique (que peut donner Bourbaki : j'en ai été une "victime") où l'objet "vit" car on l'a définit syntaxiquement, il n'en est pas de même avec les modèles (prend un ensemble quelconque non vide avec le langage réduit à l'égalité). Pour se rassurer, on parle au départ de théorie des ensembles "naïve", etc., enfin bref on développe un formalisme minimum. Cette approche se heurte à celle qui vise à établir "qui vient en premier, la syntaxe ou les ensembles", l'oeuf ou la poule ... la logique est formalisée par des ensembles (naïfs ou pas) et les propriétés des ensembles étudiées par des règles logiques.
Comme je l'ai déjà dit, je ne me sens pas à l'aise sur la notion d'entiers naturels.
Tu te demandes de quels entiers naturels on parle ? Moi aussi ... Voici pourquoi.
Je me place dans un modèle M de la théorie des ensembles (avec au minimum l'axiome du choix, je ne sais pas si on peux s'en passer pour le théorème de complétude de Gödel).
Dans M, on définit (c'est à dire via une formule du langage) un entier naturel, on définit l'ensemble des entiers naturels $\mathbb N$, etc.
A partir de là, on développe une "théorie de la logique classique syntaxique" et une "théorie des modèles" interne à M.
Le modèle M connaît "parfaitement" tous les théorèmes que l'on peut construire sur $\mathbb N$ ; "vu par M", on récupère un modèle $\mathbf N$ :
tous les énoncés sont $\mathbf N$-vrais ou $\mathbf N$-faux ("vu par M"), où la notion de $N$-vérité est interne à $M$.
On dispose des théorèmes de Gödel (complétude et incomplétudes) relatifs à M.
Tout semble relatif à M ... même $\mathbb N$.
Mais on peut adopter le point de vu que $\mathbb N$ "préexiste" en tant qu'ensemble "naïf" (il faut quand même quelques explications certes) et se poser beaucoup moins de questions que moi.
Cordialement -
Merci pour ta blague Rescassol, je sais que j'aurai été important dans ta vie, ça me réchauffe le coeur ;-)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Bonjour,
Tu ne comprends rien CC.
Tu n'es pas spécialement important dans ma vie et ce n'était pas une blague.
C'est une expression du langage courant, que tu ne connais peut-être pas, qui traduit une réalité.
Cela signifie:
Tu reproches à quelqu'un d'écrire de trop longs messages, alors que tu en écris couramment de bien plus longs.
Cordialement,
Rescassol -
@ petit-o: je crois que je te suis, je n'en suis pas sûr ; en tout cas je te remercie pour les efforts.
Aux autres: le concert de "il ne sait pas ceci ou cela", dont je conviens, ce n'est pas très utile pour apprendre. Le concept de "modèle" avec tous les énoncés dedans vrai ou faux, est loin d'être trivial - je n'arrive pas à le comprendre ce qu'on veut bien dire avec ça. Je peux seulement comprendre "une théorie T2 est "un modèle" pour une théorie T1" mais on me dit que ce n'est surtout pas ça.
Je vais encore essayer. On a une théorie T1, qui implémente d'un coté "un ensemble d'énoncés" qu'on nommera E, et de l'autre coté, un jeu d'axiomes et de règles d'inférence.
Cela nous définit une fonction Booléenne sur E, f, qui doit satisfaire, pour tout x dans le domaine partie de E:
1) f(x) = Vrai si s. si (x est axiome ou x est prouvable avec les règles d'inférence à partir d'axiomes)
2) f(y) = Faux si s. si f(not y) = Vrai
le domaine de f n'est pas nécessairement E. Les x de E qui ne sont pas prouvables n'appartiennent pas au domaine de f.
On définit alors un modèle M de T1, qui est un autre jeu d'énoncés F, et une autre fonction booléenne h, mais avec une "interprétation dans E", c.à.d. une application injective k de E en F de telle façon que, après "réduction à E", h devient une application booléenne g sur E, telle que, pour tout x dans le domaine de f, g(x) = f(x).
Bon, on peut bien "concevoir" qu'il y ait des applications booléennes sur E, mais la seule façon d'en "définir" une, c'est quand-même par une méthode axiomatique + logique ? (oui/non ?) Y a-t-il une autre façon d'assigner les valeurs d'une fonction booléenne à un ensemble d'énoncés (qui peut avoir un sens logique) ? Et alors il est loin d'être certain que cette fonction "g" soit une application, non ?
Quand on parle des "entiers naturels" on a quand-même introduit un système axiomatique+logique pour dire ce que c'est, ce $\N$-là et donc, il y a peu de chances que ce système soit complet, et puisse donc être "un modèle" de quoi que ce soit, non ?
Je ne peux pas concevoir qu'on puisse définir un concept mathématique autre que par une méthode axiomatique + déduction logique, et qu'on puisse donc avoir des "modèles" sous la main qui soient complets. Enfin, ceci dans l'idée qu'on n'ait aucune théorie complète sauf pour des systèmes simples (oui ?). Je n'arrive pas à saisir d'où viendrait la valeur vrai/faux d'un énoncé, autre que par une preuve. -
@petit-o:
J'ai aussi du mal déjà avec "Le modèle M connaît "parfaitement" tous les théorèmes que l'on peut construire sur N". Même de façon informelle.
Je vais encore essayer de dire où "ça bugge":
Oui, on connaît "les éléments de $\N$, mais même avec une axiomatique informelle de $\N$ dans la théorie naïve des ensembles, et un style informel de preuve, je ne vois pas du tout en quoi on aurait assigné une valeur de vérité à tout théorème de $\N$.
Exemple trivial:
Imagine que j'ai un ensemble de "bananes". Il y en a 12.
je donne l'axiome: toute banane a un seul successeur, et un seul prédécesseur.
Et c'est tout. C'est ma définition axiomatique informelle de ce que j'entends par "banane".
Alors, l'énoncé "on peut atteindre toute banane à partir d'une autre banane de façon récursive par successeurs" est improuvable. Si je suis dans le cas d'un grand cycle avec les 12 bananes dedans, cet énoncé est vrai, et si je suis dans le cas de deux cycles de 6 bananes, cet énoncé est faux.
C'est informel, mais c'est improuvable. Je le sais parce que je peux ajouter un autre axiome, et selon que je le fais, cet énoncé deviendra vrai ou faux.
Tant que je n'ajoute pas un axiome, je ne peux pas dire que cet énoncé "est parfaitement connu" par la théorie des ensembles: ce n'est pas le cas.
Maintenant, je sais qu'on va me dire "mais tu utilises toi-même deux modèles de ta théorie" !
Non, j'ai juste introduit un axiome de plus dans une nouvelle théorie. Ce n'est pas que mon idée de banane "pré-existait" mais je n'avais juste pas trouvé tous les axiomes pour pouvoir le prouver. Je n'avais simplement PAS DÉCIDÉ ce que je voulais dire avec mes bananes.
Et je vois tout objet mathématique comme ça, aussi les entiers naturels: on en a dit "des choses" (comme moi j'avais dit des choses concernant les bananes). Mais on n'a pas tout dit. Alors ce qu'on n'a pas dit, "le modèle" ne peut pas le savoir. La seule façon d'avoir tout dit, c'est de pouvoir tout déduire de ce qu'on en a dit. Sinon, on ne l'a pas décidé encore.
C'est pour cela que j'ai du mal à distinguer "vrai/faux" et "prouvable". Car je me sens libre de choisir quand ce n'est pas prouvable, alors on ne peut pas "savoir" ce que je vais choisir. -
Patrick123 a écrit:C'est pour cela que j'ai du mal à distinguer "vrai/faux" et "prouvable".
Et pourtant c'est ce que tu as fait dans ton exemple avec les bananes non ? Tu as dit : "Si je suis dans le cas d'un grand cycle avec les 12 bananes dedans, cet énoncé est vrai".
Tu as bien attribué une valeur de vérité ("vrai") à ton énoncé dans le "modèle" avec les 12 bananes. Et tu as fait de même dans le "modèle" constitué des deux cycles de 6 bananes ("faux"). -
@Patrick-123 : si tu avais lu mon dernier pavé tu serais moins dans le flou. Mais tu préfères t'arrêter au fait que l'on te dit que tu ne comprends rien. Tant pis pour toi.
-
@Patrick123 ,
Je commence par une remarque : l'axiomatique de Peano ne définit pas $\mathbb N$ (cela a déjà été écrit).
Plus généralement, une théorie ne définit pas en général un modèle.
Mais quand on se donne un modèle M, on récupère une théorie Th(M) définie comme étant l'ensemble des énoncés M-vrais, telle que
1) pour tout énoncé F, soit F soit (non F) est Th(M)-prouvable ;
2) pour tout énoncé de la forme « il existe x tel que F(x) », il existe "concrètement" un élément m de M qui satisfait la formule F(x).
3) peut-être qu'il y a d'autres propriétés (je ne sais pas, je t'aide avec mes modestes moyens)
En bref, si tu ne donnes pas toutes les propriétés sur tes bananes pour avoir 1), tu n'as pas un modèle.
(il y a d'autre problème plus formel dans ce que tu as écrit, mais cela ne sert à rien ici de rentrer dans les détails).
Quand on a une théorie T consistante, en lui rajoutant petit à petit des énoncés indécidables tout en restant consistant (on vise 1)),
et en lui rajoutant des symboles m (de telle sorte qu'on ait 2)), on arrive à une théorie de la forme Th(M).
Derrière ce "proche en proche", on utilise d'ailleurs à ma connaissance le lemme de Zorn, Th(M) étant en quelque sorte "maximale" dans son ensemble.
J'ai écrit "Le modèle M connaît parfaitement tous les théorèmes que l'on peut construire sur $\mathbb N$".
Je voulais dire qu'un énoncé arithmétique E est parfaitement "vu" par M dans le sens où celui-ci sait s'il est vrai ou faux ; il n'y a pas d'énoncé indécidable pour M.
Je dis bien "vu par M", car pour nous tant qu'on n'a pas de preuve on ne sait pas si c'est E ou sa négation qui est vraie.
Si intuitivement il te semble que pourtant certain énoncé E reste indécidable, c'est selon moi parce que tu changes implicitement de modèle ;
autrement dit tu raisonne dans une théorie T et non dans la théorie "maximale" Th(M).
Bon tu as plus ou moins anticipé cet argument.
Soit F un énoncé T-indécidable où T est une théorie qui admet M comme modèle (donc tout énoncé T-prouvable est M-vrai et Th(M)-prouvable). Dans M, F ou sa négation est M-vrai. Si on décide de l'opportunité de rajouter F à T, on doit changer de modèle si c'est (non F) qui est M-vraie. En pratique, cela n'a pas vraiment d'importance puisque nous ne connaissons pas parfaitement M ; on se contente de le considérer.
Quand on parle de $\mathbb N$, c'est toujours de l'ensemble des entiers naturels mais jamais il est sous-entendu par rapport à quel "univers" ou "modèle" M on le considère. Si on fixe un modèle $M$, on fixe $\mathbb N$ (pour $M$) car "il existe un unique ensemble dont les éléments sont exactement les entiers naturels" est un énoncé M-vrai. Ainsi $M$ dit tout sur $\mathbb N$, mais nous on ne sait pas concrètement tout ce que dit $M$ sur $\mathbb N$. Autrement dit, on ne connait pas tous les énoncés vrais du modèle $\mathbf N$ de mes posts précédents.
Pour l'histoire du vrai/faux et prouvable ... c'est autre chose.
T-prouvable : tu appliques des règles "syntaxiques" pour déterminer, à partir d'une théorie T, si un énoncé peut-être qualifié de "T-prouvable"
M-vrai : tu appliques des règles "sémantiques" pour déterminer, à partir d'un modèle M, si un énoncé peut-être qualifié de "M-vrai"
Il y a des détails ou des exemples des post précédents.
Je rappelle le lien entre les deux approches (Gödel) : E est T-prouvable ssi pour tout modèle M de T, E est T-vrai.
Cordialement -
@Poirot:
Si si, j'ai bien sûr lu tes contributions. Mais tu écris:
" Pour tout énoncé $\phi$ sur L, je peux définir récursivement une valeur de vérité dans M, qui voudra dire si $\phi$ est vraie ou non dans M. En particulier, il n'y a pas de "formule indécidable dans M", une formule y est vraie, ou fausse, point."
Je ne sais pas si je dois prendre cela comme d'une façon triviale, que bien sûr il y a un énoncé dans M qui correspond à un énoncé dans L, "avec les variables remplacées par des éléments de l'ensemble de base de M" - ça, j'ai bien sûr compris, ce n'est pas le problème. Le problème est "que peut bien être ce modèle dans lequel tous les énoncés seraient vrais ou faux, et qu'il n'y auraient pas d'indécidables ?"
On me voit peut-être comme une nouille mais quand-même pas au point de ne pas avoir compris qu'il fallait "interpréter" l'énoncé de L dans M j'espère :-D
Quand je lis ce que tu écris, je pense que tu me prends pour la-dite nouille B-)
Je vais encore une fois essayer d'expliquer sur quoi je bute dans le post suivant, en étant le plus court possible. Il est vrai que cette discussion me permet de le voir de plus en plus "clairement" pourquoi je ne vois pas ce que vous voulez dire. Mais je ne vois donc toujours pas ce que vous voulez dire.
petit-o a saisi mon souci, je crois. -
Patrick si tu es à Paris Anatole chapotte un exposé d'un de ses étudiants qui va exposer en guise de mémoire M2 "le théorème d'incomplétude de Godel" aujourd'hui de 16h à 18h à Sophie Germain premier ou deuxième étage je ne sais plus avec entrée libre métro bibliothèque ou tramway avenue de France.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
@ petit-o:
"En bref, si tu ne donnes pas toutes les propriétés sur tes bananes pour avoir 1), tu n'as pas un modèle. "
Oui, c'est exactement ça !
Mon idée était qu'en gros, tout système axiomatique, qu'il soit formel ou non, qui puisse *contenir* un truc suffisamment complexe comme Péano, est "bourré d'inprouvables". Je sais que Gödel ne l'a prouvé que dans un contexte bien plus restreint, mais il a ouvert la boîte de Pandore: il y a toutes les chances que n'importe quelle définition axiomatique/logique, qu'elle soit formelle ou non, de tout objet mathématique suffisamment complexe, sera bourrée d'improuvables, c.à.d. il y aura toujours pleins d'affirmations/énoncés qu'on pourra en faire, dont on ne peut pas déduire une preuve (formelle ou informelle) à partir des axiomes et des "formes de raisonnement logiques acceptées", ni de sa négation.
Alors, je pensais que cela voulait simplement dire que ce que j'avais défini comme mon objet mathématique avec "mon axiomatique, et mes formes de raisonnement acceptées", contenait toujours encore des "libertés non-prises", des décisions libres sur leur définition que je n'avais pas faites. On peut donc "ajouter des axiomes à l'infini", et chaque axiome est un libre choix. Je n'aurai donc JAMAIS fini de "définir toutes mes propriétés de mes bananes".
Avec mon exemple de banane, mon objet était trop simple, et le nombre de choix libres était limité. Donc oui, à un certain moment, tous les choix étaient faits, il n'en restaient plus, j'avais bien un système complet et oui, c'était alors "un modèle utilisable".
Mais je pensais qu'on n'en avait pas, des systèmes complets qui pouvaient servir comme modèle, sauf des choses simples comme mes bananes. Je pensais que "l'esprit" de Gödel, c'était: dès qu'il y suffisamment de richesse dans le système pour que ça fasse "des nombres entiers", il y a une infinité de choix encore à faire.
Et donc, à part des objets plus simples que $\N$, je pensais qu'on n'avait pas d'objets "totalement" définis. Alors je ne comprenais pas qu'on pouvait en prendre "comme modèle".
Merci de m'avoir aidé à pouvoir accoucher "nettement" de mon problème. -
@ christophe c: c'est gentil, mais je suis à 500 km de Paris (Grenoble).
-
La charrue avant les boeufs. Pour la 1000ème fois, un modèle n'est pas défini par une théorie, c'est juste un "truc" qui satisfait chaque énoncé de cette théorie, mais il y a tout un tas d'énoncés qui ne sont pas dans la théorie qui ont quand même droit à un statut de vérité dans un tel modèle. Tu ne peux pas décréter qu'une théorie définit un unique modèle, qui sera la "réalisation canonique" de ta théorie, surtout si ta théorie n'est pas complète.
Dans tout modèle de la théorie des groupes, l'énoncé $(\forall x, (\forall y, y*x=x*y=y) \Rightarrow x=e)$ est également satisfait, bien qu'il ne fasse pas partie de l'ensemble de trois formules que j'appelle "théorie des groupes". Dans un modèle fixé de la théorie des groupes, l'énoncé $\forall x, \forall y, x*y=y*x$ est vrai ou faux, il n'y a pas d'alternative. -
@Poirot:
Ah, non, je ne dis pas qu'une théorie aurait "un modèle canonique". Je pensais qu'on utilisait "des objets mathématiques" comme modèle pour certaines théories formelles, et mon problème était: ces objets mathématiques sont eux-mêmes définis par une axiomatique et "des raisonnements acceptés" et ne sont donc dans beaucoup de cas, eux-mêmes "incomplets".
Je pensais qu'on disait "$\N$ avec les opérations + et * est un modèle pour Peano" par exemple. Mais je pensais qu'on n'avait aucun objet de tel sorte qui soit complet (c.à.d. pour lequel on a une définition de vérité pour tout énoncé de Péano, interprété dans ce modèle). Parce que je croyais que toute définition axiomatique de $\N$ qu'on a sous la main, menait toujours à des improuvables à partir de cette définition axiomatique, et laissait donc encore des choix libres dans sa définition et donc dans la définition de ce qu'on entend par "vrai" ou "faux" pour cet objet, choix qu'on n'avait pas fait et donc "statut de vérité" pas encore choisi.
Oui, bien sûr, on peut s'imaginer des "modèles" (c.à.d. des applications booléennes sur les énoncés d'une théorie "interprétée dans ce modèle"), mais ils ne correspondent alors pas à des objets mathématiques connus. (sauf cas simples).
C'est peut-être simplement ça: que les modèles dont on parle, ne correspondent pas à des objets mathématiques connus (axiomatiquement définis), mais sont simplement "un libre choix d'une application booléenne sur les énoncés, définissant alors un modèle". -
Patrick123 a écrit:les modèles dont on parle [...] sont simplement "un libre choix d'une application booléenne sur les énoncés, définissant alors un modèle"
Mais oui ! Ça s'arrête là ! Bon après on ne peut pas prendre n'importe quelle opération booléenne mais l'idée est là.Patrick123 a écrit:Je pensais qu'on utilisait "des objets mathématiques" comme modèle pour certaines théories formelles
Ben non, on construit des objets avec notre théorie des ensembles favorite, et on montre qu'ils sont modèles de certaines théories. Par exemple, quelle que soit la construction que l'on fait de l'ensemble des entiers naturels, il s'agira d'un modèle de l'arithmétique de Peano. Ce n'est pas pour autant une définition de $\N$.Patrick123 a écrit:je croyais que toute définition axiomatique de $\N$ qu'on a sous la main, menait toujours à des improuvables à partir de cette définition axiomatique
Tu répètes ce que l'on s'évertue à te dire depuis le début, on ne définit pas un modèle à partir d'une théorie. Il n'y a pas de "définition axiomatique de $\N$" en logique du premier ordre.
Exercice : notons $Th(\mathbb N)$ la théorie de $\mathbb N$, c'est-à-dire, la construction de l'ensemble $\mathbb N$ ayant été faite, l'ensemble de toutes les formules qui sont vraies dans $\mathbb N$ (au sens de vrai dans cette structure fixée). C'est une théorie complète une fois que l'on a compris les arguments donnés plus haut. Pourtant cette théorie contient la théorie de Peano et donc Gödel nous dit que $TH(\mathbb N)$ est incomplète. Chercher l'erreur dans ce raisonnement. :-D -
@Martial Ah c'est moins subtil ?
Bon ben alors je ne vois pas. Je regarde bien la théorie complète de $\N$ et... qu'est ce qui m'échappe ?
PS: "La théorie complète de $\N$" c'est bien l'ensemble des formules closes qui sont vraies dans $\N$, non ? (je deviens Pablo...:-()
Donc pour toute formule close $F$ on a : $(F\in$ "La théorie complète de $\N)$" ou $( \lnot F \in$ "La théorie complète de $\N)$"... non ? -
:-D mieux vaut ne pas donner d'indication :-D l'exercice est trop court pour que ça ne le spoile pas.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
@Martial et @christophe c
Voici l'énoncé du premier théorème d'incomplétude récupéré sur Wikipedia :
Dans n'importe quelle théorie récursivement axiomatisable, cohérente et capable de « formaliser l'arithmétique », on peut construire un énoncé arithmétique qui ne peut être ni démontré ni réfuté dans cette théorie.
Il faut que la théorie soit récursivement axiomatisable pour appliquer le théorème. Je pensais que l'erreur délibérée de Poirot était celle-ci (de ne pas avoir mentionné cette condition pour l'application du th. d'incomplétude). Raison pour laquelle j'ai dit :
"Gödel n'a jamais dit que toute théorie contenant la théorie de Peano est incomplète".
Mais vous semblez me dire que j'ai loupé un truc vachement plus évident... et je ne vois toujours pas...
PS. je n'ai qu'une vague idée de ce que signifie "récursivement axiomatisable" mais pas besoin de le savoir dans les détails dans ce cas. -
Je me détends un peu (mais pas au point de lire tout) en revenant "enfin" vers toi, Patrick. Je ne sais pas où tu en es, et j'ai parcouru rapidement les efforts assez gigantesques des autres pour te permettre de dissiper les ambiguités.
1/ Je reviens sur la critique de GBZM (justifiée, mais trop sévère) concernant mon gommage de la frontière syntaxe/sémantique.
1.1/ Soit $E$ un ensemble et $\to$ une application de $E^2\to E$.
1.2/ On peut s'amuser à appeler $E$ un ensemble de phrases et $\to$ l'implication.
1.3/ Quand je commence comme ça, on n'est ni sémantique ni syntaxique, mais pour tout dire, "plutôt sémantique", avec un poil de compacité qui va like-syntaxiser les choses derrière.
1.4/ Tel que commencé, on est dans ce que les gens appelle vulgairement "le propositionnel"; ie "que des phrases".
1.5/ Appelons "preuve" dans $E$, une suite finie d'éléments de $E$.
1.6/ Pour une telle preuve $u\in E^n$ ($n$ étant ici vu comme l'ensemble $\{0;..;n-1\}$, appelons "axiome" (ou hypothèse) de $u$ chaque $u_i$ tel que:
a/ $\forall j<i: u_j\neq u_i$
b/ $(u_{i-1} \to u_i) \neq u_{i-2}$
1.7/ Ce que je viens d'écrire traduit le modus ponens dans ce paradigme.
1.8/ Les points 1.5 à 1.7 sont ce qu'on peut appeler la partie "syntaxique" du paradigme.
1.9/ Je passe au "sémantique". Une application $f$ de $E$ dans $F_2$ (le corps à deux éléments: on s'orientera sur la convention que $vrai:=0$ et $faux:=1$) sera appelée un prémodèle. Un prémodèle $f$ est un modèle ssi $\forall x,y$ dans $E: f(x\to y) = f(x)f(y)+f(y)$. Je note $M$ l'ensemble des modèles.
1.10/ Soit $A$ une partie de $E$. On dira même que $P(E)$ est l'ensemble des "théories de $E$".
1.11/ Un théorème de $A$ est un élément $x$ de $E$ qui est le dernier élément d'une preuve dans $E$ dont tous les axiomes sont dans $A$. On note $theo(A)$ l'ensemble des théorèmes de la théorie $A$.
1.12/ Les développements de la logique ont conduit à de gros théorèmes, dont l'incontournable "théorème de complétude". Il dit que (pour les couples $(E,\to)$ vérifiant certaines hypothèses très raisonnables) pour tout $A\subset E$ et pour $x\in E: $
$$ x\in theo(A) \iff \forall f\in M: [(f_{|A} = Constante(0)) \Rightarrow f(x)=0]$$
2.1/ Dans "la vraie vie" mathématique, on ne se contente pas de (a+b) du point 1.6 pour définir le mot preuve. On ajoute un peu de richesse déductive mais le principe reste là.
2.2/ Les théorèmes d'incomplétude de Godel disent que dans le $E$ "qui intéresse tout le monde", aucun théorie récursivement énumérable n'est à la fois complète et différente de $E$, sauf si elle ne contient pas certains axiomes considérés comme des évidences de base triviaux. Ils disent un peu, ils disent qu'il existe une fonction primitive récursive très simple $h$ telle que pour toute $t$ qui décrit une théorie $T$ récursivement énumérable, différente de $E$ et contenant certains axiomes de base, alors $\{g(t); non(g(t))\} \cap T = \emptyset$
2.3/ Il faut que tu saches que tu peux ou bien développer une dextérité en théorie des modèles (branche de la logique), mais tout autant développer des compétences en informatique et ce qu'on appelle la compétence "calculabilité" de base, pour aborder le théorème de Godel et le prouver COMPLTEMENT ET FORMELLEMENT.
2.4/ Le fil semble montrer que tu galères avec le paradigme "modèles", alors, peut-être, tout dépend de ton objectif, peux-tu aussi aller voir du côté, beaucoup plus simple de l'informatique théorique de base pour le prouver.
2.5/ Je te laisse réagir si tu veux pluss.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Dans la mesure où ce fil risque d'être cliqué par des gens qui ne veulent pas forcément entrer dans la technique, je rappelle rapidement comment tout ça marche.
1/ on a découvert dans le courant du 19e siècle que la notion de théorie utilisable par l'humain et de preuve sont simples et programmables.
2/ On se donne une théorie (l'arithmétique de base, sans le schéma de réccurrence, suffit par exemple), assez expressive, on peut y décrire l'informatique (théorique, ie mémoire non limitée, finie, mais non uniformément limitée). On fixe cette théorie dans la suite. De plus, "prouver" veut dire "prouver dans T" dans la suite.
3/ soit alors le programme $a$ qui est tel que pour tout programme $b: [a(b)$ s'arrête sur "Bingo" si et seulement si il existe une preuve que $b(b)$ ne s'arrête pas sur "Bingo" $]$.
4/ On obtient le programme $p:=(a(a))$ tel que $[p$ s'arrête sur Bingo si et seulement si il existe une preuve que $p$ ne s'arrête pas sur "Bingo"$]$
5/ Ce qui prouve le théorème de Godel pour toute théorie qui permet de parler de l'informatique théorique.
6/ La notation $x(y)$ désigne le programme obtenu en lançant le programme $x$ après avoir, d'abord vidé la pile, puis avoir empilé le programme $y$ sur le sommet de la pile.
7/ Pourquoi l'arithmétique SUFFIT à parler de l'informatique théorique?
8/ Réponse: parce qu'elle PEUT PARLER DE SUITES FINIES d'entiers et que c'est suffisant. L'informatique théorique n'est rien d'autre que ce qui arrive aux suites finies d'entiers, décrit avec des quantificateurs ici ou là.
9/ Les noms de suites peuvent être choisis comme suit: $(a,b,c)$ triplet d'entiers.
10/ En effet, l'application de $\N^3$ dans $\N^\N$
$$ (a,b,c) \mapsto (n\mapsto a\ Modulo\ (b+nc))$$
a une image directe dense dans $\N^\N$ doté de la topologie produit de la discrète.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Poirot a écrit:http://www.les-mathematiques.net/phorum/read.php?16,1934124,1937078#msg-1937078
Exercice : notons $Th(\mathbb N)$ la théorie de $\mathbb N$, c'est-à-dire, la construction de l'ensemble $\mathbb N$ ayant été faite, l'ensemble de toutes les formules qui sont vraies dans $\mathbb N$ (au sens de vrai dans cette structure fixée). C'est une théorie complète une fois que l'on a compris les arguments donnés plus haut. Pourtant cette théorie contient la théorie de Peano et donc Gödel nous dit que $TH(\mathbb N)$ est incomplète. Chercher l'erreur dans ce raisonnement. :-D
Je ne suis pas tout à fait sûr de comprendre exactement tout ce qui est dans cette phrase comme il le faut, mais je crois que dans la mesure où je le comprends, c'était exactement ma question du début du fil.
@christophe: je vais prendre du temps pour digérer tout ça. -
@Poirot : oui, c'est exactement ce que je voulais dire.
Histoire de ménager un peu le suspense, au lieu d'écrire : "le raisonnement de Poirot ne marcha pas car $Th(\N)$ est "loin" d'être récursive", j'ai préféré dire à raoul.S de relire l'énoncé du théorème de Gödel... ce qui au final revient au même, puisqu'il a trouvé instantanément. Mais au moins il aura un peu cherché, même s'il lui a suffi de 2/3 clics de souris... -
Pour info, Patrick, quand-même, je signale que le théorème de Godel était potentiellement connu depuis la nuit des temps ou presque mais flirtait avec la frontière conscient/subconsient.
Ca ne nécessite pas de connaissance, mais juste un "esprit philo correct et fin". Je te donne la preuve.
Sans formaliser plus que ça, la phrase "je ne suis pas prouvable" est une phrase parfaitement scientifique. C'est en effet une suite de caractères et sa valeur de vérité dépend de l'appartenance de cette suite de caractère à une ensemble parfaitement technique, celui des phrases prouvables. (Je ne mets pas "prouvable dans T" pour simplifier)
Il n'est pas très difficile de formaliser complètement en 2020, avec juste des bases basiques en informatique.
Historiquement, l'apport de Godel est surtout de le faire avec des + et des × pour entrer à "l'académie des maths numériques bêtes et méchantes", mais comme les gens n'avaient pas conscience de l'évidence de son théorème, il a aussi joué le rôle de fond de faire basculer dans le conscient ce qui auparavant ne l'était pas (et donc de "ridiculiser" gentiment le manque de soins psychanalytiques que s'est offert Hilbert au cours de sa vie).
Mais comme Freud devait vaguement vivre à la même époque...Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
@Christophe : "je signale que le théorème de Godel était potentiellement connu depuis la nuit des temps ou presque mais flirtait avec la frontière conscient/subconsient."
OK.
Mais alors Hilbert devait assez peu flirter avec son subconscient, car si mes infos sont justes il a très mal vécu les théorèmes d'incomplétude, même si, en bon mathématicien, il a finalement accepté sa défaite. En tous cas il ne s'y attendait pas.
Peut-être aurait-il dû consulter Freud avant, mais je ne sais pas si c'eût été possible, il me semble que Freud était mort avant l'apogée de la carrière de Hilbert, mais je peux me tromper... -
Non, je dis des conneries, Freud est mort en 1939, 4 ans avant Hilbert.
Je le situais plus en arrière dans l'histoire, comme quoi il faut se méfier de ses intuitions... -
CC a écrit:Sans formaliser plus que ça, la phrase "je ne suis pas prouvable" est une phrase parfaitement scientifique.
Je ne suis pas d'accord avec le fait que c'est une évidence. Comme la phrase est auto-référente, on peut facilement s'imaginer que son statut est le même que celui du paradoxe de Richard ! L'apport de Gödel c'est d'avoir montré qu'effectivement cette phrase peut être vue comme scientifique, et pas simplement comme "un jeu de mot métathéorique". -
Comme je suis sur mon téléphone je vais suivre ton paradigme. D'un PC, je te répondrai sur un autre versant.
Dans ton paradigme, c'est l'apport de Cantor (ie x|
> f ( x(x) ) ). L'apport de Godel est de donner un sens MATHÉMATIQUE au mot prouvable.
La phrase "je ne suis ni vrai ni insensée" (de Richard) achoppe non pas sur son auto référence mais sur l'absence de définition scientifique du mot vrai.
Exemple "je contiens un nombre pair de lettres" est évaluable.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Etant sur un pc, je ne m'adresse pas qu'à toi Poirot, maintenant, car tu es suffisamment adulte, majeur et vacciné pour te faire une idée propriétaire.
L'important ici est de dire aux gens qu'ils doivent avoir confiance à leur propre réflexion quand ils sont déductifs. Les choses sont sous leurs yeux, point barre. Pas de pudibonderie pénalisante pour la science.
La phrase "je suis fausse" (ou encore mieux psychologiquement, la phrase "j'implique tout") se suffit à elle-même et pas besoin de "consulter des érudits" pour s'interroger sur le trouble qu'elle provoque. C'est une phrase $P$ telle que la langue naturelle l'oblige à vérifier:
$$ P \iff (nonP)$$
et ça n'a rien d'un problème absolu.
Pas plus que ce n'est un problème absolu que d'appuyer sur break après avoir lancé l'exécution du programme
$$a():=a()+1$$
"Calculer" ces activités diverses et variées, les formaliser ne constitue pas un problème.
A l'époque de Cantor-Godel-Hilbert-Freud and Co, ces choses étaient en gestation (à peine quelques centaines d'années plus tôt, on brulait, au sens propre, vivantes des sorcières), et en particulier la dualité, aujourd'hui si appuyée, entre syntaxe et sémantique était très floue.
Dans l'expression $a(b)$ aujourd'hui, la valeur sémantique (le signifié) de $a$ s'applique HELAS à la valeur sémantique de $b$.
C'est pourquoi une sorte de technologie superfétatoire et superficielle oblige le monopole à des experts sur ces questions, et c'est un peu dommage, car ça divise par combien ? 10000? le nombre de pensées qui peuvent s'impliquer dans les débats.
A priori, mais nous n'avons pas habitué les gens au bon système, la bonne façon de procéder aurait dû être:
$$ A_{semantique} (B_{syntaxique})$$
mais les choses ne se sont pas faites ainsi, et donc Godel a pu accéder à la gloire en passant.
Mais n'importe qui peut voir que Cantor (et probablement pas mal des acteurs de la crise des fondements) que l'ensemble
$$\{x\mid Non(Prouvable(x\in x))\}$$
qui a été "tué" par le choix de l'argument de fonction sémantique et non pas syntaxique, était le théorème de Godel tel qu'il se transmet de bouche d'érudit à oreille de béotien dans les cafés où on cause de ce sujet.
L'apport de Godel est par contre IMMENSE, et HISTORIQUE, en ce qu'il a provoqué la prise de conscience que l'ensemble des théorèmes de maths est un ensemble récursivement énumérable (je le dis en langage d'aujourd'hui) et que l'ensemble des preuves de maths est un ensemble PRIMITIF RECURSIF, et même, pour à peine exagérer quasiment l'intersection de DEUX langages algébriques.
Et ça, non seulement ça se dit avec des $+$ et des $\times$, mais en plus ça se dit, bien que longuement, TRES FACILEMENT.
Il faut bien noter (j'ai reçu plus de 30 mails en 30ans de philosophes en herbe ou auto-déclarés ou confirmés qui m'écrivaient à Jussieu pour me proposer des "erreurs" qu'ils prétendaient avoir trouvées dans la preuve du théorème de Godel) que la constance de leur erreur à eux, c'est de ne pas avoir compris ce que je viens de décrire.
Quant à la phrase "je suis fausse" (ou mieux) "je suis fausse ou insensée", il faut bien avoir conscience qu'elle ne constitue EN AUCUN CAS un problème, mais un acquis démontrant qu'il y a des tas de phrases égales à leur négation ou, en tout cas point fixe de tas de fonctions.
Hélas, ces sujets "ne vendent plus", puisque la théorie quantique (dont je rappelle qu'elle produit en quantité industrielle*** de telles phrases, sans besoin d'auto-référer) est passée par là, il y a 100 ans. Mais pourtant, on n'aurait pas dû appeler ça une crise (des fondements) mais de nouveaux théorèmes. qui ne se cantonnent pas à l'absence de surjection de $E$ sur $P(E)$ comme l'a pudiquement filtré le système scolaire jusqu'à bac +2.
***
$$ non(a+(non(a))) = (non(a)) + (non(non(a))) = (non(a)) + a = a+non(a) $$Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Il existe une différence entre
1°) -un banal combinateur de point fixe Y tel que Yf = f(Yf) (après réduction)
2°) -un encodage #: envoyant les termes dans les termes et une procédure A -> A* telle que A(# (x (#x))) = A*(#x) pour tous A,x permettant d'avoir un terme e tel que A(#e)=e (et non pas Ae = e. Prendre e := #A* (#A*)).
De plus les égalités en sont pas "en dur" mais à beta-réduction près puisque le nombre de caractères de chaque terme diffère.Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$. -
@foys, la science est avant tout opératoire (même si je suis platonicien, car pense que ne pas l'être est avant tout, sans sens, plus qu'autre chose), et le platonisme écliptique*** venant au secours ou, à l'opposé, bridant l'opératoire me semble mauvais conseiller.
Point fixe et duplication de ressources sont équi-opératoriellement puissants:
1/ avec $p:=a(a)$ où $\forall x: a(x) = f(x(x))$, tu obtiens $f(p)=p$, comme tu sais, et comme ton évocation de cadage "construit" à la sueur te le donne à la fin
2/ Mais SANS duplication, n'importe quel opérateur de point fixe te donne la duplication comme suit:
Soit $p$ tel que $p = (a,p)$, donc tel que $p=(a,(a,p))$ et via
$f:=[(x,(y,z)) \mapsto ((x,y),z)]$ et
$g:=[(x,y)\mapsto x]$,
tu obtiens $g(f(p)) = (a,a)$ de manière affine (ie sans rien dupliquer**).
*** qui autorise un point fixe pour $u\mapsto (n\mapsto f(u(n-1)))$, mais pas pour d'autres.
** elle s'est faite via la prise d'un point fixe de $x\mapsto (a,x)$, qui est linéaire (pas la prise, mais la fonction)Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Pour les néophytes
J'ai deux euros, donc je peux acheter un croissant
J'ai deux euros, donc je peux acheter un kouin amagn
J'ai deux euros, donc (je peux acheter un croissant et je peux acheter un kouin amagn)
J'ai deux euros, donc je peux acheter un croissant et un kouin amagnAide les autres comme toi-même car ils sont toi, ils sont vraiment toi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 40
+29 Invités