タルスキーの指数関数問題

モデル理論において、タルスキの指数関数問題は、指数関数を含む実数の理論が決定可能かどうかを問うものである。アルフレッド・タルスキは以前、指数関数を含まない実数の理論は決定可能であることを示した。^{[ 1 ]}

順序付けられた実数体${\displaystyle \mathbb {R} }$順序付き環の言語上の構造である${\displaystyle L_{\text{or}}=(+,-,<,0,1)}$各記号には通常の解釈が与えられている。タルスキは実体理論が、${\displaystyle \operatorname {Th} (\mathbb {R} )}$は決定可能である。つまり、任意の が与えられた場合、${\displaystyle L_{\text{or}}}$-文${\displaystyle \varphi }$効果的な手順があるかどうか

${\displaystyle \mathbb {R} \models \varphi .}$

彼は次に、単項関数を追加した場合でも同じことが言えるのかと尋ねた。${\displaystyle \exp }$指数関数として解釈された言語へ${\displaystyle \mathbb {R} }$構造を取得するために$\displaystyle \mathbb {R} _{\exp }}$。

この問題は、与えられた指数多項式が${\displaystyle n}$変数と係数${\displaystyle \mathbb {Z} }$解決策があります$\displaystyle \mathbb {R} ^{n}}$マッキンタイアとウィルキー（1996）は、 シャヌエルの予想がそのような手順の存在を示唆していることを示し、タルスキの問題に対する条件付き解を与えた。^{[ 2 ]}シャヌエルの予想はすべての複素数を扱っているので、決定可能性よりも強い結果になると予想される。$\displaystyle \mathbb {R} _{\exp }}$そして実際、マッキンタイアとウィルキーは、この理論の決定可能性を導くには、シャヌエルの予想の実数版のみが必要であることを証明した。

シャヌエル予想の実際のバージョンでさえ、理論の決定可能性の必要条件ではない。マッキンタイアとウィルキーは論文で、決定可能性と同等の結果を示した。${\displaystyle \operatorname {Th} (\mathbb {R} _{\exp })}$これは、彼らが弱いシャヌエル予想と呼んだものです。この予想は、与えられた条件の下で有効な手順が存在すると述べています。${\displaystyle n\geq 1}$指数多項式${\displaystyle n}$整数係数を持つ変数${\displaystyle f_{1},\dots ,f_{n},g}$整数を生成します${\displaystyle \eta \geq 1}$それは${\displaystyle n,f_{1},\dots ,f_{n},g}$、そしてもし$\alpha \in \mathbb {R} ^{n}}$はシステムの非特異解である

${\displaystyle f_{1}(x_{1},\ldots ,x_{n},e^{x_{1}},\ldots ,e^{x_{n}})=\ldots =f_{n}(x_{1},\ldots ,x_{n},e^{x_{1}},\ldots ,e^{x_{n}})=0}$

そして、${\displaystyle g(\alpha )=0}$または${\displaystyle |g(\alpha )|>{\tfrac {1}{\eta }}}$。