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: Samples from the proofs.
Tuesday, 11/7: Computable Structures V: Degree Spectra I
Shihao Xiong, 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: Menger compacta and simplexes through projective Fraisse limits I
Slawek Solecki, Cornell University
Abstract: In each dimension d, there exists a canonical compact, second countable
space, called the d-dimensional Menger space, with certain universality and homogeneity
properties. For d = 0, it is the Cantor set, for d = infinity, it is the Hilbert cube.
In this talk, I will concentrate on the 1-dimensional Menger space.
I will prove that it is a quotient of a projective Fraisse limit (a construction with
roots in Model Theory). I will describe how a property of projective Fraisse
limits coming from Logic, called the projective extension property, can be used to
prove high homogeneity of the 1-dimensional Menger space.
This is joint work with Aristotelis Panagiotopoulos.
Wednesday, 11/15: Motivic integration on p-adic fields
Julia Gordon, Michler Fellow (Cornell University) and University of British Columbia
Abstract: I will give a brief introduction to the theory of motivic integration developed by
R. Cluckers and F. Loeser, which is based on model theory techniques, and allows to
understand the measure on p-adic fields in a ``uniform in p'' way. I will also try
to sketch some applications in representation theory, which can be thought of as a
far-reaching extension of the Ax-Kochen-Ersov principle.
Tuesday, 11/21: Menger compacta and simplexes through projective Fraisse limits II
Slawek Solecki, Cornell University
Abstract: In this talk, I will either go over some
proofs or give a presentation of simplexes as quotients of projective Fraisse
limits leading to a homology theory for projective Fraisse limits.
This is done with the hope of handling Menger
compacta with dimension d > 1.
This is joint work with Aristotelis Panagiotopoulos.
Wednesday, 11/22 No Meeting, Thanksgiving break.
Tuesday, 11/28: Computable Structures V: Degree Spectra II
Shihao Xiong, Cornell University
Wednesday, 11/29: Holomorphic shadows in the eyes of model theory
Liat Kessler, Cornell University and Univesity of Haifa
Abstract: Zariski-type structures were introduced and studied by Zilber and
Hrushovski in their study of strongly minimal sets. A Zariski-type
structure is a set X with a collection of compatible Noetherian topologies,
one on each X^n, and an assignment of dimension to the closed sets,
satisfying certain conditions. For example, taking the complex analytic
subvarieties of M^n, for a compact complex analytic manifold M, to be the
closed sets and the dimension to be the complex dimension gives a
Zariski-type structure. I am showing that a similar statement holds if the
manifold is almost complex, i.e., admits an automorphism J of the tangent
bundle TM such that J^2=-Id, that does not necessarily arise from a
holomorphic atlas on the manifold. I will define an almost complex subvariety, and outline
the geometric results that are needed to show that the obtained structure is Zariski-type. I
will also talk about geometric applications.