Model-theoretic research

[Click here to download this document as a PDF.]

The current focus of my research is definable Skolem functions in weakly o-minimal structures, specifically constructive definitions of Skolem functions. I have found an explicit construction of Skolem functions for a subclass of valuational weakly o-minimal theories called T-immune, where it was known that there were definable Skolem functions, but for which there was no construction. I have also analyzed a certain subclass of nonvaluational weakly o-minimal structures, regarded colloquially to be as close as possible to being o-minimal, and found that such theories in fact do not have definable Skolem functions.

I currently have a paper in preparation which narrates the results outlined above and some extensions to more general cases.

Background

For the purpose of this introduction, a model M is a set (called the universe of the model) together with a specified algebraic structure of definable sets, which may be subsets of the universe M itself, or of Mn for a finite integer n. A canonical example of a model is the field of real numbers, (R,+,·,0,1,<), in which case the definable subsets are precisely the semialgebraic subsets of Rn.

An o-minimal structure is a model M whose definable sets include a dense linear order on the universe, and for which any definable set of M is a finite union of points and intervals (whose infema and suprema are elements of the universe). The real field is the archetype for this study. During the past several decades, a rash of work has led to a powerful structure theory for general o-minimal structures (cf. [6] [8] [11] [12]). Among the properties enjoyed by this class, every o-minimal structure has a strong cellular decomposition property which guarantees all definable subsets Mn can be written as a finite union of simple definable subsets, called cells.

Independently of this, Skolem functions were developed initially in order to prove what is now known as the Löwenheim-Skolem theorem (cf. [2]). Given a model M and definable set DMn, a Skolem function is a function f such that for every aMn-1, if there is some yM so that (a,y) ∈ D, then (a, f(a)) ∈ D.

Informally, one says that a Skolem function finds a witness for D, if there is one. Skolem functions are useful in their own right, both in providing conditions for model completeness, and as a tool used in automated theorem-proving. Any o-minimal model with a group operation (an o-minimal group) can also be shown to have definable Skolem functions. The algorithm for determining Skolem functions expands upon the following simple case: if D(x,y) ⊆ M2 defines, for every fixed value of x, an interval, then value of the Skolem function for each a is the midpoint of the interval defined by the set D(a,y). O-minimal structures also satisfy the related property of having uniform elimination of imaginaries.

Weakly o-minimal structures generalize o-minimal structures by allowing each definable subset of the model M to be a finite union of convex sets which are not necessarily intervals. Consider the ordered group of rational numbers, (Q,+,<). This structure is o-minimal. If we add to the structure the definable set P={xQ: x<π}, then the resulting expansion (Q, +, <, P) is not o-minimal: the supremum of the set named by P is not a rational number, thus P cannot represent an interval in Q. But this set is convex in Q, and it can be shown that the expanded structure is weakly o-minimal. In fact, it is shown by Baizhanov in [1] that any o-minimal theory, if new convex subsets are introduced, yields a weakly o-minimal theory. A more complex structure of this type is the real-closed valued field (R, +, ·, 0, 1, <, V), in which R is a real-closed field with value ring V. This theory (called RCVF) is also weakly o-minimal, and the model theory is explored at length in [3], [4], and [10].

In view of these facts, there is a large program of study concerned with determining which of the properties of o-minimal groups also hold true in the weakly o-minimal case. The authors of [9] distinguish between a valuational weakly o-minimal group, in which there is a proper definable subgroup, and a nonvaluational weakly o-minimal group. They showed that while weakly o-minimal groups in general need not have cellular decomposition, the class of nonvaluational weakly o-minimal groups does have an analogue of this property.

My research projects

Proposition: Let T be a weakly o-minimal theory with uniform elimination of imaginaries and definable Skolem functions, and MT. Then M is nonvaluational.

This proposition actually arises as a simple corollary of a deeper lemma, which may yet have some broader consequences.

Lemma: Let M be a model of a weakly o-minimal theory T which has definable Skolem functions and uniform elimination of imaginaries. Then there is no equivalence relation E definable on M with infinitely many convex equivalence classes of nonzero length.

It is shown in [10] that under certain limitations, real-closed valued fields have elimination of imaginaries. A possible consequence of this along with the proposition is that such structures will fail to have definable Skolem functions; in future research I hope to be able to determine whether this is the case.

Hoping to understand the implications of the above results, we began studying the class of properly nonvaluational weakly o-minimal models, in order to see whether there in fact are any such models which satisfy the conditions of the proposition. A natural class of these is the nonvaluational weakly o-minimal theories obtained by adding a predicate for a new nonvaluational convex subset to an o-minimal structure. However, this work turned up the surprising result that in fact such structures cannot have definable Skolem functions at all.

Theorem: Let M be an o-minimal expansion of an ordered group in the language L. Let U be a new unary predicate symbol, L'=L &cup {U}, and M'=(M,U), where UM' is a downward-closed convex set which defines a properly convex nonvaluational cut. Then M' does not have definable Skolem functions in L'.

The proof of this theorem is based in part on work by L. van Den Dries on dense pairs of o-minimal structures (cf. [5]), and relied on my lemma below, which establishes the connection between weakly o-minimal structures and dense pairs of o-minimal structures.

Lemma: Let M be o-minimal with language L; let L' = L ∪ {U}, and M' = (M, U) with UM' a downward-closed nonvaluational convex set, and N = pr(M ∪ {b}), where b realizes tpC(sup U / M). Then for any X ⊆ M definable in M', there is an L-formula φX (x,y) such that X=φX(Nn,b) ∩ Mn.

Finally, we investigated the question of Skolem functions in valuational models obtained in the same way. In this work, I discovered an algorithmic way to prove the existence of Skolem functions in a subclass of such models.

Definition: Let M be an o-minimal expansion of an ordered group, and VM be a convex set. We say that the pair (M, V) is T-immune if VM and for any 0-definable function F: MM and any open convex set IVM, if F restricted to I is continuous, then F(V) ⊆ V.

As an example of T-immunity, consider a nonstandard model of the real group, M=(R*, +, <, 0), where RR*, and consider V interpreted by R. Then (M, V) is valuational and has a weakly o-minimal theory, and in particular is T-immune.

Theorem: Let (M, +, <, 0, ε, ...) be an o-minimal expansion of a group with named positive element ε in a language L which admits elimination of quantifiers, and V⊆ M such that (M,V) is T-immune. (Note that since ε ∈ L, then εM ∈ V.) Let c be a new constant symbol and cM>0 an element of M\V. Then (M, V, c) has definable Skolem functions in the language L ∪ {V,c}.

L. van den Dries has studied theories with a property known as T-convexity, which generalizes the notion of T-immunity. The authors of [7] showed that T-convex theories also have definable Skolem functions. I am currently working on generalizing the algorithm for calculating Skolem functions in a T-immune theory to the T-convex case in order to give an explicit construction.

A natural extension of these results would be a precise set of conditions for definable Skolem functions in any weakly o-minimal theory. For technical reasons, there are many theories which fail to be T-convex, but may be made so by augmenting the language in a simple way. Modulo a reasonable concept of "almost T-convexity," I am investigating now whether it is true that no weakly o-minimal theory obtained by the Baizhanov technique which fails to be "almost T-convex" has definable Skolem functions. For now, the chief method for doing this is to generalize the concept of dense pairs to theories which may be valuational.

last updated 2010

References

[1] B. Baizhanov, "Expansion of a model of a weakly o-minimal structure by a family of convex predicates," J. Symb. Log. 66 No. 3, 1382-1414 (2001).
[2] C. Chang, H. J. Keisler, Model Theory, Studies in Logic and the Foundations of Mathematics, vol 73 (Elsevier, Amsterdam 1973).
[3] G. Cherlin, M. A. Dickmann, "Real closed rings I: Residue rings of rings of continuous functions," Fund. Math. 126 147-183 (1986).
[4] G. Cherlin, M. A. Dickmann, "Real closed rings II: Model theory," Ann. Pure App. Logic 25 213-231 (1983).
[5] L. van den Dries, "Dense pairs of o-minimal structures," Fund. Math. 157, 61-78 (1998).
[6] L. van den Dries, Tame Topology and O-minimal Structures, London Mathematical Society Lecture Note Series, vol. 248 (Cambridge University Press, Cambridge 1998).
[7] L. van den Dries, A. H. Lewenberg, "T-Convexity and tame extensions," J. Symb. Log. 60 No. 1, 74-102 (1995).
[8] J. Knight, A. Pillay, C.Steinhorn, "Definable sets and ordered structures II," Trans. AMS 295, 593-605 (1986).
[9] D. MacPherson, D. Marker, C. Steinhorn, "Weakly o-minimal structures and real closed fields," Trans. Amer. Math. Soc. \textbf{352} No. 12, 5435-5483 (2000).
[10] T. Mellor, "Imaginaries in real closed valued fields," Ann. Pure App. Logic 139, 230-279 (2006).
[11] A. Pillay, C. Steinhorn, "Definable sets in ordered structures I," Trans. AMS 295, 565-592 (1986).
[12] A. Pillay, C. Steinhorn, "Definable sets in ordered structures III," Trans. AMS 309, 469-476 (1988).