# Model theory seminar

# Countable Model Theory and the Complexity of Isomorphism

We discuss the Borel complexity of the isomorphism relation (for countable models of a first order theory) as the “right” generalization of the model counting problem. In this light we present recent results of Dave Sahota and the speaker which completely characterize the complexity of isomorphism for o-minimal theories, as well as recent work of Laskowski and Shelah which give a partial answer for omega-stable theories. Along the way, we introduce a few open problems and barriers to generalizing the existing results.

# Some new maximum VC classes

Vapnik-Chervonenkis classes with the maximum property are in some sense the most perfect set systems of finite Vapnik-Chervonenkis dimension. Definability of maximum VC classes in model theoretic structures is closely tied to other measures of complexity such as dp-rank. In this talk we show that set systems realizable as sets of positivity for linear combinations of real analytic functions have the maximum property on sets in general position. This may have applications to proving lower bounds on dp-rank in certain theories.

# Representing Scott sets in algebraic settings

The long standing problem of representing Scott sets as standard systems of models of Peano Arithmetic is one of the most vexing in the subject. We show that the analogous question has a positive solution for real closed fields and Presburger arithmetic. This is joint work with Alf Dolich, Julia Knight and Karen Lange.

# Independence in tame abstract elementary classes

Good frames are one of the main notions in Shelah’s classification theory for abstract elementary classes. Roughly speaking, a good frame describes a local forking-like notion for the class. In Shelah’s book, the theory of good frames is developed over hundreds of pages, and many results rely on GCH-like hypotheses and sophisticated combinatorial set theory.

In this talk, I will argue that dealing with good frames is much easier if one makes the global assumption of tameness (a locality condition introduced by Grossberg and VanDieren). I will outline a proof of the following result: Assume K is a tame abstract elementary class which has amalgamation, no maximal models, and is categorical in a cardinal of cofinality greater than the tameness cardinal. Then K is stable everywhere and has a good frame.

# Morphic Modules and the Ziegler Spectrum

We will review the definitions of morphic rings and modules, and prove a result concerning conditions equivalent to total uniform morphicity of a ring (all R-modules being morphic in a uniform way). We consider questions such as, which abelian groups are morphic, and when products of morphic modules are morphic. This will lead us to a discussion of the Ziegler spectrum, and its relation to morphicness.

# Model theory of difference fields, part II

This talk is a continuation of last week’s Logic Workshop. The necessary background will be summarized briefly at the beginning of this talk.

**ACFA**, the theory of difference closed fields, is a rich source of explicit examples of forking independence and nonorthogonality, the distinction between stable and simple theories, and the distinction between one-based and locally-modular groups. To present these examples, I will introduce “difference varieties”, which are the basic building blocks of definable sets in **ACFA**, and “sigma-varieties”, a more tractable special case of these.

# Modular Invariant of Quantum Tori

The modular invariant *j ^{qt}* of quantum tori is defined as a discontinuous,

*-invariant multi-valued map of the reals*

**PGL(2,Z)****. For**

*R**θ ∈*

**Q**,

*j*and for quadratic irrationalities, experiments conducted with the PARI/GP computer algebra system suggest that

^{qt}(θ) = ∞*j*is a finite set. In the case of the golden mean φ, we produce explicit formulas for the experimental supremum and infimum of

^{qt}(θ)*j*involving weighted generalizations of the Rogers–Ramanujan functions. Finally, we define a universal modular invariant as a continuous and single-valued map of “ultrasolenoids” (quotients of sheaves of ultrapowers over Stone spaces) from which

^{qt}(φ)*j*as well as the classical modular invariant of elliptic curves may be recovered as subquotients.

^{qt}# No seminars on Sept. 26 or October 3

CUNY will have holidays on two consecutive Fridays, September 26 and October 3, 2014, so the Logic Workshop and other seminars will not meet on those days.

# Model theory and the Painlevé equations

The Painlevé equations are nonlinear 2nd order ODEs and come in six families P1,…, P6, where P1 consists of the single equation $y′′=6y^2+t$, and P2,…, P6 come with some complex parameters. They were discovered strictly for mathematical considerations at the beginning of the 20th century but have arisen in a variety of important physical applications, including for example random matrix theory and general relativity.

# Effective Bounds For Finite Differential-Algebraic Varieties (Part I)

Given a differential algebraic variety over a partial differential field, can one give bounds for the degree of the Zariski closure which depend only on the order and degree of the differential polynomials (but not the parameters) which determine the variety? We will discuss the general theory of prolongations of differential algebraic varieties as developed by Moosa and Scanlon, and use this theory to reduce the problem to a combinatorial problem (which will be discussed in detail in the second part of the talk). Along the way we will give numerous examples of the usefulness of the result, some of an arithmetic flavor. We will also describe some other applications of the theory of prolongations.

This is joint work with Omar Sanchez.

# On compositions of symmetrically and elementarily indivisible structures

A structure M in a first order language L is indivisible if for every colouring of its universe in two colours, there is a monochromatic substructure M’ of M such that M’ is isomorphic to M. Additionally, we say that M is symmetrically indivisible if M’ can be chosen to be symmetrically embedded in M (That is, every automorphism of M’ can be can be extended to an automorphism of M}), and that M is elementarily indivisible if M’ can be chosen to be an elementary substructure.

The notion of indivisibility is a long-studied subject. We will present these strengthenings of the notion,

examples and some basic properties. in [1] several questions regarding these new notions arose: If M is symmetrically indivisible or all of its reducts to a sublanguage symmetrically indivisible? Is an elementarily indivisible structure necessarily homogeneous? Does elementary indivisibility imply symmetric indivisibility?

We will define a new “product” of structures, generalising the notions of lexicographic order and lexicographic product of graphs, which preserves indivisibility properties and use it to answer the questions above.

[1] Assaf Hasson, Menachem Kojman and Alf Onshuus, On symmetric indivisibility of countable structures, Model Theoretic Methods in Finite Combinatorics, AMS, 2011, pp.417–452.

# VC-dimension in model theory and other subjects

Finite VC-dimension, a combinatorial property of families of

sets, was discovered simultaneously by Vapnik and Chervonenkis in the

context of probabilistic learning theory, and by Shelah in model

theory in the context of classification of unstable first-order

theories (where it is called NIP). From the model theoretic point of

view it is a very attractive setting generalizing stability and

o-minimality, and admitting a deep theory which had been recently used

to study ordered and valued fields. I will give an overview of some

results around NIP related to set theory (counting Dedekind cuts in

infinite linear orders), topological dynamics and compression schemes

in computational learning theory.

# Automorphism groups of large models: small index property and AECs

The general question of recovering a model (or its theory, or some appropriate AEC connected to it) from its automorphism group was originally studied by Hodges, Lascar, Shelah among others. The “Small Index Property” (SIP) emerged in their work as a bridge between topological and purely algebraic properties of those groups and ultimately as a tool to understand. I will speak about the SIP from two perspectives: first, I will present aspects of Lascar and Shelah’s proof of SIP for uncountable saturated structures (succinctly, if M is such a structure and G is a subgroup of Aut(M) with index less than or equal to λ=|M|, then G is open in the “λ-topology”) and then I will present an extension of the SIP to some abstract elementary classes. This second part of the lecture is joint work with Zaniar Ghadernezhad.

# Symmetric random constructions in model theory

Several well known universal homogeneous structures, such as the Rado graph and the rational Urysohn space, can be obtained via probabilistic constructions that do not make use of the labeling of the underlying set. Which other countable structures admit random constructions that are symmetric in this way? Several years ago in the CUNY Logic Workshop I presented a characterization of such structures, due to Ackerman, Patel and myself. Here I will report on two recent extensions. This is joint work with Nate Ackerman, Aleksandra Kwiatkowska, Jaroslav Nesetril, and Rehana Patel.

One natural question concerns theories rather than structures. I will present results describing when there are symmetric probabilistic constructions of models of a given theory that assign probability zero to each isomorphism class of models.

One may further ask which structures admit just one such probabilistic construction. I will provide a complete list: there are only five of them, up to interdefinability. Furthermore, any countable structure admitting more than one invariant measure must admit continuum-many ergodic invariant measures.

# Model theoretic advances for groups with bounded chains of centralizers

Stable groups have a rich literature, extending ideas about algebraic groups to a wider setting, using the framework of model theory. Stable groups gain much of their strength through their chain conditions, notably the Baldwin-Saxl chain condition. In this talk, we will concern ourselves with one mild, yet very important, chain condition shared by many infinite groups studied by group theorists. A group $G$ is said to be $M_C$ if every chain of centralizers $C_G(A_1)$ ≤ $C_G(A_2)$ ≤ ⋅ ⋅ ⋅ is finite. This class is not elementary, yet there is increasing evidence that they share many important properties of stable groups. All the present results concern nilpotence in $M_C$ groups. The first results in this area were purely group-theoretic, but recent results by Wagner, Altinel and Baginski have uncovered that some of the desired definability results are also present. We will recount the progress that has been made and the obstacles that researchers in this area face.

# The consistency of Peano Arithmetic

In 1936, only a few years after the incompleteness theorems were proved, Gentzen proved the consistency of Peano arithmetic by using transfinite induction up to the ordinal epsilon_0. I will give a short proof of the result, based on on the simplification introduced by Schutte, and discuss some of the consequences.

# Turing degree spectra of differentially closed fields

The spectrum Spec(_{0} is isomorphic to a computable one. The latter theorem (which relativizes, to give the main result above) resembles the famous result of Downey and Jockusch on Boolean algebras, but the proof is different, yielding a Δ_{2} isomorphism between the low model and its computable copy; moreover, our first theorem shows that the extension of the result to the low_{4} case for Boolean algebras does not hold for _{0}.

This is joint work by Dave Marker and the speaker. The slides for this talk are available here.

# Fullness

A model M of PA is full if, for every set X definable in (M, omega), there is an X’ definable in M with the same standard part (i.e. X intersect omega = X’ intersect omega). I will show a result due to R. Kaye that characterizes fullness: M is full if and only if its standard system is a model of full second order comprehension (CA0). I will give a brief outline of the proof, which involves translations (in both directions) between the language of second order arithmetic and the (first order) language of PA with a “standardness” predicate. If there is time, I also plan to discuss full saturation and some connections to other notions of saturation (in particular, transplendence and possibly arithmetic saturation).

# Ordered structures with dense/co-dense sets

The canonical class of densely ordered structures which may be considered “tame” are the o-minimal structures – namely those structures (M,<,…) where any definable subset

X is a finite union of points and intervals. In this talk I will consider structure (M,<,…) in which there are definable subsets which are dense and co-dense in the line yet which may still be considered “tame”. I will outline some of the general theory of these structures, compare the model theoretic properties of the examples, and discuss various open problems arising out of this study.

# VC Density and Breadth on Modules

I will review the notions of VC-dimension, VC-density, and breadth on modules, before describing and motivating some partial results to open questions from a paper by Aschenbrenner, Dolich, Haskell, Macpherson, and Starchenko.

# Dividing and conquering: locally definable sets as stand-alone structures

In what sense is the ring of polynomials in one variable over a field k interpretable in k? In what sense is the subgroup of G generated by a definable subset D of G interpretable in G? These questions have been answered in various particular contexts by various people. We set up a general formalism to treat such piece-wise interpreted objects as stand-alone multi-sorted first-order structures. This formalism is motivated by our quest to create a model-theoretically tractable analog of sheaf theory. This is a very preliminary report on joint work with Ramin Takloo-Bighash.

# On dense independent subsets of geometric structures

We consider expansions of geometric theories obtained by adding a predicate distinguishing a “dense” independent subset, generalizing a construction introduced by A. Dolich, C. Miller and C. Steinhorn in the o-minimal context. The expansion preserves many of the properties related to stability, simplicity, rosiness and NIP. We also study the structure induced on the predicate, and show that despite its geometric triviality, it inherits most of the “combinatorial” complexity of the original theory. This is a joint work with Alexander Berenstein.

# A class of strange expansions of dense linear orders by open sets

There are expansions of dense linear orders by open sets (of arbitrary arities) such that all of the following hold:

1) Every definable set is a boolean combination of existentially definable sets.

2) Some definable sets are not existentially definable.

3) Some projections of closed bounded definable sets are somewhere both dense and codense.

4) There is a unique maximal reduct having the property that every unary definable set either has interior or is nowhere dense. It properly expands the underlying order, yet is still rather trivial.

At least some of these structures come up naturally in model theory. For example, if G is a generic predicate for the real field, then the expansion of (G,<) by the G-traces of all semialgebraic open sets is such a structure, which moreover is interdefinable with the structure induced on G in (R,+,x,G).

# Seminar Cancelled

Seminar cancelled Lipell will give his talk at 2:00 in the Workshop.

# LE-Series

In this expository talk I will discuss the construction of the field of LE-series after van den Dries, Macintyre, and Marker. The field of LE-series is an ordered differential field extending the field of real Laurent series which also has a well-behaved exponential function. The field of LE-series is closed under a host of operations, in particular it is closed under formal integration as well as compositional inverse (once composition has been properly interpreted). As such this field may be viewed, at least conjecturally, as providing a universal domain for ordered differential algebra as witnessed in Hardy fields.

# Ramsey Transfer Theorems

We survey some of the known approaches to transfer a Ramsey theorem for one class of finite structures to another. We will isolate some easy consequences and point to further directions.

# $\omega_1$-like models of PA

I will give a brief survey of what is known about $omega_1$-like models of PA (much) and what is not known (much).

# Real closures of $omega_1$-like models of PA

In an earlier seminar I showed that assuming diamond we can build many $omega_1$-like models of PA with the same standard system but non-isomorphic real closures. In this lecture I will show how to do this without diamond. This is joint work with Jim Schmerl and Charlie Steinhorn.

# Finite forms of Gowers’ Theorem on the oscillation stability of c_0

We give a constructive proof of the finite version of Gowers’ FIN_k Theorem and analyze the corresponding upper bounds. The FIN_k Theorem is closely related to the oscillation stability of c_0. The stabilization of Lipschitz functions on arbitrary finite dimensional Banach spaces was proved well before by V. Milman. We compare the finite FIN_k Theorem with the Finite Stabilization Principle found by Milman in the case of spaces of the form ell_{infty}^n, ninN, and establish a much slower growing upper bound for the finite stabilization principle in this particular case.

# Resplendent and Transplendent Models

This will be a more systematic overview of several topics mentioned by me an others in several talks last year. In particular, I will go over details of some basic arguments involving chronic resplendence.

# Transplendent models of rich theories

Following up on a talk by Roman Kossak earlier this semester, I will discuss work by Engstrom and Kaye which address the question of existence of transplendent models (models with expansions omitting a type). If there is time, I will talk about transplendent models of PA.

# VC Dimension and Breadth in Modules

I will review the concept of vc-dimension of a formula, and the vc-function of a first order theory. The concept of breadth on the lattice of PP-definable subgroups of a module will be defined, and the relationship between these notions will be explored. Some model theory of Modules will be used to refine certain questions from the paper of Aschenbrenner, Dolich, Haskell, Macpherson, and Starchenko. The talk will include several pictures and examples to clarify the notions involved.

# The Non-Axiomatizability of the First-Order Theory of O-Minimality

For a fixed language L, the first-order L-theory of o-minimality is the set of those L-sentences true in all o-minimal L-structures. It follows from a classical model-theoretic result that a model of this theory is either o-minimal or an elementary substructure of an ultraproduct of o-minimal L-structures. We call these structures pseudo-o-minimal, and note that they will generally not be o-minimal.

In this talk, I will discuss how the study of pseudo-o-minimality fits in to the ongoing project of classifying the tame weakenings of o-minimality. My main focus will be on the recent question of whether for certain fixed languages L, the first-order L-theory of o-minimality is recursively axiomatizable. I will show that it is not whenever L extends the language of ordered fields by at least one new predicate or function symbol. With the time remaining, I will outline some of what is known about the relative tameness of pseudo-o-minimal structures, and mention some open problems in the area.

# Pfaffian functions vs. Rolle leaves

In the early 1980s, after Khovanskii’s ICM lecture, van den Dries formulated the conjecture that the expansion P of the real field by all pfaffian functions was model complete. Thinking about the problem led him to formulate a minimality notion in expansions of the real order, which directly inspired Pillay and Steinhorn in their discovery of o-minimality. However, while P has been known to be o-minimal since Wilkie’s groundbreaking work in 1996, van den Dries’s conjecture is still open today. Recently, Lion and I proved a variant of this conjecture, in which “pfaffian functions” are replaced with “nested Rolle leaves”, which in essence correspond to the objects originally studied by Khovanskii. The mystery lies in how these two expansions are related. I will explain each of them and exhibit a third related notion, found recently in joint work with Jones, which might clarify this relationship.

# Stability revisited

I will discuss an observation Ivo Herzog and I made in the last millennium that yields a purely topological definition of stability of a complete first-order theory in terms of their Stone spaces.

# On strength of weakness

I will explain why countable models of PA which are just recursively saturated do not have maximal automorphisms. If time permits I will also show why recursive saturation implies standard system saturation for models of rich theories.

# Maximal Automorphisms

A maximal automorphism of a structure M is an automorphism under which no non-algebraic element of M is fixed. A problem which has attracted some attention is when for a theory T any countable recursively saturated model of T has a maximal automorphism. In this talk I will review what is known about this problem in various contexts and then prove a general result that guarantees, under certain mild conditions on T, that any countable recursively saturated model of T does indeed have a maximal automorphism.

# Transplendence

Resplendence is a very useful form of second order saturation. Transplendence, introduced by Fredrik Engström and Richard Kaye, is a stronger notion, that guarantees existence of expansions omitting a type. I will give motivation and outline Engström and Kaye’s general theory of transplendent structures.

# Independent sets in computable free groups and fields

We consider maximal independent sets within various sorts of groups and fields freely generated by countably many generators. The simplest example is the free divisible abelian group, which is just an infinite-dimensional rational vector space. As one moves up to free abelian groups, free groups, and “free fields” (i.e. purely transcendental field extensions), maximal independent sets and independent generating sets both become more complicated, from the point of view of computable model theory, but sometimes in unpredictable ways, and certain questions remain open. We present the topic partly for its own sake, but also with the intention of introducing the techniques of computable model theory and illustrating some of its possible uses for an audience to which it may be unfamiliar.

This is joint work with Charles McCoy.

# Organizational Meeting

We’ll meet to discuss topics to be covered for the semester.