# Blog Archives

These are the items posted in this seminar, currently ordered by their post-date, rather than by the event date. We will create improved views in the future. In the meantime, please click on the Seminar menu item above to find the page associated with this seminar, which does have a more useful view order.# 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.

# No model theory seminar on Feb. 26

The model theory seminar will not meet on February 26.

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

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

# 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 *Π _{2}^{0}* 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

*ω*which is not approximated by models of low Scott rank.

_{1}^{CK}+1# 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 November 27

There will be no talks on November 27, the day after Thanksgiving.

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

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

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

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