O-minimal theory

<h2 id="set-theoretic-definition">Set-theoretic definition</h2>
O-minimal structures can be defined without recourse to model theory. Here we define a structure on a nonempty set M in a set-theoretic manner, as a sequence S = (Sn), n = 0,1,2,... such that

<ol><li>Sn is a <a href="/facts/Boolean_algebra_(structure)/cHbo65jm">boolean algebra</a> of subsets of Mn</li>
<li>if D ∈ Sn then M × D and D ×M are in Sn+1</li>
<li>the set {(x1,...,xn) ∈ Mn : x1 = xn} is in Sn</li>
<li>if D ∈ Sn+1 and π : Mn+1 → Mn is the projection map on the first n coordinates, then π(D) ∈ Sn.</li></ol>
For a subset A of M, we consider the smallest structure S(A) containing S such that every finite subset of A is contained in S1. A subset D of Mn is called A-definable if it is contained in Sn(A); in that case A is called a set of parameters for D. A subset is called definable if it is A-definable for some A.
If M has a dense linear order without endpoints on it, say <, then a structure S on M is called o-minimal (respect to <) if it satisfies the extra axioms

<ol>
<li>the set  < (={(x,y) ∈ M2 : x < y}) is in S2
</li><li>the definable subsets of M are precisely the finite unions of intervals and points.
</li></ol>
The "o" stands for "order", since any o-minimal structure requires an ordering on the underlying set.

<h2 id="model-theoretic-definition">Model theoretic definition</h2>
O-minimal structures originated in model theory and so have a simpler — but equivalent — definition using the language of model theory.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> Specifically if L is a language including a binary relation <, and (M,<,...) is an L-structure where < is interpreted to satisfy the axioms of a dense linear order,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> then (M,<,...) is called an o-minimal structure if for any definable set X ⊆ M there are finitely many open intervals I1,..., Ir in M ∪ {±∞} and a finite set X0 such that

X
        =
        
          X
          
            0
          
        
        ∪
        
          I
          
            1
          
        
        ∪
        …
        ∪
        
          I
          
            r
          
        
        .
      
    
    {\displaystyle X=X_{0}\cup I_{1}\cup \ldots \cup I_{r}.}

<h2 id="examples">Examples</h2>
Examples of o-minimal theories are:

<ul><li>The complete theory of dense linear orders in the language with just the ordering.</li>
<li>RCF, the <a href="/facts/Theory/9vrNS1Rr">theory</a> of <a href="/facts/Real_closed_field/Vj1Un2fw">real closed fields</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>The complete theory of the <a href="/facts/Real_number/R02gw5Pb">real field</a> with restricted <a href="/facts/Analytic_function/JhL3z8FP">analytic functions</a> added (i.e. analytic functions on a neighborhood of [0,1]n, restricted to [0,1]n; note that the unrestricted sine function has infinitely many roots, and so cannot be definable in an o-minimal structure.)</li>
<li>The complete theory of the real field with a symbol for the <a href="/facts/Exponential_function/ewlYxvR2">exponential function</a> by <a href="/facts/Wilkie%27s_theorem/0Bv7FGvj">Wilkie's theorem</a>. More generally, the complete theory of the real numbers with <a href="/facts/Pfaffian_function/wNt4A2Y3">Pfaffian functions</a> added.</li>
<li>The last two examples can be combined: given any o-minimal expansion of the real field (such as the real field with restricted analytic functions), one can define its Pfaffian closure, which is again an o-minimal structure.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> (The Pfaffian closure of a structure is, in particular, closed under Pfaffian chains where arbitrary definable functions are used in place of polynomials.)</li></ul>
In the case of RCF, the definable sets are the <a href="/facts/Semialgebraic_set/S8My37ww">semialgebraic sets</a>. Thus the study of o-minimal structures and theories generalises <a href="/facts/Real_algebraic_geometry/lkHGrkLn">real algebraic geometry</a>. A major line of current research is based on discovering expansions of the real ordered field that are o-minimal. Despite the generality of application, one can show a great deal about the geometry of set definable in o-minimal structures. There is a cell decomposition theorem,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> <a href="/facts/Hassler_Whitney/ljAyGQME">Whitney</a> and <a href="/facts/Jean-Louis_Verdier/nR3cH3Lj">Verdier</a> <a href="/facts/Stratification_(mathematics)/RXXeG04r">stratification</a> theorems and a good notion of dimension and Euler characteristic.
Moreover, continuously differentiable definable functions in a o-minimal structure satisfy a generalization of <a href="/facts/%C5%81ojasiewicz_inequality/fIpHNbez">Łojasiewicz inequality</a>,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> a property that has been used to guarantee the convergence of some non-smooth optimization methods, such as the stochastic subgradient method (under some mild assumptions).<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Semialgebraic_set/S8My37ww">Semialgebraic set</a></li>
<li><a href="/facts/Real_algebraic_geometry/lkHGrkLn">Real algebraic geometry</a></li>
<li><a href="/facts/Strongly_minimal_theory/NofaScbc">Strongly minimal theory</a></li>
<li><a href="/facts/Weakly_o-minimal_structure/V1Rwvkvp">Weakly o-minimal structure</a></li>
<li><a href="/facts/C-minimal_theory/ujq6b4nD">C-minimal theory</a></li>
<li><a href="/facts/Tame_topology/I8XlSrJj">Tame topology</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>van den Dries, Lou (1998). Tame Topology and o-minimal Structures. London Mathematical Society Lecture Note Series. Vol. 248. Cambridge: <a href="/facts/Cambridge_University_Press/fgEBSSRq">Cambridge University Press</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-521-59838-5. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0953.03045">0953.03045</a>.</li>
<li>Marker, David (2000). <a href="https://www.ams.org/bull/2000-37-03/S0273-0979-00-00866-1/S0273-0979-00-00866-1.pdf">"Review of "Tame Topology and o-minimal Structures""</a> (PDF). <a href="/facts/Bulletin_of_the_American_Mathematical_Society/8ER5KY5z">Bulletin of the American Mathematical Society</a>. 37 (3): 351–357. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0273-0979-00-00866-1">10.1090/S0273-0979-00-00866-1</a>.</li>
<li>Marker, David (2002). Model theory: An introduction. Graduate Texts in Mathematics. Vol. 217. New York, NY: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-98760-6. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:1003.03034">1003.03034</a>.</li>
<li>Pillay, Anand; Steinhorn, Charles (1986). <a href="https://www.ams.org/journals/tran/1986-295-02/S0002-9947-1986-0833697-X/S0002-9947-1986-0833697-X.pdf">"Definable Sets in Ordered Structures I"</a> (PDF). <a href="/facts/Transactions_of_the_American_Mathematical_Society/JmKtyCwK">Transactions of the American Mathematical Society</a>. 295 (2): 565–592. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2000052">10.2307/2000052</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2000052">2000052</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0662.03023">0662.03023</a>.</li>
<li><a href="/facts/Julia_F._Knight/HuPQperE">Knight, Julia</a>; Pillay, Anand; Steinhorn, Charles (1986). <a href="https://doi.org/10.2307%2F2000053">"Definable Sets in Ordered Structures II"</a>. <a href="/facts/Transactions_of_the_American_Mathematical_Society/JmKtyCwK">Transactions of the American Mathematical Society</a>. 295 (2): 593–605. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2000053">10.2307/2000053</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2000053">2000053</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0662.03024">0662.03024</a>.</li>
<li>Pillay, Anand; Steinhorn, Charles (1988). <a href="https://doi.org/10.2307%2F2000920">"Definable Sets in Ordered Structures III"</a>. <a href="/facts/Transactions_of_the_American_Mathematical_Society/JmKtyCwK">Transactions of the American Mathematical Society</a>. 309 (2): 469–476. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F2000920">10.2307/2000920</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/2000920">2000920</a>. <a href="/facts/Zbl_(identifier)/P6rFxKKx">Zbl</a> <a href="https://zbmath.org/?format=complete&q=an:0707.03024">0707.03024</a>.</li>
<li><a href="/facts/Alex_Wilkie/wXGaHqa0">Wilkie, A.J.</a> (1996). <a href="https://www.ams.org/jams/1996-9-04/S0894-0347-96-00216-0/S0894-0347-96-00216-0.pdf">"Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function"</a> (PDF). <a href="/facts/Journal_of_the_American_Mathematical_Society/qR98drCm">Journal of the American Mathematical Society</a>. 9 (4): 1051–1095. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1090%2FS0894-0347-96-00216-0">10.1090/S0894-0347-96-00216-0</a>.</li>
<li>Denef, J.; van den Dries, L. (1989). "p-adic and real subanalytic sets". <a href="/facts/Annals_of_Mathematics/CUYktUqD">Annals of Mathematics</a>. 128 (1): 79–138. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.2307%2F1971463">10.2307/1971463</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/1971463">1971463</a>.</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.logique.jussieu.fr/modnet/Publications/Preprint%20server/">Model Theory preprint server</a></li>
<li><a href="http://www.maths.manchester.ac.uk/raag/">Real Algebraic and Analytic Geometry Preprint Server</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Knight, Pillay and Steinhorn (1986), Pillay and Steinhorn (1988). <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Marker (2002) p.81 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">The condition that the interpretation of < be dense is not strictly necessary, but it is known that discrete orders lead to essentially trivial o-minimal structures, see, for example, MR0899083 and MR0943306. <a href="/wiki/MR_(identifier)" target="_blank">/wiki/MR_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Marker (2002) p.99 <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Patrick Speisseger, Pfaffian sets and o-minimality, in: Lecture notes on o-minimal structures and real analytic geometry, C. Miller, J.-P. Rolin, and P. Speissegger (eds.), Fields Institute Communications vol. 62, 2012, pp. 179–218. doi:10.1007/978-1-4614-4042-0_5 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Marker (2002) p.103 <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Kurdyka, Krzysztof (1998). "On gradients of functions definable in o-minimal structures". Annales de l'Institut Fourier. 48 (3): 769–783. doi:10.5802/aif.1638. ISSN 0373-0956. <a href="https://aif.centre-mersenne.org/item/AIF_1998__48_3_769_0/" target="_blank">https://aif.centre-mersenne.org/item/AIF_1998__48_3_769_0/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Davis, Damek; Drusvyatskiy, Dmitriy; Kakade, Sham; Lee, Jason D. (2020). "Stochastic Subgradient Method Converges on Tame Functions". Foundations of Computational Mathematics. 20 (1): 119–154. arXiv:1804.07795. doi:10.1007/s10208-018-09409-5. ISSN 1615-3375. S2CID 5025719. <a href="http://link.springer.com/10.1007/s10208-018-09409-5" target="_blank">http://link.springer.com/10.1007/s10208-018-09409-5</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Garrigos, Guillaume (2015-11-02). Descent dynamical systems and algorithms for tame optimization, and multi-objective problems (PhD thesis). Université Montpellier; Universidad técnica Federico Santa María (Valparaiso, Chili). <a href="https://tel.archives-ouvertes.fr/tel-02023313" target="_blank">https://tel.archives-ouvertes.fr/tel-02023313</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Ioffe, A. D. (2009). "An Invitation to Tame Optimization". SIAM Journal on Optimization. 19 (4): 1894–1917. doi:10.1137/080722059. ISSN 1052-6234. <a href="http://epubs.siam.org/doi/10.1137/080722059" target="_blank">http://epubs.siam.org/doi/10.1137/080722059</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

O-minimal theory open-in-new

O-minimal theory