Logic seminar
Fall 2017

Richard Shore

We meet in Malott 206. Tuesday 2:55-4:10 and Wednesday 4:00-5:15.
The Topic day will be Tuesday except for scheduling issues arising for some specific weeks.

The topic for this semester will be a new view of computable structure theory.

We will be using a draft of a book in progress by Antoio Montalban

Antonio Montalban, Computable Structure Theory: Part 1, Draft..

From the Preface: The objective of this book is to describe some of the main ideas and techniques used in the field. Most of these ideas are old, but for many of them, the style of the presentation is not. Over the last few years, the author has developed new frameworks for dealing with these old ideas as for instance for forcing, r.i.c.e. relations, jumps, Scott ranks, back-and-forth types, etc. One of the objectives of the book is to present these frameworks in a concise and self-contained form.

We may also use some recent papers.

We will begin with an introduction at the first lecture of the third week of class. The listings of chapters by week for the topic are only estimates until after the dates have passed.

Schedule of Seminars:

Tuesday, 8/22: Hilbert's Tenth Problem for subrings of the rationals
  Russell Miller, Queens College and CUNY Graduate Center

Abstract: For a ring R, Hilbert’s Tenth Problem is the set HTP(R) of polynomials f ∈ R[X1,X2,…] for which f=0 has a solution in R. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that HTP(Z) is Turing-equivalent to the Halting Problem. The Turing degree of HTP(Q) 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 HTP(Q) computes the Halting Problem if and only if HTP(R) computes it for a nonmeager set of subrings R. We also draw parallels and make distinctions between the jump operator and the operator HTP, which maps an element of Cantor space to the the HTP of the corresponding subring of Q.

There will be a dinner with the speaker at Mia's, 6:00 p.m. Please contact me (shore@math.cornell.edu) if you would like to join us.

Wednesday, 8/23: Classification and measure for algebraic fields
  Russell Miller, Queens College and CUNY Graduate Center

Abstract: The algebraic fields of characteristic 0 are precisely the subfields of the algebraic closure of the rationals, up to isomorphism. Continuing a topic introduced in this seminar last May, we describe a way to classify them effectively, via a computable homeomorphism onto Cantor space. This homeomorphism makes it natural to transfer Lebesgue measure from Cantor space onto the class of these fields, but there is another probability measure on the same class which seems in some ways more natural than Lebesgue measure. We will discuss how certain properties of these fields -- notably, relative computable categoricity -- interact with these measures: the basic result is that only measure-0 many of these fields fail to be relatively computably categorical.

Tuesday, 8/29: Organizational meeting

Wednesday, 8/30: Department Reception is at 4:00 so no seminar.

Tuesday, 9/5: A history of foundations with a bias toward λ-calculus and type-free systems part 1
  Scott Messick,

Abstract: I will sketch a brief motivation for my project to design a new foundational system, and then dive into the history of formal foundations. This talk will cover the period of approximately 1870-1950. Highlights will include the work of Frege, Hilbert's program, Principia Mathematica (Russell and Whitehead), Zermelo's axiomatization of set theory and Fraenkel's later improvement, Brouwer's intuitionism and his conflict with Hilbert, Gödel's incompleteness theorems, and Church's λ-calculus, all with detailed technical commentary (or at least, more detailed than usual historical overviews).
The history is of independent interest, of course, but will also help facilitate an explanation of what properties I want in a new system. The history gives context and clues as to the fundamental capabilities and limitations of formal systems, as well as psychological pitfalls for the humans who study them. Audience commentary and discussion is strongly encouraged!

Wednesday, 9/6: Computable Structure Theory, Ch. I, II Structures and...
  Richard Shore, Cornell University

Tuesday, 9/12: A history of foundations with a bias toward λ-calculus and type-free systems part 2
  Scott Messick,

Abstract: Despite the name, this talk should make sense for anyone; attendance of part 1 is not needed. In part 2 I will shift to focus more specifically on two threads in the modern history of foundations: constructive type theories and type-free systems. I'll talk about how these kinds of systems were developed historically and how they contrast ontologically with each other and with set theoretic foundations. I'll go into more detail on the two major strong type-free foundational systems in the literature: Myhill and Flagg's system (1989) and Grue and Berline's system Map Theory (1992-2016), and contrast these with each other. Finally, I'll discuss which properties of those two systems I do and do not want to incorporate into my own system under construction, called OE (Operations and Equalities).

Wednesday, 9/13: Computable Structure Theory, Ch. II,III Relations and ...
  Jamie Barnes, Cornell University

Tuesday, 9/19: Computable Structure Theory, Ch. III Relations and Existentially-atomic models part 1
  Jun le Goh, Cornell University

Wednesday, 9/20: A Club Minimal Kurepa Tree I
  Hossein Lamei Ramandi, Cornell University

Abstract: We will show it is consistent with GCH that there is a club minimal Kurepa tree.

Tuesday, 9/26: Increasing dimension s to dimension t with few changes
  Linda Brown Westrick, University of Connecticut, Storrs

Abstract: We show that for every s < t in [0,1], every sequence of effective dimension s can be changed on density at most H^{-1}(t) - H^{-1}(s) of its bits in order to obtain a sequence of effective dimension t, where H is the Shannon binary entropy function. This is the infinitary analogue of a known finite result, but passing from the finite to the infinite requires, among other techniques, a convexity argument with a puzzling dichotomy. The density bound is the best possible, and this answers a question which was left open at the time of previous presentations on this subject. Joint work with Noam Greenberg, Joe Miller and Sasha Shen.

There will be a dinner with the speaker, 6:00 p.m. at Mehak. Please let me know if you will join us.

Wednesday, 9/27: Computable Structure Theory, Ch.III Existentially-atomic models part 2
  Jun Le Goh, Cornell University

Tuesday, 10/3: Computable Structure Theory, Ch.III Existentially-atomic models part 3
  Jun Le Goh, Cornell University

Wednesday, 10/4: A Club Minimal Kurepa Tree II
  Hossein Lamei Ramandi, Cornell University

Tuesday, 10/10: No Seminar - Fall Break

Wednesday, 10/12: Detecting Automorphism Groups Interpretably
  Romin Abdolahzadi, Cornell University

Abstract: Recall that if E/K is an infinite Galois extension, then the Galois group G = Gal(E/K) comes endowed with a canonical topology which in turn makes G a profinite topological group. Observing that E can be written as a union of finite Galois orbits over K, we consider E to be a finitary structure. Generalizing this situation using definability leads to a model-theoretic reformulation of Galois groups for schemes. As such, we develop a category of interpretations to detect differences in automorphism groups of multi-sorted structures. This yields a restriction functor from the category of finitary structures to the category of profinite groups, and we show that this functor is an almost equivalence of categories.

Tuesday, 10/17: Scott Ranks of Computable Structures
  Matthew Harrison-Trainor, University of Waterloo

Abstract: The Scott rank of a structure is a measure of its complexity. I will talk about a few results about the Scott ranks of computable structures, focusing on structures of high Scott rank and in particular of Scott rank $\omega_1^{CK}$. We will start with a few different constructions of structures of this Scott rank with different properties, such as one whose infinitary theory is not countably categorical. Then we will argue that there is no natural/canonical construction of a computable structure of Scott rank $\omega_1^{CK}$.

There will be a dinner with the speaker after the seminar.

Wednesday, 10/18:Some Computable Structure Theory of Finitely Generated Structures
  Matthew Harrison-Trainor, University of Waterloo

Abstract: Every countable structure has a sentence of infinitary logic, called a Scott sentence, which describes it up to isomorphism among countable structures. We can characterize the complexity of a structure by the complexity of the simplest description of that structure. A finitely generated structure always has a $\Sigma^0_3$ description. We show that there is a finitely generated group which has no simpler description. The proof of this leads us to talk about notions of universality for finitely generated structures. Finitely generated groups are universal, but finitely generated fields are not. By this, we mean that for every finitely generated structure, there is a finitely generated group which has the same computability-theoretic properties; but the same is not true for finitely generated fields. We apply the results of this investigation to pseudo Scott sentences.

Tuesday, 10/24: Computable Structures IV: Generic Presentations
  Jeffrey Bergfalk, Cornell University


Wednesday, 10/25: Gowers' Fin_k Theorem: an elementary proof and equivalence with Iterated Hindman's Theorem I
  Richard Shore, Cornell University

Abstract: Gowers' Fin_k theorem is a combinational result about for colorings of a particular family of (countable) partial semigroups with homomorphisms between them where the homogeneity requirement applies to sets generated by both the semigroup operations and the homomorphisms. It has important applications in analysis.
The proof uses ultrafilters and indeed spaces of ultrafilters and Zorn's lemma type arguments on various subspaces to produce an ultrafilter that guides the construction of the homogeneous set. We prove that Gowers' theorem is provable in recursive mathematics (RCA_0) from a version of a seemingly much simpler special case, Hindman's theorem. Hindman's theorem is known to have a quite elementary proof. So too, then does Gowers'. We will also try to explain what such a proof would be without the metamathematical arguments.

Tuesday, 10/31: Computable structure theory as group actions
  Antonio Montalban, University of California, Berkeley

Abstract: We discuss how to generalize some classical results in computable structure theory the the general setting of actions of polish groups into polish spaces.
Joint work with Alexander Melnikov.

There will be a dinner with the speaker.

Wednesday, 11/1: Gowers' Fin_k Theorem an elementary proof and equivalence with Iterated Hindman's Theorem II
  Richard Shore, Cornell University


Tuesday, 11/7: TBA
  , Cornell University


Wednesday, 11/8: A game characterizing Baire class 1 functions
  Viktor Kiss, Cornell University

Abstract: Duparc introduced a two-player game G_f for a self-map f of the Baire space such that Player II has a winning strategy iff f is Baire class 1. We define a game G'_f for an arbitrary function f between arbitrary Polish spaces such that Player II has a winning strategy in G'_f iff f is Baire class 1. We also show that G'_f is always determined.

Tuesday, 11/14: TBA
  , Cornell University


Wednesday, 11/15: TBA
  Julia Gordon, Michler Fellow (Cornell University) and University of British Columbia


Tuesday, 11/21: TBA
  , Cornell University


Wednesday, 11/22 No Meeting, Thanksgiving break.

Tuesday, 11/28: TBA
  , Cornell University

Wednesday, 11/29: TBA
  Liat Kessler, Cornell University and Univesity of Haifa