• QUELQUES BRÈVES DE LA GALAXIE

    Lire la suite...


    votre commentaire
  • Georg Cantor (1845 - 1918)

     

    Georg Cantor est célèbre avant tout pour sa construction des Nombres Réels, pour sa Théorie des ensembles, et sa Théorie des infinis. il a fait également des découvertes sur les séries trigonométriques, en Topologie Générale, dans la théorie de la mesure. On peut citer l'ensemble triadique de Cantor, sorte de poussière de points (totalement discontinu, sans points isolés, non dénombrable, de mesure nulle), que l'on pourrait appeler, à la suite de Benoît Mandelbrot, un ensemble fractal.


  • Le comte Alfred Habdank Scarbeck Korzybski (3 juillet 1879 à Varsovie, alors en Russie - 1er 1950 à Sharon, Connecticut) était un philosophe, un ingénieur et un expert des services de renseignements. Il est le fondateur de la sémantique générale, une philosophie de la connaissance remettant en cause les schémas de pensée aristotéliciens toujours en vigueur

  • mathématicien anglais 1702-1761

  • Kurt Gödel (1906 - 1978) )


    Kurt Gödel est né le 28 avril 1906 à Brno, à 180 km au sud-est de Prague (Empire Austro-Hongrois, aujourd'hui situé en république tchèque). Il est le fils cadet de deux enfants de Rudolf et Marianne Gödel, des allemands expatriés travaillant dans l'industrie textile.


    Énoncé simplifié du théorème d'incomplétude


    Dans toute branche des mathématiques suffisamment complexe (par exemple l'arithmétique), il existe une infinité de faits vrais qu'il est impossible de prouver en utilisant la branche des mathématiques en question.

    Bien évidement le théorème tel qu'il a été écrit par Gödel est plus précis, de même que la preuve qu'il en a donné. L'idée de cette preuve est néanmoins accessible, et nous en donnons plus loin une esquisse.


    Qu'a fait Gödel avec son théorème ?


    Jusqu'au début du siècle les mathématiciens étaient persuadés qu'on pouvait, un peu à la manière des écoliers en géométrie, démontrer toutes les vérités mathématiques par déduction.


    Gödel a démontré en 1931 deux résultats mathématiques :



    • Il se peut que dans certains cas, on puisse démontrer une chose et son contraire (inconsistance).
    • Il existe des vérités mathématiques qu'il est impossible de démontrer (incomplétude)

    Le plus célèbre de ces résultats est le second, qu'on appelle théorème d'incomplétude de Gödel.


     


    Une preuve simplifiée du théorème


    Malgré les performances et la diversité des ordinateurs actuels, tous ont un modèle théorique commun appelé machine de Turing. On peut donner à une machine de Turing un programme arbitrairement long, mais évidemment de taille finie, qui répond VRAI ou FAUX à une affirmation qu'on lui donne, sans jamais se tromper.
    La question est:
    Si un humain est capable de savoir si la phrase qu'il donne à la machine est vraie ou fausse, la machine est-elle aussi capable de découvrir la vérité ?


    Gödel donne alors la phrase suivante à la machine:
    "La machine ne répondra jamais VRAI à cette phrase"

    Que fait la machine ?


    • Si elle répond VRAI, elle affirme que "La machine ne répondra jamais VRAI à cette phrase" est une affirmation vraie. Or ce n'est pas le cas, puisqu'elle vient justement de répondre VRAI à la phrase. Si la machine ne se trompe pas, elle ne peut donc pas répondre VRAI.
       
    • Si elle répond FAUX, elle affirme que "La machine ne répondra jamais VRAI à cette phrase" est une affirmation fausse. Or l'affirmation n'est pas fausse puisque la machine vient justement de répondre FAUX. Si la machine ne se trompe pas, elle ne peut donc pas répondre FAUX.

     


    Et nous, pouvons nous répondre à la question ?...
    La phrase dit : "La machine ne répondra jamais VRAI à cette phrase". Nous venons de voir qu'en effet, la machine ne peut pas répondre VRAI. Nous savons donc que cette phrase est une vérité. Pourtant la machine ne pourra pas la découvrir...






    Tout sur le théorème



    La géométrie d'Euclide

    Tous les écoliers le savent, la géométrie est une discipline déductive. Elle se différencie en cela des sciences physiques, par exemple, qui sont une science en partie expérimentale car on peut vérifier la véracité de ce que l'on affirme par l'expérience.


    D'aucun répondront qu'on peut faire de même en géométrie : mesurer un angle, les côtés d'un triangle...Eh bien, oui et non... Ce qui a fait le succès de la géométrie et le malheur de nombreux écoliers depuis les Grecs c'est la méthode axiomatique utilisée par Euclide, qui permet de démontrer en géométrie des théorèmes en utilisant uniquement la logique de l'esprit et des axiomes de base (axiomes d'Euclide par exemple) comme le fameux :


    "Par deux points, on ne mène qu'une droite"


    Ce type de démonstration se passe de vérification par l'expérience. Le côté évidement vrai des axiomes et la logique normalement implacable de la déduction font que le résultat obtenu ne peut être que vrai, ce qui a fait de la géométrie Euclidienne un modèle de connaissance scientifique pendant 2000 ans.


    On pensait encore, il y a 200 ans, que toutes les branches des mathématiques, à l'instar de la géométrie, pouvaient être axiomatisées et qu'on pouvait déduire logiquement de ces axiomes toutes les vérités concernant la discipline en question.


    Mais au 19ème siècle, certains scientifiques ont remplacé un des axiomes d'Euclide :






    "par un point donné, on fait passer exactement une parallèle à une droite donnée"

    par un autre énoncé, comme par exemple celui de Riemann :






    "par un point hors d'une droite, on ne peut faire passer aucune parallèle à cette droite"

    En utilisant le nouveau jeu d'axiomes comme vérités de base, on peut déduire, comme en géométrie Euclidienne, des théorèmes, dont certains seront faux dans notre monde, puisqu'ils sont déduis d'un axiome faux dans notre monde (ce qui n'exclu pas qu'ils soient justes dans un monde imaginaire dans lequel les axiomes seraient vrais).


    Ce phénomène a fait prendre conscience aux mathématiciens que la géométrie était une chose "palpable", dont les affirmations, énoncés et théorèmes n'étaient pas vides de sens, et que ce sens "intuitif" pouvait les gêner dans leur tâche qui consiste à déduire une chose de certaines autres, sans forcément se soucier de la véracité des faits démontrés.
    Or on sait qu'il faut se méfier de l'intuition et du « C'est clair ! » des profs de maths, comme le montre l'exemple suivant dû à Russel :






    Il y a deux sortes d'ensembles, les ensembles normaux, qui ne se contiennent pas eux même, comme l'ensemble des mots de ce texte, et les ensembles non-normaux, qui se contiennent eux même, comme l'ensemble des choses dont on parle dans ce texte (en effet, je viens d'en parler). Considérons à présent N, l'ensemble des ensembles normaux. La question est : N est-il normal ?

    • Si N est normal, alors, il est dans N puisque N est l'ensemble des ensembles normaux. N se contient donc lui-même et par conséquent N est non-normal.
    • Au contraire, si N est non-normal, alors il se contient lui-même, or les éléments de N sont les ensembles normaux, donc N est normal.
    Où est passée l'intuition...?

    La tentative de Hilbert

    Afin de trouver une solution à un certain nombre de ces problèmes, Hilbert a proposé au début du siècle un programme de recherche visant entre autres à formaliser les mathématiques, c'est à dire à définir les termes utilisés de façon non ambigu et sans faire appel à l'intuition.


    Un des buts de Hilbert était d'obtenir des théories formelles en mathématiques, c'est à dire :



    • un ensemble de règles pour écrire les formules
    • un ensemble d'axiomes (formules de base qui représentent ce qu'on juge vrai) écrits dans le système formel
    • un ensemble de règles de transformation qui permettent de passer d'une formule à une autre, c'est à dire de déduire d'un axiome ou d'un théorème, un nouveau théorème

    Les règles doivent être suffisamment précises pour être applicables mécaniquement, par une machine par exemple, sans faire appel à l'intelligence.
    On pourrait ainsi programmer un ordinateur en lui donnant les règles et les axiomes, puis en lui demandant d'appliquer successivement toutes les règles à tous les axiomes, dans un processus éventuellement infini. L'ordinateur serait alors capable de lister tout ce qu'on peut déduire des axiomes, c'est à dire tous les théorèmes possibles de la théorie formelle.
    Imaginons à présent que nous voulions savoir si une certaine formule F est un théorème, c'est à dire si elle peut être déduite des axiomes en utilisant une suite de déductions. Quatre cas peuvent se présenter si nous utilisons l'ordinateur en question :



    1. Il listera la formule F , et pas la formule non F
    2. Il listera la formule non F , et pas la formule F
    3. Il listera la formule F et la formule non F
    4. Il ne listera ni la formule F , ni la formule non F

    Dans le cas 1, cela signifie que la formule F est un théorème. Dans le cas 2, que la formule non F est un théorème. Que dire des autres cas ? Dans le cas 3, on dit que la théorie est inconsistante, c'est à dire qu'on peut à la fois prouver une chose et son contraire. Dans le quatrième cas, on dit que la théorie est incomplète, c'est à dire qu'il existe des choses dont on ne peut savoir si elles sont vraies ou non.


    Un exemple concret de système formel, avec redéfinition des termes consistance et complétude est accessible ici.


    La deuxième partie du programme de Hilbert consistait justement à démontrer que les théories formelles des mathématiques étaient consistantes.


    Si beaucoup de travail a été réalisé en ce qui concerne la formalisation des mathématiques (des théories formelles pour de nombreuses branches des mathématiques ont été développées à partir du 19ème siècle, avant même le programme de Hilbert), il a fallu attendre les résultats de Gödel, assez inattendus, pour répondre entre autres à la deuxième partie du programme.



    La réponse de Gödel

    En 1931, dans un article intitulé "Über formal unentscheidbare Sâtze der Principia Mathematica und verwandter Systeme" (Sur les propositions formellement indécidables des Principia Mathematica et des systèmes apparentés) Gödel a démontré qu'il était impossible de prouver la consistance d'un certain nombre de théories formelles (dont l'arithmétique) en utilisant ces théories, contrairement à ce que semblait croire Hilbert. Ce premier résultat, très inattendu pour l'époque s'est accompagné d'un deuxième, plus célèbre, le théorème d'incomplétude qui énonce que la plupart des théories formelles (dont l'arithmétique), si elles sont consistantes, sont incomplètes, c'est à dire qu'il existe des résultats effectivement vrais qui ne peuvent pas être prouvés dans cette théorie.


    Pour en revenir à notre ordinateur qui déduit des théorèmes, les résultats de Gödel prouvent que pour la plupart des théories formelles, il existe des formules F pour lesquelles l'ordinateur sera confronté au 3ème ou au 4ème cas.


    On pourra en premier lieu consulter une démonstration simplifiée du théorème avant de lire ce qui suit.


    Très basiquement, la démonstration de Gödel a consisté à écrire le paradoxe du menteur (Tous les crétois sont des menteurs, c'est un crétois qui le dit...) en utilisant l'arithmétique. Plus précisément, il a construit une formule de l'arithmétique qui affirme d'elle même qu'elle est indémontrable.


    Le système formel qu'a utilisé Gödel pour sa démonstration est voisin de celui des Principia Mathematica de Whitehead et Russell. Ce système formel permet d'exprimer les relations arithmétiques courantes.
    Nous ne referons pas bien sûr dans la suite la démonstration complète de Gödel qui est longue et difficile, mais nous essaierons d'en indiquer clairement les étapes.

    La numération de Gödel et les métamathématiques

    La première étape a consisté à assigner à chaque symbole du sytème formel un nombre différent. Puis Gödel a trouvé le moyen d'affecter un nombre à chaque formule (en faisant le produit des premiers nombres premiers élevés à la puissance du nombre représentant les symboles qui y figurent), puis à chaque suite de formule.
    L'important est de comprendre qu'un nombre de Gödel étant donné, on peut déterminer si c'est une suite de formules (et si oui de quelles formules elle est composée), une formule (et si oui laquelle) ou un symbole.
    Inversement, étant donné un symbole, une formule ou une suite de formules, on peut facilement calculer le nombre de Gödel associé.


    Tous ces nombre qui représentent des formules ou des suites de formules représentent donc des faits de l'arithmétique, mais nous pouvons aussi nous intéresser à la méta-arithmétique, qui consiste à parler des faits qui concernent l'arithmétique. Par exemple, dire que






    "Pour tout x, il existe y tel que y > 2x"

    est un fait arithmétique, c'est à dire un fait qui concerne les nombres entiers. D'un autre côté, dire que






    La formule "Pour tout x, il existe y tel que y > 2x" est démontrable en arithmétique

    est un fait meta-arithmétiquen, c'est à dire un fait qui concerne l'arithmétique.


    Les formules et suites de formules étant représentés par Gödel sous forme de nombres, celui-ci a ainsi pu exprimer des faits méta-arithmétiques par des formules arithmétiques... Par exemple, dire qu'une formule de nombre de Gödel g1 contient la formule de nombre de Gödel g2 revient plus ou moins, avec la méthode de Gödel à affirmer que g2 est un diviseur de g1, ce qui une propriété arithmétique, exprimant un fait méta-arithmétique.
    Gödel a ainsi réussi à exprimer, en utilisant les nombres de Gödel et l'arithmétique (mais la formule reste assez complexe) que :






    La formule de nombre de Gödel g1 est démontrable par la suite de formules de nombre de Gödel g2.

    Dans la suite, nous appellerons cette formule G.

    La preuve d'incomplétude

    La suite du raisonnement a été de montrer que si G était était démontrable, alors la négation de G le serait aussi, et inversement. On aurait alors la possibilité de démontrer une formule et son constraire, ce qui est la définition de l'inconsistance vue plus haut. Par conséquent, si on suppose que le système formel employé est consistant (i.e. que l'arithmétique est consistante), alors on ne peut pas démontrer la formule G ni son contraire. On dit que G est indécidable. Or, la formule G dit que la formule G est indémontrable (rappellons la formule)






    n : Il n'existe aucun nombre de Gödel qui représente une suite de formule qui soit la démonstration de la formule portant le nombre de Gödel n .

    Cette affirmation métamathématique (disant que G est indémontrable) est manifestement vraie, comme nous venons de le voir. Et elle est representée par une formule arithmétique, selon la methode de Gödel, qui est donc vraie elle aussi...


    Gödel a donc au final construit une fomule arithmétique qui est vraie, et qu'on ne peut pas démontrer en utilisant un système formel de l'arithmétique si celui-ci est consistant.


    En allant un peu plus loin, Gödel a montré que même en posant comme axiome que G soit vraie, on pourrait toujours trouver une formule vraie et indémontrable, ce qui signifie que si l'arithmétique est consistante, non seulement elle est incomplète, mais le sera toujours même si on y ajoute des axiomes supplémentaires.

    Inconsistance de l'arithmétique ?

    Par un raisonnement un peu similaire, Gödel a construit une formule, exprimée dans le système formel qui affirme que :






    Si l'arithmétique est consistante, alors la fomule G est vraie.

    Puis il démontre cette affirmation, toujours en utilisant le système formel. Ceci implique que si on pouvait démontrer dans le système formel, que l'arithmétique est consistante, alors, en utilisant la preuve donnnée par Gödel, il s'en suivrait que G serait démontrable dans le système formel. Or nous venons de voir que ce n'était pas le cas. Par conséquent, c'est qu'il est impossible de démontrer dans le système formel que l'arithmétique est consistante, ce qui a apporté une réponse au problème de Hilbert...






    Suivre le flux RSS des articles
    Suivre le flux RSS des commentaires