- 9/13/2022 4PM,
Jim
Freitag, University of Illinois at Chicago
Title: What is forking degree and why should you
care?
(video
and slides)
Abstract: In this talk we will introduce a new invariant of types in stable
theories which has applications to functional transcendence and the geometry
of compact complex manifolds. The talk won't assume that you know any stability
theory (or really even any model theory at all). In this talk, we'll focus on
applications around transcendence results and talk about connections with
point-counting problems and o-minimality. If time permits, we'll talk about
how the new invariant has played a role in the resolution of an old open
problem in algebraic differential equations and new proofs of the
irreducibility of equations from the Painlevé family.
Dinner: Great Dane Pub (123 E. Doty St.) around 6PM
- 9/20/2022 4PM,
Sam
Braunfeld, Charles University, Prague, Czech Republic
Title: A tour of monadically tame theories
(video
and slides)
Abstract: For a property P, say a theory T is monadically P if every unary
expansion of T has P. We will survey various characterizations of the monadic
variants of model-theoretic dividing lines, and their applications to the
combinatorics of finite and countable structures.
- 9/27/2022 4PM,
Manlio Valenti,
UW
Title: Some results on the structure of Weihrauch
degrees
(video
and slides)
Abstract: In this talk, we will explore some algebraic properties of the
Weihrauch degrees. Despite the recent efforts, a large number of questions
regarding the structure of Weihrauch degrees are still unexplored. We will
start with a brief overview of some known results, and then present some
recent findings on the existence of chains/antichains in the Weihrauch degrees.
We will also show how, despite the close interplay between Medvedev and
Weihrauch reducibility, the two lattices have a very different structure.
- 10/4/2022 4PM,
Steffen Lempp,
UW
Title: Toward deciding the ∀∃-theory of the
Σ02-enumeration
degrees
(video
and slides)
Abstract: I will report on joint work with Goh, Ng and Soskova on particular
extensions of embeddings of finite partial orders into the
Σ
02-enumeration
degrees: Let P be a finite antichain, and let Q
i (i ≤ n) each
extend P by one point. We will present a complete decision procedure on when
an embedding of P into the
Σ
02-enumeration
degrees can be extended to an embedding of Q
i for some
i ≤ n.
This constitutes progress toward the general case of arbitrary finite partial
orders Qi (i ≤ n) extending an arbitrary finite partial order P,
a decision procedure for which
would also give a decision procedure for the ∀∃-theory of the
Σ02-enumeration
degrees.
- 10/11/2022 4PM,
Dan
Turetsky, Victoria University of Wellington, New Zealand
Title: Wadge degrees, games, and the separation and
reduction properties
(video
and slides)
Abstract: In this talk, I will give an overview of the picture of the Borel
Wadge degrees. Our system of descriptions allows us to describe their
Delta-classes, as well as specify which degrees have the separation or
reduction properties. Part of our analysis is based on playing games along our
descriptions, and so I will explain how these games are played and what they
can tell us.
- 10/18/2022 4PM,
Dana
Bartošová, University of Florida, Gainesville
Title: Transfer of Ramsey phenomena via
semi-retractions
(video
and slides)
Abstract: The classical finite Ramsey theorem states that for any natural
numbers m ≤ n and a number of colours k ≥ 2, there is a natural number
N such that whenever we colour m-tuples of {1,2,..., N} by k colours, there is
an n-element subset of {1,2,..., N} whose all m-element subsets received the
same colour. This theorem has generalizations in possibly every area of
mathematics. In this talk, we will focus on structural Ramsey theory, which in
place of finite sets speaks about finite structures in some first-order
language, such as finite graphs, finite Boolean algebras, or finite vector
spaces over finite fields. Lynn Scow isolated a model-theoretic notion of a
semi-retraction between a pair of structures. In our recent paper, we
identified the optimal conditions on the structures under which a
semi-retraction transfers the Ramsey properties from the class of
finitely generated substructure of one structure to the other. We found that,
surprisingly, the notion of semi-retraction is related to a more abstract notion
of pre-adjunction from category theory. This is a joint work with Lynn Scow.
Dinner: Himal
Chuli (318 State St.) around 5:30PM
- 10/25/2022 4PM,
Joe Miller, UW
Title: Generic Muchnik reducibility
(video
and slides)
Abstract: If A and B are countable structures, then A is Muchnik reducible to B
if every ω-copy of B computes an ω-copy of A. This can be
interpreted as saying that B is intrinsically at least as complicated as A.
Schweber suggested a natural extension of Muchnik reducibility to arbitrary
structures: if A and B are (possibly uncountable) structures, then A is
generically Muchnik reducible to B if in some (equivalently, any) forcing
extension that makes both A and B countable, A is Muchnik reducible to B.
I will survey most of what is known about the generic Muchnik degrees,
culminating in work with Andrews, Schweber, and Soskova. We have proved
the existence of a structure with degree strictly between Cantor space and
Baire space. It remains open whether an expansion of Cantor space can be
strictly in between, but we have proved that no closed expansion or unary
expansion can work. Similar results hold for the interval between Baire
space and the Borel complete degree (i.e., the degree that bounds all Borel
structures). The proofs mix descriptive set theory (including some use of
determinacy) with injury and forcing constructions native to computable
model theory.
- 11/1/2022
Midwest Computability Seminar, University of Chicago,
Ryerson 352 (masks recommended indoors!)
(live streamed on Zoom, Meeting ID: 997 5433 2165, Passcode: midwest)
Brown bag lunch: in Ryerson 352 at noon
Speakers:
- 1PM, Luca San Mauro,
Sapienza University of Roma, Italy
Title: Effectivizing the theory of Borel equivalence
relations
(video and slides)
Abstract: The study of the complexity of equivalence relations has been a major
thread of research in diverse areas of logic. In descriptive set theory, one
investigates Borel reductions of equivalence relations on Polish spaces.
In computability theory, one focuses on computable reductions of countable
equivalence relations. Despite the clear analogy between the two notions,
for a long time the study of Borel reducibility and the study of computable
reducibility were conducted
independently. Yet, a theory of computable reductions which blends ideas from
both computability theory and descriptive set theory is rapidly emerging.
In this talk, we will discuss differences and similarities between the Borel
and the computable settings as we provide computable, or computably enumerable,
analogs of fundamental concepts from the Borel theory. In particular, we
concentrate on natural effectivizations of two classic concepts: orbit
equivalence relations and the Friedman-Stanley jump. This is joint work
with Uri Andrews.
- 2:30PM, Don Stull,
Northwestern University, Evanston, Illinois
Title: Pinned distance sets using effective
dimension
(video and slides)
Abstract: Given a set E in the plane and a point x, the pinned distance set of
E with respect to x is the set of distances between x and the points in E.
Determining the Hausdorff dimension of pinned distance sets is a central open
problem in geometric measure theory. In this talk, I will discuss how we can
use effective methods to improve the bounds on the dimension of pinned
distance sets.
- 4PM, Manlio
Valenti, UW
Title: The first-order part of computational
problems
(video and slides)
Abstract: Given a partial order (P,≤), a natural strategy to prove that a
≤ b is to present an example of some c ≤ a such that c ≰ b.
In general, finding such a c can be very challenging.
In this talk, we will present a degree-theoretic operator on computational
problems called "first-order part". This operator was introduced by Dzhafarov,
Solomon, Yokoyama, and maps a multi-valued function f to the "strongest
computational problem that is Weihrauch-below f". Characterizing the
first-order part of a given problem can be challenging as well, but it proved
to be a very useful tool, especially when comparing principles that are
(relatively) high in the Weihrauch hierarchy. After a few examples, we will
discuss some results on the algebraic properties of the first-order part,
showing how they can simplify the characterization of the first-order part
in many practical situations.
Dinner: Daisy's
Po-Boy and Tavern (5215 S. Harper Ave.) at 5:30PM
- 11/15/2022 4PM,
Natasha Dobrinen, University of Notre Dame, Indiana
Title: Infinite-dimensional structural Ramsey
theory
(video
and slides)
Abstract: Infinite-dimensional Ramsey theory extends Ramsey’s Theorem for
colorings of finite sets of natural numbers to colorings of infinite sets,
i.e., points of the Baire space, [
N]
N. A subset X of
the Baire space is called Ramsey if given any infinite set N ⊆
N,
there is an infinite subset M ⊆ N such that the cube [M]
N
is either contained in X or disjoint from X. The Galvin–Prikry Theorem states
that Borel sets are Ramsey; Ellentuck’s Theorem extends this to sets with the
property of Baire in the Ellentuck topology.
The question of developing infinite-dimensional Ramsey theory for
Fraïssé structures was raised in the 2005 paper of
Kechris–Pestov–Todorcevic. We addressed this question for the Rado graph in
2019, proving Galvin–Prikry analogues. Recently we proved Galvin–Prikry and
some Ellentuck analogues for the class of binary relational
structures satisfying an amalgamation property called SDAP+;
this work recovers exact big Ramsey degrees as a Nash-Williams corollary.
In ongoing work with Zucker, we prove infinite-dimensional Ramsey theorems
for binary relational structures with free amalgamation and finitely many
forbidden substructures; e.g., k-clique-free Henson graphs.
Dinner: The Globe
Restaurant (309 N. Henry St.) at 5:30PM
(Monday, Nov. 14th)
- 11/18/2022
(department colloquium), 4PM in
room B239 Van Vleck,
Jim
Freitag, University of Illinois-Chicago
Title: When any three solutions are independent
(video
and slides)
Abstract: In this talk, we'll talk about a surprising recent result about the
algebraic relations between solutions of a differential equation. The result
has applications to functional transcendence, diophantine geometry, and
compact complex manifolds.
Lunch: Steenbock's on
Orchard (330 N. Orchard St.) leaving from 2nd floor of Van Vleck at noon
Dinner: Cadre
(2540 University Ave.) at 6PM
- 11/29/2022 4PM,
Uri Andrews, UW
Title: Equivalence relations on ω under
computable reductions: Low levels of the arithmetical hierarchy
(video
and slides)
Abstract: We study equivalence relations on ω modulo computable
reductions. That is, we say that E ≤ R if there is a total computable f so
that xEy iff f(x)Rf(y). This is an old notion studied by Ershov and Lachlan
in the 1970's, but has recently been revived. It has received a lot of
attention lately with focus towards structural questions, and the topic has
received new motivation coming from analogies with invariant descriptive set
theory. I'll give a survey of what is known about this structure on the lowest
levels of the arithmetical hierarchy. I'll try to point to open questions that
are likely quite tractable and some (hopefully) deeper research directions.
- 12/6/2022 4PM,
Don Stull,
Northwestern University, Evanston, Illinois
Title: Optimal oracles for point-to-set
principles
(video
and slides)
Abstract: The point-to-set principle of J. Lutz and N. Lutz characterizes the
Hausdorff dimension of a set by the effective dimension of its points.
Recent work has used this bridge to prove results in geometric measure theory
using algorithmic techniques. One of the fundamental results of geometric
measure theory is Marstrand's projection theorem. This theorem gives tight
bounds on the size of the orthogonal projection of a set onto a line through
the origin. Until recently, Marstrand's theorem was only known to hold for
analytic sets. In this talk, we will discuss the notion of optimal oracles,
which give the weakest known sufficient conditions for Marstrand's theorem
to hold.
Dinner: TBA around 6PM
- 12/13/2022 4PM,
Andrej Bauer, University of
Ljubljana, Slovenia
Title: Extended Weihrauch degrees
(video
and related paper)
Abstract: Say that a predicate φ ranging over A is instance reducible to a
predicate ψ ranging over B when ∀ x ∈ A ∃ y ∈ B
(ψ(y) ⇒ φ(x)). This notion is ubiquitous in constructive
mathematics, and is generally the usual way of showing that ∀ y ∈ B
ψ(y) implies ∀ x ∈ A φ(x). Such predicates form a complete
lattice with respect to instance reducibility, even a frame and therefore a
Heyting algebra. Its structure is related to Smyth’s upper powerdomain.
When instance reducibility is interpreted in the Kleene-Vesley realizability
topos, it yields a proper generalization of the Weihrauch degrees, which I call
the extended Weihrauch degrees. Apart from having a better order-theoretic
structure than the Weihrauch degrees, the extended degrees offer a new and
interesting notion of reduction that allows one to mix and combine uniform
and non-uniform reducibility.