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

редактировать

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

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

Содержание

  • 1 Утверждение
  • 2 Неудача с алгебраическими множествами
  • 3 Связь со структурами
  • 4 См. Также
  • 5 Ссылки
  • 6 Внешние ссылки

Утверждение

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

p (x 1,…, xn) = 0 {\ displaystyle p (x_ {1}, \ ldots, x_ {n}) = 0 \,}p (x_ {1}, \ ldots, x_ {n}) = 0 \,

и

q (x 1,…, xn)>0 {\ displaystyle q (x_ {1}, \ ldots, x_ {n})>0 \,}q(x_{1},\ldots,x_{n})>0 \,

для многочленов p и q. Мы определяем карту проекции π : R→ Rпутем отправки точки (x 1,..., x n,xn + 1) в (x 1,..., x n). Тогда теорема Тарского – Зайденберга утверждает, что если X - полуалгебраическое множество в R для некоторого n ≥ 1, то π (X) является полуалгебраическим множеством в R.

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

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

xy - 1 = 0. {\ displaystyle xy-1 = 0. \,}{\ displaystyle xy-1 = 0. \,}

Это является совершенно хорошим алгебраическим множеством, но проецируя его вниз, отправляя (x, y) в R в x в R, получаем набор точек, удовлетворяющих x ≠ 0. Это полуалгебраический набор, но это не алгебраический набор, поскольку алгебраические множества в R - это сам R, пустой набор и конечные множества.

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

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

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

См. Также

Ссылки

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

Последняя правка сделана 2021-06-09 10:25:26
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте