# Model theory seminar

# 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.

# 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.