In mathematical logic, and more specifically in model theory, an infinite structure (M,<,...) that is totally ordered by < is called an o-minimal structure if and only if every definable subset X ⊆ M (with parameters taken from M) is a finite union of intervals and points.

O-minimality can be regarded as a weak form of quantifier elimination. A structure M is o-minimal if and only if every formula with one free variable and parameters in M is equivalent to a quantifier-free formula involving only the ordering, also with parameters in M. This is analogous to the minimal structures, which are exactly the analogous property down to equality.

A theory T is an o-minimal theory if every model of T is o-minimal. It is known that the complete theory T of an o-minimal structure is an o-minimal theory.[1] This result is remarkable because, in contrast, the complete theory of a minimal structure need not be a strongly minimal theory, that is, there may be an elementarily equivalent structure that is not minimal.

Set-theoretic definition

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

  1. Sn is a boolean algebra of subsets of Mn
  2. if D ∈ Sn then M × D and D ×M are in Sn+1
  3. the set {(x1,...,xn) ∈ Mn : x1 = xn} is in Sn
  4. if D ∈ Sn+1 and π : Mn+1 → Mn is the projection map on the first n coordinates, then π(D) ∈ Sn.

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

  1. the set  < (={(x,y) ∈ M2 : x < y}) is in S2
  2. the definable subsets of M are precisely the finite unions of intervals and points.

The "o" stands for "order", since any o-minimal structure requires an ordering on the underlying set.

Model theoretic definition

O-minimal structures originated in model theory and so have a simpler — but equivalent — definition using the language of model theory.[2] 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,[3] 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

Examples

Examples of o-minimal theories are:

In the case of RCF, the definable sets are the semialgebraic sets. Thus the study of o-minimal structures and theories generalises real algebraic geometry. 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,[6] Whitney and Verdier stratification theorems and a good notion of dimension and Euler characteristic.

Moreover, continuously differentiable definable functions in a o-minimal structure satisfy a generalization of Łojasiewicz inequality,[7] 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).[8][9][10]

See also

Notes

  1. ^ Knight, Pillay and Steinhorn (1986), Pillay and Steinhorn (1988).
  2. ^ Marker (2002) p.81
  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.
  4. ^ Marker (2002) p.99
  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
  6. ^ Marker (2002) p.103
  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.
  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.
  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).
  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.

References