Fall 2017

shore@math.cornell.edu

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.

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

Abstract:

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

Abstract:

Tuesday, 11/7: *TBA *

, Cornell University

Abstract:

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

Abstract:

Wednesday, 11/15: *TBA*

**Julia Gordon**, Michler Fellow (Cornell University) and University of British Columbia

Abstract:

Tuesday, 11/21: *TBA*

, Cornell University

Abstract:

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

Abstract: