En lógica matemática , y más específicamente en teoría de modelos , una estructura infinita ( M ,<,...) que está totalmente ordenada por < se llama estructura o-mínimo si y sólo si cada subconjunto definible X ⊆ M (con parámetros tomados de M ) es una unión finita de intervalos y puntos.
La minimalidad O puede considerarse como una forma débil de eliminación de cuantificadores . Una estructura M es o-mínima si y solo si cada fórmula con una variable libre y parámetros en M es equivalente a una fórmula sin cuantificadores que involucra solo el orden, también con parámetros en M. Esto es análogo a las estructuras mínimas , que son exactamente la propiedad análoga hasta la igualdad.
Una teoría T es una teoría o-mínimo si todo modelo de T es o-mínimo. Se sabe que la teoría completa T de una estructura o-mínimo es una teoría o-mínimo. [1] Este resultado es notable porque, en contraste, la teoría completa de una estructura mínima no necesita ser una teoría fuertemente mínima , es decir, puede haber una estructura elementalmente equivalente que no sea mínima.
Definición de teoría de conjuntos
Las estructuras O-mínimas se pueden definir sin recurrir a la teoría de modelos. Aquí definimos una estructura en un conjunto no vacío M de manera teórica de conjuntos, como una secuencia S = ( S n ), n = 0,1,2,... tal que
- S n es un álgebra booleana de subconjuntos de M n
- si D ∈ S n entonces M × D y D × M están en S n +1
- el conjunto {( x 1 ,..., x n ) ∈ M n : x 1 = x n } está en S n
- si D ∈ S n +1 y π : M n +1 → M n es el mapa de proyección en las primeras n coordenadas, entonces π ( D ) ∈ S n .
Para un subconjunto A de M , consideramos la estructura más pequeña S ( A ) que contiene S tal que cada subconjunto finito de A está contenido en S 1 . Un subconjunto D de M n se llama A -definible si está contenido en S n ( A ); en ese caso A se llama conjunto de parámetros para D . Un subconjunto se llama definible si es A -definible para algún A .
Si M tiene un orden lineal denso sin puntos finales, digamos <, entonces una estructura S en M se llama o-mínima (con respecto a <) si satisface los axiomas adicionales
- el conjunto < (={( x , y ) ∈ M 2 : x < y }) está en S 2
- los subconjuntos definibles de M son precisamente las uniones finitas de intervalos y puntos.
La "o" significa "orden", ya que cualquier estructura mínima o requiere un orden en el conjunto subyacente.
Definición teórica del modelo
Las estructuras O-mínimas se originaron en la teoría de modelos y, por lo tanto, tienen una definición más simple, pero equivalente, utilizando el lenguaje de la teoría de modelos. [2] Específicamente, si L es un lenguaje que incluye una relación binaria <, y ( M ,<,...) es una estructura L donde < se interpreta para satisfacer los axiomas de un orden lineal denso, [3] entonces ( M ,<,...) se llama estructura o-mínimo si para cualquier conjunto definible X ⊆ M hay un número finito de intervalos abiertos I 1 ,..., I r en M ∪ {±∞} y un conjunto finito X 0 tal que
Ejemplos
Ejemplos de teorías o-mínimas son:
- La teoría completa de los órdenes lineales densos en el lenguaje con solo el orden.
- RCF, la teoría de los campos cerrados reales . [4]
- La teoría completa del campo real con funciones analíticas restringidas agregadas (es decir, funciones analíticas en una vecindad de [0,1] n , restringidas a [0,1] n ; tenga en cuenta que la función seno no restringida tiene infinitas raíces, por lo que no puede ser definible en una estructura o-mínima.)
- La teoría completa del campo real con un símbolo para la función exponencial según el teorema de Wilkie . De manera más general, se agregó la teoría completa de los números reales con funciones pfaffianas .
- Los dos últimos ejemplos se pueden combinar: dada cualquier expansión o-mínima del campo real (como el campo real con funciones analíticas restringidas), se puede definir su cierre pfaffiano, que es nuevamente una estructura o-mínimo. [5] (El cierre Pfaffiano de una estructura está, en particular, cerrado bajo cadenas Pfaffianas donde se utilizan funciones arbitrarias definibles en lugar de polinomios).
En el caso de RCF, los conjuntos definibles son los conjuntos semialgebraicos . Así, el estudio de estructuras y teorías mínimas generaliza la geometría algebraica real . Una importante línea de investigación actual se basa en descubrir expansiones del campo ordenado real que son o-mínimas. A pesar de la generalidad de la aplicación, se puede mostrar mucho sobre la geometría del conjunto definible en estructuras o-mínimas. Existe un teorema de descomposición celular, [6] teoremas de estratificación de Whitney y Verdier y una buena noción de dimensión y característica de Euler.
Además, funciones definibles continuamente diferenciables en una estructura mínima o satisfacen una generalización de la desigualdad de Łojasiewicz , [7] una propiedad que se ha utilizado para garantizar la convergencia de algunos métodos de optimización no suaves, como el método de subgradiente estocástico (bajo algunas condiciones suaves). supuestos). [8] [9] [10]
Ver también
Notas
- ^ Knight, Pillay y Steinhorn (1986), Pillay y Steinhorn (1988).
- ^ Marcador (2002) p.81
- ^ La condición de que la interpretación de < sea densa no es estrictamente necesaria, pero se sabe que los órdenes discretos conducen a estructuras o-mínimas esencialmente triviales, véanse, por ejemplo, MR 0899083 y MR 0943306.
- ^ Marcador (2002) p.99
- ^ Patrick Speisseger, Conjuntos de Pfaffian y o-minimidad, en: Apuntes de conferencias sobre estructuras o-mínimas y geometría analítica real, C. Miller, J.-P. Rolin y P. Speissegger (eds.), Fields Institute Communications vol. 62, 2012, págs. 179-218. doi :10.1007/978-1-4614-4042-0_5
- ^ Marcador (2002) p.103
- ^ Kurdyka, Krzysztof (1998). "Sobre gradientes de funciones definibles en estructuras o-mínimas". Anales del Instituto Fourier . 48 (3): 769–783. doi : 10.5802/aif.1638 . ISSN 0373-0956.
- ^ Davis, Damek; Drusvyatskiy, Dmitriy; Kakade, farsa; Lee, Jason D. (2020). "El método estocástico de subgradiente converge en funciones domesticadas". Fundamentos de la Matemática Computacional . 20 (1): 119-154. arXiv : 1804.07795 . doi :10.1007/s10208-018-09409-5. ISSN 1615-3375. S2CID 5025719.
- ^ Garrigos, Guillaume (2 de noviembre de 2015). Sistemas dinámicos de descenso y algoritmos para optimización mansa y problemas multiobjetivo (tesis doctoral). Universidad Montpellier; Universidad técnica Federico Santa María (Valparaíso, Chile).
- ^ Ioffe, ANUNCIO (2009). "Una invitación a la optimización domesticada". Revista SIAM sobre Optimización . 19 (4): 1894-1917. doi :10.1137/080722059. ISSN 1052-6234.
Referencias
- van den Dries, Lou (1998). Topología domesticada y estructuras mínimas . Serie de notas de conferencias de la Sociedad Matemática de Londres. vol. 248. Cambridge: Prensa de la Universidad de Cambridge . ISBN 978-0-521-59838-5. Zbl 0953.03045.
- Marcador, David (2000). "Revisión de" Topología domesticada y estructuras mínimas"" (PDF) . Boletín de la Sociedad Matemática Estadounidense . 37 (3): 351–357. doi : 10.1090/S0273-0979-00-00866-1 .
- Marcador, David (2002). Teoría de modelos: una introducción . Textos de Posgrado en Matemáticas. vol. 217. Nueva York, Nueva York: Springer-Verlag . ISBN 978-0-387-98760-6. Zbl 1003.03034.
- Pillay, Anand; Steinhorn, Charles (1986). «Conjuntos definibles en estructuras ordenadas I» (PDF) . Transacciones de la Sociedad Matemática Estadounidense . 295 (2): 565–592. doi : 10.2307/2000052 . JSTOR 2000052. Zbl 0662.03023.
- Caballero, Julia ; Pillay, Anand; Steinhorn, Charles (1986). "Conjuntos definibles en estructuras ordenadas II". Transacciones de la Sociedad Matemática Estadounidense . 295 (2): 593–605. doi : 10.2307/2000053 . JSTOR 2000053. Zbl 0662.03024.
- Pillay, Anand; Steinhorn, Charles (1988). "Conjuntos definibles en estructuras ordenadas III". Transacciones de la Sociedad Matemática Estadounidense . 309 (2): 469–476. doi : 10.2307/2000920 . JSTOR 2000920. Zbl 0707.03024.
- Wilkie, AJ (1996). "Resultados de completitud del modelo para expansiones del campo ordenado de números reales mediante funciones de Pfaff restringidas y la función exponencial" (PDF) . Revista de la Sociedad Matemática Estadounidense . 9 (4): 1051-1095. doi : 10.1090/S0894-0347-96-00216-0 .
- Denef, J.; van den Dries, L. (1989). " Conjuntos subanalíticos p -ádicos y reales". Anales de Matemáticas . 128 (1): 79-138. doi :10.2307/1971463. JSTOR 1971463.
enlaces externos
- Servidor de preimpresión de teoría de modelos
- Servidor de preimpresión de geometría analítica y algebraica real