Теорема Тарского – Зайденберга. - Tarski–Seidenberg theorem

В математика, то Теорема Тарского – Зайденберга. утверждает, что набор в (п + 1) -мерное пространство, определяемое полиномиальные уравнения и неравенство может быть спроецирован на п-мерное пространство, и получившееся множество все еще можно определить в терминах полиномиальных тождеств и неравенств. Теорема, также известная как свойство проекции Тарского – Зайденберга, названа в честь Альфред Тарский и Авраам Зайденберг.^[1] Это означает, что исключение квантора возможна над вещественными числами, то есть любая формула, построенная из полиномиальных уравнений и неравенств с помощью логических связок ∨ (или же), ∧ (и), ¬ (нет) и кванторы ∀ (для всех), ∃ (существуют) эквивалентна аналогичной формуле без кванторов. Важным следствием является разрешимость теории реально закрытые поля.

Хотя первоначальное доказательство теоремы было конструктивным, полученный алгоритм имеет вычислительная сложность это слишком много для использования метода на компьютере. Джордж Э. Коллинз представил алгоритм цилиндрическое алгебраическое разложение, что позволяет исключить квантор над вещественными числами в двойное экспоненциальное время. Эта сложность оптимальна, поскольку есть примеры, когда на выходе имеется двойное экспоненциальное число связанных компонентов. Таким образом, этот алгоритм является фундаментальным и широко используется в вычислительная алгебраическая геометрия.

Заявление

А полуалгебраическое множество в р^п представляет собой конечное объединение множеств, определяемых конечным числом полиномиальных уравнений и неравенств, то есть конечным числом утверждений вида

{displaystyle p (x_ {1}, ldots, x_ {n}) = 0,}

и

{displaystyle q (x_ {1}, ldots, x_ {n})> 0,}

для многочленов п и q. Определим карту проекции π : р^п+1 → р^п отправив точку (Икс₁,...,Икс_п,Икс_п+1) к (Икс₁,...,Икс_п). Тогда теорема Тарского – Зайденберга утверждает, что если Икс полуалгебраическое множество в р^п+1 для некоторых п ≥ 1, то π(Икс) - полуалгебраическое множество в р^п.

Неудача с алгебраическими множествами

Если мы определяем множества только с помощью полиномиальных уравнений, а не неравенств, то мы определяем алгебраические множества скорее, чем полуалгебраические множества. Для этих множеств теорема неверна, т.е. проекции алгебраических множеств не обязательно должны быть алгебраическими. В качестве простого примера рассмотрим гипербола в р² определяется уравнением

{displaystyle xy-1 = 0.,}

Это совершенно хороший алгебраический набор, но его можно спроецировать, отправив (Икс,у) в р² к Икс в р производит набор точек, удовлетворяющих $Икс \neq 0$ . Это полуалгебраическое множество, но это не алгебраическое множество, как алгебраические множества в р находятся р сам, пустой набор и конечные множества.

Этот пример также показывает, что для комплексных чисел проекция алгебраического множества может быть неалгебраической. Таким образом, существование вещественных алгебраических множеств с неалгебраическими проекциями не основывается на том факте, что поле действительных чисел не является алгебраически замкнутый.

Отношение к конструкциям

Этот результат подтвердил, что полуалгебраические множества в р^п сформировать то, что сейчас известно как о-минимальная структура на р. Это коллекции подмножеств S_п из р^п для каждого п ≥ 1 такое, что мы можем взять конечные объединения и дополнения подмножеств в S_п и результат все равно будет в S_п, причем элементы S₁ представляют собой просто конечные объединения интервалов и точек. Последним условием того, чтобы такая коллекция была о-минимальной структурой, является то, что отображение проекции на первом п координаты от р^п+1 к р^п должен отправить подмножества в S_п+1 к подмножествам в S_п. Теорема Тарского – Зайденберга говорит нам, что это верно, если S_п - множество полуалгебраических множеств в р^п.

Смотрите также

Разрешимость теории действительных чисел первого порядка

внешняя ссылка

Теорема Тарского – Зайденберга. на PlanetMath.org

[1] Мишра, Бхубанешвар (1993). Алгоритмическая алгебра. Нью-Йорк: Спрингер. стр.345 –347. ISBN 0-387-94090-1.

[1]