- 9/10/2024 4PM,
Steffen Lempp,
UW
Title: Some results on the Ziegler degrees
(video
and related paper)
Abstract: In a landmark 1980 monograph, Ziegler studied finitely generated
subgroups of existentially closed groups and uncovered a surprising connection
of this purely algebraic question and computability. To this end, he defined a
new reducibility which he called *-reducibility and which I will call Ziegler
reducibility, which is a refinement of both Turing and enumeration reducibility.
In particular, he showed that if a finitely generated group H is a subgroup of
an existentially closed group G and the word problem of a finitely generated
group H
0 is Ziegler reducible to the word problem of H, then
H
0 is (isomorphic to) a subgroup of G as well.
In joint work with Isabella Scott and Josiah Jacobsen-Grocott, I studied the
induced degree structure of the Ziegler degrees and was able to show that there
is a minimal Ziegler degree, and indeed that any finite distributive lattice is
isomorphic to an initial segment of the Ziegler degrees. As a consequence, the
∀∃∀-theory of the Ziegler degrees (as a partial order) is
undecidable.
- 9/17/2024 4PM,
Yayi Fu,
UW
Title: O-minimal coherence
(video
and slides)
Abstract: Bakker, Brunebarbe, Tsimerman showed in 2022 that the definable
structure sheaf O
Cn of
Cn is a
coherent O
Cn-module as a sheaf on the site
Cn, where the coverings are finite coverings by
definable open sets.
In general, let K be an algebraically closed field of
characteristic zero. We give another proof of the coherence of
OKn as a sheaf of OKn-modules on
the site Kn using spectral topology on the type space
Sn(K). (Here Sn(K) just means
S2n(R) for some real closed field R.)
It also gives an example of how the intuition that sheaves on the type space
are the same as sheaves on the site with finite coverings (see Proposition 3.2
in Edmundo (2006)) can be applied.
- 9/24/2024 4PM,
Jake
Fiedler, UW
Title: Bounds on the dimension of lineal
extensions
(video
and slides)
Abstract: How does the size of a collection of line segments in
Rn change if we extend each segment to a full line? In this
talk, we investigate this problem in geometric measure theory using techniques
from algorithmic information theory, specifically Kolmogorov complexity and
the point-to-set principle of Lutz and Lutz. Working in the plane, we show
that the packing dimension of any set does not increase under line segment
extension. This allows us to prove the generalized Kakeya conjecture for
packing dimension in the plane. Finally, we discuss versions of this problem
in higher dimensions. This is based on joint work with Ryan Bushling.
- 10/4/24
(department colloquium), 4PM in
room B239 Van Vleck,
Su Gao, Nankai University, Tianjin, China
Title: Continuous combinatorics of countable abelian
group actions
(slides)
Abstract: We consider combinatorial problems on the free parts of the Bernoulli
shift actions of countable abelian groups, such as chromatic numbers, edge
chromatic numbers, perfect matchings, etc. These problems can all be regarded
as special cases of the problem whether there exist continuous equivariant
maps from the free part of the Bernoulli shift action to a subshift of finite
type. We prove a master theorem which in theory gives complete answers to the
subshift problem. Furthermore, we show that the class of (codes for) all
subshifts of finite type with a positive answer to the subshift problem is a
complete c.e. set. This is joint work with Steve Jackson, Ed Krohne, and
Brandon Seward.
Dinner: Vintage Brewing Company (676 S. Whitney Way) on
Saturday, Oct. 5th, at 7PM
- 10/7/2024 4PM (room B123),
Liang Yu,
Nanjing University, China
Title: When is A + xA = R?
(slides)
Abstract: We investigate which algebra substructures A of reals are such
that there is a real x for which A+xA=R.
- 10/8/2024 4PM,
Hongyu Zhu,
UW
Title: Survey on Vaught's Conjecture
(specialty exam)
(video
and slides)
Abstract: In 1961, Vaught proposed his conjecture on the number of countable
models of a first-order theory. Despite some early progress and attempts from
various areas of logic, the conjecture remains unsolved today. In this talk,
we will survey certain results around the conjecture, including alternative
formulations and solved special cases. In particular, we will discuss Shelah's
proof of Vaught's conjecture for complete ω-stable first-order theories
and how that relates to my own work in progress.
- 10/15/2024 4PM,
Antonio Nakid
Cordero, UW
Title: Uniform Martin’s Conjecture in the enumeration
degrees
(video
and slides)
Abstract: Martin's Conjecture is a long open problem in computability theory
that seeks to explain the structure of the "naturally occurring" Turing degrees.
Even though the full conjecture remains open, several significant partial
results have been obtained both in the Turing degrees and by translating the
conjecture to other degree structures. In the enumeration degrees, the naive
version of Martin's conjecture is known to be false. Moreover, the technical
machinery used to mathematize "naturally occurring" in the Turing degrees does
not work.
We present a surprising positive result based on Bard's local approach to the
uniform Martin's conjecture. From this, we get that part 1 of Martin's
conjecture is true for uniformly Turing-to-enumeration invariant functions.
Additionally, we give a counterexample for both parts of the global uniform
Martin's conjecture in the enumeration degrees.
- 10/22/2024 4PM,
Joel David Hamkins,
University of Notre Dame, Indiana
Title: The covering reflection principle
(video
and slides and
speaker's blog)
Abstract: The principle of covering reflection holds of a cardinal κ
if for every structure B in a countable first-order language there is a
structure A of size less than κ such that B is covered by elementary
images of A in B. Is there any such cardinal? Is the principle consistent?
Does it have large cardinal strength? This is joint work with myself, Nai-Chung
Hou, Andreas Lietz, and Farmer Schlutzenberg.
Dinner: The Cooper's Tavern (20 W. Mifflin St.) around 5:30PM
- 10/29/2024 4PM,
Matthew Harrison-Trainor,
University of Illinois-Chicago
Title: Scott ranks of models of theories of linear
orders
(video
and slides)
Abstract: The Scott rank of a countable structure is an ordinal measuring the
complexity of that structure. Given a sentence of infinitary logic, we think
of it as a theory defining a class of models. There are simple theories (as
measured by quantifier complexity) all of whose models have high Scott rank.
By universality results, these theories could be theories of groups, graphs,
fields, etc. However, they cannot be theories of linear orders: We show instead
that given a consistent theory of linear orders expressed with α
alternations of quantifiers, there is a model with Scott rank at most
α+3.
Dinner: Great Dane Pub & Brewing (123 E. Doty St.) around 5:30PM
- 11/5/2024 4PM,
Tim
McNicholl, Iowa State University, Ames
Title: The computability of K-theory for operator
algebras (joint work with C. Eagle, I. Goldbring, and R. Miller)
(video
and slides)
Abstract: K-theory is a general method for associating countable Abelian groups
with mathematical structures. These groups are invariants, but they are not
always classifiers. Lately, Chris Eagle, Isaac Goldbring, Russell Miller, and
I have been thinking about the computability of K-theory as it applies to
operator algebras (i.e., C*-algebras). I will try to explain the
machinery of K-theory for operator algebras and explain at least the
architecture of the following theorems. 1) If A is a computably presentable
C*-algebra, then the Abelian group K0(A) has a c.e.
(a.k.a. recursive) presentation. 2) If A is a computably presentable uniformly
hyperfinite algebra, then K0(A) has a computable presentation;
moreover, the trace of A is computable and its supernatural number is lower
semi-computable.
Dinner: The Globe (309 N. Henry St.) around 5:30PM
- 11/12/2024
Midwest Computability Seminar, University of Chicago,
John Crerar Library Building 390
(live streamed on Zoom, Meeting ID: 997 5433 2165, Passcode: midwest)
Brown bag lunch: in John Crerar Library Building 390 at noon
Speakers:
- 1PM, Jake Fiedler, UW
Title: Universal sets for projections
(video and slides)
Abstract: Marstrand's projection theorem is one of the most prominent results
in geometric measure theory. Essentially, it states that given any Borel set,
its orthogonal projections in almost every direction have the maximum possible
size. In this talk, we consider variants of Marstrand's projection theorem
that hold for classes of sets instead of individual sets and sets of directions
instead of individual directions. In particular, we discuss how assuming the
sets in a class have a greater degree of "regularity", or similarity across
scales, leads to improved bounds on the size of these sets of directions (which
we call universal sets). We use Kolmogorov complexity and other tools from the
study of algorithmic randomness throughout, connecting pointwise statements to
this classical problem in geometric measure theory through the point-to-set
principle of Lutz and Lutz. This talk is based on joint work with Don Stull.
- 1:45PM,
Gabriela Laboska, University of Chicago, Illinois
Title: Some computability-theoretic aspects of
partition regularity over algebraic structures
(video and slides)
Abstract: An inhomogeneous system of linear equations over a ring R is
partition regular if for any finite coloring of R, the system has a
monochromatic solution. In 1933, Rado showed that an inhomogeneous system is
partition regular over Z if and only if it has a constant solution.
Following a similar approach, Byszewski and Krawczyk showed that the result
holds over any integral domain. In 2020, Leader and Russell generalized this
over any commutative ring R, with a more direct proof than what was previously
used. We analyze some of these combinatorial results from a
computability-theoretic point of view, starting with a theorem by Straus used
directly or as a motivation to many of the previous results on the subject.
- 3:15PM, Ang
Li, UW
Title: Countable ordered groups and Weihrauch
reducibility
(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 shall study the uniform computational power of outputting some of
α, ε, and the order-preserving function.
- 4PM, Mariya
Soskova, UW
Title: Enumeration Weihrauch reducibility
(video and slides)
Abstract: Enumeration Weihrauch (eW) reducibility is a variant of Weihrauch
reducibility 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. We then turn
towards examining the structural properties of the eW degrees in search for a
first-order difference with the Weihrauch degrees.
This is joint work with Alice Vidrine.
Dinner: Giordano's (5311 S. Blackstone Ave.) at 5:30PM
- 11/18/24
(department colloquium), 4PM in
room B239 Van Vleck,
Will Johnson, Fudan University, Shanghai, China
Title: Model theory, VC classes, and Henselian
rings
(slides)
Abstract: Model theory is a subject which analyzes algebraic structures likei
groups and rings using tools from mathematical logic, such as definability and
elementary equivalence. A number of important mathematical structures, such as
the fields of real numbers and p-adic numbers, satisfy a special
model-theoretic property called "NIP" (or "dependence"). NIP is closely related
to the notion of "VC classes" in statistical learning theory — a structure M
is NIP if and only if every definable family of sets in M is a VC class.
In the past 20 years, NIP structures have become a central area of research in
model theory. It is natural to ask which fields and rings are NIP. While these
questions remain open, a conjectural classification of NIP fields has now
emerged: almost all NIP fields are expected to arise from Henselian valuation
rings. The classification is already known in the "finite-dimensional" case.
For rings, the situation is murkier, though we now have a classification of
the "one-dimensional" NIP integral domains. Moreover, a growing amount of
evidence suggests that NIP integral domains are always Henselian local rings.
In this talk, I will sketch how VC classes arise independently in statistics
and model theory, and give a high-level overview of what we know and what we
expect to hold for NIP fields and NIP commutative rings.
Interview Dinner: Eno Vino (1 N. Webster St.) at 6PM
- 11/26/2024 4PM,
Karthik Ravishankar, UW
Title: Characterizing Ahmad pairs in the local
structure (specialty exam)
(video)
Abstract: A pair (A,B) of Σ2-sets forms an Ahmad pair if every
set strictly below A is also below B. We give a characterization for when a
set can be the left half of an Ahmad pair. We also introduce a
hierarchy of Ahmad n-pairs in the local structure and characterize them using
different notions of join irreducibility. The eventual goal is to come up with
a property separating the two halves of an Ahmad pair. This is joint work with
Joe Miller and Mariya Soskova.
- 12/3/2024 4PM,
Peter Cholak,
University of Notre Dame, Indiana
Title: Coding in the universal n-clique free graph
Hn+1
Abstract: Color a finite graph G in Hn+1 with finitely many colors.
There is another copy Hn+1 inside our original copy of
Hn+1 where G takes on some minimal number of colors (the number is
determined by G and n). Call this the minimal heterogeneous copy. The question
we will address in this talk is how difficult it is to compute this copy.
Mostly, we will provide lower bounds, but we will include one upper bound and
an appealing question. These results depend on understanding the structure of
copies of Hn+1.
Dinner: The Cooper's Tavern (20 W. Mifflin St.) around 5:30PM
- 12/10/2024 4PM,
Antonio Nakid
Cordero, UW
Title: Computability of subshifts
(specialty exam)
(video, missing first couple
of minutes)
Abstract: Subshifts are sets of infinite words that describe symbolic
dynamical systems on discrete spaces. Early interest in their computational
properties, driven by their connection to tilings of the plane, stalled due to
a sharp contrast: While one-dimensional subshifts defined by finite information
can be well-understood using linear algebra and finite automata, properties of
higher-dimensional subshifts are notoriously undecidable. Recently, the use of
computability-theoretic tools has made multidimensional subshifts more
accessible, leading to significant breakthroughs. In this talk, I’ll discuss
how these ideas are forging connections between symbolic dynamics and
combinatorial group theory and share updates from an ongoing project aimed
at clarifying this connection.
This is joint work with Isabella Scott.