Namespaces
Variants
Actions

Difference between revisions of "O-minimal"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (link)
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100202.png" /> be a first-order language containing a binary [[relation symbol]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100203.png" /> and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100204.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100205.png" />-structure (cf. [[Structure(2)|Structure]]) in which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100206.png" /> is interpreted as a total order (cf. [[Order (on a set)|Order (on a set)]]). Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100207.png" /> is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100208.png" />-minimal if every parametrically definable subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o1100209.png" /> is a finite union of intervals of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002010.png" />. An interval of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002011.png" /> is a subset of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002012.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002013.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002014.png" /> stand for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002015.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002016.png" />. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002017.png" />, a subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002018.png" /> of the Cartesian product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002019.png" /> is called parametrically definable if there are an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002020.png" />-formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002021.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002022.png" /> such that
+
Let $L$ be a first-order language containing a binary [[relation symbol]] $<$ and let $M$ be an $L$-structure (cf. [[Structure(2)|Structure]]) in which $<$ is interpreted as a [[total order]] (cf. [[Order (on a set)|Order (on a set)]]). Then $M$ is called $o$-minimal if every parametrically definable subset of $M$ is a finite union of intervals of $M$. An interval of $M$ is a subset of the form $\{ x \in M : a <_1 x <_2 b \}$ for some $a,b \in M \cup \{\pm\infty \}$, where $<_1,\,<_2$ stand for $<$ or $\le$. For $n \ge 1$, a subset $A$ of the Cartesian product $M^n$ is called parametrically definable if there are an $L$-formula $\phi(x_1,\ldots,x_n,y_1,\ldots,y_k)$ and $b_1,\ldots,b_k \in M$ such that
 +
$$
 +
A = \{ (a_1,\ldots,a_n) \in M^n : \phi(a_1,\ldots,a_n,b_1,\ldots,b_k)\ \text{is true in}\ M \} \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002023.png" /></td> </tr></table>
+
An [[elementary theory]] is called $o$-minimal if every model of it is $o$-minimal.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002024.png" /></td> </tr></table>
+
This notion was introduced by L. van den Dries in [[#References|[a2]]], while studying the expansion $(\mathbf{R},\exp)$ of the ordered field $\mathbf{R}$ of the real numbers by the [[Exponential function, real|real exponential function]].   He observed that the sets parametrically definable in Cartesian products $M^n$ for an $o$-minimal expansion $M$ of $\mathbf{R}$ share many of the geometric properties of [[semi-algebraic set]]s. For example, a semi-algebraic set has only finitely many connected components, each of them semi-algebraic (cf. [[#References|[a1]]]), and van den Dries showed that this result remains true if one replaces  "semi-algebraic"  by  "parametrically definable in an $o$-minimal expansion of $\mathbf{R}$" . This is a finiteness theorem, and van den Dries aims to explain the other finiteness phenomena in real algebraic and real analytic geometry as consequences of $o$-minimality (cf. [[#References|[a3]]]).
 
 
An [[Elementary theory|elementary theory]] is called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002025.png" />-minimal if every model of it is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002026.png" />-minimal.
 
 
 
This notion was introduced by L. van den Dries in [[#References|[a2]]], while studying the expansion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002027.png" /> of the ordered field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002028.png" /> of the real numbers by the real exponential function (cf. [[Exponential function, real|Exponential function, real]]). He observed that the sets parametrically definable in Cartesian products <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002029.png" /> for an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002030.png" />-minimal expansion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002031.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002032.png" /> share many of the geometric properties of semi-algebraic sets (cf. [[Semi-algebraic set|Semi-algebraic set]]). For example, a semi-algebraic set has only finitely many connected components, each of them semi-algebraic (cf. [[#References|[a1]]]), and van den Dries showed that this result remains true if one replaces  "semi-algebraic"  by  "parametrically definable in an o-minimal expansion of R" . This is a finiteness theorem, and van den Dries aims to explain the other finiteness phenomena in real algebraic and real analytic geometry as consequences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002034.png" />-minimality (cf. [[#References|[a3]]]).
 
  
 
In [[#References|[a6]]], J.F. Knight, A. Pillay and C. Steinhorn prove the following results.
 
In [[#References|[a6]]], J.F. Knight, A. Pillay and C. Steinhorn prove the following results.
  
1) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002035.png" />-minimality is preserved under elementary equivalence.
+
1) $o$-minimality is preserved under [[elementary equivalence]].
  
2) An [[Ordered group|ordered group]] is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002036.png" />-minimal if and only if it is divisible Abelian.
+
2) An [[ordered group]] is $o$-minimal if and only if it is divisible Abelian.
  
3) An [[Ordered ring|ordered ring]] is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002037.png" />-minimal if and only if it is a [[Real closed field|real closed field]].
+
3) An [[ordered ring]] is $o$-minimal if and only if it is a [[real closed field]].
  
4) Any parametrically definable unary function in an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002038.png" />-minimal structure is piecewise strictly monotone or constant, and continuous. The real closed field <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002039.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002040.png" />-minimal. The expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002041.png" /> by restricted analytic functions (cf. [[Model theory of the real exponential function|Model theory of the real exponential function]]) is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002042.png" />-minimal (cf. [[#References|[a4]]]), as a consequence of Gabrielov's theorem of the complement that the complement of a subanalytic set is subanalytic (cf. [[#References|[a5]]]). It follows from work of A. Wilkie [[#References|[a7]]] that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002043.png" /> is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002044.png" />-minimal. His recent generalization of Gabrielov's theorem establishes the much stronger result that the expension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002045.png" /> by Pfaffian chains of total functions is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002046.png" />-minimal, see [[#References|[a8]]]. A. Macintyre, van den Dries and D. Marker establish in [[#References|[a4]]] the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002047.png" />-minimality of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002048.png" /> expanded by the restricted analytic functions and the exponential function. For a research account on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002049.png" />-minimal structures, see [[#References|[a3]]].
+
4) Any parametrically definable unary function in an $o$-minimal structure is piecewise strictly monotone or constant, and continuous. The real closed field $\mathbf{R}$ is $o$-minimal. The expansion of $\mathbf{R}$ by restricted analytic functions (cf. [[Model theory of the real exponential function]]) is $o$-minimal (cf. [[#References|[a4]]]), as a consequence of Gabrielov's theorem of the complement that the complement of a subanalytic set is subanalytic (cf. [[#References|[a5]]]). It follows from work of A. Wilkie [[#References|[a7]]] that $(\mathbf{R},\exp)$ is $o$-minimal. His recent generalization of Gabrielov's theorem establishes the much stronger result that the expansion of $\mathbf{R}$ by Pfaffian chains of total functions is $o$-minimal, see [[#References|[a8]]]. A. Macintyre, van den Dries and D. Marker establish in [[#References|[a4]]] the $o$-minimality of $\mathbf{R}$ expanded by the restricted analytic functions and the exponential function. For a research account on $o$-minimal structures, see [[#References|[a3]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.E. Collins,  "Quantifier elimination for real closed fields by cylindrical algebraic decomposition, automata theory and formal language" , ''2nd G.I. Conf. Kaiserslautern'' , Springer  (1975)  pp. 134–183</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  L. van den Dries,  "Remarks on Tarski's problem concerning <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002050.png" />"  G. Lolli (ed.)  G. Longo (ed.)  A. Marcja (ed.) , ''Logic Colloquium '82'' , North-Holland  (1984)  pp. 97–121</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  L. van den Dries,  "o-minimal structures"  W. Hodges (ed.)  M. Hyland (ed.)  C. Steinhorn (ed.)  J. Truss (ed.) , ''Logic: From Foundations to Applications, European Logic Colloquium'' , Oxford  (1996)  pp. 137–185</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  L. van den Dries,  A.J. Macintyre,  D. Marker,  "The elementary theory of restricted analytic fields with exponentiation"  ''Ann. of Math.'' , '''140'''  (1994)  pp. 183–205</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Gabrielov,  "Projections of semi-analytic sets"  ''Funct. Anal. Appl.'' , '''2'''  (1968)  pp. 282–291</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J.F. Knight,  A. Pillay,  C. Steinhorn,  "Definable sets in ordered structures I, II"  ''Trans. Amer. Math. Soc.'' , '''295'''  (1986)  pp. 565–605</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.J. Wilkie,  "Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function"  ''J. Amer. Math. Soc.'' , '''9''' :  4  (1996)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A.J. Wilkie,  "A general theorem of the complement and new <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o110/o110020/o11002051.png" />-minimal expansions of the reals" , manuscript  (1996)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  G.E. Collins,  "Quantifier elimination for real closed fields by cylindrical algebraic decomposition, automata theory and formal language" , ''2nd G.I. Conf. Kaiserslautern'' , Springer  (1975)  pp. 134–183</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  L. van den Dries,  "Remarks on Tarski's problem concerning $(\mathbf{R},{+},{\cdot},\exp)$"  G. Lolli (ed.)  G. Longo (ed.)  A. Marcja (ed.) , ''Logic Colloquium '82'' , North-Holland  (1984)  pp. 97–121</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  L. van den Dries,  "$o$-minimal structures"  W. Hodges (ed.)  M. Hyland (ed.)  C. Steinhorn (ed.)  J. Truss (ed.) , ''Logic: From Foundations to Applications, European Logic Colloquium'' , Oxford  (1996)  pp. 137–185</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  L. van den Dries,  A.J. Macintyre,  D. Marker,  "The elementary theory of restricted analytic fields with exponentiation"  ''Ann. of Math.'' , '''140'''  (1994)  pp. 183–205</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Gabrielov,  "Projections of semi-analytic sets"  ''Funct. Anal. Appl.'' , '''2'''  (1968)  pp. 282–291</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  J.F. Knight,  A. Pillay,  C. Steinhorn,  "Definable sets in ordered structures I, II"  ''Trans. Amer. Math. Soc.'' , '''295'''  (1986)  pp. 565–605</TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top">  A.J. Wilkie,  "Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function"  ''J. Amer. Math. Soc.'' , '''9''' :  4  (1996)</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top">  A.J. Wilkie,  "A general theorem of the complement and new $o$-minimal expansions of the reals" , manuscript  (1996)</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Latest revision as of 09:27, 26 November 2016

Let $L$ be a first-order language containing a binary relation symbol $<$ and let $M$ be an $L$-structure (cf. Structure) in which $<$ is interpreted as a total order (cf. Order (on a set)). Then $M$ is called $o$-minimal if every parametrically definable subset of $M$ is a finite union of intervals of $M$. An interval of $M$ is a subset of the form $\{ x \in M : a <_1 x <_2 b \}$ for some $a,b \in M \cup \{\pm\infty \}$, where $<_1,\,<_2$ stand for $<$ or $\le$. For $n \ge 1$, a subset $A$ of the Cartesian product $M^n$ is called parametrically definable if there are an $L$-formula $\phi(x_1,\ldots,x_n,y_1,\ldots,y_k)$ and $b_1,\ldots,b_k \in M$ such that $$ A = \{ (a_1,\ldots,a_n) \in M^n : \phi(a_1,\ldots,a_n,b_1,\ldots,b_k)\ \text{is true in}\ M \} \ . $$

An elementary theory is called $o$-minimal if every model of it is $o$-minimal.

This notion was introduced by L. van den Dries in [a2], while studying the expansion $(\mathbf{R},\exp)$ of the ordered field $\mathbf{R}$ of the real numbers by the real exponential function. He observed that the sets parametrically definable in Cartesian products $M^n$ for an $o$-minimal expansion $M$ of $\mathbf{R}$ share many of the geometric properties of semi-algebraic sets. For example, a semi-algebraic set has only finitely many connected components, each of them semi-algebraic (cf. [a1]), and van den Dries showed that this result remains true if one replaces "semi-algebraic" by "parametrically definable in an $o$-minimal expansion of $\mathbf{R}$" . This is a finiteness theorem, and van den Dries aims to explain the other finiteness phenomena in real algebraic and real analytic geometry as consequences of $o$-minimality (cf. [a3]).

In [a6], J.F. Knight, A. Pillay and C. Steinhorn prove the following results.

1) $o$-minimality is preserved under elementary equivalence.

2) An ordered group is $o$-minimal if and only if it is divisible Abelian.

3) An ordered ring is $o$-minimal if and only if it is a real closed field.

4) Any parametrically definable unary function in an $o$-minimal structure is piecewise strictly monotone or constant, and continuous. The real closed field $\mathbf{R}$ is $o$-minimal. The expansion of $\mathbf{R}$ by restricted analytic functions (cf. Model theory of the real exponential function) is $o$-minimal (cf. [a4]), as a consequence of Gabrielov's theorem of the complement that the complement of a subanalytic set is subanalytic (cf. [a5]). It follows from work of A. Wilkie [a7] that $(\mathbf{R},\exp)$ is $o$-minimal. His recent generalization of Gabrielov's theorem establishes the much stronger result that the expansion of $\mathbf{R}$ by Pfaffian chains of total functions is $o$-minimal, see [a8]. A. Macintyre, van den Dries and D. Marker establish in [a4] the $o$-minimality of $\mathbf{R}$ expanded by the restricted analytic functions and the exponential function. For a research account on $o$-minimal structures, see [a3].

References

[a1] G.E. Collins, "Quantifier elimination for real closed fields by cylindrical algebraic decomposition, automata theory and formal language" , 2nd G.I. Conf. Kaiserslautern , Springer (1975) pp. 134–183
[a2] L. van den Dries, "Remarks on Tarski's problem concerning $(\mathbf{R},{+},{\cdot},\exp)$" G. Lolli (ed.) G. Longo (ed.) A. Marcja (ed.) , Logic Colloquium '82 , North-Holland (1984) pp. 97–121
[a3] L. van den Dries, "$o$-minimal structures" W. Hodges (ed.) M. Hyland (ed.) C. Steinhorn (ed.) J. Truss (ed.) , Logic: From Foundations to Applications, European Logic Colloquium , Oxford (1996) pp. 137–185
[a4] L. van den Dries, A.J. Macintyre, D. Marker, "The elementary theory of restricted analytic fields with exponentiation" Ann. of Math. , 140 (1994) pp. 183–205
[a5] A. Gabrielov, "Projections of semi-analytic sets" Funct. Anal. Appl. , 2 (1968) pp. 282–291
[a6] J.F. Knight, A. Pillay, C. Steinhorn, "Definable sets in ordered structures I, II" Trans. Amer. Math. Soc. , 295 (1986) pp. 565–605
[a7] A.J. Wilkie, "Model completeness results for expansions of the ordered field of real numbers by restricted Pfaffian functions and the exponential function" J. Amer. Math. Soc. , 9 : 4 (1996)
[a8] A.J. Wilkie, "A general theorem of the complement and new $o$-minimal expansions of the reals" , manuscript (1996)
How to Cite This Entry:
O-minimal. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=O-minimal&oldid=39425
This article was adapted from an original article by S. Kuhlmann (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article