Théorèmes de Gödel

Discussions générales concernant les mathématiques et n'entrant pas dans les catégories suivantes.
[participation réservée aux utilisateurs inscrits]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Théorèmes de Gödel

Message non lu par MB »

Gödel a démontré en 1931 deux théorèmes :
  • Théorème d'inconsistance : Il se peut que, dans certains cas, on puisse démontrer une chose et son contraire.
  • Théorème d'incomplétude : Il existe des vérités mathématiques qu'il est impossible de démontrer.
Le second théorème est le plus célèbre cependant c'est le premier théorème que je trouve le plus étonnant, mais je suis très loin d'être un spécialiste de ces théorèmes que je n'ai d'ailleurs jamais croisés durant ma scolarité.

Mon problème concernant le premier théorème (d'inconsistance) semble provenir d'un problème concernant la définition de la notion de vérité. Pour moi, une chose est vraie (modulo un certain nombre d'axiomes) si elle est démontrée à partir de ces axiomes (et des théorèmes déjà déduis des axiomes).

Mais on trouve ici :
La première conséquence de ces théorèmes est que la Vérité ne peut pas être exprimée en terme de démonstrabilité. Une chose prouvable n'est pas nécessairement vraie et une chose vraie n'est pas toujours prouvable. Beaucoup de philisophes ont pensé le contraire et ont essayé de définir la vérité comme étant égale aux choses démontrables. De manière générale, dans quasiment toutes les entreprises intellectuelles conséquentes, on peut exprimer des arguments mathématiques simples et on risque donc de rentrer dans le cadre du théorème de Gödel. Je peux ainsi prétendre des choses fausses sans qu'on ne puisse démontrer le contraire.

De la même manière, je peux prétendre des choses vraies sans pouvoir me justifier par une démonstration. De la même manière que l'ensemble des vérités est plus important que l'ensemble de ce qui est démontrable, la réalité est plus importante que l'ensemble des connaissances possibles. Contrairement aux enseignements de nombreux philosophes, être raisonné n'est pas simplement une question de règles. La raison est créative et originale. Pour trouver des vérités dans un système donné, il faut pouvoir s'en extraire et pour cela il faut une raison qui soit capable, non pas de simplement rajouter des axiomes à un système, mais d'en créer un nouveau dans lequel l'ancienne vérité indémontrable deviendra au contraire tout à fait démontrable.
Avec tout ça, je ne comprend pas comment la 'vérité' est définie. De plus, si quelqu'un à un exemple illustrant le théorème d'inconsistance ...
Dernière modification par MB le dimanche 12 juin 2005, 23:15, modifié 1 fois.
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Nightmare

Message non lu par Nightmare »

Bonjour MB :)

Je suis justement en train de lire un livre sur ce fameux théorème de Godël (du moins, fameux pour les logiciens).

Jusqu'a ce que Gödel surprenne tout le monde par ses deux théorèmes , les mathématiciens étaient persuadés qu'en mathématique, tant que l'on disposait d'un systéme formel (ie d'un systéme muni d'axiomes et de régles d'inférences qui permettent de transformer une formule en une autre), il était possible de prouver par raisonnement déductif tout les théorémes mathématiques (ou leur négation). Ils ont nommé ça la complétude mathématique. De même, ils crurent jusque là que toute formule mathématique était soit vraie ou soit fausse et que du fait de la complétude, on pouvait démontrer l'un des deux fait mais pas les deux. On a nommé ça la consistance.

Notamment, en géométrie qui est la science déductive par excellence, on pensait que, de part les axiomes d'Euclide et par les régles de logique usuelle, on pouvait tout démontrer, jusqu'a ce que survint Riemann qui prouva qu'il était impossible de démontrer grace à ces axiomes que part un point arbitraire on ne pouvait mener qu'une parallèle à une droite donnée.

C'était un choc pour les mathématiciens qui jusque là ne pensait pas qu'il était possible de démontrer si une formule était démontrable ou pas, et d'autre part, ils se sont rendu compte que tout n'était pas démontrable dans le systéme formel de géométrie.

C'est alors que surgit Gödel et qui mis en forme le théorème suivant répondant aux interrogations des mathématiciens :
"Dans toute branche mathématique suffisament complexe et contenant le language d'arithmétique, il existe une formule F dont ni elle , ni sont contraire ne sont démontrable dans cette même branche" (c'est une version simplifié de l'énoncé exact du théorème qui est plus compliqué).
Ce théorème fut appellé théorème d'incomplétude de Gödel et eut un réel impact dans la logique mathématique.

Voici un exemple d'inconsistance et d'incomplétude en même temps dût à Russel :

-------------------------------------------

Il existe deux types d'ensembles :

1) Les ensembles dit normaux, qui ne se contiennent pas eux même (exemple : l'ensemble des hommes qui n'est pas un homme),
2) Les ensembles non-normaux, qui se contiennent eux même (exemple : l'ensemble des idées abstraites qui est une idée abstraites ;))

Soit N l'ensemble des ensembles normaux : N est-il normal ou non-normal ?

A) Supposons N normal, alors il se contient lui même puisque c'est l'ensemble des ensembles normaux, ce qui est absurde puisque s'il est normal il ne se contient pas lui même ...
B) Supposons N non-normal, alors il se contient lui même, or, comme c'est l'ensemble des ensembles normaux, si il se contient lui même alors il est normal ce qui est absurde puisqu'il est non-normal ...

Alors , quel type d'ensemble est N ?

-------------------------------------------

D'aprés l'incomplétude et l'inconsistance de Gödel, il est impossible d'apporter une réponse à cette question.

Pour aller un peu plus loin mais je ne m'attarde pas trop sur le sujet que je vais aborder car je ne m'y connais pas trop, Russel a répondu lui même à son paradoxe en inventant une théorie qu'il appella théorie simple des types et dont l'élément principal était le méta-language.
Dans ce méta-language, on parle des choses d'un domaine sans parler du domaine lui même.
Exemple, dans le language formel on dira : La neige est blanche, alors que dans le méta-language on dira : La neige est blanche est une phrase vraie.
Ainsi, selon cette théorie de nouveau language, aucun ensemble ne peut se contenir lui-même.

Voila à peu prés le résumer de ce que je sais à ce sujet.

:)
Jord
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Merci pour ces remarques, mais il y a toujours quelque chose qui m'échappe.
Nightmare a écrit :Soit N l'ensemble des ensembles normaux : N est-il normal ou non-normal ?
On considère (P) la proposition "N est normal" et donc (non P) correspond à "N est non-normal". Dans ton exemple, tu montres que (P) implique (non P) et que (non P) implique (P) et donc que (P) est équivalent à (non P). Par contre, ni (P) ni (non P) ne sont démontrées. Si l'on suppose la complétude alors en effet, on aura un exemple d'inconsistance (puisque par complétude soit (P) soit (non-P) est démontrable et vraie et puisqu'il y a équivalence, on a bien inconsistance). Mais justement, il n'y a pas complétude. Cet exemple d'inconsistance ne me satisfait donc pas trop, mais il est fort possible que quelquechose m'échappe.

De plus, il reste le problème de la définition de N en tant qu'ensemble. Un tel 'ensemble' n'est pas un ensemble en se basant sur la Théorie axiomatique des ensembles même si il est parfaitement défini pour la Théorie naïve des ensembles. D'ailleurs, j'aimerais bien savoir quel axiome interdit la définition d'un tel ensemble (je pense que c'est l'axiome du choix mais je ne suis pas certain).
Nightmare a écrit : Ainsi, selon cette théorie de nouveau language, aucun ensemble ne peut se contenir lui-même.
Oui, cela confirme bien le problème.
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Nightmare

Message non lu par Nightmare »

En fait , c'est vrai que ce n'est pas une preuve d'inconsistance et d'incomplétude en même temps , mais selon comment on le voit , il prouve soit l'inconsistance , soit l'incomplétude .

En effet , on peut considérer que dans l'exercice on a montré que N était normal et non-normal en même temps => Inconsistance
Mais de l'autre côté , on a aussi montré qu'il était impossible de démontrer que N était normal ou non-normal => Incomplétude

C'est pour cela que je disais que ce paradoxe énoncait bien les deux théorémes , car selon comment on le prend , on peut conclure sur la nature du probléme grace aux deux théorèmes de Gödel .
Mais il est vrai que comme tu le dis , il ne prouve pas l'inconsistance et l'incomplétude en même temps .


Pour ce qui est de ta deuxiéme question de l'ensemble , je ne sais pas ... je n'ai pas trop travaillé sur ces deux théories des ensembles . Je vais essayer de lire les liens que tu m'as donné , je vais aussi essayer de finir le livre sur Gödel , si j'ai d'autres informations interressantes je te les rapporterais

:)
Jord
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Nightmare a écrit :En effet , on peut considérer que dans l'exercice on a montré que N était normal et non-normal en même temps => Inconsistance
C'est là ou je ne suis pas d'accord. D'après moi, l'exercice prouve uniquement que si N est normal, alors il est non-normal et réciproquement. Par contre, on n'a prouvé la véracité d'aucune de ses deux propositions. En cas d'incomplétude, il est possible qu'aucune des deux propositions ne soit démontrable (et cela semble justement être le cas).

Note : Je trouve que ce document, concernant les théorèmes de Gödel, est assez bien fait tout en étant assez poussé dans sa seconde partie (presque illisible d'ailleurs).
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Nightmare

Message non lu par Nightmare »

l'exercice prouve uniquement que si N est normal, alors il est non-normal et réciproquement
Oui , mais en suivant le raisonnement par l'absurde alors on tire les conclusions que je donne .

En effet , l'exercice montre :
1)$\rm (N\;normal)\;\Rightarrow\;(N\;non-normal)$ : Absurde . On en déduit par ce raisonnement ab absurdum que N est non-normal
mais aussi :
2)$\rm (N\;non-normal)\;\Rightarrow\;(N\;normal)$ : Absurde . Ainsi ab absurdum N est normal

On en a bien conclut que N était normal et que N était non-normal non ?

Je l'ai dit , c'est une question de voir les choses

:)
Jord
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Oui, mais le raisonnement par l'absurde est il viable dans un système non consistant ?
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Nightmare

Message non lu par Nightmare »

Oui , pourquoi ne marcherait-il pas ?
Nous travaillons dans le systéme formel F de logique (logique de Boole) dans lequel le raisonnement par l'absurde est une régle d'inférence .
Si le raisonnement par l'absurde ne s'appliquait pas à une formule d'une théorie inconsistante S , cela voudrait dire que la théorie ne fait pas partie de F .
Mais si S ne fait pas partie de F , dans ce cas là que signifie l'inconsistance de S ? En effet , ce n'est parcequ'une théorie est inconsistance ou incompléte qu'elle ne fait pas partie du systéme formel , bien au contraire , je recite le théorème d'incomplétude version simplifiée :
Dans toute branche mathématique suffisament complexe et contenant le language d'arithmétique, il existe une formule F dont ni elle , ni sont contraire ne sont démontrable dans cette même branche
On ne dit d'une théorie qu'elle est inconsistante ou incompléte que sur un systéme (ou branche mathématique) , ce qui signifie qu'elle appartient bien à cette branche

Je ne sais pas si j'ai été trés clair ...

:roll:
Jord
Nightmare

Message non lu par Nightmare »

J'ai oublié de réagir :
MB a écrit :Oui, mais le raisonnement par l'absurde est il viable dans un système non consistant ?
Dans ce cas là , on ne pourrait utiliser le raisonnement par l'absurde dans aucun exercice d'arithmétique , celle-ci étant inconsistante ...

:roll:
Jord
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Nightmare a écrit :
MB a écrit :Oui, mais le raisonnement par l'absurde est il viable dans un système non consistant ?
Dans ce cas là , on ne pourrait utiliser le raisonnement par l'absurde dans aucun exercice d'arithmétique , celle-ci étant inconsistante ...
Oui, en effet. Cela me posait problème car ce principe est basé sur le fait : "si ce n'est pas faux, c'est que c'est vrai". Or dans un système non complet, on peut démontrer une chose et son contraire. J'avais ainsi déduit qu'une chose pouvait être vraie et fausse mais c'est la que je dois me tromper depuis le début.
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Nightmare

Message non lu par Nightmare »

Oui , ne pas oublier que l'arithmétique est aussi incompléte .

Maintenant , que penser de la géométrie ? Compléte ? incompléte ? consistante ? inconsistante ?

:)
Jord
@l

Message non lu par @l »

Salut,

en ce qui concerne tous ces problemes, voila ce qu'on peut dire.

Si on considere une theorie $T$ du premier ordre dans un langage donne et $F$ une formule close dans ce langage alors:
  • soit $T$ satisfait $F$
  • soit $T$ satisfait non- $F$
  • soit $T$ ne satisfait ni n'infirme $F$
Dans ce dernier cas, on dit que $F$ est indecidable pour $T$. Si une theorie $T$ n'a que des formules decidables, $T$ est complete.

Ainsi, par exemple, Godel a prouve que l'arithmetique de Peano (et j'insiste la-dessus) est incomplete.
$ZF$, la theorie des ensembles, est incomplete. Un exemple celebre de formule indecidable est l'Axiome du Choix.

La geometrie reelle est complete; c'est un resultat tres important. Il existe meme un algorithme qui permet de dire automatiquement si une formule est vraie ou pas.

La theorie des corps algebriquement clos de caracteristique donnee est complete.

@l
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

@l a écrit :Si on considere une theorie $T$ du premier ordre dans un langage donne et $F$ une formule close dans ce langage alors:
  • soit $T$ satisfait $F$
  • soit $T$ satisfait non- $F$
  • soit $T$ ne satisfait ni n'infirme $F$
Je ne connais pas bien le vocabulaire utilisé (théorie du premier ordre, formule close, langage) mais je suppose que "$T$ satisfait $F$" signifie que l'on peut prouver $F$ en utilisant les propriétés (et les axiomes) de cette théorie $T$. On ne peut donc pas avoir :
  • $T$ satisfait $F$ et non-$F$ (inconsistance ?)
Dernière modification par MB le lundi 18 juillet 2005, 17:11, modifié 1 fois.
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
@l

Message non lu par @l »

Oui, tout a fait; c'est meme la defintion de l'inconsistance.

@l
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

@l a écrit :Oui, tout a fait; c'est meme la defintion de l'inconsistance.
Donc c'est cela qui me pose problème. Si on peut prouver une chose et son contraire, cela signifie que F et non-F peuvent être vraies toutes les deux ? Un exemple pour que je comprenne mieux ?
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Zaim KHELIFI

Message non lu par Zaim KHELIFI »

Si je ne me trompe pas, il y a une relation entre le théorème de Gödel et la notion de "degré de vérité" d'une proposition.
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Zaim KHELIFI a écrit :Si je ne me trompe pas, il y a une relation entre le théorème de Gödel et la notion de "degré de vérité" d'une proposition.
Tu peux en dire plus aue sujet de cette notion ?
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
Jedai

Message non lu par Jedai »

Théorème d'inconsistance : Il se peut que, dans certains cas, on puisse démontrer une chose et son contraire.
Ce n'est pas du tout ce que dit le théorème d'inconsistance étant donné qu'il s'agit là d'une évidence : il suffit de prendre un système formel dont les axiomes sont trivialement contradictoire...

Ce qu'a prouvé Gödel, c'est que pour tout système formel capable de décrire les entiers naturels, on ne peut prouver que le système est cohérent (ou consistant) à l'intérieur de ce système. Rien n'empèche de démontrer cette cohérence en sortant de ce système formel, heureusement ! (On peut prouver l'arithmétique de Peano en employant un modèle par exemple)

--
Jedaï
MB
Administrateur
Administrateur
Messages : 8058
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant
Contact :

Message non lu par MB »

Jedai a écrit :
Théorème d'inconsistance : Il se peut que, dans certains cas, on puisse démontrer une chose et son contraire.
Ce n'est pas du tout ce que dit le théorème d'inconsistance étant donné qu'il s'agit là d'une évidence : il suffit de prendre un système formel dont les axiomes sont trivialement contradictoire...
Oui c'est très approximatif, mais le "dans certain cas" est là pour éviter ce genre de chose. Je t'accorde que c'est 'énoncé' n'a que peu de sens.
Jedai a écrit :Ce qu'a prouvé Gödel, c'est que pour tout système formel capable de décrire les entiers naturels, on ne peut prouver que le système est cohérent (ou consistant) à l'intérieur de ce système. Rien n'empèche de démontrer cette cohérence en sortant de ce système formel, heureusement ! (On peut prouver l'arithmétique de Peano en employant un modèle par exemple)
Merci pour cette précision et bienvenu sur ce forum.

En tant que novice ce qui me pose problème c'est les différences qui peuvent exister entre les notions de vérité et de prouvabilité ! Tu peux m'en dire plus ?
MB. (rejoignez pCloud et bénéficiez de 10Go de stockage en ligne gratuits)
Pas d'aide en message privé. Merci de consulter ce sujet avant de poster votre premier message.
icare_1er

Message non lu par icare_1er »

A titre indicatif, l'hypothèse du continu de Cantor était à la fois vraie et fausse, c'est d'ailleurs ce qui l'a rendu fou.

Plus tard, Gödel et un autre mathematicien ont montré que cette hypothèse était conforme au systeme ZF et que sa négation aussi, ne violait pas le système ZF.
D'ou l'idée de rajouter des axiomes pour statuer.
Répondre