# CUNY Logic Workshop

# A finitary analogue of the downward Lowenheim-Skolem property

We present a new logic based combinatorial property of finite structures, that can be regarded as a finitary analogue of the classical downward Lowenheim-Skolem property from model theory. This property, that we call the *Equivalent Bounded Substructure Property*, abbreviated EBSP, intuitively states that a large structure contains a small “logically similar” substructure. It turns out that this simply stated property is enjoyed by a variety of classes of interest in computer science: examples include classes defined using posets, such as words, trees (unordered, ordered or ranked) and nested words, and classes of graphs, such as graph classes of bounded tree-depth, those of bounded shrub-depth, m-partite cographs, and more generally, graph classes that are well-quasi-ordered under the (isomorphic) embedding relation. Further, EBSP remains preserved under various well-studied operations, such as complementation, transpose, the line-graph operation, disjoint union, join, series and parallel connects, and various products including the cartesian and tensor products. This enables constructing a wide spectrum of interesting classes that satisfy EBSP. We present applications of our investigations into EBSP, to complexity theory and graph minor theory: for the former, we show that many NP-complete problems (such as 3-colorability) become polynomial time solvable over several EBSP classes, and for the latter, we show that every finite graph has a small logically similar minor.

# Describing finite groups by short first-order sentences

We say that a class of finite structures for a finite first-order signature is *R-compressible* for an unbounded function *R* on the natural numbers if each structure *G* in the class has a first-order description of size at most *O(R(|G|))*. We show that the class of finite simple groups is log-compressible, and the class of all finite groups is log-cubed compressible.

The results rely on the classification of finite simple groups, the bi-interpretability of the twisted Ree groups with finite difference fields, the existence of profinite presentations with few relators for finite groups, and group cohomology. We also indicate why the results are close to optimal.

This is joint work with Katrin Tent, to appear in IJM, available here.

# Learnability thesis, FM-representability and Turing Ideals

We consider the notion of the so-called intuitive learnability and its relation to the so-called intuitive computability. We briefly present and discuss Church’s Thesis in the context of the notion of learnability. A set is intuitively learnable if there is a (possibly infinite) intuitive procedure that for each input produces a finite sequence of yeses and nos such that the last answer in the sequence is correct. We further formulate the Learnability Thesis which states that the notion of intuitive learnability is equivalent to the notion of algorithmic learnability. The claim is analogous to Church’s Thesis. Afterwards we analyse the argument for Church’s Thesis presented by M. Mostowski (employing the concept of FM-representability which is equivalent to Turing-reducibility to 0′ or to being $Delta^0_2$). The argument goes in unusual lines – by giving a model of potential infinity, the so-called FM-domains, which are inifnite sequences of growing finite models, separating knowable (intuitively computable) sets from FM-representable (algorithmically learnable) ones via the so-called testing formulae and showing that knowable sets are exactly recursive. We indicate which assumptions of the Mostowski’s argument (concerning recursive enumeration of the finite models being elements of an FM-domain) implicitely include that Church’s Thesis holds. The impossibility of this kind of argument is strengthened by showing that the Learnability Thesis does not imply Church’s Thesis. Specifically, we show a natural interpretation of intuitive computability – containing a low set – under which intuitively learnable sets are exactly algorithmically learnable but intuitively computable sets form a proper superset of recursive sets. Last, using the Sacks Density Theorem, we show that there is a continuum of Turing ideals of low sets satisfying our assumptions. Therefore, if we admit certain non-recursive but intuitively computable relations (namely: some low relations) we are able to consider expanded FM-domains and there are continuum many of such. On the other hand, relations FM-representable in such FM-dommains are still $Delta^0_2$. The general conclusion is that justifying Church’s Thesis solely on the grounds of procedures recursive in the limit is by far insufficient.

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

# Some necessary applications of logic to operator algebras

Connections between logic and operator algebras in the past century were few and sparse. Recently, some long-standing open problems on the structure of operator algebras were solved using methods from mathematical logic. I will survey some of these results, with a particular emphasis on applications of set theory.

# Cardinal invariants of analytic P-ideals

I will introduce several cardinal invariants associated with analytic P-ideals, concentrating on the ideal of sets of asymptotic density zero. I will give a summary of some recent work on these invariants relating them to the dominating, bounding and splitting numbers, and to some variants of the splitting number. Several fundamental problems remain open and I will try to discuss as many of these as I can.

# Set-theoretic potentialism

In analogy with the ancient views on potential as opposed to actual infinity, set-theoretic potentialism is the philosophical position holding that the universe of set theory is never fully completed, but rather has a potential character, with greater parts of it becoming known to us as it unfolds. In this talk, I should like to undertake a mathematical analysis of the modal commitments of various specific natural accounts of set-theoretic potentialism. After developing a general model-theoretic framework for potentialism and describing how the corresponding modal validities are revealed by certain types of control statements, which we call buttons, switches, dials and ratchets, I apply this analysis to the case of set-theoretic potentialism, including the modalities of true-in-all-larger-*V _{β}*, true-in-all-transitive-sets, true-in-all-Grothendieck-Zermelo-universes, true-in-all-countable-transitive-models and others. Broadly speaking, the height-potentialist systems generally validate exactly S4.3 and the height-and-width-potentialist systems generally validate exactly S4.2. Each potentialist system gives rise to a natural accompanying maximality principle, which occurs when S5 is valid at a world, so that every possibly necessary statement is already true. For example, a Grothendieck-Zermelo universe

*V*, with κ inaccessible, exhibits the maximality principle with respect to assertions in the language of set theory using parameters from

_{κ}*V*just in case κ is a Σ

_{κ}_{3}-reflecting cardinal, and it exhibits the maximality principle with respect to assertions in the potentialist language of set theory with parameters just in case it is fully reflecting

*V*.

_{κ}< VThis is current joint work with Øystein Linnebo, in progress, which builds on some of my prior work with George Leibman and Benedikt Löwe in the modal logic of forcing. Comments and questions can be made on the speaker’s blog.

# Invariant random subgroups of locally finite groups

Let *G* be a countably infinite group and let Sub_{G} be the compact space of subgroups *H≤G*. Then a probability measure ν on Sub_{G} which is invariant under the conjugation action of *G* on Sub_{G} is called an * invariant random subgroup*. In this talk, I will discuss the invariant random subgroups of inductive limits of finite alternating groups. (This is joint work with Robin Tucker-Drob.)

# A model theory of affine n-space via differential algebra

Affine $n$-space $A_k^n$ and its algebraic equivalent, the polynomial ring $k[x_1,…,x_n]$, are basic and widely studied objects in geometry and algebra, about which we know a great deal. However, there remains a host of basic open problems (like the Jacobian conjecture, Zariski Cancellation Conjecture, Complement Problem, …) indicating that our knowledge is nonetheless quite limited. In fact, the greatest obstacle in solving the above conjectures is our inability to “pinpoint” affine space among all varieties (or $k[x]$ among all finitely generated $k$-algebras): this is the so-called Characterization Problem.

The most recent approach to these problems is via additive group actions on affine $n$-space, which corresponds on the algebraic side, to the theory of locally nilpotent derivations. Using this, for instance, N. Gupta recently showed the falsitude of the Zariski Cancellation Conjecture in positive characteristic.

From a model-theoretic point of view, the polynomial ring (in its natural ring language) is quite expressive: in characteristic zero, one can define the integers (as a subset), one can express in general that, say, Embedded Resolution of Singularities holds, etc. Of course, one of the peculiarities of model theory (and probably one of the reasons for its pariah status) is the unavoidable presence of non-standard models. In other words, a characterization problem is never solvable in model theory, unless one allows some non first-order conditions as well (e.g., cardinality in categorical theories–but most mainstream mathematicians would not be too happy about that either). But other, more intrinsic problems arise: there are elementary equivalent fields whose polynomial rings are not. So, can we find an expanded language plus a “natural” but non first-order condition, that pinpoints the standard model, i.e., $k[x]$ within the models of its theory. Or even better, since these complete theories will have unwieldy axiomatizations, can we find a (recursive?) theory, whose only model satisfying the extra non first-order condition is $k[x]$?

In view of the recent developments in algebra/geometry, to this end, I will propose in this talk some languages that include additional sorts, in particularly, a sort for derivations. This is different from the usual language of differential fields, where one only studies a fixed (or possibly finitely many) derivation: we need all of them! We also need a substitute for the notion of degree, and the corresponding group $Z$-action as power maps. To test our theories, we should verify which algebraic/geometric properties are reflected in this setup. For instance, affine $n$-space has no cohomology, which is equivalent to the exactness of the de Rham complex, and this latter statement is true in any of the proposed models. Nonetheless, this is only a preliminary analysis of the problem, and nothing too deep will yet be discussed in this talk.

# Trichotomy principle for partial differential fields

The Zilber trichotomy principle gives a precise sense in which the structure on a sufficiently well behaved one-dimensional set must have one of only three possible kinds: disintegrated (meaning that there may be some isolated correspondences, but nothing else), linear (basically coming from an abelian group with no extra structure), or algebro-geometric (essentially coming from an algebraically closed field). This principle is true in differentially closed fields when “one dimensional” is understood as “strongly minimal” (proven by Hrushovski and Sokolovic using the theory of Zariski geometries and then by Pillay and Ziegler using jet spaces).

When working with differentially closed fields with finitely many, but more than one, distinguished commuting derivations, there are sets which from a certain model theoretic point of view (having to do with the notion of a regular type) are one dimensional even though they are infinite dimensional from the point of view of differential dimension. Moosa, Pillay and Scanlon showed that a weakening of the trichotomy principle is true for these sets: if there is a counter example to the trichotomy principle, then one can be found for a set defined by linear PDEs.

In this lecture, I will explain in detail what the trichotomy principle means in differential algebra, how the reduction to the linear case works, and then how one might approach the open problems.

This is a joint event of the CUNY Logic Workshop and the Kolchin Seminar in Differential Algebra, as part of a KSDA weekend workshop.

# Edmund Husserl’s Philosophy of Arithmetic

Edmund Husserl, the principal founder of phenomenology, is well known for his contributions to philosophy. What is less known is his early work in mathematics. Husserl studied under Kronceker and Weierstrass in Berlin, and got his Ph.D. in 1883 in Vienna working on the calculus of variations under supervision of Leo Königsberger. Under influence of Franz Brentano, he moved to philosophy, and in from 1901 to 1916 he taught philosophy in Göttingen, where he interacted with Hilbert. In “Logic and Philosophy of Mathematics in the Early Husserl” Springer 2010, Stefania Centrone analyses Husserl’s work on foundations of mathematics from that period, and shows its connections to Hilbert’s ideas. I will say a few words about phenomenology, and I’ll talk about fragments of Husserl’s “Philosophy of Arithmetic.”

# Studying profinite monoids via logic

This talk is about my ongoing joint research project with Benjamin Steinberg (CCNY). We begin with the observation that the free profinite aperiodic monoid over a finite set *A* is isomorphic to the Stone dual space (spectrum) of the Boolean algebra of first-order definable sets of finite *A*-labelled linear orders (“*A*-words”). This means that elements of this monoid can be viewed as elementary equivalence classes of models of the first-order theory of finite *A*-words. We exploit this view of the free profinite aperiodic monoid to prove both old and new things about it using methods from model theory, in particular (weakly) saturated models.

The talk is aimed at anyone with a basic knowledge of model theory, not necessarily of profinite monoids; in particular I will take care to review some background on profinite monoids and on how they relate to logic and regular languages.

# Classification of strongly normal extensions of a differential field, and related issues

The material is taken from a joint paper with M. Kamensky, “Interpretations and differential Galois extensions.” Given a differential field *K* with field of constants *k*, and a logarithmic differential equation over *K*, the strongly normal extensions of *K* for the equation correspond (up to isomorphism over *K*) with the connected components of *G(k)* where *G* is the Galois groupoid of the equation. This generalizes to other contexts (parameterized theory,….), and is also the main tool in existence theorems for strongly normal extensions with prescribed properties.

This is a joint event of the CUNY Logic Workshop and the Kolchin Seminar in Differential Algebra, as part of a KSDA weekend workshop.

# Woodin’s AD-conjecture and local Reinhardt cardinals

We will discuss Woodin’s AD-conjecture, which gives a deep relationship between very large cardinals and determined sets of reals. In particular we will show that the AD-conjecture holds for the axiom I0 and that there are many interesting consequences of this fact. We will also discuss the notion of a local Reinhardt cardinal and how variations of the AD-conjecture might show that such cardinals do not exist.

# The model theory of some j-functions

The model theory of j-functions (and more generally of modular and Shimura curves) has been studied by Adam Harris and Christopher Daw. They connected in an intriguing way the categoricity of (an infinitary theory of) the j-function with results in arithmetic geometry (a version of the Mumford-Tate conjecture). I will discuss some of these connections and the questions they raise for model theory, especially in connection with the quest for new versions of j-functions (e.g. on real fields).

# No Logic Workshop March 4.

We do not have a speaker for Friday, March 4, so there will be no Logic Workshop that day. (The Set Theory and Model Theory Seminars will meet as usual.)

# What we talk about when we talk about truth

The goal of set theory, as articulated by Hugh Woodin in his recent Rothschild address at the Isaac Newton Institute, is develop a “convincing philosophy of truth.” There he described the work of set theorists as falling into one of two categories: studying the universe of sets and studying models of set theory. We offer a new perspective on the nature of truth in set theory that may to some extent reconcile these two efforts into one. Joint work with Shoshana Friedman.

# The definability of radicals in noncommutative rings

We will survey some results in the definability of radicals in rings, focusing on some recent results about noncommutative rings. In particular, we will show that there is no simple definition of the prime radical in the noncommutative setting, thus differentiating prime radicals in commutative/noncommutative rings.

# Boolean ultrapowers in set theory

Boolean ultrapowers can serve to explain phenomena that arise in the context of iterated ultrapowers, such as the genericity of the critical sequence over the direct limit model. The examples we give are ultrapowers formed using the complete Boolean algebras of Prikry forcing, Magidor forcing, or a generalization of Prikry forcing. Boolean ultrapowers can also be viewed as a direct limit of ultrapowers, and we present some criteria for when the intersection of these ultrapowers is equal to the generic extension of the Boolean ultrapower, thus arriving at a generalization of a phenomenon first observed by Bukovsky and Dehornoy in the context of Prikry forcing.

# Ramsey theory and topological dynamics

I will introduce two prominent dynamical systems for a given toplogical group, the greatest ambit and the universal minimal flow, as spaces of (near) ultrafilters on certain Boolean algebras. Representing a topological group as a group of isometries of a highly symmetric structure, I will hint how metrizability and triviality of the universal minimal flow is linked to the (approximate) structural Ramsey property. My focus will lie on problems that arise in the study of universal minimal flows in Ramsey theory, model theory, set theory and continuum theory.

# Hilbert’s Tenth Problem inside the rationals

For a ring *R*, Hilbert’s Tenth Problem is the set *HTP(R)* of polynomials *f ∈ R[X _{1},X_{2},…]* for which

*f=0*has a solution in

*R*. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that

*HTP(*is Turing-equivalent to the Halting Problem. The Turing degree of

**Z**)*HTP(*remains unknown. Here we consider the problem for subrings of

**Q**)*. One places a natural topology on the space of such subrings, which is homeomorphic to Cantor space. This allows consideration of measure theory and also Baire category theory. We prove, among other things, that*

**Q***HTP(*computes the Halting Problem if and only if

**Q**)*HTP(R)*computes it for a nonmeager set of subrings

*R*.

# No talks November 27

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

# Loftiness

Loftiness is a weak notion of saturation. It was defined and studied in detail by Matt Kaufmann and Jim Schmerl in two substantial papers published in 1984 and 1987. Kaufman and Schmerl discovered that there are many shades of loftiness. I will give an overview of model theory of lofty models of arithmetic and I will talk about constructions of lofty models that are not recursively saturated.

# In search of a complete axiomatization for $F_p((t))$

I will give a survey of the attempts that have been made since the mid 1960’s to find a complete recursive axiomatization of the elementary theory of $F_p((t))$. This problem is still open, and I will describe the difficulties researchers have met in their search. Some new hope has been generated by Yu. Ershov’s observation that $F_p((t))$ is an “extremal” valued field. However, while his intuition was good, his definition of this notion was flawed. It has been corrected in a paper by Azgin, Kuhlmann and Pop, in which also a partial characterization of extremal fields was given. Further progress has been made in a recent manuscript, on which I will report at the AMS meeting at Rutgers. The talk at the Graduate Center will provide a detailed background from the model theoretic point of view.

The property of being an “extremal valued field” is both elementary and very natural, so it is an ideal candidate for inclusion in a (hopefully) complete recursive axiomatization for $F_p((t))$. It implies an axiom scheme that was considered previously, which describes the behavior of additive polynomials under the valuation. I will discuss why additive polynomials are crucial for the model theory of valued fields of positive characteristic.

The open problems around extremal fields provide a good source of research projects of various levels of difficulty for young researchers.

This talk is jointly sponsored by the Commutative Algebra & Algebraic Geometry Seminar and the CUNY Logic Workshop.

# Diophantine approximation, scalar multiplication and decidability

It has long been known that the first order theory of the expansion (R,<,+,Z) of the ordered additive group of real numbers by just a predicate for the set of integers is decidable. Arguably due to Skolem, the result can be deduced easily from Buechi's theorem on the decidability of monadic second order theory of one successor, and was later rediscovered independently by Weispfenning and Miller. However, a consequence of Goedel's famous first incompleteness theorem states that when expanding this structure by a symbol for multiplication, the theory of the resulting structure (R,<,+,*,Z) becomes undecidable. This observation gives rise to the following natural and surprisingly still open question: How many traces of multiplication can be added to (R,<,+,Z) without making the first order theory undecidable? We will give a complete answer to this question when "traces of multiplication" is taken to mean scalar multiplication by certain irrational numbers. To make this statement precise: for b in R, let f_b: R -> R be the function that takes x to bx. I will show that the theory of (R,<,+,Z,f_b) is decidable if and only if b is quadratic. The proof rests on the observation that many of the Diophantine properties (in the sense of Diophantine approximation) of b can be coded in these structures.

# Intrinsic density and computability

The idea of a negligible subset of the natural numbers is highly appealing; bad behavior often seems restricted to a “small” set. Asymptotic density (the usual solution) has been used repeatedly in many fields, most prominently in number theory. Unfortunately, this is largely incompatible with the computability theorist’s perspective; even 1-equivalent sets can have wildly different densities. However, by restricting to cases where density is computably invariant, we develop a new notion with appealing properties. We will characterize exactly how hard it is to make a set with intrinsic density, and uncover connections to both computability and randomness. In particular, we suggest that Post missed a very natural immunity property when developing his notions of hyperimmunity.

# Categories turned models: taming the finite

Whereas a category theorist sees mathematics as objects interacting with each other via maps, a model theorist looks instead at their internal structure. So we may think of the former as the sociologues of mathematics and the latter as their psychologues. It is well-known that to a first-order theory we can associate the category of its models, but this produces often a non-natural category, as the maps need to be elementary, and maps rarely are! I will discuss the opposite (Jungian?) perspective: viewing a category as a first-order structure. This yields some unexpected rewards: it allows us to define certain second-order concepts, like finiteness, in a first-order way. I will illustrate this with some examples: sets, modules, topologies, …

# On computing VC-density in VC-minimal theories

In model theory, theories are typically distinguished by the complexity of their definable families. One popular notion of complexity, Vapnik-Chervonenkis density, is borrowed from statistical learning theory. In this talk, I discuss the general notion of computing VC-density in NIP theories, a notion explored by Aschenbrenner, Dolich, Haskell, MacPherson, and Starchenko in recent work. In this work, they ask if there is a relationship between dp-rank and VC-density. I show a partial result pointing in that direction by studying VC-minimality (a condition stronger than having minimal dp-rank). Any formula in a VC-minimal theory with two parameter variables has VC-density at most two. I conclude by discussing the possibility of extending this result to higher dimensions.

# The Hanf number for amalgamation

In a joint work with Chris Lambie-Hanson, we study a family of abstract elementary classes (AEC) that we call coloring classes. Each coloring class is an AEC in a relational language $L$ containing exactly the $L$-structures whose finite substructures are isomorphic to one of the “allowed” finite structures. The work takes advantage of the fact that model-theoretic properties (e.g., existence of models and amalgamation) can be rephrased as properties of certain coloring functions. This allows us to improve the results of Baldwin, Kolesnikov, and Shelah: we show in ZFC that disjoint amalgamation can hold up to beth_{alpha}, alpha less than omega_1 (previously, only consistency results were known). We also give a partial answer to the question of Grossberg about the Hanf number for amalgamation property (not just disjoint amalgamation).

# Theories where any definable infinite set has interior

We consider the case of a theory $T$ which expands that of divisible ordered Abelian groups and has the property that in any model of $T$ any infinite definable subset has non-empty interior (in the order topology). We will call such theories visceral. Visceral theories arise naturally in the study theories with a strong form of the independence property and generalize the class of o-minimal and weakly o-minimal theories. We consider the structure of definable sets and definable functions in visceral theories, giving some weak structural results. We also consider how to build general classes of examples of visceral theories, and relate these example back to questions about strong forms of the independence property.

# Open determinacy for games on the ordinals is stronger than ZFC

The principle of open determinacy for class games — two-player games of perfect information with plays of length ω, where the moves are chosen from a possibly proper class, such as games on the ordinals — is not provable in Zermelo-Fraenkel set theory ZFC or Gödel-Bernays set theory GBC, if these theories are consistent, because provably in ZFC there is a definable open proper class game with no definable winning strategy. In fact, the principle of open determinacy and even merely clopen determinacy for class games implies Con(ZFC) and iterated instances Con(Con(ZFC)) and more, because it implies that there is a satisfaction class for first-order truth, and indeed a transfinite tower of truth predicates TR_α for iterated truth-about-truth, relative to any class parameter. This is perhaps explained, in light of the Tarskian recursive definition of truth, by the more general fact that the principle of clopen determinacy is exactly equivalent over GBC to the principle of elementary transfinite recursion ETR over well-founded class relations. Meanwhile, the principle of open determinacy for class games is provable in the stronger theory GBC + Pi^1_1 comprehension, a proper fragment of Kelley-Morse set theory KM.

This is joint work with Victoria Gitman, with helpful participation of Thomas Johnstone.

See also related article: V. Gitman, J.D. Hamkins, Open determinacy for class games, submitted.

For further information and commentary concerning this talk, please see the related post on my blog.

# No talks on September 25

On Friday, September 25, CUNY will follow a Tuesday schedule. Therefore, no logic seminars will meet that day.

# Ehrenfeucht principles in set theory

A powerful tool in the field of models of Peano Arithmetic (${\rm PA}$) is Ehrenfeucht’s lemma, due to Ehrenfeucht, which states that if $a\neq b$ are elements of a model $M$ of ${\rm PA}$ such that $b$ is definable from $a$ in $M$, then $a$ and $b$ must have different types in $M$. Considering the active and fruitful interchange of ideas that has historically existed between the fields of models of ${\rm PA}$ and of models of set theory, it is natural to wonder whether Ehrenfeucht’s lemma holds for models of ${\rm ZFC}$ (or even ${\rm ZF}$). Ehrenfeucht’s original argument generalizes to show that Ehrenfeucht’s lemma holds in every model of ${\rm ZF}+V={\rm HOD}$. I will show that Ehrenfeucht’s lemma fails in a very strong sense in any Cohen forcing extension. I will then introduce the more general *Ehrenfeucht principles*, which are parametric generalizations of Ehrenfeucht’s lemma, and argue that they unify several interesting and already deeply studied model-theoretic/set-theoretic principles for models of set theory. Finally, I will discuss some open questions surrounding this topic involving a connection between Ehrenfeucht principles and global choice principles. This is joint work with Gunter Fuchs and Joel David Hamkins.

# Model theory of right-angled buildings

# Effective symmetry breaking

Symmetry breaking involves the coloring of elements of a structure so that the only automorphism of the structure which respects the coloring is the trivial one. We investigate how much information we would need to be able to compute a 2-coloring of a computable finite-branching tree under the predecessor function which eliminates all automorphisms except the trivial one; we also generalize to n-colorings for fixed n and for variable n. Then, we suppose the tree is no longer finite branching, and we observe what happens to the difficulty of computing a 2-coloring.

# No Logic Workshop May 8

Our prospective speaker has had to postpone her talk, so there will be no CUNY Logic Workshop on May 8.

# A Local Characterization of VC-minimality

(Work joint with Vincent Guingona.) I’ll talk about a problem in the intersection of computable model theory and classical model theory. The notion of VC-minimality, though intriguing, has proven very difficult to work with. It has even been difficult to check whether familiar examples are VC-minimal. This has led model theorists (chiefly my co-author) to ask whether there was a “local” (read “simpler”) characterization of VC-minimality. I suggested a computable model theoretic version of this question in terms of the index set of VC-minimality. We answered this question by giving a local characterization of VC-minimality, and we showed that VC-minimality is a Π^{0}_{4}-complete notion.

# Feedback computability

Many notions of computability allow for an oracle. One natural oracle is the set of algorithms which converge. Normally the way that’s taken is that the programs that are running are different from those in the oracle — the ones running can access an oracle, and the ones in the oracle can’t. But what if the computations running and those in the oracle are the same?

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.

# Counting lattice points and parametric Presburger formulas

In 2013, Kevin Woods showed that for a subset S of the d-th Cartesian power of the natural numbers N, the following are equivalent:

(1) S is definable in Presburger arithmetic,

(2) S is a finite union of intersections of polyhedra with translates of lattices,

(3) S has a rational generating function.

More recently, Woods has studied so-called parametric Presburger families: subsets of powers of N definable with addition and the ordering, plus one special “parameter” variable t which can be multiplied by terms in the other variables. The special variable t also ranges over N, but it is the only variable which cannot be quantified over. This is useful for defining many families which are combinatorially interesting, such as the lattice points inside the t-th dilate of a given polyhedron and a version of the Frobenius problem.

Jointly with Tristram Bogart, we are working to understand the properties of parametric Presburger families. We will present a quantifier elimination result and some conjectures of Woods on Skolem functions and counting functions for these families, which we are studying using logical and syntactic methods.

# Bases for two weak reducibilities

While the standard Turing reduction is the main tool recursion theorists use to compare the computational strength of two sets, comparisons of other types of computational strength give rise to other reducibilities. Many of these reducibilities arise from the study of algorithmic randomness and are strictly weaker than Turing reducibility. In this talk, I will focus on two of these reducibilities, *JT*– and *LR*-reducibility, and study them through the lens of sets that avoid being random in a very strong way.

A base for randomness is a set *A* that is Turing computable from some *A*-random set *Z*. We can extend this concept to reducibilities other than the standard Turing reducibility: given a weak reducibility *≤ _{W}*, we say that a set

*A*is a

*W*-base for randomness if

*A ≤*for some

_{W}Z*A*-random set

*Z*. I will fully characterize the

*JT*-bases for randomness and partially characterize the

*LR*-bases for randomness.

This work is joint with Keng Meng Ng and Reed Solomon.

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

# Σ-Presentable structures over *HF(R)*

If we replace in the definition of computable structures the concept of classical computability over ω with Σ-definability over the structure ** HF(R)** (the hereditarily finite superstructure over the ordered field

**of reals), we obtain its generalization, namely, the notion of Σ-presentable structures over**

*R***. This generalization could correspond to the hypothetical situation when we have an opportunity to use algorithms written in a powerful programming language with “real” reals, elements of**

*HF(R)***, not approximations, where we in addition have opportunity to find roots of polynomials and use them in further computations.**

*R*In the talk, a survey will be given of the results on the existence of Σ-presentations for various structures, on the number of non Σ-isomorphic presentations, and on the existence of Σ-parameterizations for classes of presentations.

# Lengths of roots of polynomials over *k((G))*

Mourgues and Ressayre showed that any real closed field $R$ can be mapped isomorphically onto a truncation-closed subfield of the Hahn field $k((G))$, where $G$ is the natural value group of $R$ and $k$ is the residue field. If we fix a section of the residue field and a well ordering < of $R$, then the procedure of Mourgues and Ressayre yields a canonical section of $G$ and a unique embedding $d: R$ → $k((G))$. Julia Knight and I believed we had shown that for a real closed field $R$ with a well ordering < of type ω, the series in $d(R)$ have length less than ω^{ωω}, but we found a mistake in our proof. We needed a better understanding of what happens to lengths under root-taking. In this talk, we give a partial answer, which allows us to prove the original statement and generalize it. We make use of unpublished notes of Starchenko on the Newton-Puiseux method for taking roots of polynomials.

# Definability in linear fragments of Peano arithmetic

In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal *k*, the *k*-linear arithmetic (*LA _{k}*) is a full-induction arithmetical theory extending Presburger arithmetic by

*k*non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild.

I will present a quantifier elimination result for *LA _{1}* and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of

*LA*(or any

_{2}*LA*with

_{k}*k*at least

*2*) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible).

There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for *LA _{1}* implies interesting properties of the structure of saturated models of Peano arithmetic.

Slides from this talk.

# Effective dimension in subshifts

A subshift is a subset of Cantor space that is both topologically closed and closed under the shift operation. Any element of a subshift can be viewed as a trajectory in a discrete dynamical system. One way a trajectory can be complicated is to have a large effective dimension. We consider the effective dimension spectrum of a subshift *X*, defined as { dim *x : x ∈ X* }, where dim is the effective dimension. Most commonly, the dimension spectrum of *X* is [ *0, h(X)* ], where *h(X)* is the entropy of *X*. We give examples where the dimension spectrum does not follow this pattern, and discuss partial results and open questions related to the problem of characterizing the dimension spectra of subshifts. No prior knowledge about subshifts will be assumed.

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

# Finding definable henselian valuations

(Joint work with Jochen Koenigsmann.) There has been a lot of recent progress in the area of definable henselian valuations. Here, a valuation is called *definable* if its valuation ring is a first-order definable subset of the field in the language of rings. Applications of results concerning definable henselian valuations typically include showing decidability of the theory of a field or facts about its absolute Galois group.

We study the question of which henselian fields admit definable henselian valuations with and without parameters. In equicharacteristic 0, we give a complete characterization of henselian fields admitting parameter-definable (non-trivial) henselian valuations. We also give a partial characterization result for the parameter-free case.

# Large cardinals, AECs and category theory

Shelah’s Categoricity Conjecture is a central test question in the study of Abstract Elementary Classes (AECs) in model theory. Recently Boney has shown that under the assumption that sufficiently large strongly compact cardinals exist, the Shelah Categoricity Conjecture holds at successor cardinals. Lieberman and Rosicky have subsequently shown that AECs can be characterised in a very natural way in a category-theoretic setting, and with this perspective Boney’s result can actually be seen as a corollary of an old category-theoretic result of Makkai and Pare. Rosicky and I have now been able to improve upon this result of Makkai and Pare (and consequently Boney’s Theorem), obtaining it from α-strongly compact cardinals.

# Computable functors and effective interpretations

We give an overview of a number of recent results in computable model theory, by various researchers (not necessarily including the speaker). The results are not all directly connected to each other, but they serve to illustrate the principle that much of the work in this discipline can be viewed through the prism of functors, on categories **C** and **D** whose elements are countable (or computable) structures and whose morphisms are isomorphisms (not necessarily computable). Ideally, such a functor *F* from **C** to **D** should be effective: given a structure *M* from **C** as an oracle, it should compute the structure *F(M)* in **D**, and given a **C**-morphism *g* from *M* to *N* as an oracle, it should compute the **D**-morphism *F(g)* from *F(M)* to *F(N)*. Moreover, one would hope for *F* to be full and faithful, as a functor, and to have a computable inverse functor. In practice, it is unusual for an *F* to have all of these properties, and for particular applications in computable model theory, only certain of the properties are needed. Many familiar examples will be included to help make these concepts clear.

Recent joint work by Harrison-Trainor, Melnikov, Montalbán, and the speaker has established that computable functors are closely connected to Montalban’s notion of *effective interpretation* of one class **C** of countable structures in another class **D**. We will explain the connections and discuss the extent to which they realize the model-theorist’s suspicion that functors are really just another version of interpretations.

# Towards a model theory of Zariski-Riemann spaces of valuations

Zariski introduced the space of all valuations on a given field *K* and named it after his mentor the `Riemann manifold’. This terminology is justified because of the following two facts he proved about it: (1) one can define a (quasi-)compact topology on this space (and we honor him embracingly by calling it the Zariski-Riemann space), and (2) if *K* is the function field of a curve, then this space is isomorphic to a non-singular curve with the same function field. Hence (2) gives resolution of singularities in dimension one, and he then used fact (1) to show the same in dimension two. Abhyankar then followed suit by proving that in dimension two, any point (=valuation) in this space is attainable by blowing ups, but his student Shannon showed that this failed in dimension three and higher. This latter negative result somehow ended the Zariski project of using the space of all valuations to prove resolution of singularities in higher dimensions.

However, there is a resurgence of this space and its use in resolution of singularities during the last decades, and often, these results are combined with model-theoretic techniques (Kuhlmann, Knaf, Pop, Cutkosky, Cossart, Piltant, Teissier, Scanlon,…). However, the model-theoretic setting always departs from Robinson’s point of view of a valued field: a field together with a valuation. However, the Zariski-Riemann space talks about not just one valuation, but all, so that we need a new framework. I will present some preliminary remarks of how this could be done using either a simple-minded one-sorted language or a more sophisticated two-sorted language. As a simple application of the one-sorted case, I will reprove fact (1) by simply relating it to the compactness of the Stone space of types.

# Algebraic and model-theoretic methods in constraint satisfaction

The Constraint Satisfaction Problem (CSP) of a first-order structure **S** in a finite relational language is the problem of deciding whether a given conjunction of atomic formulas in that language is satisfiable in **S**. Many classical computational problems can be modeled this way. The study of the complexity of CSPs involves an interesting combination of techniques from universal algebra, Ramsey theory, and model theory. I will present an overview over these techniques as well as some wild conjectures.

# Choice principles and Ramsey theory

This talk will provide an overview of results of Ramsey theory that have close relationships with constructions of models of **ZF** that distinguish between various forms of the Axiom of Choice. Some open problems and directions for further research will also be discussed.

# Mordell-Lang and Manin-Mumford in positive characteristic, revisited

We give a reduction of function field Mordell-Lang to function field Manin-Mumford, in positive characteristic. The upshot is another account of or proof of function field Mordell-Lang in positive characteristic, avoiding the recourse to difficult results on Zariski geometries.

(This work is joint with Benoist and Bouscaren.)

# Set theory without the infinite

The historical origins of set theory lay in the study of the infinite. Later came the universalist claim that set theory is a foundation for all of mathematics. We consider the consequences of accepting the universalism without accepting the infinite. We come to see finite sets as graphs or as processes, the result of their own coming into being. Basic methods of set construction give rise to arithmetics of sets with some surprising properties.

# On transformations in the Painlevé family

The Painlevé equations are nonlinear 2nd order ODE and come in six families *P _{1}–P_{6}*, where

*P*consists of the single equation

_{1}*y′′=6y*, and

^{2}+t*P*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. In this talk I will explain how one can use model theory to answer the question of whether there exist algebraic relations between solutions of different Painlevé equations from the families

_{2}–P_{6}*P*.

_{1}–P_{6}# Model theory of difference fields, part I

I’ll begin by setting up the first-order language and axioms of difference, and give some interesting examples, including frobenius automorphisms of fields in positive characteristic and difference equations from analysis that give the subject its name. Difference-closed fields, a natural analog of algebraically closed fields, have a nice model theory, starting with almost-quantifier elimination. Further model-theoretic notions – algebraic closure, elementary equivalence, forking independence – all have elementary purely algebraic characterizations that I will explain. The model theory of difference fields has been used in arithmetic geometry in several exciting ways (Hrushovski’s results on the Manin-Mumford Conjecture; his twisted Lang-Weil estimates; several people’s work on algebraic dynamics) that I will probably not explain in detail.

This talk will be continued in the Model Theory Seminar the following week.

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

# Choice schemes for Kelley-Morse set theory

Kelley-Morse (${\rm KM}$) set theory is one of the standard axiomatic foundations for set theory with classes as well as sets. Its defining feature is a strong class existence principle which states that any collection defined by a second-order assertion is a class. Choice schemes are choice/collection axioms for classes. The full choice scheme states for every second-order assertion $\varphi$ that if for every set $x$, there is a class $X$ such that $\varphi(x,X)$, then there is a single class $Z$ collecting all the witnesses, so that $\varphi(x,Z_x)$ holds, where $Z_x$ is the slice on coordinate $x$ of $Z$. The full choice scheme can be weakened in a number of ways. For instance, the set-sized choice scheme allows only set many choices to be made and the $\Sigma^1_n$-choice scheme restricts the complexity of $\varphi$. Study of the choice schemes dates back to the work of Marek and Mostowski from the 1970s. They have recently found application in nonstandard set theory with infinitesimals and analysis of properties of class forcing extensions. We show that even the weakest fragment of the choice scheme, where $\omega$-many choices must be made for a first-order assertion, may fail in a model of ${\rm KM}$ and that it is possible for the set-sized choice scheme to hold, while the full choice scheme fails for a first-order assertion. We argue that the theory ${\rm KM^+}$ consisting of ${\rm KM}$ together with the full choice scheme is more robust than ${\rm KM}$ because it is able to prove the Łoś Theorem for second-order ultrapowers and the absorption of first-order quantifiers in second-order assertions. We show that both these properties can fail in a model of ${\rm KM}$: the second-order ultrapower of a ${\rm KM}$-model may not even be a model of ${\rm KM}$ and a second-order assertion of complexity $\Sigma^1_n$ with a set quantifier in front may fail to have complexity $\Sigma^1_n$. This is joint work with Joel David Hamkins and Thomas Johnstone.

# Computable algebra: a personal perspective

I will give a brief overview of some of my recent research in the field of Computable Algebra, emphasizing connections between Computability Theory and Algebra. Some of the topics that I hope to cover include Artinian and Euclidean rings, as well as infinite dimensional vector spaces. There will be no proofs, just statements of theorems along with discussions on their logical and algebraic significance.

# Topological Ramsey spaces and Fraïssé structures

There seems to be a natural relationship between topological Ramsey spaces and Fraïssé classes of finite structures. In fact, for some Fraïssé classes satisfying the Ramsey property, it is possible to define a topological Ramsey space such that the Fraïssé limit of the class is essentially an element of the space. We will talk about examples of this phenomenon, describe the general case to some extent, and comment about how this could be understood as a abstract tool to classify Fraïssé structures.

# The domatic numbers of computable graphs

A dominating set $D$ of a graph is a set of vertices “near” all other vertices, in that every vertex outside of $D$ is adjacent to a vertex in $D$. In this talk, we will compare two values associated with a graph $G$: the domatic number $d(G)$ and computable domatic number $d^c(G)$, which give the size of the largest partition and computable partition (respectively) of $G$ into dominating sets. Our goal is to maximize the value of $d(G)-d^c(G)$ for highly computable graphs (in which we can computably count each vertex’s neighbors). Specifically, is it even possible for this difference to be greater than 1? To find an answer, we will work with total dominating sets (where $D$ must now be near *all* vertices, instead of only the ones outside of $D$) and regular graphs (where each vertex has exactly the same number of neighbors). In our proofs and constructions, we will play the “game” of computable graph theory, as we set up gadgets and spring traps against adversaries who are determined to thwart our every move.

The slides for the talk are available here.

# A natural strengthening of Kelley-Morse set theory

I shall introduce a natural strengthening of Kelley-Morse set theory KM to the theory we denote KM+, by including a certain class collection principle, which holds in all the natural models usually provided for KM, but which is not actually provable, we show, in KM alone. The absence of the class collection principle in KM reveals what can be seen as a fundamental weakness of this classical theory, showing it to be less robust than might have been supposed. For example, KM proves neither the Łoś theorem nor the Gaifman lemma for (internal) ultrapowers of the universe, and furthermore KM is not necessarily preserved, we show, by such ultrapowers. Nevertheless, these weaknesses are corrected by strengthening it to the theory KM+. The talk will include a general elementary introduction to the various second-order set theories, such as Gödel-Bernays set theory and Kelley-Morse set theory, including a proof of the fact that KM implies Con(ZFC). This is joint work with Victoria Gitman and Thomas Johnstone.

# Maximal Automorphisms

Given a model M, a maximal automorphism is one which fixes as few points in M as possible. We begin by outlining what the correct definition of “as few points as possible” should be and then proceed to study the notion. An interesting question arises when one considers the existence of maximal automorphisms of countable recursively saturated models. In particular an interesting dichotomy arises when one asks whether for a given theory T all countable recursively saturated models of T have a maximal automorphism. Our primary goal is to determine which classes of theories T lie on the positive side of this dichotomy. We give several examples of such classes. Attacking this problem requires a detailed understanding of recursive saturation, which we will also review in this talk.

# The lattice problem

Ordered by inclusion, the set of elementary substructures of a model of PA is a lattice.

It is an ℵ_{1}-compactly generated lattice, meaning that every element of the lattice is a supremum of its compact elements, and for every compact element, there are at most countably many compact elements below it. The lattice problem for models of PA is to determine which lattices can be represented as lattices of elementary substructures of a model of PA. The condition above puts a restriction on the types of lattices that can be represented this way. As far as we know, this can be the only restriction. Much work on the problem has been done in the 1970s by Gaifman, Knight, Mills, Paris, Schmerl, and Wilkie, and has been continued by Schmerl. It involves some specialized knowledge of models of PA, highly nontrivial lattice representation theory, combinatorics, and sometimes number theory. There are many positive results, but we still do not know if there is a finite lattice which cannot be represented as a substructure lattice of a model of PA. My talk will be an introduction to the lattice problem. I’ll introduce basic definitions and I’ll prove a couple of introductory negative results.

# 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 search for computable domatic partitions

A domatic $k$-partition of a graph is a partition of the vertex set into $k$ many classes, in which each vertex $v$ is adjacent to some vertex in every partition class of which $v$ is not a member; the domatic number is the largest $k$ for which there is a domatic $k$-partition (compare to the chromatic number of a graph, which is the size of the smallest partition into independent sets). The authors previously showed that there is a computable, locally finite graph $G$ with a domatic $k$-partition, but no computable domatic $3$-partition. In this talk we will investigate whether the same result holds for highly computable graphs, and $A$-computable graphs (we say a graph $G$ is $A$-computable if $A$ can compute the neighborhood function of $G$). This work is joint with Oscar Levin and Tyler Markkanen.

# Structurability and countable Borel equivalence relations

The dynamical and descriptive set theoretic complexity of a countable Borel equivalence relation E can often be understood in terms of the kinds of countable first order structures which are compatible with E in a suitable sense. In this talk I will make this suitable sense precise by discussing the notion of Borel structurability. I will also discuss some recent joint work with Brandon Seward in which we show that the equivalence relation generated by the free part of the translation action of a countable group G on its powerset is structurably-universal among equivalence relations generated by free Borel actions of G.

# Generalized descriptive set theory with very large cardinals

We will discuss the structure *L(V _{λ+1})* and attempts to generalize facts of descriptive set theory to this structure in the presence of very large cardinals. In particular we will introduce an axiom called Inverse Limit Reflection which we will argue is analogous to the Axiom of Determinacy in this context. The slides for this talk are available here.

# The theory of fields is complete for isomorphisms

We give a highly effective coding of countable graphs into countable fields. For each countable graph $G$, we build a countable field $F(G)$, uniformly effectively from an arbitrary presentation of $G$. There is a uniform effective method of recovering the graph $G$ from the field $F(G)$. Moreover, each isomorphism $g$ from $G$ onto any $G’$ may be turned into an isomorphism $F(g)$ from $F(G)$ onto $F(G’)$, again by a uniform effective method so that $F(g)$ is computable from $g$. Likewise, an isomorphism $f$ from $F(G)$ onto any $F(G’)$ may be turned back into an isomorphism $g$ with $F(g)=f$. Not every field $F$ isomorphic to $F(G)$ is actually of the form $F(G’)$, but for every such $F$, there is a graph $G’$ isomorphic to $G$ and an isomorphism $f$ from $F$ onto $F(G’)$, both computable in $F$.

It follows that many computable-model-theoretic properties which hold of some graph $G$ will carry over to the field $F(G)$, including spectra, categoricity spectra, automorphism spectra, computable dimension, and spectra of relations on the graph. By previous work of Hirschfeldt, Khoussainov, Shore, and Slinko, all of these properties can be transferred from any other countable, automorphically nontrivial structure to a graph (and then to various other standard classes of structures), so our result may be viewed as saying that, like these other classes, fields are complete for such properties.

This work is properly joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh. The slides for the talk are available here.

# The proof/plan correspondence in databases

We consider answering queries over datasources (for logicians: finite relational structures) that are connected to one another by integrity constraints (logical relationships). A relation in a datasource may have multiple means of access with different required arguments, and the means of access within and across relations may differ radically in cost. We present a method for generating the lowest cost query plan, where a plan is a reformulation of the query referencing only the allowable access methods, equivalent to the original query on all datasources satisfying the integrity constraints. A solution to this problem can be applied in many database contexts, including answering queries using views, optimizing queries using constraints, and querying on top of web services or web forms. It could also be applied to give a more logic-based foundation for traditional database query planning.

Proof-driven query reformulation generates plans by applying interpolation procedures to a “proof that the query can be answered,” an approach that goes back at least to Craig’s proof of the Beth Definability theorem via interpolation. A few additional ingredients are needed to apply interpolation to database problems, including:

— variations of Beth Definability that allow us to target plans (explicit definitions) of specific forms

— an extension of interpolation that considers the “access patterns” within quantification

— specialized proof procedures for classes of integrity constraints of interest to databases

— cost-based search procedures for concurrently exploring the collection of proofs and plans

The resulting query planning system blends automated deduction, query optimization, and heuristic search.

This is joint work with Balder ten Cate, Julien Leblay and Efi Tsamoura.

# Ramsey cardinals and the continuum function

In his famous theorem, Easton used the Easton Product forcing to show that if $V\models{\rm GCH}$ and $F$ is any weakly increasing function on the regular cardinals such that $\text{cf}(F(\alpha))>\alpha$, then there is a cofinality preserving forcing extension in which $F$ is realized as the continuum function. The investigation then shifted to identifying which continuum patterns are compatible with large cardinals. It is not difficult to see that large cardinals affect the behavior of the continuum function. Obviously, if $\kappa$ is inaccessible, then by definition, the continuum function must have a closure at $\kappa$. Some other large cardinal influences are much more subtle. Easton’s original forcing does not work well in the presence of large cardinals; it, for instance, destroy weak compactness over $L$. So set theorists have had to develop some general and other very specific forcing techniques to address the behavior of the continuum function for a given large cardinal. In this talk, we will show that if $V\models{\rm GCH}$, $\kappa$ is Ramsey, and $F$ is any weakly increasing class function on the regular cardinals with a closure point at $\kappa$ such that $\text{cf}(F(\alpha))>\alpha$, then there is a cofinality preserving forcing extension in which $\kappa$ remains Ramsey and $F$ is realized as the continuum function. This is joint work with Brent Cody.

An extended abstract can be found here.

# New directions in reverse mathematics

Mathematics today benefits from having “firm foundations,” by which we usually mean a system of axioms sufficient to prove the theorems we care about. But given a particular theorem, can we specify precisely which axioms are needed to derive it? This is a natural question, and also an ancient one: over 2000 years ago, the Greek mathematicians were asking it about Euclid’s geometry. Reverse mathematics provides a modern approach to this kind of question. A striking fact repeatedly demonstrated in this area is that the vast majority of mathematical propositions can be classified into just five main types, according to which set-existence axioms are needed to carry out their proofs. But more recently, a growing number of principles falling outside this classification have emerged, whose logical strength is more difficult to understand. These turn out to include many important mathematical results, such as various combinatorial problems related to Ramsey’s theorem, and several set-theoretic equivalents of the axiom of choice. I will discuss some of these “irregular” principles, and some new approaches that have arisen from trying to understand why their strength is so different from that of most other theorems. In particular, this investigation reveals new connections between different mathematical areas, and exposes the rich and complex combinatorial and algorithmic structure underlying mathematics as a whole.

# Higher-order Reverse Mathematics: Where existence meets computation via infinitesimals.

Classically, the existence of an object tells us very little about how to construct said object.

We consider a nonstandard version of Ulrich Kohlenbach’s higher-order Reverse Mathematics

in which there is a very elegant and direct correspondence between, on one hand, the existence

of a functional computing an object and, on the other hand, the classical existence of this object

with the same standard and nonstandard properties. We discuss how these results -potentially-

contribute to the programs of finitistic and predicativist mathematics.

# On forcing and the (elusive) free two-generated left distributive algebra

We begin with an extended introduction to free left distributive algebras (LDs) including a normal form theorem for the one-generated free LD, which itself arises naturally from the assumption of a very large cardinal axiom. After discussing some applications and open problems, we make remarks on the difficulty of using forcing to attempt to construct a two-generated free LD by lifting the rank-to-rank elementary embedding used to create the one-generated free LD.

This is joint work with Joel David Hamkins.

# Measure semantics for modal logics

Long before Kripke semantics became standard in modal logic, Tarski showed us that the basic propositional modal language can be interpreted in topological spaces. In Tarski’s semantics for the modal logic $S4$, each propositional variable is evaluated to an arbitrary subset of a fixed topological space. I develop a related, measure theoretic semantics, in which modal formulas are interpreted in the Lebesgue measure algebra, or algebra of Borel subsets of the real interval $[0,1]$, modulo sets of measure zero. This semantics was introduced by Dana Scott in the last several years. I discuss some of my own completeness results, and ways of extending the semantics to more complex modal languages.

# The recursive spectrum of a strongly minimal modular theory of groups in a finite language

# Prikry-type sequences, iterations and critical sequences

I will present some old, some new and some classic results on the kinds of sequences which are added by some forcings which are related to Prikry forcing, in some sense. After finding combinatorial properties characterizing these sequences, I will show how to iterate the universe in such a way that the critical sequence of that iteration will satisfy that combinatorial property with respect to the target model, rendering it generic. This connection enables us to analyze precisely the collection of generic sequences which are present in one specific forcing extension. Time permitting, I will also explore connections to Boolean ultrapowers.

# Reverse VC Calculations

Note Hill’s Workshop talk is cancelled due to illness.

Let F be a family of sets, for example, a uniformly definable semi-algebraic family in real or p-adic n-space. The Vapnik-Chervonenkis (VC) dimension of F is a measurement of the combinatorial complexity of F. Once you know the VC dimension of F, theorems from computational geometry, like the Epsilon-Net Theorem, give nice geometric consequences for F. I will discuss a statistical strategy for reversing the flow of information in this theorem. Instead of starting with knowledge of the VC dimension, we merely hypothesize “dimension=d” for some value d. Then, we observe the geometric behavior of F using computer experiments and compare the observed behavior with the behavior that is predicted by the theorem (under the hypothesis “dimension=d”). If our observed results have sufficiently low probability (conditioned on “dimension=d”), then we can reject the hypothesis “dimension=d” with a high degree of confidence. Ultimately, we hope to use such methods to shed light on conjectures about VC density in the p-adics. This project is joint work with Deirdre Haskell and Nigel Pynn-Coates.

# Automorphism Groups of Countable, Recursively Saturated Models of Peano Arithmetic

It is still unknown whether there are nonisomorphic countable recursively saturated models M and N whose automorphism groups Aut(M) and Aut(N) are isomorphic. I will discuss what has happened over the last 20 years towards showing that such models do not exist, including some very recent results.

# Generic choice functions and ultrafilters on the integers

We will discuss a question asked by Stefan Geschke, whether the existence of a selector for the equivalence relation $E_0$ implies the existence of a nonprincipal ultrafilter on the integers. We will present a negative solution which is undoubtedly more complicated than necessary, using a variation of Woodin’s $mathbb{P}_{mathrm{max}}$. This proof shows that, under suitable hypotheses, if $E$ is a universally Baire equivalence relation on the reals, with countable classes, then forcing over $L(E,mathbb{R})$ to add a selector for $E$ does not add a nonprincipal ultrafilter on the integers.

# Randomness and ergodic theorems under measure-preserving transformations

Ergodic theorems describe regular measure-theoretic behavior, and a point is said to be algorithmically random if it has no rare measure-theoretic properties of a certain kind. The connections between these two types of regularity have been well studied over the past five years. I will discuss Birkhoff’s ergodic theorem with respect to transformations that are measure-preserving but not necessarily ergodic in the context of a computable probability space. Then I will show that each point in such a space that is not Martin-L”of random does not satisfy Birkhoff’s ergodic theorem with respect to every computable set and measure-preserving transformation.

This work is joint with Henry Towsner.

# Why model-theorists shouldn’t think that ACF is easy

We all learned that stability theory derived many of its ideas from what happens in ACF, where everything is nice and easy. After all ACF has quantifier elimination and is strongly minimal, decidable, superstable, uncountably categorical, etc. However, my own struggles with ACF have humbled my opinion about it: it is an awfully rich theory that encodes way more than our current knowledge. I will discuss some examples showing how “difficult” ACF is: Grothendieck ring, isomorphism problem, set-theoretic intersection problem. Oddly enough, RCF seems to not have any of these problems. It is perhaps my ignorance, but I have come to think of RCF as much easier. Well, all, of course, is a matter of taste.

# Satisfaction is not absolute

I will discuss a number of theorems showing that the satisfaction relation of first-order logic is less absolute than might have been supposed. Two models of set theory $M_1$ and $M_2$, for example, can agree on their natural numbers $langlemathbb{N},{+},{cdot},0,1,{lt}rangle^{M_1}=langlemathbb{N},{+},{cdot},0,1,{lt}rangle^{M_2}$, yet disagree on arithmetic truth: they have a sentence $sigma$ in the language of arithmetic that $M_1$ thinks is true in the natural numbers, yet $M_2$ thinks $negsigma$ there. Two models of set theory can agree on the natural numbers $mathbb{N}$ and on the reals $mathbb{R}$, yet disagree on projective truth. Two models of set theory can have the same natural numbers and have a computable linear order in common, yet disagree about whether this order is well-ordered. Two models of set theory can have a transitive rank initial segment $V_delta$ in common, yet disagree about whether this $V_delta$ is a model of ZFC. The theorems are proved with elementary classical methods.

This is joint work with Ruizhi Yang (Fudan University, Shanghai). We argue, on the basis of these mathematical results, that the definiteness of truth in a structure, such as with arithmetic truth in the standard model of arithmetic, cannot arise solely from the definiteness of the structure itself in which that truth resides; rather, it must be seen as a separate, higher-order ontological commitment.

# A survey of the model theory of tracial von Neumann algebras

Von Neumann algebras are certain algebras of bounded operators on Hilbert spaces. In this talk we will survey some of the model theoretic results about (tracial) von Neumann algebras, focusing mainly on (in)stability, quantifier-complexity, and decidability. No prior knowledge of von Neumann algebras will be necessary. Some of the work presented is joint with Ilijas Farah, Bradd Hart, David Sherman, and Thomas Sinclair.

# What is the theory ZFC without power set?

The theory ZFC-, consisting of the usual axioms of ZFC but with the power set axiom removed — specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well-ordered — is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context.

For example, there are models of ZFC- in which a countable union of countable sets is not countable. There are models of ZFC- for which the Los ultrapower theorem fails, even for wellfounded ultrapowers on a measurable cardinal. Moreover, the theory ZFC- is not sufficient to establish that the union of Σ_{n} and Π_{n} sets is closed under bounded quantification. Lastly, there are models of ZFC- for which the Gaifman theorem fails, in that there exists cofinal embeddings *j:M–>N* between ZFC- models that are Σ_{1}-elementary, but not fully elementary.

Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory obtained by using collection rather than replacement in the axiomatization above. This is joint work with Joel David Hamkins and Victoria Gitman, and it extends prior work of Andrzej Zarach.

arxiv preprint | post at jdh.hamkins.org | post on Victoria Gitman’s blog

# Models of Reverse Mathematics

We discuss two results relating ideas in Reverse Mathematics to the properties of models of first order arithmetic. The first shows that we can extend second order arithmetic by the existence of a non-principal ultrafilter — a third order property — while remaining conservative. The second result shows that we can extend models of RCA so that any particular set is definable; this allows us to recover some properties of models of Peano arithmetic for models of RCA.

# Mittag-Leffler objects in definable categories of modules

Definable categories are classes of modules closed under direct product, direct limit, and pure submodule. These play an important role in the theory of modules as they are in bijection with the closed sets of the Ziegler spectrum (and thus with the product closed complete theories of modules). Mittag-Leffler objects for such categories (some sort of generalized atomic module) will be introduced and a necessary and sufficient condition in terms of generators and generalized relations will be given for them to exist.

# An algebraic characterization of recursively saturated real closed fields

We (with D’Aquino and Kuhlmann) give a valuation theoretic characterization for a real closed field to be recursively saturated. Previously, Kuhlmann, Kuhlmann, Marshall, and Zekavat gave such a characterization for kappa-saturation, for all infinite cardinals kappa. Our result extends the characterization for a divisible ordered abelian group to be recursively saturated found in some unpublished work of Harnik and Ressayre.

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

# Determinacy in analysis and beyond

Recently Montalban and Shore derived precise limits to the amount of determinacy provable in second order arithmetic. We review some of the results in this area and recent work on lifting this to a setting of ZF^- with a single measurable cardinal.

# Namba-like singularizations of successor cardinals

Bukowski-Namba forcing preserves aleph_1 and changes the cofinality of aleph_2 to omega. We lift this to cardinals kappa > aleph_1 : Assuming a measurable cardinal lambda we construct models over which there is a further “Namba-like” forcing which preserves all cardinals <= kappa and changes the cofinality of kappa^+ to omega. Cofinalities different from omega can also be achieved by starting from measurable cardinals of sufficiently strong Mitchell order. Using core model theory one can show that the respective measurable cardinals are also necessary. This is joint work with Dominik Adolf (Münster). Slides

# Some approaches to model theory for classes of finite structures

This talk surveys work on the development of model theory for classes of finite structures due primarily to Macpherson and the speaker, and to several of Macpherson’s students. The underlying theme of this work has been to bring to the model-theoretic study of classes of finite structures aspects of the model theory of infinite structures.

# Reverse mathematics for second-order categoricity theorem

It is important in the foundations of mathematics that the natural number system is characterizable as a system of 0 and a successor function by second-order logic. In other words, the following Dedekind’s second-order categoricity theorem holds: every Peano system $(P,e,F)$ is isomorphic to the natural number system $(N,0,S)$. In this talk, I will investigate Dedekind’s theorem and other similar statements. We will first do reverse mathematics over $RCA_0$, and then weaken the base theory. This is a joint work with Stephen G. Simpson.

# Understanding genericity for cuts

In a nonstandard model of arithmetic, initial segments with no maximum elements are traditionally called *cuts*. It is known that even if we restrict our attention to cuts that are closed under a fixed family of functions (e.g., multiplication, the primitive recursive functions, or the Skolem functions), the properties of cuts can still vary greatly. I will talk about what *genericity* means amongst such great variety. This notion of genericity comes from a version of model theoretic forcing devised by Richard Kaye in his 2008 paper. Some ideas were already implicit in the work by Laurence Kirby and Jeff Paris on indicators in the 1970s.

# Very NIP Ordered Groups

In recent years there has been renewed interest in theories without the independence property (NIP theories), a class of theories including all stable as well as all o-minimal theories. In this talk we concentrate on theories, T, which expand that of divisible ordered Abelian groups (a natural situation to consider if one is motivated by the study of o-minimal theories) and consider the problem determining the consequences of assuming that T is NIP on the structure of definable sets in models of T. One quickly realizes that given the great generality of the NIP assumption in order to address this type of question one wants to consider much stronger variants of not having the independence property. Thus we are led to the study of definable sets in models of theories T expanding that of divisible ordered Abelian groups satisfying various very strong forms of the NIP condition such as finite dp-rank, convex orderability, and VC minimality. In this talk I will survey results in this area and discuss many open problems.

# On the axiom of constructibility and Maddy’s conception of restrictive theories

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible. Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory.

In this talk, I shall criticize Maddy’s specific proposal. For example, it turns out that the fairly-interpreted-in relation on theories is not transitive, and similarly the maximizes-over and strongly-maximizes-over relations are not transitive. Further, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s proposal, although this is not what she had desired.

Ultimately, I argue that the $Vneq L$ via maximize position loses its force on a multiverse conception of set theory, in light of the classical facts that models of set theory can generally be extended to (taller) models of V=L. In particular, every countable model of set theory is a transitive set inside a model of V=L. I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

# Model theory of satisfaction classes

All countable recursively saturated models of Peano Arithmetic have nonstandard satisfaction classes. In fact, each such model has a great variety of nonstandard satisfaction classes. I will survey model theoretic techniques that can be applied to construct many different inductive satisfaction classes, and I will show how, in return, inductive satisfaction classes are used to prove important result about recursively saturated models of PA. I will also pose an open problem concerning a possible converse to Tarski’s undefinability of truth theorem.

Pdf slides for the talk are here: Satisfaction Classes

# Transfinite linear algebra

# Boolean subalgebras of the computable atomless Boolean algebra

An abstract of this talk will be added.

# Recent progress on the modal logic of forcing and grounds

The modal logic of forcing arises when one considers a model of set theory in the context of all its forcing extensions, with “true in all forcing extensions” and“true in some forcing extension” as the accompanying modal operators. In this modal language one may easily express sweeping general forcing principles, such as the assertion that every possibly necessary statement is necessarily possible, which is valid for forcing, or the assertion that every possibly necessary statement is true, which is the maximality principle, a forcing axiom independent of but equiconsistent with ZFC. Similarly, the dual modal logic of grounds concerns the modalities “true in all ground models” and “true in some ground model”. In this talk, I shall survey the recent progress on the modal logic of forcing and the modal logic of grounds. This is joint work with Benedikt Loewe and George Leibman.

# The countable models of ZFC, up to isomorphism, are linearly pre-ordered by the submodel relation; indeed, every countable model of ZFC, including every transitive model, is isomorphic to a submodel of its own L

This will be a talk on some extremely new work. The proof uses finitary digraph combinatorics, including the countable random digraph and higher analogues involving uncountable Fraisse limits, the surreal numbers and the hypnagogic digraph.

The story begins with Ressayre’s remarkable 1983 result that if $M$ is any nonstandard model of PA, with $langletext{HF}^M,{in^M}rangle$ the corresponding nonstandard hereditary finite sets of $M$, then for any consistent computably axiomatized theory $T$ in the language of set theory, with $Tsupset ZF$, there is a submodel $Nsubsetlangletext{HF}^M,{in^M}rangle$ such that $Nmodels T$. In particular, one may find models of ZFC or even ZFC + large cardinals as submodels of $text{HF}^M$, a land where everything is thought to be finite. Incredible! Ressayre’s proof uses partial saturation and resplendency to prove that one can find the submodel of the desired theory $T$.

My new theorem strengthens Ressayre’s theorem, while simplifying the proof, by removing the theory $T$. We need not assume $T$ is computable, and we don’t just get one model of $T$, but rather all models—the fact is that the nonstandard models of set theory are universal for all countable acyclic binary relations. So every model of set theory is a submodel of $langletext{HF}^M,{in^M}rangle$.

Theorem.(JDH) Every countable model of set theory is isomorphic to a submodel of any nonstandard model of finite set theory. Indeed, every nonstandard model of finite set theory is universal for all countable acyclic binary relations.

The proof involves the construction of what I call the countable random $mathbb{Q}$-graded digraph, a countable homogeneous acyclic digraph that is universal for all countable acyclic digraphs, and proving that it is realized as a submodel of the nonstandard model $langle M,in^Mrangle$. Having then realized a universal object as a submodel, it follows that every countable structure with an acyclic binary relation, including every countable model of ZFC, is realized as a submodel of $M$.

Theorem.(JDH) Every countable model $langle M,in^Mrangle$ of ZFC, including the transitive models, is isomorphic to a submodel of its own constructible universe $langle L^M,in^Mrangle$. In other words, there is an embedding $j:Mto L^M$ that is quantifier-free-elementary.

The proof is guided by the idea of finding a universal submodel inside $L^M$. The embedding $j$ is constructed completely externally to $M$.

Corollary.(JDH) The countable models of ZFC are linearly ordered and even well-ordered, up to isomorphism, by the submodel relation. Namely, any two countable models of ZFC with the same well-founded height are bi-embeddable as submodels of each other, and all models embed into any nonstandard model.

The work opens up numerous questions on the extent to which we may expect in ZFC that $V$ might be isomorphic to a subclass of $L$. To what extent can we expect to have or to refute embeddings $j:Vto L$, elementary for quantifier-free assertions?