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

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

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

Заявление

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

а также

для многочленов 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 ) из R 2 в x в R дает набор точек, удовлетворяющих x ≠ 0. Это полуалгебраическое множество, но это не алгебраический набор, как алгебраические множества в R - это само R , пустое множество и конечные множества.

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

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

Этот результат подтверждает , что полуалгебраическое множество в R п формы , что теперь известен как о-минимальной структура на 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 .

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

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

Внешние ссылки