Preuve d'impossibilité - Proof of impossibility

En mathématiques , une preuve d'impossibilité , également connue sous le nom de preuve négative , preuve d'un théorème d'impossibilité ou résultat négatif est une preuve démontrant qu'un problème particulier ne peut pas être résolu comme décrit dans la revendication, ou qu'un ensemble particulier de problèmes ne peut pas être résolu en général. Les preuves d'impossibilité mettent souvent des décennies ou des siècles de travail à s'arrêter pour trouver une solution. 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 théorie. Les théorèmes d'impossibilité sont généralement exprimables sous forme de propositions existentielles négatives ou de propositions universelles en logique (voir la quantification universelle pour en savoir plus).

L'une des plus anciennes preuves d'impossibilité est peut-être celle de l' irrationalité de la racine carrée de 2 , qui montre qu'il est impossible d'exprimer la racine carrée de 2 sous la forme d'un rapport d'entiers. Une autre preuve célèbre d'impossibilité était la preuve 1882 de Ferdinand von Lindemann , montrant que le problème ancien de la quadrature du cercle ne peut être résolu, car le nombre π est transcendant (ie non-algébrique) et un sous - ensemble des nombres algébriques peut être construit à l'aide d'un compas et d'une règle. Deux autres problèmes classiques, la trisection de l'angle général et le doublement du cube, se sont également révélés impossibles au XIXe siècle.

Un problème survenu au 16ème siècle était celui de créer une formule générale utilisant des radicaux exprimant la solution de toute équation polynomiale de degré fixe k , où k 5. 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 .

Parmi les preuves d'impossibilité les plus importantes du 20ème siècle se trouvaient celles liées à l' indécidabilité , qui ont montré qu'il existe des problèmes qui ne peuvent être résolus en général par aucun algorithme du tout, le plus célèbre étant le problème de l' arrêt . D'autres résultats similaires sont ceux des théorèmes d'incomplétude de Gödel , qui révèlent certaines limitations fondamentales dans la prouvabilité des systèmes formels.

Dans la théorie de la complexité computationnelle , des techniques comme la relativisation (voir machine oracle ) fournissent des preuves "faibles" d'impossibilité excluant certaines techniques de preuve. D'autres techniques, telles que les preuves d' exhaustivité pour une classe de complexité , fournissent des preuves de la difficulté des problèmes, en montrant qu'ils sont tout aussi difficiles à résoudre que d'autres problèmes connus qui se sont avérés insolubles .

Types de preuve d'impossibilité

Preuve par contradiction

Un type de preuve d'impossibilité largement utilisé est la preuve par contradiction . Dans ce type de preuve, il est montré que si quelque chose, comme une solution à une classe particulière d'équations, était possible, alors deux choses mutuellement contradictoires seraient vraies, comme un nombre à la fois pair et impair. La contradiction implique que la prémisse originale est impossible.

Preuve par descendance

Un type de preuve par contradiction est la preuve par descendance, qui procède d'abord en supposant que quelque chose est possible, telle qu'une solution entière positive à une classe d'équations, et qu'il doit donc y avoir une plus petite solution. À partir de la prétendue plus petite solution, il est ensuite 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 (qu'une solution existe) doit être fausse.

Types de réfutation des conjectures d'impossibilité

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é en fournissant un seul contre-exemple. Par exemple, Euler a proposé qu'au moins n puissances n ^ième différentes soient nécessaires pour additionner à une autre puissance n ^ième . La conjecture a été réfutée en 1966, avec un contre-exemple impliquant un décompte de seulement quatre puissances 5ème différentes additionnant à une autre puissance cinquième :

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

Une preuve par contre-exemple est une preuve constructive , en ce sens qu'un objet réfutant l'affirmation est exposé. En revanche, une preuve non constructive d'une allégation 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 en fait être un contre-exemple valide à la conjecture d'impossibilité . Par exemple, une conjecture selon laquelle il est impossible qu'un pouvoir irrationnel élevé à un pouvoir irrationnel soit rationnel 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 est.

L'existence des nombres irrationnels : la preuve des Pythagoriciens

La preuve par Pythagore (ou plus probablement l'un de ses étudiants) environ 500  avant notre ère a eu un effet profond sur les mathématiques. Il montre que la racine carrée de 2 ne peut pas être exprimée comme le rapport de deux nombres entiers (compter des nombres). La preuve a divisé « les nombres » en deux collections qui ne se chevauchent pas : les nombres rationnels et les nombres irrationnels . Cette bifurcation a été utilisée par Cantor dans sa méthode diagonale , qui à son tour a été utilisée par Turing dans sa preuve que le problème d'Entscheidungs , le problème de décision de Hilbert , est indécidable.

On ne sait pas quand, ou par qui, le "théorème de Pythagore" a été découvert. La découverte ne peut guère avoir été faite par Pythagore lui-même, mais elle a certainement été faite à son école. Pythagore a vécu environ 570-490 avant notre ère. Démocrite, né vers 470 avant notre ère, a écrit sur des lignes et des solides irrationnels  ...

-  Heath,

Les preuves ont suivi pour diverses racines carrées des nombres premiers jusqu'à 17.

Il y a un passage célèbre de Platon de Théétète dans lequel il est indiqué que Teodorus (le professeur de Platon) prouva l'irrationalité de

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

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

Une preuve plus générale existe maintenant que :

La m ième racine d'un entier N est irrationnelle, sauf si N est la m ième puissance d'un entier n ".

C'est-à-dire qu'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 anciens Grecs

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

1. ... avec boussole et règle pour couper n'importe quel angle ,
2. construire un cube avec un volume deux fois le 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 19ème siècle, il a été prouvé que les constructions souhaitées sont logiquement impossibles.

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

Tous ces éléments sont des problèmes de construction euclidienne , et les constructions euclidiennes ne peuvent être réalisées que si elles impliquent uniquement des nombres euclidiens (par définition de ces derniers) (Hardy et Wright p. 159). Les nombres irrationnels peuvent être euclidiens. Un bon exemple est le nombre irrationnel racine carrée de 2. C'est simplement la longueur de l'hypoténuse d'un triangle rectangle avec des jambes toutes deux d'une unité de longueur, et il peut être construit avec une règle et une boussole. Mais il a été prouvé des siècles après Euclide que les nombres euclidiens ne peuvent impliquer d'autres opérations que l'addition, la soustraction, la multiplication, la division et l'extraction de racines carrées.

Trisection d'angle et doublement du cube

La trisection de l'angle général et le doublement du cube nécessitent de prendre des racines cubiques , qui ne sont pas des nombres constructibles à la boussole et à la règle.

La quadrature du cercle

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

Une preuve existe pour démontrer que tout nombre euclidien est un nombre algébrique, un nombre qui est la solution d'une équation polynomiale . Par conséquent, parce qu'il a été prouvé en 1882 qu'il était un nombre transcendantal et donc par définition pas un nombre algébrique, ce n'est pas un nombre euclidien. Par conséquent, la construction d'une longueur à partir d'un cercle unité est impossible, et le cercle ne peut pas être carré. ${\style d'affichage \pi }$${\style d'affichage \pi }$

Construire un n -gon équilatéral

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

L'axiome parallèle d'Euclide

Nagel et Newman considèrent que la question soulevée par le postulat parallèle est "... peut-être le développement le plus significatif de ses effets à long terme sur l'histoire mathématique ultérieure" (p. 9).

La question est : l'axiome selon lequel deux droites parallèles "... ne se rencontreront même pas 'à l'infini'" (note de bas de page, ibid) peut-il être dérivé des autres axiomes de la géométrie d'Euclide ? Ce n'est que dans les travaux du XIXe siècle de "... Gauss, Bolyai, Lobatchevsky et Riemann, que l'impossibilité de déduire l'axiome parallèle des autres a été démontrée. Ce résultat était de la plus grande importance intellectuelle. ...a la preuve peut être donnée de l' impossibilité de prouver certaines propositions [dans ce cas, le postlat parallèle] au sein d'un système donné [dans ce cas, les quatre premiers postulats d'Euclide] ». (p. 10)

Le dernier théorème de Fermat

Le dernier théorème de Fermat a été conjecturé par Pierre de Fermat dans les années 1600, é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 cas n  = 4 en 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 . ${\style d'affichage x^{n}+y^{n}=z^{n}}$${\style d'affichage n>2}$

Le paradoxe de Richard

Ce profond paradoxe présenté par Jules Richard en 1905 a nourri les travaux de Kurt Gödel (cf Nagel et Newman p. 60ff) et Alan Turing. Une définition succincte se trouve dans les Principia Mathematica :

Le paradoxe de Richard... est le suivant. Considérons tous les nombres décimaux qui peuvent être définis au moyen d'un nombre fini de mots [les « mots » sont des symboles ; caractères gras ajoutés pour l'emphase] ; soit E la classe de tels nombres décimaux. Alors E a [un nombre infini de] termes ; par conséquent, ses membres peuvent être ordonnés comme le 1er, le 2e, le 3e, ... Soit X un nombre défini comme suit [Whitehead & Russell emploient maintenant la méthode diagonale de Cantor] . Si le n- ième chiffre de la n- ième décimale est p , que le n- ième chiffre de X soit p  + 1 (ou 0, si p  = 9). Alors X est différent de tous les membres de E , puisque, quelle que soit la valeur finie de n , le n -ième chiffre de X est différent du n -ième chiffre de la n -ième des décimales composant E , et donc X est différent de la n- ième décimale. Néanmoins nous avons défini X en un nombre fini de mots [c'est-à-dire cette définition même de « mot » ci-dessus.] et donc X devrait être membre de E . Ainsi X à la fois est et n'est pas membre de E.${\displaystyle \aleph _{0}}$

—  Principia Mathematica , 2e édition 1927, p. 61

Kurt Gödel considérait sa preuve comme « une analogie » du paradoxe de Richard, qu'il appelait « l'antinomie de Richard ». Voir plus ci-dessous sur la preuve de Gödel.

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) sera piégée dans une « boucle infinie » improductive (c'est-à-dire qu'elle ne continue pas son calcul du nombre diagonal).

Ce théorème peut-il être prouvé à partir de ces axiomes ? 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'atteindre les principaux résultats » (p. 68). En fait, Nagel et Newman ont demandé une introduction de 67 pages à leur exposé de la preuve. Mais si le lecteur se sent assez fort pour aborder l'article, Martin Davis observe que « cet article remarquable n'est pas seulement un repère intellectuel, mais est écrit avec une clarté et une vigueur qui en font un plaisir à lire » (Davis in Undecidable, p. 4). Il est recommandé que la plupart des lecteurs voient d'abord Nagel et Newman.

Alors qu'est-ce que 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 ; pour plus, voir le paradoxe de Richard ):

« 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 : chaque antinomie épistémologique peut être utilisée pour une preuve similaire d'indécidabilité)... Ainsi nous avons une proposition devant nous qui affirme sa propre indémontrabilité [15]. (Sa note de bas de page 15 : Contrairement aux apparences, une telle proposition n'est pas circulaire, car, pour commencer, elle affirme l'unprouvabilité d'une formule bien définie) » (Gödel dans Indécidable , p.9).

Cette machine informatique va-t-elle se verrouiller dans un « cercle » ? La première preuve de Turing

• Le problème d'Entscheidungs , le problème de décision , a été résolu pour la première fois par l'Église en avril 1935 et a devancé Turing de plus d'un an, car l'article de Turing a été reçu pour publication en mai 1936. (Également reçu pour publication en 1936 - en octobre, plus tard que celui de Turing - a été un court article par Emil Post qui a discuté de la réduction d'un algorithme à une simple « méthode » semblable à une machine très similaire au modèle de machine informatique de Turing (voir Post-Turing machine pour plus de détails).
• La preuve de Turing est rendue difficile par le nombre de définitions requises et sa nature subtile. Voir la machine de Turing et la preuve de Turing pour plus de détails.
• 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 lui-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 par séquence à partir de 1, en convertissant les nombres (base 8) en chaînes de sept lettres à tester. Lorsqu'il parvient à 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 réussie, mais lorsqu'il essaie de faire le calcul de cette machine ( le sien ), il se verrouille dans un cercle et ne peut pas continuer. Nous sommes ainsi arrivés au paradoxe de Richard. (Si vous êtes déconcerté, consultez la preuve de Turing pour en savoir plus).

Un certain nombre de preuves d'indécidabilité similaires sont apparues peu de temps 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 était de "... proposer une définition de la calculabilité effective... et de 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 postale (cf Hopcroft et Ullman p. 193ff, 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). Cela est depuis devenu connu sous le nom de "Le problème de la parole de Thue" ou "Le problème de la parole 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. 185ff)
5. Théorème de Greibach : indécidabilité en théorie du langage (cf Hopcroft et Ullman p. 205ff et référence p. 401 ibid : Greibach [1963] "The undecidability of the ambiguity problem for minimal lineal Grammaires," Information and Control 6:2, 117–125 , également référence à la page 402 ibid : Greibach [1968] « A note on indecidable properties of formal languages », Math Systems Theory 2:1, 1–6.)
6. Questions sur le carrelage Penrose
7. Question des solutions pour les équations diophantiennes et la réponse résultante dans le théorème MRDP ; voir l'entrée ci-dessous.

Cette chaîne peut-elle être compressée ? La preuve de Chaitin

Pour une exposition adaptée aux non-spécialistes voir Beltrami p. 108ff. Voir aussi Franzen Chapitre 8 pp. 137-148, et Davis pp. 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 . Le traitement plus ancien de Davis aborde la question du point de vue de la machine de Turing . Chaitin a écrit un certain nombre de livres sur ses efforts et les retombées philosophiques et mathématiques qui en découlent.

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

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

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 vingtième siècle qui demande « le plus petit entier positif qui ne peut pas être défini par une phrase anglaise de moins de 1000 caractères ». Évidemment, la définition la plus courte de ce nombre doit avoir au moins 1000 caractères. Cependant, la phrase entre guillemets, qui est elle-même une définition du nombre allégué, fait moins de 1000 caractères !" (Beltrami, p. 108)

Cette équation diophantienne a-t-elle une solution entière ? Le dixième problème de Hilbert

La question "Est-ce qu'une "équation diophantienne" arbitraire a une solution entière?" est indécidable , c'est-à-dire qu'il est impossible de répondre à la question dans tous les cas.

Franzén introduit le problème de dixième de Hilbert et le théorème de MRDP (théorème Matiyasevich-Robinson-Davis-Putnam) qui stipule que « aucun algorithme existe qui peut décider si oui ou non une équation diophantienne a une solution à tout ». MRDP utilise la preuve d'indécidabilité de Turing : "... l'ensemble des équations diophantiennes résolubles est un exemple d'un ensemble calculable mais non décidable, et l'ensemble des équations diophantiennes insolubles n'est pas calculable énumérable" (p. 71).

En sciences sociales

En science politique , le théorème d'impossibilité d'Arrow déclare qu'il est impossible de concevoir un système de vote qui satisfasse 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.

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

En sciences naturelles , les affirmations d'impossibilité (comme d'autres affirmations) sont largement acceptées comme extrêmement probables plutôt que considérées comme prouvées au point d'être irréfutables. La base de cette forte acceptation est une combinaison de preuves étendues de quelque chose qui ne se produit pas, combinée à 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 la quantité de mouvement d'une particule. Aussi le théorème de Bell : aucune théorie physique des variables cachées locales ne pourra jamais reproduire toutes les prédictions de la mécanique quantique.

Alors qu'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 exigerait que les hypothèses sous-jacentes à la théorie qui impliquait l'impossibilité soient réexaminées.

Voir également

• Liste des problèmes non résolus en mathématiques  – Les solutions de ces problèmes sont toujours recherchées. En revanche, les problèmes ci-dessus sont connus pour n'avoir aucune solution.
• Théorème de non-droit , la notion physique correspondante.

Notes et références

Bibliographie