Задача об экспоненциальной функции Тарского - Tarskis exponential function problem

В теория моделей, Проблема экспоненциальной функции Тарского спрашивает, есть ли теория из действительные числа вместе с экспоненциальная функция является разрешимый. Альфред Тарский ранее показал, что теория действительных чисел (без экспоненциальной функции) разрешима.

Проблема

Упорядоченное реальное поле р это структура над языком заказанные кольца L_{или же} = (+, ·, -, <, 0,1), причем каждому символу дана обычная интерпретация. Тарский доказал, что теория реальное поле, Чт (р), разрешима. То есть при любом L_{или же}-приговор φ существует эффективная процедура определения того,

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

Затем он спросил, будет ли это по-прежнему так, если к языку добавить унарную функцию exp, которая интерпретировалась как экспоненциальная функция на р, чтобы получить структуру р_exp.

Условные и эквивалентные результаты

Проблема может быть сведена к поиску эффективной процедуры для определения того, экспоненциальный многочлен в п переменные и с коэффициентами в Z имеет решение в р^п. Макинтайр и Уилки (1995) показало, что Гипотеза Шануэля подразумевает, что такая процедура существует, и, следовательно, дала условное решение проблемы Тарского. Гипотеза Шануэля имеет дело со всеми комплексными числами, поэтому можно было бы ожидать, что это будет более сильный результат, чем разрешимость р_exp, и действительно, Макинтайр и Уилки доказали, что требуется только реальная версия гипотезы Шануэля, чтобы сделать вывод о разрешимости этой теории.

Даже настоящая версия гипотезы Шануэля не является необходимое условие на разрешимость теории. В своей статье Макинтайр и Уилки показали, что результат, эквивалентный разрешимости Th (р_exp) - это то, что они назвали гипотезой Слабого Шануэля. Эта гипотеза утверждает, что существует эффективная процедура, которая при условии п ≥ 1 и экспоненциальные многочлены от п переменные с целыми коэффициентами ж₁,..., ж_п, грамм, производит целое число η ≥ 1, что зависит от п, ж₁,..., ж_п, грамм, и такой, что если α ∈ р^п это неособый решение системы

${\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}$

тогда либо грамм(α) = 0 или |грамм(α)| > η⁻¹.

Обходной путь

В последнее время предпринимаются попытки обработать теорию действительных чисел с помощью таких функций, как exp, sin, путем ослабления разрешимости до более слабого понятия квазиразрешимости. Теория квазиразрешима, если существует процедура, которая определяет выполнимость, но может выполняться бесконечно для входных данных, которые не являются надежными в определенном, четко определенном смысле. Такая процедура существует для систем из n уравнений от n переменных (Франек, Ратчан и Згличински (2011) ).

Рекомендации

• Kuhlmann, S. (2001) [1994], «Модельная теория действительной экспоненциальной функции», Энциклопедия математики, EMS Press
• Macintyre, A.J .; Уилки, А.Дж. (1995), «О разрешимости действительного экспоненциального поля», в Odifreddi, P.G. (ред.), Том 70-летия Крейзеля, CLSI
• Франек, Питер; Ратшан, Стефан; Згличинский, Петр (2011), "Выполнимость систем уравнений вещественных аналитических функций квазиразрешима", Математические основы компьютерных наук 2011, LNCS, 6907, Спрингер, Дои:10.1007/978-3-642-22993-0_30