Model theory seminar

Model theory seminar

The Model theory seminar meets weekly at the CUNY Graduate Center on Fridays 12:30 until 1:45, covering a broad collection of topics in model theory. The seminar is organized by Alfred Dolich, Roman Kossak, Hans Schoutens and Philipp Rothmaler.
(41 items)

Model theory seminarFriday, May 23, 201412:30 pmGC6417
Nadav Meir

On compositions of symmetrically and elementarily indivisible structures

Ben Gurion University of the Negev

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.

Model theory seminarFriday, May 9, 201412:30 pmGC6417
Artem Chernikov

VC-dimension in model theory and other subjects

Université Paris Diderot - Paris 7

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.

Model theory seminarFriday, April 11, 201412:30 pmGC 6417
Andres Villaveces

Automorphism groups of large models: small index property and AECs

Universidad Nacional de Colombia

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.

Model theory seminarFriday, April 4, 201412:30 pmGC6417
Cameron Freer

Symmetric random constructions in model theory

M.I.T.

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 theory seminarCUNY Logic WorkshopFriday, March 28, 201412:30 pm
Paul Baginski

Model theoretic advances for groups with bounded chains of centralizers

Fairfield University

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.

Model theory seminarFriday, March 21, 201412:30 pmGC 6417
Henry Towsner

The consistency of Peano Arithmetic

University of Pennsylvania

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.

Model theory seminarFriday, March 7, 201412:30 pmGC 6417
Russell Miller

Turing degree spectra of differentially closed fields

City University of New York

The spectrum Spec(M) of a countable structure M is the set of all Turing degrees of structures isomorphic to M. This topic has been the focus of much research. Here we describe the spectra of countable differentially closed fields of characteristic 0: they are precisely the preimages { d : d’ ∈ Spec(G) } of spectra of arbitrary countable graphs G, under the jump operation. To establish this, we describe the proofs of two theorems: one showing how to build the appropriate differential field K from a given graph G, and the other showing that every low model of the theory DCF0 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 low4 case for Boolean algebras does not hold for DCF0.

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

Model theory seminarFriday, February 28, 201412:30 pmGC 6417
Athar Abdul-Quader

Fullness

The CUNY Graduate Center

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

Model theory seminarFriday, February 21, 201412:30 pm
Alf Dolich

Ordered structures with dense/co-dense sets

The City University of New York

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.

Model theory seminarFriday, December 6, 201312:30 pmGC 6417

VC Density and Breadth on Modules

CUNY Grad Center

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.

Model theory seminarFriday, November 22, 201312:30 pm
Alice Medvedev

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

City College -- CUNY

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.

Model theory seminarFriday, November 15, 201312:30 pmGC 6417
Yevgeniy Vasilyev

On dense independent subsets of geometric structures

Memorial University of Newfoundland and Christopher Newport University

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.

Model theory seminarFriday, November 8, 201312:30 pmGC6417

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

Ohio State University

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

Model theory seminarFriday, November 1, 201312:30 pmGC6417
David Lippel

Seminar Cancelled

Haverford College

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

Model theory seminarFriday, October 25, 201312:30 pm
Alf Dolich

LE-Series

The City University of New York

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.

Model theory seminarFriday, October 18, 201312:30 pmGC6417
Lynn Scow

Ramsey Transfer Theorems

Vassar College

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.

Model theory seminarFriday, October 11, 201312:30 pm
Roman Kossak

$\omega_1$-like models of PA

The City University of New York

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

Model theory seminarFriday, October 4, 201312:30 pmGC6417
David Marker

Real closures of $omega_1$-like models of PA

University of Illinois at Chicago

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.

Model theory seminarFriday, September 27, 201312:30 pmGC 6417
Diana Ojeda Aristizabal

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

Cornell University

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.

Model theory seminarFriday, September 20, 201312:30 pmGC 6417
Roman Kossak

Resplendent and Transplendent Models

The City University of New York

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.

Model theory seminarFriday, May 10, 201312:30 pmGC 6417
Athar Abdul-Quader

Transplendent models of rich theories

The CUNY Graduate Center

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.

Model theory seminarFriday, May 3, 201312:30 pmGC 6417

VC Dimension and Breadth in Modules

CUNY Grad Center

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.

Model theory seminarFriday, April 26, 201312:30 pmGC 6417

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

University of Toronto

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.

Model theory seminarCUNY Logic WorkshopFriday, April 12, 201312:30 pmGC 6417
Patrick Speissegger

Pfaffian functions vs. Rolle leaves

McMaster University

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.

Model theory seminarKolchin seminar in Differential AlgebraFriday, March 15, 201312:00 am
Philipp Rothmaler

Stability revisited

The City University of New York

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.

Model theory seminarFriday, March 8, 201312:00 amGC 6417
Roman Kossak

On strength of weakness

The City University of New York

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.

Model theory seminarFriday, March 1, 201312:30 pm
Alf Dolich

Maximal Automorphisms

The City University of New York

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.

Model theory seminarFriday, February 22, 201312:00 am
Roman Kossak

Transplendence

The City University of New York

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.

Model theory seminarFriday, February 15, 201312:30 pmGC 6417
Russell Miller

Independent sets in computable free groups and fields

City University of New York

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.

Model theory seminarFriday, February 8, 201312:30 pm
Alf Dolich

Organizational Meeting

The City University of New York

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

Set theory seminarModel theory seminarCUNY Logic Workshop

No seminars April 18


Friday, April 18 is part of CUNY’s spring break, and there will be no seminars at the Graduate Center that day.