- 1/30/2024 4PM,
Steffen Lempp,
UW
Title: The Borel complexity of the class of models
of first-order theories
(video
and slides and
related paper)
Abstract: We investigate the descriptive complexity of the set of models of
first-order theories. Using classical results of Solovay and Knight, we give a
sharp condition for complete theories to have a
Π0ω-complete
set of models. We also calibrate the complexity of sets of models of some
other complete theories. (This is joint work with Andrews, Gonzalez, Rossegger
and Zhu, and related to recent work of Enayat and Visser.)
- 2/6/2024 4PM,
Hongyu
Zhu, UW
Title: The Borel complexity of the class of models of
first-order theories: the finite case
(video
and slides and
related paper)
Abstract: This is a follow-up to the previous week's talk where we mainly
consider boundedly axiomatizable theories. We relate the quantifier complexity
of the axiomatization to the Wadge degree of the set of models and present
several examples demonstrating the relationship. We then consider the
effectiveness of the reductions. At last, we discuss some open questions of
interest to us. (Based on joint work with Andrews, Gonzalez, Lempp, Rossegger
and related to recent work of Enayat and Visser.)
- 2/7/2024 (analysis seminar in VV B223,
3:30PM),
Don Stull, University of Chicago,
Illinois
Title: Dimensions of pinned distance sets in the
plane
(slides)
Abstract: In this talk, we discuss recent work on the Hausdorff and packing
dimension of pinned distance sets in the plane. Given a point x in the plane,
and a subset E, the pinned distance set of E with respect to x is the set of
all distances between x and the points of E. An important open problem is
understanding the Hausdorff, and packing, dimensions of pinned distance sets.
We will discuss ongoing progress on this problem, and present improved lower
bounds for both the Hausdorff and packing dimensions of pinned distance sets.
We also discuss the computability-theoretic methods used to achieve these
bounds.
- 2/13/2024 4PM,
Uri Andrews,
UW
Title: Degree spectra of theories
(related papers:
Andrews/Miller,
Andrews/Knight,
Andrews/Cai/Diamondstone/Lempp/Miller)
Abstract: The degree spectrum of a theory T captures the difficulty of the
problem of computing some model of the theory T. Explored previously in
several different contexts, e.g., Solovay characterized the degree spectra of
completions of PA, theory spectra were introduced as a topic of focus in their
own right by myself and Joseph S. Miller in the early 2010s. I hope to give a
sampling of results and an overview of what we know about this topic. I
believe there are yet many interesting and accessible questions in this topic.
- 2/16/2024
(department colloquium in VV B239, 4PM),
Jack Lutz,
Iowa State University, Ames
Title: Algorithmic fractal dimensions
(slides)
Abstract: Algorithmic fractal dimensions are computability-theoretic versions
of Hausdorff dimension and other fractal dimensions. This talk will introduce
algorithmic fractal dimensions with particular focus on the Point-to-Set
Principle. This principle has enabled several recent proofs of new theorems
in geometric measure theory. These theorems, some solving long-standing open
problems, are classical (meaning that their statements do not involve
computability or logic), even though computability has played a central in
their proofs.
- 2/20/2024 4PM,
Josiah
Jacobsen-Grocott, UW
Title: The theory of degree structures with jump
(video)
Abstract: It in this talk we look at work done in understanding the complexity
of the structure the Turning degrees DT with different languages
using ≤, ∨, and jump. For instance, it is known that all of these are
definable from ≤, and that the full theory is equivalent to second-order
arithmetic. We also consider what happens when we limit the number of
quantifiers. For instance. the ∀∃-theory of (DT,≤)
is decidable, but the ∀∃-theory of (DT,≤,∨,') is
undecidable. We will also look how some of these results can be translated to
results about the theory of the enumeration degrees.
- 2/29/2024
Midwest Model Computability Seminar (joint with Midwest Model Theory
Seminar), John Crerar Library Building 390, 5730 S. Ellis Ave.,
University of Chicago
Brown Bag Lunch: noon
Speakers:
- 1PM, Ronnie Nagloo, University of Illinois-Chicago
Title: Model theory and differential equations
This talk provides a survey of recent work around applications of model theory
to the study differential equations. In particular, we will focus on the work
over the past decade centered around using geometric stability to study
concrete definable sets in Differentially Closed Fields (DCF).
- 1:55PM, Isabella Scott, University of Chicago, Illinois
Title: Effective constructions of existentially closed
groups
(video)
Existentially closed groups were introduced in 1951 as a group-theoretic
analogue to algebraically closed fields. Since then, they have been further
studied by Neumann, Macintyre, and Ziegler, who elucidated deep connections
with model theory and computability theory. We review some of the literature
on existentially closed groups and present new results that further refine
these connections. In particular, we are able to pinpoint more precisely how
complexity arises in existentially closed groups, and quantify how much is
visible to the "local" structure. We will also discuss constructions giving
two existentially closed groups that are "as different as possible".
Coffee Break: 2:50PM
- 3:10PM, Adam Topaz,
University of Alberta, Edmonton, Canada
Title: Formalizing Lawvere theories in dependent type
theory
(video)
Lawvere theories provide a categorical approach to doing Universal Algebra,
and their algebras have the benefit of being easily interpreted in any category
with the correct limits. This talk will discuss some work in progress toward
encoding (multi-sorted) Lawvere theories in dependent type theory, using the
Lean4 interactive proof assistant (ITP). Specifically, after an introduction
to the mathematical theory itself, I'll talk about why one might be interested
in formalizing these objects in an ITP, as well as some of the challenges
around making this formalization useful in relation to preexisting algebraic
hierarchies.
- 4:05PM, Steffen
Lempp, UW
Title: Minimal covers in the Weihrauch degrees
(video and slides)
We study the existence of minimal covers and strong minimal covers in the
Weihrauch degrees. We characterize when a problem f is a minimal cover or
strong minimal cover of a problem h. We show that strong minimal covers only
exist in the cone below id and that the Weihrauch lattice above id is dense.
From this, we conclude that the degree of id is first-order definable in the
Weihrauch degrees and that the first-order theory of the Weihrauch degrees is
computably isomorphic to third-order arithmetic.
This is joint work with J. Miller, Pauly, M. Soskova and Valenti.
Dinner: Nile Restaurant,
1162 E. 55th St. at 5:30PM
- 3/12/2024 4PM,
Vittorio
Cipriani (remote talk), Technical University of Vienna, Austria
Title: Classifying isomorphism problems and learning
of algebraic structures
(video
and slides)
Abstract: We study the classification of isomorphism problems with countably
many isomorphism types, combining ideas from computable structure theory and
algorithmic learning theory. The framework we use was defined in a series of
papers by Bazhenov, Fokina, Kötzing, and San Mauro. Here, given a
countable family K of structures, a
learner receives larger and larger
pieces of an isomorphic copy of a structure in K and, at each stage, is
required to output a conjecture about the isomorphism type of such a structure.
The learning is
successful if the conjectures eventually stabilize to
a correct guess.
Together with Bazhenov and San Mauro, we showed that a countable family of
countable structures is learnable if and only if the corresponding isomorphism
problem reduces to the equivalence relation E0. Replacing
E0 with other Borel equivalence relations, one obtains a hierarchy
to rank such isomorphism problems.
Bazhenov, Fokina, and San Mauro gave a model-theoretic characterization of
learnability; here we provide similar characterizations about other classical
learning criteria and the learning power of several equivalence relations
(with a focus on Friedman-Stanley jumps of the identity on 2N and
NN). This talk collects joint work with Bazhenov, Jain, Marcone,
San Mauro, and Stephan.
- 3/19/2024 4PM,
Steffen Lempp,
UW
Title: A jump for the Weihrauch degrees
(video
and slides)
Abstract: I will present the definition of a
version of a jump function on the Weihrauch degrees which is degree-theoretic,
strictly increasing on each degree, and monotonic. The jump can in fact be
defined in two different ways, each of which has the flavor of a total
continuation of a multi-valued function given by the original problem.
This new version of a jump has a number of surprising properties, in
particular, it is indeed injective on the Weihrauch degrees (and thus induces
an embedding of these degrees into themselves).
We have determined the specific jump of some problems: E.g., the
jump of the least degree is the degree of id; and the jump of choice on Baire
space is the total continuation of this problem.
I will discuss other recent results on this jump notion in my talk.
This is joint with Andrews, Marcone, J. Miller and Valenti.
- 4/2/2024 4PM,
Alice Vidrine, UW
Title: Some results on enumeration Weihrauch
reduction
(video
and slides)
Abstract: Enumeration Weihrauch (eW) reduction is a variant of Weihrauch
reduction that replaces Turing functionals by enumeration operators, using a
notion of "positive information" computation. In this setting, several of the
benchmark choice problems in the Weihrauch setting become separated. We discuss
some of the more striking examples and their proofs, and describe the
progress in the search for a first-order difference between the eW degrees
and Weihrauch degrees.
- 4/9/2024 4PM,
Tim McNicholl,
Iowa State University, Ames
Title: Computability theory of operator algebras
(video and related
papers: Burton/Eagle/Fox/Goldbring/Harrison-Trainor/McNicholl/Melnikov/Thewmorakot and
McNicholl)
Abstract: Over the past decade, a program to adopt computable structure theory
to metric structures has emerged. This program, called effective metric
structure theory, blends the fundamental ideas of computable analysis and
computable structure theory. Many results about computable presentations of
metric spaces and Banach spaces have been obtained. I will discuss recent
discoveries about computable presentability and computable categoricty of
C*-algebras.
Dinner: Fugu Asian Fusion (411 W. Gilman St.) around 6PM
- 4/16/2024 4PM,
Isabella Scott, University of Chicago, Illinois
Title: Computability-theoretic investigations into
existentially closed groups
(video and
related paper)
Abstract: Existentially closed groups were introduced by WR Scott in 1951 in
analogue with algebraically closed fields. Since then, they have been further
studied by Neumann, Macintyre, and Ziegler, who elucidated deep connections
with model theory and computability theory. We undertake an investigation
into the complexity of existentially closed groups, which uncovers surprising
stratifications and connections not visible without computability-theoretic
tools.
(For those who have seen me give similarly titled and abstracted talks, I plan
to dive deeper into the proofs of my results than in earlier versions of the
talk.)
Dinner: A La
Brasa Mexican Grill (15 N. Broom St.) around 6PM
- 4/30/2024 4PM,
Josiah
Jacobsen-Grocott, UW
Title: Structural and topological aspects of the
enumeration and hyperenumeration degrees (thesis defense)
(video and
slides)
Abstract: I will give a broad overview of the results I have proved during my
Ph.D., with a focus on the enumeration degrees and the relationship between
subclasses of the enumeration degrees and non-metrizable topology.
A point in a represented second-countable T0-space can be identified
with the set of basic open sets containing that point. Using this coding, we can
consider the enumeration degrees of the points in a second-countable
T0-space. For example, the ω-product of the Sierpiński
space is universal for second-countable T0-spaces and gives us all
enumeration degrees, and the Hilbert cube gives us all continuous degrees.
We look at how the topological separation axioms interact when applied to
classes of enumeration degrees, and extend results of Kihara, Ng, and Pauly
to show that the hierarchy of T0, T1, T2,
T2.5, submetrizable, metrizable is strict for classes of
enumeration degrees.
- 5/2/2024 4PM (room B115 Van Vleck)
Yayi Fu,
University of Notre Dame, Indiana
Title: The Erdős-Hajnal property in
NIP theories
(video and
slides)
Abstract: We show a proof using model-theoretic techniques and substitution
that the Erdős-Hajnal property holds for graphs with VC-dimension ≤
2.
We also show that the family of graphs with bounded VC-minimal complexity, a
notion that arises from VC-minimal theory, has the strong Erdős-Hajnal
property.
And we show a lemma about combs and pure pairs that I found when attempting to
prove the Erdős-Hajnal property for dp-minimal graphs.
Dinner: Himal Chuli Restaurant (318 State St.) around 6PM
- 5/7/2024 4PM,
Meng-Che ("Turbo")
Ho, California State University, Northridge
Title: Turing embeddings between abelian groups and
fields
(video
and related paper)
Abstract: TFAb
r, the class of torsion-free abelian groups of rank r,
and FD
r, the class of fields of transcendence degree r, have many
structural similarities. However, under Borel reducibility, the isomorphism
relations on these classes behave differently. For instance, Hjorth (for r = 1)
and Thomas (for r > 1) showed that TFAb
r+1 has strictly higher
complexity than TFAb
r. On the other hand, Thomas and
Veličković showed that the class FD
r has maximal possible
complexity for r ≥ 13.
In this talk, we compare TFAbr and FDr using a couple of
reducibilities. We show that there are functorial Turing computable reductions
from TFAbr to FDr, as well as from FDr to
FDr+1. However, we do not know if these embeddings are strict. We
also show that under computable countable reductions, all these classes are
equivalent and
Σ03-complete.
This is a joint work with Julia Knight and Russell Miller.
Dinner: The Old
Fashioned (23 N. Pinckney St.) around 6PM
- 5/21/2024 3PM,
Keng Meng ("Selwyn")
Ng, Nanyang Technological University, Singapore
Title: Enumeration degrees and applications
(video and
slides)
Abstract: We discuss some recent work on the local enumeration degrees. We
discuss the so-called “one point extension” problem, which is a critical
subproblem of the decidability of the AE-theory of the local enumeration
degrees.
same day: 4PM,
Luca San Mauro,
University of Bari, Italy and Technical University of Vienna, Austria
Title: Beyond the ceers
(video and
slides)
Abstract: Ceers (c.e. equivalence relations) have garnered a lot of interest
in the last couple of decades. The classification of equivalence relations of
higher complexity has been less systematic. In this talk, we review a number
of results about degree structures properly extending the ceers, with a focus
on the global structure of all countable equivalence relations under
computable reducibility.
Dinner: The Globe (309 N. Henry St.) around 6PM
- 6/21/2024 2PM,
Ang Li, UW
Title: Countable ordered groups and Weihrauch
reducibility (specialty exam)
(video
and slides)
Abstract: It is known that a countable ordered group has order type
ZαQε, where α is an
ordinal and ε is either 0 or 1. This theorem falls into
Π11-CA0,
the highest of the big five axiom systems in reverse mathematics. In this talk,
we study this theorem using Weihrauch reducibility. Given a countable ordered
group, we will study the uniform computational power of outputting some of
α, ε, and the order-preserving function.