В математике теорема Тарского–Зейденберга утверждает, что множество в ( n + 1)-мерном пространстве, определенное полиномиальными уравнениями и неравенствами, может быть спроецировано на n -мерное пространство, и полученное множество по-прежнему определимо в терминах полиномиальных тождеств и неравенств. Теорема , также известная как свойство проекции Тарского–Зейденберга, названа в честь Альфреда Тарского и Авраама Зейденберга . [1] Она подразумевает, что элиминация кванторов возможна над вещественными числами , то есть каждая формула, построенная из полиномиальных уравнений и неравенств логическими связками ∨ ( или ), ∧ ( и ), ¬ ( не ) и кванторами ∀ ( для всех ), ∃ ( существует ) , эквивалентна аналогичной формуле без кванторов. Важным следствием является разрешимость теории вещественно -замкнутых полей .
Хотя первоначальное доказательство теоремы было конструктивным , полученный алгоритм имеет вычислительную сложность , которая слишком высока для использования метода на компьютере. Джордж Э. Коллинз представил алгоритм цилиндрической алгебраической декомпозиции , который позволяет исключить квантификатор по действительным числам за двойное экспоненциальное время . Эта сложность оптимальна, поскольку существуют примеры, когда выход имеет двойное экспоненциальное число связанных компонентов. Поэтому этот алгоритм является фундаментальным и широко используется в вычислительной алгебраической геометрии .
Полуалгебраическое множество в Rn — это конечное объединение множеств , определяемое конечным числом полиномиальных уравнений и неравенств, то есть конечным числом утверждений вида
и
для полиномов p и q . Мы определяем проекционное отображение π : R n +1 → R n , отправляя точку ( x 1 , ..., x n , x n +1 ) в ( x 1 , ..., x n ). Тогда теорема Тарского–Зейденберга утверждает, что если X является полуалгебраическим множеством в R n +1 для некоторого n ≥ 1, то π ( X ) является полуалгебраическим множеством в R n .
Если мы определяем множества только с помощью полиномиальных уравнений, а не неравенств, то мы определяем алгебраические множества , а не полуалгебраические множества. Для этих множеств теорема неверна, т.е. проекции алгебраических множеств не обязательно должны быть алгебраическими. В качестве простого примера рассмотрим гиперболу в R 2 , заданную уравнением
Это совершенно хорошее алгебраическое множество, но проецирование его вниз путем отправки ( x , y ) в R2 в x в R дает множество точек, удовлетворяющих условию x ≠ 0. Это полуалгебраическое множество, но оно не является алгебраическим множеством, поскольку алгебраическими множествами в R являются само R , пустое множество и конечные множества.
Этот пример также показывает, что над комплексными числами проекция алгебраического множества может быть неалгебраической. Таким образом, существование действительных алгебраических множеств с неалгебраическими проекциями не опирается на тот факт, что поле действительных чисел не является алгебраически замкнутым .
Другим примером является парабола в R 2 , которая определяется уравнением
Его проекция на ось x представляет собой полупрямую [0, ∞), полуалгебраическое множество, которое не может быть получено из алгебраических множеств с помощью (конечных) пересечений , объединений и дополнений множеств .
Этот результат подтвердил, что полуалгебраические множества в R n образуют то, что теперь известно как o-минимальная структура на R . Это наборы подмножеств S n из R n для каждого n ≥ 1, такие, что мы можем взять конечные объединения и дополнения подмножеств в S n , и результат все еще будет в S n , более того, элементы S 1 являются просто конечными объединениями интервалов и точек. Конечное условие для того, чтобы такой набор был o-минимальной структурой, состоит в том, что отображение проекции на первые n координат из R n +1 в R n должно отправлять подмножества в S n +1 в подмножества в S n . Теорема Тарского–Зейденберга говорит нам, что это выполняется, если S n является набором полуалгебраических множеств в R n .
