Теорема Тарского – Зайденберга - 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 .
Смотрите также
Рекомендации
- ван ден Дрис, Л. (1998). Ручная топология и о-минимальные структуры . Серия лекций Лондонского математического общества. 248 . Издательство Кембриджского университета . Zbl 0953.03045 .
- Хованский, Аскольд Г. (1991). Немногочисленные . Переводы математических монографий. 88 . Перевод с русского Смилки Здравковской. Провиденс, Род-Айленд: Американское математическое общество . ISBN 0-8218-4547-0. Zbl 0728.12002 .
- Нейман, Абрахам (2003). «Реальные алгебраические инструменты в стохастических играх» . Стохастические игры и приложения . Дордрехт: Клувер. С. 57–75. ISBN 1-4020-1492-9.
Внешние ссылки
- Теорема Тарского – Зайденберга на PlanetMath.org