Tarski の高校代数問題（Tarski’s high school algebra problem）という問題があります． 名前に違わず中学・高校レベルの知識でも（非厳密な）概要は理解できるような問題で，それでいてモデル理論の初等的な応用事例として非常に優れた題材となっています． にもかかわらずこの問題は日本ではほとんど言及されていないようで勿体なさを感じるところです．

今回はそんな Tarski の高校代数問題について紹介していきます．

問題の概要

Tarski の高校代数問題は，以下の問題です．

たとえば (x + y)^{2} = x^{2} + 2 \cdot x \cdot y + y^{2} は正整数の集合 \mathbb{N} における恒等式です． そしてこの恒等式は，以下のように11個の基本法則を繰り返し適用することで証明できます． \begin{aligned} (x + y)^{2} & = (x + y)^{1 + 1} \\ & = (x + y)^{1} \cdot (x + y)^{1} \\ & = (x + y) \cdot (x + y) \\ & = x \cdot (x + y) + y \cdot (x + y) \\ & = x \cdot x + x \cdot y + y \cdot x + y \cdot y \\ & = x \cdot x + x \cdot y + x \cdot y + y \cdot y \\ & = x \cdot x + 1 \cdot x \cdot y + 1 \cdot x \cdot y + y \cdot y \\ & = x \cdot x + (1 + 1) \cdot x \cdot y + y \cdot y \\ & = x \cdot x + 2 \cdot x \cdot y + y \cdot y \\ & = x^{1} \cdot x^{1} + 2 \cdot x \cdot y + y^{1} \cdot y^{1} \\ & = x^{2} + 2 \cdot x \cdot y + y^{2}. \end{aligned} 加法・乗法・累乗で表される \mathbb{N} 上の全ての恒等式が，このように基本法則による式変形のみで証明できるのかを問うのが Tarski の高校代数問題です．

この11個の等式は high school identities (HSI) と呼ばれ， R. Dedekind の 1888 年の論文¹の中でまとめられました． 「これらの等式が正整数のすべての恒等式を導くだろうか」という問いもその論文の中で提起されたものです． その後 1969 年に A. Tarski がこの問題を数理論理学・モデル理論の題材として取り上げた²ことで，この問題は Tarski の問題として知られるようになったようです．

ステートメントに関する注意

この問題のステートメントは明快なようで改めて考えると細かい疑問点が浮かぶものになっているため，最初に注意点を述べておきます．

負数や分数について

HSI の基本変形において，負の数や分数のような，正整数の集合 \mathbb{N} に含まれない数を経由することはできません． 1 = 1^{\frac{1}{2}}\quad\ldots\text{ ✘ } 減法のような追加の演算を含む項を作ることもできません． 1 = 1^{x^{2} - x}\quad\ldots\text{ ✘ }

なお，そもそも問題中の演算に減法が含まれていないのは，負数を問題の範疇に入れてしまうと指数法則が成り立たなくなってしまうからです． ( - 1)^{2 \cdot 2^{- 2}} = ( - 1)^{2^{- 1}} = i,\quad\left( ( - 1)^{2} \right)^{2^{- 2}} = 1^{2^{- 2}} = 1.

定数の扱いについて

先ほどの証明では 2 = 1 + 1 という変形を行っていました． これは基本法則に含まれていない等式のため許されない操作であるように思えます． しかし実際このような変形ができないと定数に対して何の操作も出来なくなってしまうため，2,3 といった定数は 1 + \cdots + 1 という式の略記であると約束しておきます． 2 ≔ 1 + 1,\quad 3 ≔ 1 + 1 + 1,\quad\ldots

指数が定数の場合

恒等式の両辺に現れる指数部分がすべて定数の場合，恒等式は基本法則のみで証明できます． 実際，両辺を展開し単項式の和の形に直せば，単項式の種類と個数を確かめることで両辺が一致するかどうか判定ができます． 多項式を展開する操作は基本法則のみで行えるため，これで一致させられれば基本法則から証明できたことになりますし，これで一致させられないのならその等式は恒等式ではなかったということになります． \begin{aligned} (x + y)^{3} & = x^{3} + 3 \cdot x^{2} \cdot y + 3 \cdot x \cdot y^{2} + y^{3}, \\ x^{3} + y^{3} + 3 \cdot x \cdot y \cdot (x + y) & = x^{3} + 3 \cdot x^{2} \cdot y + 3 \cdot x \cdot y^{2} + y^{3}. \end{aligned} したがって問題となるのは指数の部分に文字を含む場合です． \left( x^{2} + 3 \cdot x + 2 \right)^{y} = (x + 1)^{y} \cdot (x + 2)^{y}

反例

結論として，この問題は 1981 年に A. J. Wilkie によって否定的に解決されました．

Wilkie は具体的に，HSI から証明することのできない恒等式 (Wilkie’s identity)を発見しました． それが次の式です： \begin{aligned} & \left( (1 + x)^{y} + \left( 1 + x + x^{2} \right)^{y} \right)^{x} \cdot \left( \left( 1 + x^{3} \right)^{x} + \left( 1 + x^{2} + x^{4} \right)^{x} \right)^{y} \\ = & \left( (1 + x)^{x} + \left( 1 + x + x^{2} \right)^{x} \right)^{y} \cdot \left( \left( 1 + x^{3} \right)^{y} + \left( 1 + x^{2} + x^{4} \right)^{y} \right)^{x}. \end{aligned}

この式が実際に恒等式であることは中学・高校の代数の知識で証明できます． ポイントは，両辺の右側の因数がともに \left( 1 - x + x^{2} \right)^{x \cdot y} で因数分解できることです． \begin{aligned} 1 + x^{3} & = (1 + x) \cdot \left( 1 - x + x^{2} \right), \\ 1 + x^{2} + x^{4} & = \left( 1 + x + x^{2} \right) \cdot \left( 1 - x + x^{2} \right), \end{aligned} \begin{aligned} & \left( (1 + x)^{y} + \left( 1 + x + x^{2} \right)^{y} \right)^{x} \cdot \left( \left( 1 + x^{3} \right)^{x} + \left( 1 + x^{2} + x^{4} \right)^{x} \right)^{y} \\ = & \left( (1 + x)^{y} + \left( 1 + x + x^{2} \right)^{y} \right)^{x} \cdot \left( (1 + x)^{x} + \left( 1 + x + x^{2} \right)^{x} \right)^{y} \cdot \left( 1 - x + x^{2} \right)^{x \cdot y} \\ = & \left( (1 + x)^{x} + \left( 1 + x + x^{2} \right)^{x} \right)^{y} \cdot \left( (1 + x)^{y} + \left( 1 + x + x^{2} \right)^{y} \right)^{x} \cdot \left( 1 - x + x^{2} \right)^{x \cdot y} \\ = & \left( (1 + x)^{x} + \left( 1 + x + x^{2} \right)^{x} \right)^{y} \cdot \left( \left( 1 + x^{3} \right)^{y} + \left( 1 + x^{2} + x^{4} \right)^{y} \right)^{x}. \end{aligned} ここで，1 - x + x^{2} という負の項を含む因数が出てきてしまいました． 従って上記の変形は HSI の基本法則の範囲では行うことができません．

このように，負の項を含まないが，証明するには負の項を含む因数分解を行わなければならない恒等式を見つけることが，この問題を解決する鍵となっていました．

Wilkie の恒等式が基本法則から証明できないこと

Wilkie の恒等式が上記の因数分解によっては証明できないことはわかりましたが，これが Tarski の問題の反例となっていることを確かめるには他のどんな方法でも証明できないことを示す必要があります． 証明できないことの証明というと何から手を付ければいいのか分からなくなりますが，ここでモデル理論の手法を用いると明確な方針を立てることができます．

モデル理論の手法とはつまり，いま考えたい集合 \mathbb{N} とは別に，加法・乗法・累乗の３つの演算をもつミニチュアの集合を作ることです． たとえば，1,2,3 の3つの要素からなる集合 M = \left\{ 1,2,3 \right\} に，以下のように演算を定義します．

(\uparrow は累乗を表します．「行・演算・列」の計算結果が表の値です．)

このようにして定めた3つの演算は，\mathbb{N} における演算と同様にHSI の 11 個の等式を満たすことが確かめられます． すなわち，HSI の等式のみによって証明できる恒等式は，証明をそのまま M のものに置き換えることで M においても恒等式になることが示せます．

\begin{aligned} & {\text{等式}\ {f\left( x_{1},\ldots,x_{n} \right) = g\left( x_{1},\ldots,x_{n} \right)}\ が\ \text{HSI}\ \text{で証明可能}} \\ \Longrightarrow & {\text{等式}\ {f\left( x_{1},\ldots,x_{n} \right) = g\left( x_{1},\ldots,x_{n} \right)}\ は\ M\ \text{において恒等式}} \end{aligned}

このような HSI の等式を満たす演算を備えた集合を HSI のモデルと呼びます． 上の議論を繰り返せば，HSI で証明可能な恒等式は，HSI のどんなモデルにおいても恒等式にならなければなりません． したがって，Wilkie の等式が成り立たないような HSI のモデルを見つけることができれば，対偶により Wilkie の等式が HSI で証明可能でないことが示せます(こういったモデルを反例モデルといいます)．

残念ながら，先に挙げたような小さな M では Wilkie の等式は普通に成り立ってしまいます． Wilkie の等式の反例モデルを見つけるのは簡単ではなく，現在見つかっている最小の反例モデルは，S. Burris, K. Yeats(2001) によって計算機を援用して発見された，12個の要素からなる以下のモデルです³． M = \left\{ 1,2,3,4,a,b,c,d,e,f,g,h \right\}

規則性があるようなないような，奇妙な演算です． しかしともかく，この3演算は確かに HSI の等式を満たしていて，モデル M において x = a,y = e とすると Wilkie の等式の両辺は異なる値になります．

\begin{aligned} \left( (a + 1)^{e} + \left( a^{2} + a + 1 \right)^{e} \right)^{a} \cdot \left( \left( a^{3} + 1 \right)^{a} + \left( a^{4} + a^{2} + 1 \right)^{a} \right)^{e} & = h, \\ \begin{array}{r} \\ \left( (a + 1)^{a} + \left( a^{2} + a + 1 \right)^{a} \right) \end{array}^{e} \cdot \left( \left( a^{3} + 1 \right)^{e} + \left( a^{4} + a^{2} + 1 \right)^{e} \right)^{a} & = 4. \end{aligned}

このことを手計算で確かめるのはほぼ無理なのでプログラムを書いて検証してみましょう． 今回は Julia を使います．

まずは演算表を定義します．

a = 5
b = 6
c = 7
d = 8
e = 9
f = 10
g = 11
h = 12

Add = [
    2 3 4 4 2 3 d 3 3 3 3 4
    3 4 4 4 3 4 3 4 4 4 4 4
    4 4 4 4 4 4 4 4 4 4 4 4
    4 4 4 4 4 4 4 4 4 4 4 4
    2 3 4 4 b 4 b 3 h 3 3 4
    3 4 4 4 4 4 4 4 4 4 4 4
    d 3 4 4 b 4 b 3 3 3 3 4
    3 4 4 4 3 4 3 4 4 4 4 4
    3 4 4 4 h 4 3 4 4 3 h 4
    3 4 4 4 3 4 3 4 3 4 3 4
    3 4 4 4 3 4 3 4 h 3 4 4
    4 4 4 4 4 4 4 4 4 4 4 4]

Mul = [
    1 2 3 4 a b c d e f g h
    2 4 4 4 b 4 b 4 4 4 4 4
    3 4 4 4 4 4 4 4 4 4 4 4
    4 4 4 4 4 4 4 4 4 4 4 4
    a b 4 4 c b c b h 4 4 4
    b 4 4 4 b 4 b 4 4 4 4 4
    c b 4 4 c b c b 4 4 4 4
    d 4 4 4 b 4 b 4 4 4 4 4
    e 4 4 4 h 4 4 4 4 4 h 4
    f 4 4 4 4 4 4 4 4 4 4 4
    g 4 4 4 4 4 4 4 h 4 4 4
    h 4 4 4 4 4 4 4 4 4 4 4]

Pow = [
    1 1 1 1 1 1 1 1 1 1 1 1
    2 4 4 4 4 4 4 4 f 4 4 4
    3 4 4 4 e 4 4 4 g 4 e h
    4 4 4 4 4 4 4 4 4 4 4 4
    a c c c c c c c c c c c
    b 4 4 4 4 4 4 4 4 4 4 4
    c c c c c c c c c c c c
    d 4 4 4 f 4 4 4 4 4 4 4
    e 4 4 4 4 4 4 4 h 4 4 4
    f 4 4 4 4 4 4 4 4 4 4 4
    g 4 4 4 h 4 4 4 4 4 h 4
    h 4 4 4 4 4 4 4 4 4 4 4]

次に，HSI の等式をすべて満たすことを確かめます．

for x ∈ 1:h, y ∈ 1:h
    @assert Add[x, y] == Add[y, x]
    @assert Mul[x, y] == Mul[y, x]
end

for x ∈ 1:h, y ∈ 1:h, z ∈ 1:h
    @assert Add[x, Add[y, z]] == Add[Add[x, y], z]
    @assert Mul[x, Mul[y, z]] == Mul[Mul[x, y], z]
end

for x ∈ 1:h, y ∈ 1:h, z ∈ 1:h
    @assert Mul[x, Add[y, z]] == Add[Mul[x, y], Mul[x, z]]
end

for x ∈ 1:h
    @assert Mul[x, 1] == x
    @assert Pow[x, 1] == x
    @assert Pow[1, x] == 1
end

for x ∈ 1:h, y ∈ 1:h, z ∈ 1:h
    @assert Pow[x, Add[y, z]] == Mul[Pow[x, y], Pow[x, z]]
    @assert Pow[Mul[x, y], z] == Mul[Pow[x, z], Pow[y, z]]
    @assert Pow[Pow[x, y], z] == Pow[x, Mul[y, z]]
end

最後に，x = a,y = e のときの Wilkie の等式の両辺を計算し，異なることを確認します．

w₁(x, y) =
    Mul[Pow[Add[
                Pow[Add[x, 1], y],
                Pow[Add[Add[Pow[x, 2], x], 1], y]
            ], x],
        Pow[Add[
                Pow[Add[Pow[x, 3], 1], x],
                Pow[Add[Add[Pow[x, 4], Pow[x, 2]], 1], x]
            ], y]]
w₂(x, y) =
    Mul[Pow[Add[
                Pow[Add[x, 1], x],
                Pow[Add[Add[Pow[x, 2], x], 1], x]
            ], y],
        Pow[Add[
                Pow[Add[Pow[x, 3], 1], y],
                Pow[Add[Add[Pow[x, 4], Pow[x, 2]], 1], y]
            ], x]]

@assert w₁(a, e) == h
@assert w₂(a, e) == 4
@assert w₁(a, e) ≠ w₂(a, e)

println("All assertions passed")

するとすべてのアサーションが通り，実際にこれが反例モデルとなることが確かめられます．

> All assertions passed

Wilkie 自身は反例モデルを構成しない愚直な方法で証明しており，反例モデルを構成することによる証明は R. Gurevič(1985) によって行われました． 最初に構成された反例モデルは要素数が 59 で，そこから徐々に小さい例が見つかっていき，2001 年に S. Burris と K. Yeats が上述のの 12 要素の反例モデルを発見して以降，要素数の更新はありません． 一方，要素数 10 以下の反例モデルは存在しないことは確かめられており⁴，要素数 11 の反例モデルが存在するかどうかは 2024 年 1 月現在未解決のようです．

まとめ

Tarski の高校代数問題は非常に素朴な問いでありながら，「証明できる」「証明できない」それぞれの方法論を学ぶことのできる面白い問題です． 問題に減法や除法を組み込むにはどうすればいいか，ほかの演算を取り入れた場合にはどうなるかなど，さまざまに派生させて考えることのできる問題ですので，興味のある方は是非深堀りしてみてください．

本記事はS. Burris, K. Yeats, The saga of the High School Identities を参考にしています． 関連する問題を含めて幅広く紹介されているサーベイとなっているため，さらに知りたい方は読んでみることをお勧めします．

またモデル理論・普遍代数的な方法論については Model Theory: An Introduction や A Course in Universal Algebra などの入門文献を参照してみてください．