Model theory seminar
Informal Session
We will meet in an informal discussion to talk about recent work in model theory as well as any current problems we are interested in. Also we can use the opportunity to discuss plans for the seminar next semester. Bring any ideas or recent preprints you are interested in talking about. In particular see the most recent model theory preprints posted on the
ArXiv.
Foundations of cologic
The existence of a robust categorical dual to first-order logic is hinted at in (at least) four independent bodies of work: (1) Projective Fraïssé theory [Solecki & coauthors, Panagiotopolous]. (2) The cologic of profinite groups (e.g. Galois groups), which plays an important role in the model theory of PAC fields [Cherlin – van den Dries – Macintyre, Chatzidakis]. (3) Ultracoproducts and coelementary classes of compact Hausdorff spaces [Bankston]. (4) Universal coalgebras and coalgebraic logic [Rutten, Kurz – Rosicky, Moss, others]. In this talk, I will propose a natural syntax and semantics for such a dual “cologic”, in which “coformulas” express properties of partitions of “costructures”, dually to the way in which formulas express properties of tuples from structures. I will show how the basic theorems and constructions of first-order logic (completeness, compactness, ultraproducts, Henkin constructions, Löwenheim-Skolem, etc.) can be dualized, and I will discuss some possible extensions of the framework.
No seminars on Nov. 25
Friday, November 25 is the day after Thanksgiving, so there will be no seminars at the Graduate Center that day.
First order expansions of the ordered group of real numbers
We discuss (part of) the classification of first order expansions of $(\mathbb{R},<,+)$ according to the geometry and topology of their definable sets. Joint work with Philipp Hieronymi, following work of Hieronymi, Fornasiero, Miller, and Tychonievich.
Straw into gold: Turning a c.c.c. forcing construction of a model into a ZFC proof
We use $M$-normal ultrapowers to give a new proof of a theorem of Keisler that if one can construct a standard model of a sentence of $L_{\omega_1,\omega}(Q)$ using a c.c.c. forcing, then a standard model already exists in V.
We use this to investigate the class of atomic models of a countable, first order theory $T$. In particular, we show that various `unsuperstable-like’ behaviors imply the existence of many non-isomorphic atomic models of size $\aleph_1$.
This is joint work with John Baldwin and Saharon Shelah.
Isomorphisms of ordered valued fields
A real closed field with a convex valuation is a nice model-theoretic object. In this talk, I will look at some examples of such structures to get a sense of why they are nice. I will discuss two theorems which illustrate the analogues with algebraically closed valued fields, which lead us to a notion of domination by the residue field. This is joint work with Clifton Ealy and Jana Marikova.
On Collapse of Generalized Indiscernibles.
I discuss the characterization of model theoretic dividing lines by collapse of generalized indiscernibles. For example, S. Shelah showed that a theory is stable if and only if all order indiscernibles are set indiscernibles. In her thesis, L. Scow showed that a theory has NIP if and only if all graph order indiscernibles are order indiscernibles. I explore new results characterizing dp-rank and rosiness using similar methods. I also talk about some attempts to create a general framework for such results. This work is joint with C. Hill and L. Scow.
Northeast Regional Model Theory Days
The Northeast Regional Model Theory Days will take place on Saturday the 21st of October and
Sunday the 22nd of October at the University of Pennsylvania in Philadelphia PA. See the Northeast Regional Model Theory Days website for full details.
Imaginaries in valued differential fields II: Computing canonical bases
In 2000, Scanlon described a theory of existentially closed differential fields where the derivation is contractive: v(d(x)) ≥ v(x), for all x. He also proved a quantifier elimination result for this theory. Around the same time, Haskell, Hrushovski and Macpherson classified all the quotients of definable sets by definable equivalence relations in a algebraically closed valued field by proving elimination of imaginaries (relative to certain quotients of the linear group). In analogy with the pure field situation where elimination of imaginaries for differentially closed fields can be derived from elimination of imaginaries in the underlying algebraically closed field, it was conjectured that Scanlon’s theory of existentially closed contractive valued differential fields also eliminated imaginaries relatively to those same quotients of the linear group.
In this talk, I will describe the second part of the proof that this result indeed holds. Our goal will be to explain a result, joint with Pierre Simon, on definable types in enrichments of NIP theories, which is crucial to prove elimination of imaginaries. We show that under certain hypothesis if a type in some NIP theory T is definable in an enrichment of T, then it h is already be definable in T.
No logic seminars on October 14
Since CUNY will follow a Tuesday schedule on Friday, October 14, we will not have any of the usual Friday logic seminars that day. However, there will be a talk by George Metcalfe at 4 pm, described below.
Complexity of classification problems for a class of discretely ordered rings
I will give a standard introduction to the theory of Borel reducibility, including some details for non-logicians. The rest of the talk will be about some results in classification problems for countable nonstandard models of arithmetic due to Samuel Coskey and myself.
Structure and enumeration theorems in hereditary properties of L-structures
The study of structure and enumeration for hereditary graph properties has been a major area of research in extremal combinatorics. Over the years such results have been extended to many combinatorial structures other than graphs. This line of research has developed an informal strategy for how to prove these results in various settings. In this talk we formalize this strategy. In particular, we generalize certain definitions, tools, and theorems which appear commonly in approximate structure and enumeration theorems in extremal combinatorics. Our results apply to classes of finite L-structures which are closed under isomorphism and model-theoretic substructure, where L is any finite relational language.
An introduction to Pillay’s differential Galois theory (part 2)
In a series of papers from the 1990s and early 2000s, Pillay used the machinery of model-theoretic binding groups to give a slick geometric account and generalization of Kolchin’s theory of strongly normal extensions and constrained cohomology. This series of two talks is intended to be expository, with its main goal being to introduce and frame the relevant model-theoretic notions of internality and binding groups within the context of differential algebra, as well as to go through Pillay’s argument that his generalized strongly normal extensions arise from logarithmic differential equations defined over algebraic D-groups.
An introduction to Pillay’s differential Galois theory (part 1)
In a series of papers from the 1990s and early 2000s, Pillay used the machinery of model-theoretic binding groups to give a slick geometric account and generalization of Kolchin’s theory of strongly normal extensions and constrained cohomology. This series of two talks is intended to be expository, with its main goal being to introduce and frame the relevant model-theoretic notions of internality and binding groups within the context of differential algebra, as well as to go through Pillay’s argument that his generalized strongly normal extensions arise from logarithmic differential equations defined over algebraic D-groups.
The logical complexity of Schanuel’s Conjecture
In its most natural form Schanuel’s Conjecture is a $\Pi_1^1$-statement. We will show that there is an equivalent $\Pi^0_3$-statement. They key idea is a result of Jonathan Kirby showing that, if Schanuel’s Conjecture is false, then there are canonical counterexamples. Most of my lecture will describe Kirby’s work.
Measuring definable sets in nonarchimedean o-minimal fields and an application to the reals
We introduce a measure on the definable sets in an o-minimal expansion of a real closed field which takes values in an ordered semiring and assigns a positive value to a definable set iff the interior of the set is non-empty (joint work with M. Shiota). We then discuss an application to Hausdorff dimension of metric spaces definable in o-minimal expansions of the real field (joint work with E. Walsberg).
$\omega$-stability and Morley rank of bilinear maps, rings and nilpotent groups
In this talk I will present our recent results on the algebraic structure of $\omega$-stable bilinear maps, arbitrary rings and nilpotent groups. I will also discuss some rather complete structure theorems for the above structures in the finite Morley rank case. The main technique in this work is associating a canonical scalar (commutative associative unitary) ring to a bilinear map. This canonical scalar ring happens to preserve many of the logical and algebraic properties of the bilinear map. This talk is based on the joint work with Alexei Miasnikov.
The Dixmier-Moeglin problem for D-varieties
By a D-variety we mean, following Buium, an algebraic variety V over an algebraically closed field k equipped with a regular section s: V–> TV to the tangent bundle of V. (This is equivalent to the category of finite dimensional differential-algebraic varieties over the constants.) There are natural notions of D-rational map and D-subvariety. Motivated by problems in noncommutative algebra we are lead to ask under what conditions (V,s) has a maximum proper D-subvariety over k. (Model-theoretically this asks when the generic type is isolated.) A necessary condition is that (V,s) does not admit a nonconstant D-constant, that is, a D-rational map from (V,s) to the affine line equipped with the
zero section. When is this condition sufficient? I will discuss this rather open-ended problem, including some known cases.
Imaginaries in valued fields of positive characteristic
I will discuss the basic properties of the theory SCVF of separably closed valued fields, and the closely related theory SCVH of separably closed valued fields equipped with Hasse derivations. The main new result is elimination of imaginaries (in a suitable language). This is joint work with Martin Hils and Silvain Rideau.
On a question of Gaifman concerning invariant measures
In his 1964 paper “Concerning measures in first order calculi” Gaifman introduces the notion of a symmetric measure-model: a measure on the formulas of a first order calculus that is invariant under permutations of the elements instantiating the free variables of each formula, where these elements come from some fixed domain. To each symmetric measure-model there is associated a measure on sentences, which we can think of as a random (consistent) theory that the measure-model satisfies. Gaifman shows that every such random theory has a symmetric measure-model satisfying it. However, the symmetric measure-models that he constructs sometimes, necessarily, assign positive measure to instantiations of the formula “x=y” by unequal elements. Gaifman goes on to pose the question of characterizing those classical theories that admit symmetric measure-models without this pathology — those with so-called `strict equality’. In this talk I will show that when the instantiating domain is the set of natural numbers, a symmetric measure-model with strict equality is essentially a probability measure on a space of structures, with underlying set the natural numbers, that is invariant under the logic action. I will then give necessary and sufficient conditions for a classical theory to admit such an invariant measure, thereby providing an answer to the question posed by Gaifman. This is joint work with Nathanael Ackerman and Cameron Freer.
The Lattice of Definable Equivalence Relations in Homogeneous n-Dimensional Permutation Structures
In 2002, Cameron classified the homogeneous permutations (structures in a language of 2 linear orders). In working toward the classification the homogeneous n-dimensional permutation structures (structures in a language of n linear orders), consideration of the lattice of definable equivalence relations leads to a generalization of Cameron’s structures, giving a large class of new homogeneous examples, and places some constraints on lattices that can appear.
Prime-model extensions of Abelian lattice-ordered groups
This talk will consider the extent to which Abelian lattice-ordered groups have prime-model extensions within the class of existentially closed Abelian lattice-ordered groups.
Amalgamation Classes with Existential Resolutions
Let $K_d$ denote the class of all finite graphs and, for graphs $A \subseteq B$, say $A \leq_d B$ if distances in $A$ are preserved in $B$; i.e. for $a, a’ \in A$ the length of the shortest path in $A$ from $a$ to $a’$ is the same as the length of the shortest path in $B$ from $a$ to $a’$. In this situation $(K_d, \leq_d)$ forms an amalgamation class and one can perform a Hrushovski construction to obtain a generic of the class. One particular feature of the class $(K_d, \leq_d)$ is that a closed superset of a finite set need not include all minimal pairs obtained iteratively over that set but only enough such pairs to resolve distances; we will say that such classes have existential resolutions.
Larry Moss has conjectured the existence of graph $M$ which was $(K_d, \leq_d)$-injective (for $A \leq_d B$ any isometric embedding of $A$ into $M$ extends to an isometric embedding of $B$ into $M$) but without finite closures. We examine Moss’s conjecture in the more general context of amalgamation classes. In particular, we will show that the question is in some sense more interesting in classes with $\exists$-resolutions and will give some conditions under which the possibility of such structures is limited.
Potential Cardinality for Countable First Order Theories
Give a theory $T$, understanding the countable model theory of $T$ has long been a topic of research. The number of countable models of $T$ is a classical but very coarse invariant, and this was refined significantly by Friedman and Stanley with the notion of Borel reductions.
Given theories $T_1$ and $T_2$, it is often straightforward to show that $T_1$ is Borel reducible to $T_2$. However, there are few tools to show that no such Borel reduction exists. Most of the existing tools only work when the isomorphism relation of one or both is particularly simple, or at least Borel.
We define the notion of “potential cardinality” of $T$, denoted $|T|$, as the number of formally consistent, possibly uncountable Scott sentences which imply $T$. It turns out that if $T_1$ Borel reduces to $T_2$, then $|T_1|$ is less than or equal to $|T_2|$. Additionally, it turns out that very frequently, $|T|$ can be computed and is not a proper class.
We use this idea to give a new class of examples of first-order theories whose isomorphism relations are neither Borel nor Borel complete. Along the way we answer an old question of Koerwien and new question of Laskowski and Shelah.
This is joint work with Douglas Ulrich and Chris Laskowski.
Lattices of Elementary Substructures
The set of elementary substructures of a model of PA, under the inclusion relation, form a lattice. The lattice problem for models of PA asks which lattices can be represented as substructure lattices of some model of PA. This question dates back to Gaifman’s work on minimal types, which showed that the two element chain can be represented as a substructure lattice. Since then, there have been many important contributions to this problem, including by Paris, Wilkie, Mills, and Schmerl, though no complete picture has yet emerged. Studying this question involves knowledge of models of PA as well as some nontrivial lattice theory and combinatorics. In my talk, I will survey some of the major results and, if there’s time, give an idea of the techniques used to study this question.
Slides from this talk.
Scott ranks of models of a theory
I will talk about a few different results about the Scott ranks of models of a theory. (By a theory, I mean a sentence of Lω1ω.) These results are all related in that they all follow from the same general construction; this construction takes a pseudo-elementary class C of linear orders and produces a theory T such that the Scott ranks of models of T are related to the well-founded parts of linear orders in C.
The main result is a descriptive-set-theoretic classification of the collections of ordinals which are the Scott spectrum of a theory. We also answer some open questions. First, we show that for each ordinal β, there is a Π20 theory which has no models of Scott rank less than β. Second, we find the Scott height of computable infinitary sentences. Third, we construct a computable model of Scott rank ω1CK+1 which is not approximated by models of low Scott rank.
Zero-one laws for discrete metric spaces
Fix an integer $r \geq 3$. Given an integer $n$, we define $M_r(n)$ to be the set of metric spaces with underlying set ${1,\ldots,n}$ such that the distance between any two points lies in ${1,\ldots,r}$. We present results describing the approximate structure of these metric spaces when $n$ is large. As a consequence of these structural results in the case when $r$ is even, we obtain a first-order labeled $0$-$1$ law. This is joint work with Dhruv Mubayi.
No talks November 27
There will be no talks on November 27, the day after Thanksgiving.
On maximal immediate extensions of valued fields
A valued field extension is called immediate if the corresponding value group and residue field extensions are trivial. A better understanding of the structure of such extensions turned out to be important for questions in algebraic geometry, real algebra and the model theory of valued fields.
In this talk we focus mainly on the problem of the uniqueness of maximal immediate extensions.
Kaplansky proved that under a certain condition, which he called “hypothesis A”, all maximal immediate extensions of the valued field are isomorphic. We study a more general case, omitting one of the conditions of hypothesis~A. We describe the structure of maximal immediate extensions of valued fields under such weaker assumptions. This leads to another condition under which fields in this class admit unique maximal immediate extensions.
We further prove that there is a class of fields which admit an algebraic maximal immediate extension as well as one of infinite transcendence degree. We introduce a classification of Artin-Schreier defect extensions and describe its importance for the construction of such maximal immediate extensions.
We present also the consequences of the above results and and of the model theory of tame fields for the problem of uniqueness of maximal immediate extensions up to elementary equivalence.
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 of generalized Urysohn spaces
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.
Transfer of the Ramsey Property between Classes
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.
Euclidean domains of arbitrarily high Euclidean rank
We will construct Euclidean domains of arbitrarily high Euclidean rank.
Effective bounds for the existence of differential field extensions
We present a new upper bound for the existence of a differential field extension of a differential field
(K; D) that is compatible with a given field extension of K. In 2014, Pierce provided an upper bound in
terms of lengths of certain antichain sequences of N^m equipped with the product order. Pierce’s theory
has interesting applications to the model theory of fields with m commuting derivations, and his results
have been used when studying effective methods in differential algebra, such as the effective differential
Nullstellensatz problem. We use a new approach involving Macaulay’s theorem on the Hilbert function
to produce an improved upper bound. In particular, we see markedly improved results in the case of two
and three derivations.
This is joint work with Omar Leon Sanchez.
No talks on September 25
On Friday, September 25, CUNY will follow a Tuesday schedule. Therefore, no logic seminars will meet that day.
Degree spectra of real closed fields
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.
Model-completeness of transseries
The concept of a “transseries” is a natural extension of that of a Laurent series, allowing for exponential and logarithmic terms. Transseries were introduced in the 1980s by the analyst Écalle and also, independently, by the logicians Dahn and Göring. The germs of many naturally occurring real-valued functions of one variable have asymptotic expansions which are transseries. Since the late 1990s, van den Dries, van der Hoeven, and myself, have pursued a program to understand the algebraic and model-theoretic aspects of this intricate but fascinating mathematical object. Last year we were able to make a significant step forward, and established a model completeness theorem for the valued differential field of transseries in its natural language. My goal for this talk is to introduce transseries without prior knowledge of the subject, and to explain our recent work.
Actions on sets of Morley rank $2$
Recently, Borovik and Cherlin initiated a broad study of permutation groups of finite Morley rank with a key topic being high degrees of generic transitivity. One of the main problems that they pose is to show that there is a natural upper bound on the degree of generic transitivity that depends only upon the rank of the set being acted on. Specifically, the problem is to show that the only groups of finite Morley rank with a generically $(n+2)$-transitive action on a set of rank $n$ are those of the form ${PGL}_{n+1}$. A solution when $n=1$, due to Hrushovski, has been known for a few decades as in this case the set is strongly minimal. In this talk, I will present recent work, joint with Tuna Altinel, addressing the case of $n=2$. The analysis of these actions makes considerable use of the structure of groups of small rank, and as such, I will also discuss some new results on groups of Morley rank $4$.
Computable Functors between Nested Equivalence Structures and Full Trees of Finite Height
Trees have long been used throughout mathematics to better understand and represent many different types of objects and structures. In this talk we examine finitely nested equivalence structures. Such structures consist of a set of natural numbers and a finite number of equivalence relations which are nested inside of each other. (That is, their resulting equivalence classes are subsets of each other.) We utilize the notions of category theory to build functors between nested equivalence structures and full trees of finite height. These functors behave quite nicely, and we build them in a computable way so that the various computability-theoretic properties of the structures are preserved. We discuss computable isomorphisms and the Turing degree spectrum of a structure – defining and giving examples of each, and showing how, once our computable functors are constructed, such properties transfer readily between nested equivalence structures and trees.
Fermat’s Last Theorem and Catalan’s conjecture in weak exponential arithmetics
This is a joint work with Vitezslav Kala.
Wiles’s proof of Fermat’s Last Theorem (FLT) has stimulated a lively discussion on how much is actually needed for the proof.
Despite the fact that the original proof uses set-theoretical assumptions unprovable in Zermelo-Fraenkel set theory with axiom of choice (ZFC) (namely, the existence of Grothendieck universes), it is widely believed that
certainly much less than ZFC is used in principle, probably nothing beyond Peano arithmetic, and perhaps much less than that.
I will start with a brief summary of existing positive and negative results on provability of FLT in various arithmetical theories.
In this talk, we will consider structures and theories in the language L=(0,1,+,x,<,e), where the symbol e is intended for a (partial or total) binary exponential. We show that Fermat's Last Theorem for e (i.e. the statement "e(a,n)+e(b,n)=e(c,n) has no non-zero solution for n>2″) is not provable in the L-theory Th(N)+Exp, where Th(N) stands for the complete theory of the standard model N=(N,0,1,+,x,<) and Exp is a natural set of axioms for e (consisting mostly of elementary identities). On the other hand, under the assumption of ABC conjecture (in the standard model), we show that the Catalan conjecture for e is provable in Th(N)+Exp (even in a weaker theory). This gives an interesting separation of strengths of these two diophantine problems. Finally, we also show that Fermat's Last Theorem for e is provable (again, under the assumption of ABC in N) in Th(N)+Exp +"coprimality for e". Slides from this talk.
Friday, April 10, 2015
Spring break
CUNY’s spring vacation is April 3-11, 2015. Therefore, no seminars will meet at the Graduate Center on April 3, nor on April 10.
Independence, via limits
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.
Whitney’s Extension Theorem in O-minimal Context
Let $U$ be an open subset of $R^n$ and $f$, a function from $U$ to $R$, be $C^m$. We call the collection of $f$ and its derivatives, the jet of order $m$ of $f$. In 1934, H. Whitney asked how can we determine whether a collection of continuous functions on a closed subset of $R^n$ is a jet of order $m$ of a $C^m$-function and also gave a solution to this question which is known as Whitney’s Extension Theorem.
In this talk, let $R$ be an o-minimal expansion of the real field. We discuss whether a collection of continuous functions on a closed subset of $R^n$ is a jet of order $m$ of a $C^m$-function which is definable in $R$.
Ramsey-type theorems in certain NIP theories
In the paper “Crossing patterns of semi-algebraic sets” (J. Combin. Theory Ser. A 111, 2005) Alon et al. showed that families of graphs with the edge relation given by a semialgebraic relation of bounded complexity satisfy a stronger regularity property than arbitrary graphs. In this talk we show that this can be generalized to families of graphs whose edge relation is uniformly definable in a structure satisfying a certain model theoretic property called distality.
This is a joint work with A. Chernikov.
Generic Linear Functions over Divisible Ordered Abelian Groups
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.
Coding sets in end extensions
Much work in the model theory of Peano Arithmetic is based on constructions of elementary end extensions. Let N be an elementary end extension of M. An important isomorphism invariant of the pair (N,M), is Cod(N/M)—the set of intersections with M of the definable subsets of N. For a given model M, one wants to characterize those subsets X of M for which there is an elementary end extension of N of M such that X is in Cod(N/M), and those subsets A of the power set of M for which there is an N, such that A=Cod(N/M). Such characterizations involve properties of subsets of M, but also, a bit surprisingly, properties of M itself. I will talk about some old and some new results in this area.
February 13
Neither the Logic Workshop nor the Model Theory Seminar will meet on Friday, Feb. 13, 2015. Both Feb. 12 and Feb. 16 are CUNY holidays. We will resume on Friday, Feb. 20.
Model theory and algebraic geometry in groups and algebras
We consider some fundamental model-theoretic questions that can be asked about a given algebraic structure (a group, a ring, etc.), or a class of structures, to understand its principal algebraic and logical properties. These Tarski type questions include: elementary classification and decidability of the first-order theory.
In the case of free groups we proved (in 2006) that two non-abelian free groups of different ranks are elementarily equivalent, classified finitely generated groups elementarily equivalent to a finitely generated free group (also done by Sela) and proved decidability of the first-order theory.
We describe partial solutions to Tarski’s problems in the class of free associative and Lie algebras of finite rank and some open problems. In particular, we will show that unlike free groups, two free associative algebras of finite rank over the same field are elementarily equivalent if and only if they are isomorphic. Two free associative algebras of finite rank over different infinite fields are elementarily equivalent if and only if the fields are equivalent in the weak second order logic, and the ranks are the same. We will also show that for any field the theory of a free associative algebra is undecidable.
These are joint results with O. Kharlampovich
Tameness in abstract elementary classes
Tameness is a locality property of Galois types in AECs. Since its isolation by Grossberg and VanDieren 10 years ago, it has been used to prove new results (upward categoricity transfer, stability transfer) and replace set-theoretic hypotheses (existence of independence notions). In this talk, we will outline the basic definitions, summarize some key results, and discuss some open questions related to tameness.
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 longstanding 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 jqt of quantum tori is defined as a discontinuous, PGL(2,Z)-invariant multi-valued map of the reals R. For θ ∈ Q, jqt(θ) = ∞ and for quadratic irrationalities, experiments conducted with the PARI/GP computer algebra system suggest that jqt(θ) is a finite set. In the case of the golden mean φ, we produce explicit formulas for the experimental supremum and infimum of jqt(φ) 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 jqt as well as the classical modular invariant of elliptic curves may be recovered as subquotients.
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(
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.
No model theory seminar on Feb. 26
The model theory seminar will not meet on February 26.