stringtranslate.com

Teoría O-mínimo

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

  1. S n es un álgebra booleana de subconjuntos de M n
  2. si D  ∈  S n entonces M  ×  D y D  × M están en S n +1
  3. el conjunto {( x 1 ,..., x n ) ∈  M n  :  x 1  =  x n } está en S n
  4. 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

  1. el conjunto < (={( x , y ) ∈  M 2  :  x  <  y }) está en S 2
  2. los subconjuntos definibles de M son precisamente las uniones finitas de intervalos y puntos.

La "o" significa "orden", ya que cualquier estructura o-mínimo 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:

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

  1. ^ Knight, Pillay y Steinhorn (1986), Pillay y Steinhorn (1988).
  2. ^ Marcador (2002) p.81
  3. ^ 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.
  4. ^ Marcador (2002) p.99
  5. ^ 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
  6. ^ Marcador (2002) p.103
  7. ^ 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.
  8. ^ 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.
  9. ^ 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).
  10. ^ 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

enlaces externos