Welcome to New York Logic!

Oct 20 Thursday | Oct 21 Friday | Oct 22 Saturday | Oct 23 Sunday | Oct 24 Monday | Oct 25 Tuesday | Oct 26 Wednesday |
---|---|---|---|---|---|---|

**→** go to the Calendar

## Upcoming talks and events:

# No set theory seminar on October 21

Since many of the seminar members will be away, there will be no set theory seminar on October 21.

# Imaginaries in valued differential fields I: Finding prolongations

In 2000, Scanlon described a theory of existentially closed differential fields where the derivation is contractive: v(d(x)) ≥ v(x), for all x. He also proved a quantifier elimination result for this theory. Around the same time, Haskell, Hrushovski and Macpherson classified all the quotients of definable sets by definable equivalence relations in a algebraically closed valued field by proving elimination of imaginaries (relative to certain quotients of the linear group). In analogy with the pure field situation where elimination of imaginaries for differentially closed fields can be derived from elimination of imaginaries in the underlying algebraically closed field, it was conjectured that Scanlon’s theory of existentially closed contractive valued differential fields also eliminated imaginaries relatively to those same quotients of the linear group.

In this talk, I will describe the first part of the proof that this result indeed holds. Our main goal will be to explain a construction that can be interpreted as finding “generic” prolongations for valued differential constructible sets.

# Imaginaries in valued differential fields II: Computing canonical bases

In 2000, Scanlon described a theory of existentially closed differential fields where the derivation is contractive: v(d(x)) ≥ v(x), for all x. He also proved a quantifier elimination result for this theory. Around the same time, Haskell, Hrushovski and Macpherson classified all the quotients of definable sets by definable equivalence relations in a algebraically closed valued field by proving elimination of imaginaries (relative to certain quotients of the linear group). In analogy with the pure field situation where elimination of imaginaries for differentially closed fields can be derived from elimination of imaginaries in the underlying algebraically closed field, it was conjectured that Scanlon’s theory of existentially closed contractive valued differential fields also eliminated imaginaries relatively to those same quotients of the linear group.

In this talk, I will describe the second part of the proof that this result indeed holds. Our goal will be to explain a result, joint with Pierre Simon, on definable types in enrichments of NIP theories, which is crucial to prove elimination of imaginaries. We show that under certain hypothesis if a type in some NIP theory T is definable in an enrichment of T, then it h is already be definable in T.

# Northeast Regional Model Theory Days

The Northeast Regional Model Theory Days will take place on Saturday the 21st of October and

Sunday the 22nd of October at the University of Pennsylvania in Philadelphia PA. See the Northeast Regional Model Theory Days website for full details.

# The isomorphism problem for rank-1 transformations

I’ll begin by describing two fascinating questions in ergodic theory, one being the isomorphism problem for measure-preserving transformations. I’ll survey some of the progress that has been made on these problems, including some partial solutions to the isomorphism problem for certain classes of measure-preserving transformations and some anti-classification results, stating that “nice” solutions to the isomorphism problem are impossible on other classes of measure-preserving transformations. Then I’ll discuss recent work I’ve done with Su Gao on the isomorphism problem for the class of rank-1 transformations, a generic class of measure-preserving transformations where the isomorphism relation is known to be, in some sense, well-behaved. (Background information ergodic theory will be introduced as needed.)

# On Collapse of Generalized Indiscernibles.

I discuss the characterization of model theoretic dividing lines by collapse of generalized indiscernibles. For example, S. Shelah showed that a theory is stable if and only if all order indiscernibles are set indiscernibles. In her thesis, L. Scow showed that a theory has NIP if and only if all graph order indiscernibles are order indiscernibles. I explore new results characterizing dp-rank and rosiness using similar methods. I also talk about some attempts to create a general framework for such results. This work is joint with C. Hill and L. Scow.

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

# Separating Class Determinacy

In his dissertation, Steel showed that both open determinacy and clopen determinacy have a reverse math strength of $\mathsf{ATR}_0$. In particular, this implies that clopen determinacy is equivalent to open determinacy (over a weak base theory). Gitman and Hamkins in recent work explored determinacy for class-sized games in the context of second-order set theory. They asked whether the analogue of Steel’s result holds: over $\mathsf{GBC}$, is open determinacy for class games equivalent to clopen determinacy for class games?

The answer, perhaps surprisingly, is no. In this talk I will present some recent results by Hachtman which answer the question of Gitman and Hamkins. We will see how to construct a transitive model of $\mathsf{GBC}$ which satisfies clopen class determinacy but does not satisfy open class determinacy.

# Autumn 2016 NERDS at Wellesley College

The Autumn 2016 meeting of NERDS, the New England Recursion and Definability Seminar, will take place on Sunday, November 6 at Wellesley College, in Wellesley, MA. Details are available from the NERDS website, and talks are also posted here on nylogic.org.

# Σ11 in every real in a Σ11 class of reals is Σ11

We first prove a theorem about reals (subsets of **N**) and classes of reals: If a real *X* is Σ^{1}_{1} in every member *G* of a nonempty Σ^{1}_{1} class **K** of reals then *X* is itself Σ^{1}_{1}. We also explore the relationship between this theorem, various basis results in hyperarithmetic theory and omitting types theorems in ω-logic. We then prove the analog of our first theorem for classes of reals: If a class **A** of reals is Σ^{1}_{1} in every member of a nonempty Σ^{1}_{1} class **B** of reals then **A** is itself Σ^{1}_{1}. This is joint work with T. Slaman and L. Harrington .

# Recursion theoretic results for the game of Cops and Robbers on graphs

Cops and Robbers is a vertex-pursuit game played on a connected graph wherein two players, a cop and a robber, begin on a pair of vertices and alternate turns moving to adjacent vertices. A graph is cop-win if, from any pair of starting vertices, the cop can occupy the same vertex as the robber after finitely many rounds. In this talk, preliminary computability-theoretic and reverse-math results about the game of cops and robbers on infinite computable graphs will be discussed. We will consider several characterizations of infinite cop-win trees and graphs, and explore the complexity of winning strategies for both players.

# Structure within the class of K-trivial sets

The *K*-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity *K* grows as slowly as possible. Since 2002, many alternative characterisations of this class have been found: properties such as low for *K*, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked amorphous. More recently, internal structure has been found. Bienvenu et al (JEMS, 2016) showed that there is a “smart” *K*-trivial set, in the sense that any ML-random computing it must compute all *K*-trivials. Greenberg, Miller and Nies (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches via cost functions.

# Comparing notions of effective genericity

In recent work, Cholak, Dzhafarov, Hirst and Slaman showed that for *n ≥ 3*, every Mathias *n*-generic computes a Cohen *n*-generic. It is natural to wonder how other types of generic objects compare to one another. We consider generics for an effective version of Hechler forcing. Adapting a method developed by Cholak, Dzhafarov, and Soskova, we show that for *n ≥ 3*, every Mathias *n*-generic computes a Hechler *n*-generic, and every Hechler *n*-generic computes a Mathias *n*-generic. Finally, we explore the (open) question of whether, for *n ≥ 3*, the Mathias *n*-generics and the Hechler *n*-generics occupy exactly the same Turing degrees.

# Uncountable free abelian groups via κ-computability

One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ^{0}_{1} definable (with parameters, in the language of set theory) over *L _{κ}* provides the notion of κ-computability. We may also quantify over subsets of

*L*, providing a notion of a κ-analytic set (here we assume

_{κ}*V=L*). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ

^{1}

_{1}-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.

# Randomness

Is the universe inherently deterministic or probabilistic? Perhaps more importantly – can we tell the difference between the two?

Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling and more. Indeed, randomness seems indispensable! Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from “unpredictable” phenomena like the weather or the stock market?

A computational theory of randomness, developed in the past three decades, reveals (perhaps counterintuitively) that very little is lost in such deterministic or weakly random worlds. In the talk, Dr. Wigderson will explain the main ideas and results of this theory.

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

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