Voir la source de Problème d'algèbre de lycée de Tarski

En [[logique mathématique]], le '''problème d'algèbre de lycée de Tarski''' est une question posée par [[Alfred Tarski]]. Il demande s'il y a des [[Identité (mathématiques)|identités]] utilisant l'[[addition]], la [[multiplication]] et l'[[exponentiation]] sur les nombres entiers positifs qui ne peuvent pas être démontrées en utilisant onze [[axiome]]s portant sur ces opérations qui sont enseignées en mathématiques au niveau lycée. La question est résolue en 1980 par [[Alex Wilkie]], qui a montré que de telles identités indémontrables existent.

== Énoncé du problème ==

Tarski considère les 11 axiomes suivants sur l'addition ('+'), la multiplication ('·') et l'exponentiation comme des axiomes standards connus au lycée :
# ''x''&nbsp;+&nbsp;''y''&nbsp;=&nbsp;''y''&nbsp;+&nbsp;''x''
# (''x''&nbsp;+&nbsp;''y'')&nbsp;+&nbsp;''z''&nbsp;=&nbsp;''x''&nbsp;+&nbsp;(''y''&nbsp;+&nbsp;''z'')
# ''x''&nbsp;·&nbsp;1&nbsp;=&nbsp;''x''
# ''x''&nbsp;·&nbsp;''y''&nbsp;=&nbsp;''y''&nbsp;·&nbsp;''x''
# (''x''&nbsp;·&nbsp;''y'')&nbsp;·&nbsp;''z''&nbsp;=&nbsp;''x''&nbsp;·&nbsp;(''y''&nbsp;·&nbsp;''z'')
# ''x''&nbsp;·&nbsp;(''y''&nbsp;+&nbsp;''z'')&nbsp;=&nbsp;''x''&nbsp;·&nbsp;''y''&nbsp;+&nbsp;''x''&nbsp;·''z''
# 1<sup>''x''</sup>&nbsp;=&nbsp;1
# ''x''<sup>1</sup>&nbsp;=&nbsp;''x''
# ''x''<sup>''y''&nbsp;+&nbsp;''z''</sup>&nbsp;=&nbsp;''x''<sup>''y''</sup>&nbsp;·&nbsp;''x''<sup>''z''</sup>
# (''x''&nbsp;·&nbsp;''y'')<sup>''z''</sup>&nbsp;=&nbsp;''x''<sup>''z''</sup>&nbsp;·&nbsp;''y''<sup>''z''</sup>
# (''x''<sup>''y''</sup>)<sup>''z''</sup>&nbsp;=&nbsp;''x''<sup>''y''&nbsp;·&nbsp;''z''</sup>.
Ces 11 axiomes, parfois appelées les « identités lycéennes »<ref name="BurrisLee">{{Article|lang=en|auteur=Stanley Burris|auteur2=Simon Lee|titre=Tarski's high school identities|revue=[[The American Mathematical Monthly|Am. Math. Monthly]]|vol=100|année=1993|numéro=3|passage=231-236|jstor=2324454}}.</ref> sont liés aux axiomes des anneaux exponentiels<ref>Grossièrement, un anneau exponentiel possède une fonction exponentielle ''E'' qui associe à tout élément ''x'' une image qui se comporte comme ''a<sup>x</sup>'' pour un nombre ''a'' fixé.</ref>. Le problème de Tarski devient alors : existe-t-il des identités n'impliquant que l'addition, la multiplication et l'exponentiation, qui sont vraies pour tout entier positif, mais ne pouvant être démontrées en utilisant uniquement les 11 axiomes ?

== Exemple d'identité démontrables ==

Comme les axiomes semblent montrer toutes les propriétés usuelles des opérations algébriques, il n'est pas évident de voir qu'un énoncé utilisant les trois opérations ne puisse pas être démontré. Toutefois, démontrer certaines propriétés simples peuvent parfois nécessiter de longs calculs si on ne doit utiliser que les 11 axiomes. Considérons la démonstration de (''x''&nbsp;+&nbsp;1)<sup>2</sup>&nbsp;=&nbsp;''x''<sup>2</sup>&nbsp;+&nbsp;2&nbsp;·&nbsp;''x''&nbsp;+&nbsp;1 :
:(''x''&nbsp;+&nbsp;1)<sup>2</sup>
:=&nbsp;(''x''&nbsp;+&nbsp;1)<sup>1&nbsp;+&nbsp;1</sup>
:=&nbsp;(''x''&nbsp;+&nbsp;1)<sup>1</sup>&nbsp;·&nbsp;(''x''&nbsp;+&nbsp;1)<sup>1</sup>&nbsp;&nbsp;par 9.
:=&nbsp;(''x''&nbsp;+&nbsp;1)&nbsp;·&nbsp;(''x''&nbsp;+&nbsp;1)&nbsp;&nbsp;par 8.
:=&nbsp;(''x''&nbsp;+&nbsp;1)&nbsp;·&nbsp;''x''&nbsp;+&nbsp;(''x''&nbsp;+&nbsp;1)&nbsp;·&nbsp;1&nbsp;&nbsp;par 6.
:=&nbsp;''x''&nbsp;·&nbsp;(''x''&nbsp;+&nbsp;1)&nbsp;+&nbsp;''x''&nbsp;+&nbsp;1&nbsp;&nbsp;par 4. et 3.
:=&nbsp;''x''&nbsp;·&nbsp;''x''&nbsp;+&nbsp;''x''&nbsp;·&nbsp;1&nbsp;+&nbsp;''x''&nbsp;·&nbsp;1&nbsp;+&nbsp;1&nbsp;&nbsp;par 6. et 3.
:=&nbsp;''x''<sup>1</sup>&nbsp;·&nbsp;''x''<sup>1</sup>&nbsp;+&nbsp;''x''&nbsp;·&nbsp;(1&nbsp;+&nbsp;1)&nbsp;+&nbsp;1&nbsp;&nbsp;par 8. et 6.
:=&nbsp;''x''<sup>1&nbsp;+&nbsp;1</sup>&nbsp;+&nbsp;''x''&nbsp;·&nbsp;2&nbsp;+&nbsp;1&nbsp;&nbsp;par 9.
:=&nbsp;''x''<sup>2</sup>&nbsp;+&nbsp;2&nbsp;·&nbsp;''x''&nbsp;+&nbsp;1&nbsp;&nbsp;par 4.
Les parenthèses ne sont pas nécessaires par l'axiome 2. qui donne l'associativité de l'addition.

La [[Longueur d'une démonstration|longueur des preuves]] n'est pas un problème ; les calculs montrant des égalités comme le développement de (''x''&nbsp;+&nbsp;''y'')<sup>100</sup> seraient longs mais l'idée directrice des calculs resterait la même que pour la preuve donnée en exemple.

== Histoire du problème ==

La liste des onze axiomes peut être trouvée explicitement dans les travaux de [[Richard Dedekind]]<ref>Richard Dedekind, ''Was sind und was sollen die Zahlen?'', 8te unveränderte Aufl. </ref>, bien qu'ils fussent clairement connus et utilisés par de nombreux mathématiciens l'ayant précédé. Dedekind fut le premier toutefois à se demander si ces axiomes étaient en un sens suffisants pour donner tout ce qu'on pourrait chercher à savoir sur les entiers. La question est devenue, grâce à Alfred Tarski, un problème sérieux de logique et de [[théorie des modèles]] au cours des années 1960<ref name="BurrisLee" />{{,}}<ref name="Gurevic">R. Gurevič, ''Equational theory of positive numbers with exponentiation'', Proc. Amer. Math. Soc. '''94''' no.1, (1985), {{p.|135–141}}.</ref>, et a pris son nom actuel de « Problème d'algèbre de lycée de Tarski » dans les années 1980.

== Solution ==

En 1980, Alex Wilkie a démontré que toutes les identités usuelles ne pouvaient être dérivées à partir des 11 axiomes seuls<ref>A.J. Wilkie, ''On exponentiation – a solution to Tarski's high school algebra problem'', Connections between model theory and algebraic and analytic geometry, Quad. Mat., '''6''', Dept. Math., Seconda Univ. Napoli, Caserta, (2000), {{p.|107–129}}.</ref>, en donnant explicitement une telle identité. En introduisant de nouveaux symboles fonctionnels correspondant aux polynômes qui envoient les nombres positifs vers des nombres positifs, il montra la validité de cette identité, puis qu'il était nécessaire et suffisant d'avoir ces fonctions associés aux 11 axiomes pour la démontrer. L'égalité en question est :
{{retrait|<math>\begin{align}&\left((1+x)^y+(1+x+x^2)^y\right)^x\cdot\left((1+x^3)^x+(1+x^2+x^4)^x\right)^y\\={}&\left((1+x)^x+(1+x+x^2)^x\right)^y\cdot\left((1+x^3)^y+(1+x^2+x^4)^y\right)^x.\end{align}</math>}}

Cette fonctionnelle est souvent notée {{math|''W''(''x'',''y'')}} et est satisfaite pour tous les entiers positifs {{math|''x''}} et  {{math|''y''}}, ce qu'on peut voir en factorisant {{math|(1-''x''+''x''{{2}})<sup>''xy''</sup>}} après simplification ; cependant, les 11 axiomes seuls ne permettent pas de la démontrer.

Intuitivement, on peut voir que l'identité ne peut être démontrée car les axiomes sont insuffisants pour traiter le cas du polynôme {{math|1-''x''+''x''{{2}}}}. L'étude de ce polynôme et du terme {{math|-''x''}} requiert la définition de la négativité ou de la soustraction, absentes des axiomes. Cette lacune rend impossible la manipulation de ce polynôme par les axiomes et les calculs complets à partir de celui-ci. Les résultats de Wilkie montrent, dans un langage plus formel, que le « seul handicap » des axiomes « lycéens » est l'impossibilité de manipuler des polynômes à coefficients négatifs.

== Généralisations ==

Wilkie a montré qu'il y a des propositions sur les entiers positifs qui ne peuvent être prouvées à partir des 11 axiomes donnés et quelles informations supplémentaires sont nécessaires pour ce faire. Par la [[théorie de Nevanlinna]], il peut être aussi montré que si on restreint les types d'exponentielles, les onze axiomes sont suffisants pour prouver toute identité vraie<ref>C. Ward Henson, Lee A. Rubel, ''Some applications of Nevanlinna theory to mathematical logic: Identities of exponential functions'', [[Transactions of the American Mathematical Society]], vol.282 '''1''', (1984), {{p.|1–32}}.</ref>.

Un autre problème tiré du résultat de Wilkie, qui reste ouvert, est la détermination de la plus petite [[Algèbre sur un anneau|algèbre]] dans laquelle ''W''(''x'',&nbsp;''y'') est fausse mais les onze axiomes sont vrais. En 1985 une algèbre comptant 59 éléments a été construite vérifiant cette propriété<ref name="Gurevic"/>. D'autres algèbres plus petites ont depuis été trouvées, mais il reste à déterminer si la plus petite doit contenir 11 ou 12 éléments<ref>Jian Zhang, ''Computer search for counterexamples to Wilkie's identity'', Automated Deduction – CADE-20, [[Springer Science+Business Media|Springer]] (2005), {{p.|441–451}}, {{doi|10.1007/11532231_32}}.</ref>.

== Voir aussi ==

* [[Corps réel clos#Théorie des corps réels clos|Corps réel clos]] (où l'on trouve la solution donnée par Tarski d'un problème analogue sur les réels).

== Notes et références ==
{{Traduction/Référence|en|Tarski's high school algebra problem|619373441|type=note}}
{{Références|colonnes=}}

* {{Article|prénom1=Stanley N.|nom1=Burris|prénom2=Karen A.|nom2=Yeats|titre=The saga of the high school identities|périodique=[[Algebra Universalis]]|volume=52|numéro=2–3|année=2004|p.=325–342|math reviews=2161657|DOI=10.1007/s00012-004-1900-2}}.

{{Portail|Mathématiques|Logique}}

{{DEFAULTSORT:Tarski, Probleme}}
[[Catégorie:Algèbre]]