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é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 axiomes 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[modifier | modifier le code]

Tarski considère les 11 axiomes suivants sur l'addition ('+'), la multiplication ('·') et l'exponentiation comme des axiomes standards connus au lycée :

x + y = y + x
(x + y) + z = x + (y + z)
x · 1 = x
x · y = y · x
(x · y) · z = x · (y · z)
x · (y + z) = x · y + x ·z
1^x = 1
x¹ = x
x^y + z = x^y · x^z
(x · y)^z = x^z · y^z
(x^y)^z = x^y · z.

Ces 11 axiomes, parfois appelées les « identités lycéennes »^[1] sont liés aux axiomes des anneaux exponentiels^[2]. 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[modifier | modifier le code]

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 + 1)² = x² + 2 · x + 1 :

(x + 1)²

= (x + 1)^1 + 1

= (x + 1)¹ · (x + 1)¹ par 9.

= (x + 1) · (x + 1) par 8.

= (x + 1) · x + (x + 1) · 1 par 6.

= x · (x + 1) + x + 1 par 4. et 3.

= x · x + x · 1 + x · 1 + 1 par 6. et 3.

= x¹ · x¹ + x · (1 + 1) + 1 par 8. et 6.

= x^1 + 1 + x · 2 + 1 par 9.

= x² + 2 · x + 1 par 4.

Les parenthèses ne sont pas nécessaires par l'axiome 2. qui donne l'associativité de l'addition.

La longueur des preuves n'est pas un problème ; les calculs montrant des égalités comme le développement de (x + y)¹⁰⁰ 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[modifier | modifier le code]

La liste des onze axiomes peut être trouvée explicitement dans les travaux de Richard Dedekind^[3], 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^[1]^,^[4], et a pris son nom actuel de « Problème d'algèbre de lycée de Tarski » dans les années 1980.

Solution[modifier | modifier le code]

En 1980, Alex Wilkie a démontré que toutes les identités usuelles ne pouvaient être dérivées à partir des 11 axiomes seuls^[5], 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 : ${\begin{aligned}&\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{aligned}}$

Cette fonctionnelle est souvent notée $W (x, y)$ et est satisfaite pour tous les entiers positifs $x$ et $y$ , ce qu'on peut voir en factorisant $(1- x + x 2) xy$ 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 $1- x + x 2$ . L'étude de ce polynôme et du terme $- 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[modifier | modifier le code]

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^[6].

Un autre problème tiré du résultat de Wilkie, qui reste ouvert, est la détermination de la plus petite algèbre dans laquelle W(x, 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é^[4]. 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^[7].

Voir aussi[modifier | modifier le code]

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[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tarski's high school algebra problem » (voir la liste des auteurs).

↑ ^{a et b} (en) Stanley Burris et Simon Lee, « Tarski's high school identities », Am. Math. Monthly, vol. 100, n^o 3,‎ 1993, p. 231-236 (JSTOR 2324454).
↑ Grossièrement, un anneau exponentiel possède une fonction exponentielle E qui associe à tout élément x une image qui se comporte comme a^x pour un nombre a fixé.
↑ Richard Dedekind, Was sind und was sollen die Zahlen?, 8te unveränderte Aufl.
↑ ^{a et b} R. Gurevič, Equational theory of positive numbers with exponentiation, Proc. Amer. Math. Soc. 94 no.1, (1985), p. 135–141.
↑ 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.
↑ 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.
↑ Jian Zhang, Computer search for counterexamples to Wilkie's identity, Automated Deduction – CADE-20, Springer (2005), p. 441–451, DOI 10.1007/11532231_32.

Stanley N. Burris et Karen A. Yeats, « The saga of the high school identities », Algebra Universalis, vol. 52, n^os 2–3,‎ 2004, p. 325–342 (DOI 10.1007/s00012-004-1900-2, MR 2161657).

[BurrisLee-1] {a et b} (en) Stanley Burris et Simon Lee, « Tarski's high school identities », Am. Math. Monthly, vol. 100, n^o 3,‎ 1993, p. 231-236 (JSTOR 2324454).

[2] Grossièrement, un anneau exponentiel possède une fonction exponentielle E qui associe à tout élément x une image qui se comporte comme a^x pour un nombre a fixé.

[3] Richard Dedekind, Was sind und was sollen die Zahlen?, 8te unveränderte Aufl.

[Gurevic-4] {a et b} R. Gurevič, Equational theory of positive numbers with exponentiation, Proc. Amer. Math. Soc. 94 no.1, (1985), p. 135–141.

[5] 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.

[6] 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.

[7] Jian Zhang, Computer search for counterexamples to Wilkie's identity, Automated Deduction – CADE-20, Springer (2005), p. 441–451, DOI 10.1007/11532231_32.

[1]

[2]

[3]

[4]

[5]

[6]

[7]