En matemáticas , el teorema de Tarski-Seidenberg establece que un conjunto en un espacio de dimensión ( n + 1) definido por ecuaciones e inecuaciones polinómicas puede proyectarse hacia abajo en un espacio de dimensión n , y el conjunto resultante sigue siendo definible en términos de identidades e inecuaciones polinómicas. El teorema , también conocido como propiedad de proyección de Tarski-Seidenberg, recibe su nombre de Alfred Tarski y Abraham Seidenberg . [1] Implica que la eliminación de cuantificadores es posible sobre los reales , es decir, que toda fórmula construida a partir de ecuaciones e inecuaciones polinómicas mediante conectivos lógicos ∨ ( o ), ∧ ( y ), ¬ ( no ) y cuantificadores ∀ ( para todo ), ∃ ( existe ) es equivalente a una fórmula similar sin cuantificadores. Una consecuencia importante es la decidibilidad de la teoría de cuerpos reales cerrados .
Aunque la demostración original del teorema era constructiva , el algoritmo resultante tiene una complejidad computacional demasiado alta para utilizar el método en un ordenador. George E. Collins introdujo el algoritmo de descomposición algebraica cilíndrica , que permite la eliminación de cuantificadores sobre los reales en tiempo exponencial doble . Esta complejidad es óptima, ya que hay ejemplos en los que la salida tiene un número exponencial doble de componentes conexos. Este algoritmo es, por tanto, fundamental, y se utiliza ampliamente en geometría algebraica computacional .
Un conjunto semialgebraico en R n es una unión finita de conjuntos definidos por un número finito de ecuaciones y desigualdades polinómicas, es decir, por un número finito de enunciados de la forma
y
para los polinomios p y q . Definimos una función de proyección π : R n +1 → R n enviando un punto ( x 1 , ..., x n , x n +1 ) a ( x 1 , ..., x n ). Entonces el teorema de Tarski-Seidenberg establece que si X es un conjunto semialgebraico en R n +1 para algún n ≥ 1, entonces π ( X ) es un conjunto semialgebraico en R n .
Si sólo definimos conjuntos utilizando ecuaciones polinómicas y no desigualdades, entonces definimos conjuntos algebraicos en lugar de conjuntos semialgebraicos. Para estos conjuntos el teorema falla, es decir, las proyecciones de conjuntos algebraicos no necesitan ser algebraicas. Como ejemplo simple, considere la hipérbola en R 2 definida por la ecuación
Este es un conjunto algebraico perfectamente bueno, pero al proyectarlo hacia abajo enviando ( x , y ) en R 2 a x en R se produce el conjunto de puntos que satisfacen x ≠ 0. Este es un conjunto semialgebraico, pero no es un conjunto algebraico ya que los conjuntos algebraicos en R son R mismo, el conjunto vacío y los conjuntos finitos.
Este ejemplo muestra también que, sobre los números complejos , la proyección de un conjunto algebraico puede ser no algebraica. Por lo tanto, la existencia de conjuntos algebraicos reales con proyecciones no algebraicas no depende del hecho de que el cuerpo de los números reales no sea algebraicamente cerrado .
Otro ejemplo es la parábola en R 2 , que está definida por la ecuación
Su proyección sobre el eje x es la semirrecta [0, ∞), un conjunto semialgebraico que no puede obtenerse a partir de conjuntos algebraicos mediante intersecciones (finitas) , uniones y complementos de conjuntos .
Este resultado confirmó que los conjuntos semialgebraicos en R n forman lo que ahora se conoce como una estructura o-minimal en R . Estas son colecciones de subconjuntos S n de R n para cada n ≥ 1 tales que podemos tomar uniones y complementos finitos de los subconjuntos en S n y el resultado todavía estará en S n , además los elementos de S 1 son simplemente uniones finitas de intervalos y puntos. La condición final para que tal colección sea una estructura o-minimal es que la función de proyección en las primeras n coordenadas de R n +1 a R n debe enviar subconjuntos en S n +1 a subconjuntos en S n . El teorema de Tarski-Seidenberg nos dice que esto se cumple si S n es el conjunto de conjuntos semialgebraicos en R n .
