Topic Archive: model theory

University of Katowice
CUNY Logic WorkshopFriday, November 13, 20153:45 pmGC 6417

In search of a complete axiomatization for $F_p((t))$

University of Katowice

I will give a survey of the attempts that have been made since the mid 1960’s to find a complete recursive axiomatization of the elementary theory of $F_p((t))$. This problem is still open, and I will describe the difficulties researchers have met in their search. Some new hope has been generated by Yu. Ershov’s observation that $F_p((t))$ is an “extremal” valued field. However, while his intuition was good, his definition of this notion was flawed. It has been corrected in a paper by Azgin, Kuhlmann and Pop, in which also a partial characterization of extremal fields was given. Further progress has been made in a recent manuscript, on which I will report at the AMS meeting at Rutgers. The talk at the Graduate Center will provide a detailed background from the model theoretic point of view.

The property of being an “extremal valued field” is both elementary and very natural, so it is an ideal candidate for inclusion in a (hopefully) complete recursive axiomatization for $F_p((t))$. It implies an axiom scheme that was considered previously, which describes the behavior of additive polynomials under the valuation. I will discuss why additive polynomials are crucial for the model theory of valued fields of positive characteristic.

The open problems around extremal fields provide a good source of research projects of various levels of difficulty for young researchers.

This talk is jointly sponsored by the Commutative Algebra & Algebraic Geometry Seminar and the CUNY Logic Workshop.

CUNY Logic WorkshopFriday, October 9, 20152:00 pmGC 6417

Theories where any definable infinite set has interior

The City University of New York

We consider the case of a theory $T$ which expands that of divisible ordered Abelian groups and has the property that in any model of $T$ any infinite definable subset has non-empty interior (in the order topology). We will call such theories visceral. Visceral theories arise naturally in the study theories with a strong form of the independence property and generalize the class of o-minimal and weakly o-minimal theories. We consider the structure of definable sets and definable functions in visceral theories, giving some weak structural results. We also consider how to build general classes of examples of visceral theories, and relate these example back to questions about strong forms of the independence property.

Model theory seminarFriday, October 30, 201512:30 pmGC 6417

On the Existence of Parametrized Strongly Normal Extensions

In this talk we look at the problem of existence of differential Galois extensions for parameterized logarithmic equations. More precisely, if E and D are two distinguished sets of derivations and K is an E union D-field of characteristic zero, we look at conditions on (K^E,D), the E-constants of K, that guarantee that every (parameterized) E-logarithmic equation over K has a parameterized strongly normal extension. This is joint work with Omar Leon Sanchez.

Model theory seminarFriday, October 23, 201512:30 pmGC 6417

Model theory of generalized Urysohn spaces

University of Notre Dame

Many well known examples of homogeneous metric spaces and graphs can be viewed as analogs of the rational Urysohn space (for example, the random graph as the Urysohn space with distances {0,1,2}). In this talk, I consider the R-Urysohn space, where R is an arbitrary ordered commutative monoid. I will first construct an extension R* of R, such that any model of the theory of the R-Urysohn space (in a relational language) can be given the structure of an R*-metric space. I will then characterize quantifier elimination in this theory by continuity of addition in R*. Finally, I will characterize various model theoretic properties of the R-Urysohn space (e.g. stability, simplicity, weak elimination of imaginaries) using natural algebraic properties of R.

Model theory seminarFriday, October 16, 201512:30 pmGC 6417

Transfer of the Ramsey Property between Classes

Vassar College

In this talk, we investigate some ways in which the property of being Ramsey may be transferred between classes of finite structures. We look at some category-theoretic and model-theoretic approaches.

CUNY Logic WorkshopFriday, October 23, 20152:00 pmGC 6417

On computing VC-density in VC-minimal theories

Towson University

In model theory, theories are typically distinguished by the complexity of their definable families. One popular notion of complexity, Vapnik-Chervonenkis density, is borrowed from statistical learning theory. In this talk, I discuss the general notion of computing VC-density in NIP theories, a notion explored by Aschenbrenner, Dolich, Haskell, MacPherson, and Starchenko in recent work. In this work, they ask if there is a relationship between dp-rank and VC-density. I show a partial result pointing in that direction by studying VC-minimality (a condition stronger than having minimal dp-rank). Any formula in a VC-minimal theory with two parameter variables has VC-density at most two. I conclude by discussing the possibility of extending this result to higher dimensions.

Albert-Ludwigs-Universität Freiburg
CUNY Logic WorkshopFriday, September 4, 20152:00 pmGC 6417

Model theory of right-angled buildings

Albert-Ludwigs-Universität Freiburg
Model theory seminarFriday, September 11, 201512:30 pmGC 6417

Degree spectra of real closed fields

City University of New York

The degree spectrum of a countable structure is the set of all Turing degrees of isomorphic copies of that structure. This topic has been widely studied in computable model theory. Here we examine the possible degree spectra of real closed fields, finding them to offer far more complexity than the related theory of algebraically closed fields. The co-author of this project, Victor Ocasio Gonzalez, showed in his dissertation that, for every linear order L, there exists a real closed field whose spectrum is the pre-image under jump of the spectrum of L. We add further results, distinguishing the cases of archimedean and non-archimedean real closed fields, and splitting the latter into two subcases based on the existence of a least multiplicative class of positive nonstandard elements. If such a class exists, then finiteness in the field is always decidable, but the case with no such class proves more interesting.

CUNY Logic WorkshopFriday, November 13, 20152:00 pmGC 6417

Diophantine approximation, scalar multiplication and decidability

University of Illinois Urbana-Champaign

It has long been known that the first order theory of the expansion (R,<,+,Z) of the ordered additive group of real numbers by just a predicate for the set of integers is decidable. Arguably due to Skolem, the result can be deduced easily from Buechi's theorem on the decidability of monadic second order theory of one successor, and was later rediscovered independently by Weispfenning and Miller. However, a consequence of Goedel's famous first incompleteness theorem states that when expanding this structure by a symbol for multiplication, the theory of the resulting structure (R,<,+,*,Z) becomes undecidable. This observation gives rise to the following natural and surprisingly still open question: How many traces of multiplication can be added to (R,<,+,Z) without making the first order theory undecidable? We will give a complete answer to this question when "traces of multiplication" is taken to mean scalar multiplication by certain irrational numbers. To make this statement precise: for b in R, let f_b: R -> R be the function that takes x to bx. I will show that the theory of (R,<,+,Z,f_b) is decidable if and only if b is quadratic. The proof rests on the observation that many of the Diophantine properties (in the sense of Diophantine approximation) of b can be coded in these structures.

University of Illinois Urbana-Champaign
CUNY Logic WorkshopFriday, October 16, 20152:00 pmGC 6417

The Hanf number for amalgamation

Towson University

In a joint work with Chris Lambie-Hanson, we study a family of abstract elementary classes (AEC) that we call coloring classes. Each coloring class is an AEC in a relational language $L$ containing exactly the $L$-structures whose finite substructures are isomorphic to one of the “allowed” finite structures. The work takes advantage of the fact that model-theoretic properties (e.g., existence of models and amalgamation) can be rephrased as properties of certain coloring functions. This allows us to improve the results of Baldwin, Kolesnikov, and Shelah: we show in ZFC that disjoint amalgamation can hold up to beth_{alpha}, alpha less than omega_1 (previously, only consistency results were known). We also give a partial answer to the question of Grossberg about the Hanf number for amalgamation property (not just disjoint amalgamation).

University of Wisconsin
Uri Andrews received his Ph.D. from the University of California-Berkeley in 2010, as a student of Tom Scanlon, and subsequently took up an assistant professorship (now tenure-track) at the University of Wisconsin. He studies computable model theory, blending techniques from model theory and computability theory.
CUNY Logic WorkshopFriday, May 1, 20152:00 pmGC 6417

A Local Characterization of VC-minimality

University of Wisconsin

(Work joint with Vincent Guingona.) I’ll talk about a problem in the intersection of computable model theory and classical model theory. The notion of VC-minimality, though intriguing, has proven very difficult to work with. It has even been difficult to check whether familiar examples are VC-minimal. This has led model theorists (chiefly my co-author) to ask whether there was a “local” (read “simpler”) characterization of VC-minimality. I suggested a computable model theoretic version of this question in terms of the index set of VC-minimality. We answered this question by giving a local characterization of VC-minimality, and we showed that VC-minimality is a Π04-complete notion.

CUNY Logic WorkshopFriday, March 27, 20152:00 pmGC 6417

Counting lattice points and parametric Presburger formulas

Universidad de los Andes Bogotá Colombia

In 2013, Kevin Woods showed that for a subset S of the d-th Cartesian power of the natural numbers N, the following are equivalent:

(1) S is definable in Presburger arithmetic,
(2) S is a finite union of intersections of polyhedra with translates of lattices,
(3) S has a rational generating function.

More recently, Woods has studied so-called parametric Presburger families: subsets of powers of N definable with addition and the ordering, plus one special “parameter” variable t which can be multiplied by terms in the other variables. The special variable t also ranges over N, but it is the only variable which cannot be quantified over. This is useful for defining many families which are combinatorially interesting, such as the lattice points inside the t-th dilate of a given polyhedron and a version of the Frobenius problem.

Jointly with Tristram Bogart, we are working to understand the properties of parametric Presburger families. We will present a quantifier elimination result and some conjectures of Woods on Skolem functions and counting functions for these families, which we are studying using logical and syntactic methods.

Model theory seminarFriday, March 6, 201512:30 pmGC 6417

Generic Linear Functions over Divisible Ordered Abelian Groups

The City University of New York

Let T be the theory of divisible ordered Abelian groups in a language L
where T has quantifier elimination. Let f be a new unary function symbol. We
would like to consider the L(f)-theory T(a) expanding T together with axioms
for “f is an automorphism”. Unfortunately it is well known that T(a) does not
have a model companion and generally is not easy to analyze. Rather we look at
a weaker theory T(l) once again expanding T but with axioms for “l is a linear
bijection”. T(l) has a model companion and we provide a detailed analysis of
this theory.

Model theory seminarFriday, March 27, 201512:30 pmGC 6417

Independence, via limits

Wesleyan University

Given a large model M of some theory T, I will describe a method for lifting well-behaved notions of independence from the theories of substructures of M to a reasonably well-behaved notion of independence in M. (In essence, we take the limit of the independence relations in the substructures.) The motivating example – two-sorted theories of infinite-dimensional vector spaces over an algebraically closed field and with a bilinear form – was worked out by N. Granger in his thesis. I will outline this example before launching into the more general framework.