# Welcome to New York Logic

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

Model theory seminar
Northeast Regional Model Theory Days
University of Pennsylvania

go to the Calendar

## Upcoming talks and events:

Set theory seminarFriday, October 21, 2016

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

Kolchin seminar in Differential AlgebraFriday, October 21, 201610:15 amGC 5382

# Imaginaries in valued differential fields I: Finding prolongations

UC Berkeley

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.

Model theory seminarFriday, October 21, 201612:30 pmGC 6417

# Imaginaries in valued differential fields II: Computing canonical bases

UC Berkeley

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.

CUNY Logic WorkshopFriday, October 21, 20162:00 pm

# No CUNY Logic Workshop on October 21

Model theory seminarSaturday, October 22, 2016

# Northeast Regional Model Theory Days

University of Pennsylvania

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.

Set theory seminarFriday, October 28, 201610:00 amGC 6417

# The isomorphism problem for rank-1 transformations

University of Louisville

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

Model theory seminarFriday, October 28, 201612:30 pmGC6417

# On Collapse of Generalized Indiscernibles.

Towson University

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.

CUNY Logic WorkshopFriday, October 28, 20162:00 pmGC 6417

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

Set theory seminarFriday, November 4, 201610:00 amGC 6417

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

NERDS: New England Recursion & Definability SeminarSunday, November 6, 2016

# Autumn 2016 NERDS at Wellesley College

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.

NERDS: New England Recursion & Definability SeminarSunday, November 6, 201610:30 amScience Center, Room E104​, Wellesley College, Wellesley, MA

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

Cornell University

We first prove a theorem about reals (subsets of N) and classes of reals: If a real X is Σ11 in every member G of a nonempty Σ11 class K of reals then X is itself Σ11. 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 Σ11 in every member of a nonempty Σ11 class B of reals then A is itself Σ11. ​ This is joint work with T. Slaman and L. Harrington ​.​

NERDS: New England Recursion & Definability SeminarSunday, November 6, 201611:40 amScience Center, Room E104​, Wellesley College, Wellesley, MA

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

University of Connecticut

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.

NERDS: New England Recursion & Definability SeminarSunday, November 6, 20161:40 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

# Structure within the class of K-trivial sets

University of Auckland

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.

NERDS: New England Recursion & Definability SeminarSunday, November 6, 20162:50 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

# Comparing notions of effective genericity

Notre Dame University

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.

NERDS: New England Recursion & Definability SeminarSunday, November 6, 20163:30 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

# Uncountable free abelian groups via κ-computability

University of Connecticut

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 Σ01 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 Σ11-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.

Wednesday, November 9, 20165:00 pmGerald D. Fischbach Auditorium, Simons Foundation, 160 Fifth Avenue, 2nd floorTo attend this talk, you need to register here.

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

Model theory seminarFriday, November 11, 201612:30 pm

# TBA

McMaster University
CUNY Logic WorkshopFriday, November 11, 20162:00 pmGC 6417

# Describing finite groups by short first-order sentences

University of Auckland

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.

Model theory seminarFriday, November 11, 20163:45 pmGC 6417

# TBA

University of Maryland
CUNY Logic WorkshopFriday, November 18, 20162:00 pmGC 6417

# A finitary analogue of the downward Lowenheim-Skolem property

Indian Institute of Technology (IIT) Bombay, India

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.

CUNY Logic WorkshopFriday, December 2, 20162:00 pmGC 6417

# Title TBA

University of Connecticut