タルスキーの高校代数学の問題

数理論理学において、タルスキの高校代数学の問題はアルフレッド・タルスキが提起した問題である。これは、高校レベルの数学で教えられるこれらの演算に関する11の公理を使用して証明できない、正の整数の加算、乗算、累乗を含む恒等式が存在するかどうかを問うものである。この問題は1980年にアレックス・ウィルキーによって解決され、彼はそのような証明不可能な恒等式が存在することを示した。

タルスキは、加算、乗算、累乗に関する次の 11 の公理が高校で教えられる標準的な公理であるとみなしました。 ${\displaystyle (+)}$${\displaystyle (\cdot )}$$${\displaystyle {\begin{aligned}x+y&=y+x\\(x+y)+z&=x+(y+z)\\x\cdot 1&=x\\x\cdot y&=y\cdot x\\(x\cdot y)\cdot z&=x\cdot (y\cdot z)\\x\cdot (y+z)&=x\cdot y+x\cdot z\\1^{x}&=1\\x^{1}&=x\\x^{y+z}&=x^{y}\cdot x^{z}\\(x\cdot y)^{z}&=x^{z}\cdot y^{z}\\(x^{y})^{z}&=x^{y\cdot z}\end{aligned}}}$$

これら11の公理は、高校の恒等式^[1] とも呼ばれ、双デカルト閉圏または指数環の公理に関連しています。^[2]すると、タルスキの問題は次のようになります。加算、乗算、累乗のみを含み、すべての正の整数に対して真であるが、公理1～11のみを使用して 証明できない恒等式は存在するか？

公理は問題の演算に関するすべての基本的な事実を列挙しているように見えるので、3つの演算のみを使用して述べることができ、公理では証明できないことが何かあるはずであることはすぐには明らかではありません。しかし、一見無害なステートメントを証明するには、上記の11の公理のみを使用した長い証明が必要になる場合があります。次の証明を考えてみましょう。${\displaystyle (x+1)^{2}=x^{2}+2\cdot x+1:}$

$${\displaystyle {\begin{aligned}(x+1)^{2}&=(x+1)^{1+1}\\&=(x+1)^{1}\cdot (x+1)^{1}&&{\text{9.}}\\&=(x+1)\cdot (x+1)&&{\text{8. を 2 回適用}}\\&=(x+1)\cdot x+(x+1)\cdot 1&&{\text{6.}}\\&=x\cdot (x+1)+(x+1)&&{\text{4. と 3.}}\\&=(x\cdot x+x\cdot 1)+(x\cdot 1+1)&&{\text{6. と 3.}}\\&=x\cdot x+(x\cdot 1+x\cdot 1)+1&&{\text{2 を 2 回適用します。}}\\&=x^{1}\cdot x^{1}+x\cdot (1+1)+1&&{\text{6 と 8 を 2 回適用します。}}\\&=x^{1+1}+x\cdot 2+1&&{\text{9 を適用します。}}\\&=x^{2}+2\cdot x+1&&{\text{4 を適用します。}}\end{aligned}}}$$

厳密には、2 つ以上の項の和を括弧なしで書くべきではないため、完全に形式的な証明では、恒等式(または) を証明し、以降の各行に追加の括弧のセットが必要になります。 ${\displaystyle (x+1)^{2}=\left(x^{2}+2\cdot x\right)+1}$${\displaystyle (x+1)^{2}=x^{2}+(2\cdot x+1)}$${\displaystyle x\cdot x+(x\cdot 1+x\cdot 1)+1}$

証明の長さは問題ではありません。上記のような類似の証明には多くの行が必要になりますが、実際には上記の証明よりも少し多くが必要になります。 ${\displaystyle (x+y)^{100}}$

11個の公理のリストはリチャード・デデキントの著作^[3]に明示的に記されているが、それらはそれよりずっと前から数学者によって知られ、使用されていたことは明らかである。しかし、これらの公理が整数について知りたいことすべてを伝えるのに十分であるかどうかを問うたのはデデキントが初めてであったように思われる。この問題は1960年代にアルフレッド・タルスキ^{[1] [4]によって}論理学とモデル理論の問題として確固たる地位に置かれ、1980年代にはタルスキの高校代数問題として知られるようになった。

1980年にアレックス・ウィルキーは、問題となっている恒等式がすべて上記の公理を使って証明できるわけではないことを証明した。^[5]彼は、そのような恒等式を明示的に見つけることでこれを行った。正の数を正の数にマッピングする多項式に対応する新しい関数記号を導入することで、彼はこの恒等式を証明し、これらの関数と上記の11の公理が、この証明に十分かつ必要であることを示した。問題の恒等式は、 この恒等式は通常 と表され、すべての正の整数に対して真であり、各辺の2番目の因数を因数分解することでわかるが、11の高校の公理を使って真であることを証明することはできない。 $${\displaystyle {\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}}}$$${\displaystyle W(x,y)}$${\displaystyle x}$${\displaystyle y,}$${\displaystyle (1-x+x^{2})^{xy}}$

直感的に、高校の公理は多項式 について議論するのに使用できないため、恒等式は証明できません。多項式と部分項についての推論には、否定または減算の概念が必要ですが、これらは高校の公理には存在しません。これがないと、公理を使用して多項式を操作し、それに関する真の特性を証明することは不可能です。ウィルキーの論文の結果は、より正式な言葉で、高校の公理の「唯一の欠陥」は、負の係数を持つ多項式を操作できないことであることを示しています。 ${\displaystyle 1-x+x^{2}.}$${\displaystyle -x}$

R.グレヴィッチは1988年に、1を含む正の自然数、加算、乗算、累乗の有効な方程式には有限の公理化が存在しないことを証明した。 ^{[6] [7]}

ウィルキーは、正の整数に関する記述のうち、上記の11の公理では証明できないものがあることを証明し、そのような記述を証明する前にどのような追加情報が必要であるかを示した。ネヴァンリンナ理論を使用すると、指数の種類を制限すれば、上記の11の公理ですべての真の記述を証明できることも証明されている。^[8]

ウィルキーの結果から生じる、未解決のもう一つの問題は、真ではないが上記の11の公理が真である最小の代数は何かという問題である。1985年に、公理を満たすが偽である59個の要素を持つ代数が発見された。^[4] その後、より小さな代数が発見され、現在では最小の代数は11個か12個の要素を持つ必要があることが分かっている。^[9]${\displaystyle W(x,y)}$${\displaystyle W(x,y)}$

• 基本関数 – 数学関数
• 初等関数算術 – 証明理論における算術体系
• リウヴィルの定理（微分代数）  – 初等関数の不定理が初等関数として表現できる場合を述べる
• 非初等積分 – 初等関数から閉じた形式で表現できない積分
• リチャードソンの定理 – 実数の等式の決定不可能性

• スタンレー・N・バリス、カレン・A・イェイツ、「高校のアイデンティティの物語」、Algebra Universalis 52 no.2–3、(2004)、pp. 325–342、MR 2161657。