Preuve d'impossibilité

En mathématiques, une preuve d'impossibilité est une preuve qui démontre qu'un problème particulier ne peut pas être résolu comme décrit dans l'énoncé, ou qu'un ensemble particulier de problèmes ne peut pas être résolu en général. Un tel cas est également connu sous le nom de preuve négative, preuve d'un théorème d'impossibilité ou résultat négatif. Les preuves de l’impossibilité sont souvent les résolutions de décennies ou de siècles de recherche pour tenter de trouver une solution, avant finalement d'établir qu’il n’en existe pas. Prouver que quelque chose est impossible est généralement beaucoup plus difficile que la tâche inverse, car il est souvent nécessaire de développer une preuve qui fonctionne en général, plutôt que de simplement montrer un exemple particulier. Les théorèmes d'impossibilité peuvent généralement être exprimés sous forme de propositions existentielles négatives ou de propositions universelles en logique.

L’irrationalité de la racine carrée de 2 est l’une des plus anciennes preuves négatives. Elle montre qu'il est impossible d'exprimer la racine carrée de 2 comme un rapport de deux nombres entiers. Une autre preuve conséquente de l'impossibilité fut la preuve de Ferdinand von Lindemann en 1882, qui montra que le problème de la quadrature du cercle ne peut pas être résolu parce que le nombre π est transcendantal (c'est-à-dire non algébrique), et que seul un sous-ensemble des nombres algébriques peut être construit à la règle et au compas. Deux autres problèmes classiques – la trisection d'un angle quelconque et la duplication du cube – se sont également révélés impossibles au XVI^e siècle, et tous ces problèmes ont donné lieu à des recherches sur des structures mathématiques plus complexes.

Un problème apparu au XVI^e siècle consistait à établir une formule générale utilisant des radicaux pour exprimer la solution de toute équation polynomiale de degré k ≥ 5 fixe. Dans les années 1820, le théorème d'Abel-Ruffini (également connu sous le nom de théorème d'impossibilité d'Abel ) a montré que cela était impossible, en utilisant des concepts tels que les groupes résolubles de la théorie de Galois, un nouveau sous-domaine de l'algèbre abstraite.

Certaines des preuves négatives les plus importantes trouvées au XX^e siècle sont celles liées à l'indécidabilité, qui montraient qu'il existe des problèmes qui ne peuvent être résolus dans le cas général par aucun algorithme, l'un des plus importants étant le problème de l'arrêt. Les théorèmes d'incomplétude de Gödel sont d'autres exemples qui ont révélé les limites fondamentales de la prouvabilité des systèmes formels.

Dans la théorie de la complexité informatique, des techniques comme la relativisation (l'ajout d'un oracle) permettent d'obtenir des preuves d'impossibilité « faibles », dans la mesure où les techniques de preuves qui ne sont pas affectées par la relativisation ne peuvent pas résoudre le problème P contre NP. Une autre technique est la preuve de complétude pour une classe de complexité, qui fournit la preuve de la difficulté des problèmes en montrant qu'ils sont tout aussi difficiles à résoudre que n'importe quel autre problème de la classe. En particulier, un problème complet est insoluble si l’un des problèmes de sa classe l’est.

Types de preuves

Par contradiction

Un autre type de preuve par contradiction est la preuve par descente, qui procède d'abord en supposant que quelque chose est possible, comme une solution entière positive à une classe d'équations, et que par conséquent il doit y avoir une plus petite solution (par le théorème de Zermelo ). À partir de la supposément plus petite solution, il est ensuite démontré qu'une solution plus petite peut être trouvée, contredisant la prémisse selon laquelle la première solution était la plus petite possible, montrant ainsi que la prémisse originale selon laquelle une solution existe doit être fausse.

Par descente

L'un des types de preuve négatives les plus utilisés est la preuve par contraposée. Ce type de preuve fonctionne en partant d'une proposition, telle qu'une solution à une classe particulière d'équations, est supposée être vraie, puis par déduction, on établit que deux choses mutuellement contradictoires sont vraies simultanément, comme par exemple un nombre étant à la fois pair et impair ou à la fois négatif et positif. Puisque la contradiction découle de l’hypothèse initiale, cela signifie que la prémisse supposée est nécessairement impossible.

Types de réfutation

Il existe deux méthodes alternatives pour réfuter une conjecture selon laquelle quelque chose est impossible : par contre-exemple (preuve constructive) et par contradiction logique (preuve non constructive).

Le moyen évident de réfuter une conjecture d’impossibilité est de fournir un seul contre-exemple. Par exemple, Euler a proposé qu'au moins n puissances n^ièmes différentes soient nécessaires pour totaliser encore une n^ième puissance. La conjecture a été réfutée en 1966, avec un contre-exemple impliquant une somme de seulement quatre puissances cinquièmes différentes égalant une autre puissance cinquième :

27⁵ + 84⁵ + 110⁵ + 133⁵ = 144⁵.

La preuve par contre-exemple est une forme de preuve constructive, dans la mesure où un objet réfutant l'affirmation est exposé. En revanche, une preuve non constructive d'une affirmation d'impossibilité procéderait en montrant qu'il est logiquement contradictoire que tous les contre-exemples possibles soient invalides : au moins un des éléments d'une liste de contre-exemples possibles doit effectivement être un contre-exemple valide à la conjecture d'impossibilité. Par exemple, une conjecture selon laquelle il est impossible qu'une puissance irrationnelle élevée à une puissance irrationnelle soit rationnelle a été réfutée, en montrant que l'un des deux contre-exemples possibles doit être un contre-exemple valide, sans montrer lequel il s'agit.

Preuve pythagoricienne de l'existence de nombres irrationnels

La preuve par Pythagore vers 500 BCE a eu un effet profond sur les mathématiques. Elle montre que la racine carrée de 2 ne peut pas être exprimée comme le rapport de deux nombres entiers. La preuve a divisé « les nombres » en deux ensembles distincts : les nombres rationnels et les nombres irrationnels. Cette bifurcation a été utilisée par Cantor dans son argument de la diagonale, qui à son tour a été utilisée par Turing dans sa preuve que l' Entscheidungsproblem, le problème de décision de Hilbert, est indécidable.

« Il est inconnu quand, ou par qui, le "théorème de Pythagore" a été découvert. La découverte a difficilement pu être faire par Pythagore en personne, mais elle a certainement eu lieu dans son école. Pythagore a vécu autour de 570–490 BCE. Démocrité, né vers 470 BCE, a écrit Des droites et solides irrationnels ... »

— Heath

Des démonstrations ont suivi pour diverses racines carrées des nombres premiers jusqu'à 17.

Il y a un passage célèbre du Théétète de Platon dans lequel il est dit que Théodore (le professeur de Platon) a prouvé l'irrationalité de

${\sqrt {3}},{\sqrt {5}},...,$

en prenant tous les cas séparés jusqu'à la racine de 17 pieds carrés ... .

Il existe maintenant une preuve plus générale que :

La m-ième racine d'un entier N est irrationnelle, à moins que N ne soit la m-ième puissance d'un entier n.

Autrement dit, il est impossible d’exprimer la racine m-ième d’un entier N comme le rapport ^a⁄_b de deux entiers a et b, qui ne partagent aucun facteur premier commun sauf dans les cas où b = 1.

Constructions impossibles recherchées par les Grecs antiques

Trois questions célèbres de la géométrie grecque étaient de savoir comment :

1. diviser par 3 un angle donné uniquement à la règle et au compas,
2. construire un cube de volume égal au double du volume d'un cube donné,
3. construire un carré d'aire égale à celle d'un cercle donné.

Pendant plus de 2000 ans, des tentatives infructueuses ont été faites pour résoudre ces problèmes ; enfin, au XIX^e siècle, il a été prouvé que les constructions souhaitées sont logiquement impossibles.

Un quatrième problème des Grecs antiques était de construire un polygone équilatéral avec un nombre n de côtés spécifié, au-delà des cas basiques n = 3, 4, 5, 6 qu'ils savaient construire.

Tous ces problèmes sont liés à la construction euclidienne, et les constructions euclidiennes ne peuvent être réalisées que si elles impliquent uniquement des nombres constructibles (par définition de ces derniers). Les nombres irrationnels peuvent être euclidiens. Un bon exemple est la racine carrée de 2 (un nombre irrationnel). Il s’agit simplement de la longueur de l’hypoténuse d’un triangle rectangle dont les apothèmes mesurent chacune une unité de longueur et peut être construit avec une règle et un compas. Mais il a été prouvé des siècles après Euclide que les nombres euclidiens ne peuvent impliquer aucune opération autre que l’addition, la soustraction, la multiplication, la division et l’extraction de racines carrées.

Trisection d'angle et duplication du cube

Les deux problèmes de la trisection de l'angle et de la duplication du cube nécessitent d'extraire des racines cubiques, qui ne sont pas constructibles.

Quadrature du cercle

$\pi$ n'est pas un nombre euclidien ... et donc il est impossible de construire, par les méthodes euclidiennes, une longueur égale à la circonférence d'un cercle de diamètre unité

Il existe une preuve démontrant que tout nombre euclidien est un nombre algébrique – un nombre qui est la solution d’une équation polynomiale. Par conséquent, parce que $\pi$ a été prouvé en 1882 comme étant un nombre transcendantal et donc par définition pas un nombre algébrique, ce n'est pas un nombre euclidien. Ainsi, la construction d’une longueur $\pi$ à partir d'un cercle unité est impossible, et le cercle ne peut pas être quadrillé.

Construire un n -gone régulier

Le théorème de Gauss-Wantzel a montré en 1837 que la construction d'un n-gone régulier est impossible pour la plupart des valeurs de n.

Postulat des parallèles d'Euclide

« Richard's paradox ... is as follows. Consider all decimals that can be defined by means of a finite number of words [“words” are symbols; boldface added for emphasis]; let E be the class of such decimals. Then E has $\aleph _{0}$ [an infinite number of] terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let X be a number defined as follows [Whitehead & Russell now employ the Cantor diagonal method].
If the n-th figure in the n-th decimal is p, let the n-th figure in X be p + 1 (or 0, if p = 9). Then X is different from all the members of E, since, whatever finite value n may have, the n-th figure in X is different from the n-th figure in the n-th of the decimals composing E, and therefore X is different from the n-th decimal. Nevertheless we have defined X in a finite number of words [i.e. this very definition of “word” above.] and therefore X ought to be a member of E. Thus X both is and is not a member of E. »

Le postulat des parallèles des Éléments d'Euclide équivaut à l'affirmation selon laquelle, étant donné une droite et un point qui ne se trouve pas sur cette droite, une seule parallèle à la droite peut être tracée par ce point. Contrairement aux autres postulats, celui-ci était considéré comme moins évident. Nagel et Newman soutiennent que cela peut être dû au fait que le postulat concerne des régions de l'espace « infiniment éloignées » ; en particulier, les lignes parallèles sont définies comme ne se rencontrant même pas « à l'infini », contrairement aux asymptotes. Ce manque perçu de preuves a conduit à se demander si cela pouvait être prouvé à partir des autres axiomes et postulats euclidiens. Ce n'est qu'au XIX^e siècle que l'impossibilité de déduire le postulat parallèle des autres a été démontrée dans les travaux de Gauss, Bolyai, Lobatchevski et Riemann. Ces travaux ont montré que l'axiome des parallèles peut par ailleurs être remplacé par des alternatives, permettant la construction de géométries non euclidiennes.

Nagel et Newman considèrent la question soulevée par le postulat parallèle comme «... peut-être le développement le plus significatif dans ses effets à long terme sur l'histoire mathématique ultérieure». En particulier, ils considèrent que son résultat est « de la plus haute importance intellectuelle », car il montre qu'« on peut prouver l' impossibilité de prouver certaines propositions [dans ce cas, le postulat des parallèles] au sein d'un système donné [dans ce cas, les quatre premiers postulats d'Euclide]."

Grand théorème de Fermat

Le dernier théorème de Fermat a été conjecturé par Pierre de Fermat dans les années 1600 et énonce l'impossibilité de trouver des solutions en nombres entiers positifs pour l'équation : $x^{n}+y^{n}=z^{n}$ avec $n>2$. Fermat lui-même a donné une preuve pour le n = 4 cas utilisant sa technique de descente infinie, et d'autres cas particuliers ont été prouvés par la suite, mais le cas général n'a été prouvé qu'en 1994 par Andrew Wiles.

Paradoxe de Richard

Ce paradoxe profond présenté par Jules Richard en 1905 a inspiré les travaux de Kurt Gödel et d'Alan Turing. Une définition succincte se trouve dans Principia Mathematica :

Kurt Gödel considérait sa preuve comme « une analogie » du paradoxe de Richard, qu'il appelait « l'antinomie de Richard » .

Alan Turing a construit ce paradoxe avec une machine et a prouvé que cette machine ne pouvait pas répondre à une question simple : cette machine sera-t-elle capable de déterminer si une machine (y compris elle-même) se retrouvera piégée dans une « boucle infinie » improductive (c'est-à-dire qu'elle ne parvient pas à continuer son activité du nombre diagonal) ?

Incomplétude des systèmes axiomatiques : la preuve de Gödel

Pour citer Nagel et Newman (p. 68), "L'article de Gödel est difficile. Quarante-six définitions préliminaires, ainsi que plusieurs théorèmes préliminaires importants, doivent être maîtrisés avant d'arriver aux principaux résultats". En fait, Nagel et Newman avaient besoin d’une introduction de 67 pages pour leur exposé de la preuve. Mais si le lecteur se sent assez fort pour s'attaquer à l'article, Martin Davis observe que « cet article remarquable n'est pas seulement un jalon intellectuel mais il est écrit avec une clarté et une vigueur qui en font un plaisir à lire » (Davis dans Undecidable, p. 4). Il est recommandé^{[Par qui ?]} que la plupart des lecteurs voient Nagel et Newman en premier.

Gödel a prouvé, dans ses propres mots :

"Il est raisonnable... de faire la conjecture que... [les] axiomes [des Principia Mathematica et Peano ] sont... suffisants pour trancher toutes les questions mathématiques qui peuvent être formellement exprimées dans les systèmes donnés. Dans ce qui suit on montrera que ce n'est pas le cas, mais plutôt que... il existe des problèmes relativement simples de la théorie des nombres entiers ordinaires qui ne peuvent être résolus sur la base des axiomes" (Gödel dans Undecidable, p. 4).

Gödel a comparé sa preuve à l'« antinomie de Richard » (une « antinomie » est une contradiction ou un paradoxe) :

« L'analogie de ce résultat avec l'antinomie de Richard est immédiatement évidente ; il existe également une relation étroite [14] avec le paradoxe du menteur (note de bas de page 14 de Gödel : toute antinomie épistémologique peut être utilisée pour une preuve similaire d'indécidabilité)... Ainsi, nous avons devant nous une proposition qui affirme sa propre non-démontrabilité [15] (note de bas de page 15 : Contrairement aux apparences, une telle proposition n'est pas circulaire, car, pour commencer, elle affirme la non-démontrabilité d'une formule bien définie)".

Problème d'arrêt : la première preuve de Turing

• L' Entscheidungsproblem, le problème de décision, fut résolu pour la première fois par Church en avril 1935 et précéda Turing de plus d'un an, l'article de Turing étant reçu pour publication en mai 1936.
• La preuve de Turing est rendue difficile par le nombre de définitions requises et sa nature subtile.
• La première preuve de Turing (sur trois) suit le schéma du paradoxe de Richard : la machine informatique de Turing est un algorithme représenté par une chaîne de sept lettres dans une « machine informatique ». Son « calcul » consiste à tester toutes les machines informatiques (y compris elle-même) pour les « cercles » et à former un nombre diagonal à partir des calculs des machines informatiques non circulaires ou « réussies ». Il le fait, en commençant dans l'ordre à partir de 1, en convertissant les nombres (base 8) en chaînes de sept lettres à tester. Lorsqu'il arrive à son propre numéro, il crée sa propre chaîne de lettres. Il décide qu'il s'agit de la chaîne de lettres d'une machine performante, mais lorsqu'il essaie d'effectuer le calcul de cette machine ( le sien ), il se verrouille dans un cercle et ne peut pas continuer. On arrive ainsi au paradoxe de Richard.

Un certain nombre de preuves d'indécidabilité similaires sont apparues peu avant et après la preuve de Turing :

1. Avril 1935 : Preuve d'Alonzo Church (« Un problème insoluble de la théorie élémentaire des nombres »). Sa preuve consistait à "... proposer une définition de la calculabilité effective... et à montrer, au moyen d'un exemple, que tous les problèmes de cette classe ne sont pas résolubles" (Indécidable p. 90))
2. 1946 : Problème de correspondance de Post (cf Hopcroft et Ullman p. 193 et suiv., p. 407 pour la référence)
3. Avril 1947 : Preuve d'Emil Post ( Insolvabilité récursive d'un problème de Thue ) (Indécidable p. 293). Ceci est depuis devenu connu sous le nom de "Le problème des mots de Thue" ou "Le problème des mots de Thue" (Axel Thue a proposé ce problème dans un article de 1914 (cf. Références à l'article de Post dans Undecidable, p. 303)).
4. Théorème de Rice : une formulation généralisée du deuxième théorème de Turing (cf Hopcroft et Ullman p. 185 et suivants)
5. Théorème de Greibach : indécidabilité en théorie du langage (cf Hopcroft et Ullman p. 205ff et référence à la p. 401 ibid : Greibach [1963] « L'indécidabilité du problème d'ambiguïté pour les grammaires linéaires minimales », Information and Control 6 : 2, 117-125, également référence à la p. 402 ibid : Greibach [1968] « Une note sur les propriétés indécidables des langages formels », Math Systems Theory 2 :1, 1–6).
6. Questions du pavage de Penrose.
7. Question des solutions pour les équations diophantiennes et la réponse qui en résulte dans le théorème MRDP ; voir infra

Compressibilité des chaînes : la preuve de Chaitin

Pour une exposition adaptée aux non-spécialistes, voir Beltrami p. 108 et suiv. Voir également Franzen chapitre 8 pp. 137-148, et Davis p. 263-266. La discussion de Franzén est nettement plus compliquée que celle de Beltrami et se penche sur Ω — la soi-disant « probabilité d'arrêt » de Gregory Chaitin. L'ancienne approche de Davis aborde la question du point de vue d'une machine de Turing. Chaitin a écrit un certain nombre de livres sur ses efforts et leurs retombées philosophiques et mathématiques.

Une chaîne est appelée (algorithmiquement) aléatoire si elle ne peut être produite à partir d’un programme informatique plus court. Bien que le plupart des chaînes soient aléatoires, aucune chaîne en particulier ne peut être prouvée ainsi, à l'exception d'un nombre fini de chaînes courtes :

"Une paraphrase du résultat de Chaitin est qu'il ne peut y avoir aucune preuve formelle qu'une chaîne suffisamment longue est aléatoire..."

Beltrami observe que « la preuve de Chaitin est liée à un paradoxe posé par le bibliothécaire d'Oxford G. Berry au début du XXe siècle qui demandait « le plus petit entier positif qui ne puisse être défini par une phrase anglaise de moins de 1 000 caractères ». Évidemment, la définition la plus courte de ce numéro doit comporter au moins 1000 caractères. Cependant, la phrase entre guillemets, qui est elle-même une définition du numéro allégué, fait moins de 1000 caractères!".

Solutions entières des équations diophantiennes : dixième problème de Hilbert

La question « Une équation diophantienne arbitraire a-t-elle une solution entière ? » est indécidable. Autrement dit, il est impossible de répondre à la question dans tous les cas.

Franzén introduit le dixième problème de Hilbert et le théorème MRDP (théorème de Matiyasevich-Robinson-Davis-Putnam) qui déclare qu '«il n'existe aucun algorithme capable de décider si une équation diophantienne a ou non une solution». Le théorème MRDP utilise la preuve d'indécidabilité de Turing : "... l'ensemble des équations diophantiennes résolubles est un exemple d'un ensemble dénombrable par calcul mais non décidable, et l'ensemble des équations diophantiennes insolubles n'est pas dénombrable par calcul".

En sciences sociales

En sciences politiques, le théorème d'impossibilité d'Arrow énonce qu'il est impossible de concevoir un système de vote satisfaisant un ensemble de cinq axiomes spécifiques. Ce théorème est prouvé en montrant que quatre des axiomes impliquent ensemble l’opposé du cinquième.

De même, le théorème de Gibbard-Satterthwaite établit qu'aucun système électoral ne peut avoir plus de deux alternatives, être robuste au vote stratégique et empêcher un seul électeur de décider du résultat.

En économie, le théorème de Holmström est un théorème d'impossibilité prouvant qu'aucun système d'incitation pour une équipe d'agents ne peut satisfaire les trois critères souhaitables.

En sciences naturelles, les affirmations d'impossibilité (comme d'autres affirmations) en viennent à être largement acceptées comme extrêmement probables plutôt que considérées comme prouvées au point d'être incontestables. La base de cette forte acceptation est une combinaison de nombreuses preuves que quelque chose ne se produit pas, combinées à une théorie sous-jacente, très efficace pour faire des prédictions, dont les hypothèses conduisent logiquement à la conclusion que quelque chose est impossible.

Deux exemples d'impossibilités largement acceptées en physique sont les machines à mouvement perpétuel, qui violent la loi de conservation de l'énergie, et le dépassement de la vitesse de la lumière, qui viole les implications de la relativité restreinte. Un autre est le principe d'incertitude de la mécanique quantique, qui affirme l'impossibilité de connaître simultanément la position et l'impulsion d'une particule. Il y a aussi le théorème de Bell : aucune théorie physique des variables locales cachées ne pourra jamais reproduire toutes les prédictions de la mécanique quantique.

Même si une affirmation d'impossibilité en sciences naturelles ne peut jamais être absolument prouvée, elle pourrait être réfutée par l'observation d'un seul contre-exemple. Un tel contre-exemple nécessiterait que les hypothèses sous-jacentes à la théorie qui impliquait l’impossibilité soient réexaminées.

Voir également

• Problèmes non résolus en mathématiques – Des solutions à ces problèmes sont encore recherchées. En revanche, on sait que les problèmes ci-dessus n’ont pas de solution.
• Paradoxes de la théorie des ensembles

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Proof of impossibility » (voir la liste des auteurs).