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 particulierPudlák, pp. 255–256.. 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 , et tous ces problèmes ont donné lieu à des recherches sur des structures mathématiques plus complexes.
Un problème apparu au 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 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 positivePlus généralement, une preuve par descente infinie est applicable sur tout ensemble bien ordonné. à 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 nièmes différentes soient nécessaires pour totaliser encore une niè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 :
.
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.
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
en prenant tous les cas séparés jusqu'à la racine de 17 pieds carrés ... Hardy and Wright, p. 42.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 nHardy and Wright, p. 40.
Autrement dit, il est impossible d’exprimer la racine m-ième d’un entier N comme le rapport 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 :
diviser par 3 un angle donné uniquement à la règle et au compas, construire un cube de volume égal au double du volume d'un cube donné, 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 , il a été prouvé que les constructions souhaitées sont logiquement impossiblesNagel et Newman p. 8.
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)Hardy and Wright p. 159. 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 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é Hardy and Wright p. 176Il 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 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 à partir d'un cercle unité est impossibleHardy and Wright p. 159 referenced by E. Hecke. (1923). Vorlesungen über die Theorie der algebraischen Zahlen. Leipzig: Akademische Verlagsgesellschaft, 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
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 asymptotesNagel and Newman, p. 9. 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 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]." Nagel and Newman, p. 10
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 : avec . 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.