- 1/22/2019 4PM,
Chris Laskowski,
University of Maryland-College Park
Title: Mutually algebraic sets and structures -
their history and new characterizations
We begin by tracing the history that led to the discovery of mutually
algebraic structures. Recent work with Caroline Terry has led to new
characterizations of this notion in terms of disjoint arrays and uniform
bounds on the number of coordinatewise non-algebraic types over models.
In work with Sam Braunfeld, we describe the stark dividing lines arising
from `worst-case expansions' by mutually algebraic sets.
Dinner: Muramoto
(108 King St.) at 6:30PM
- 1/29/2019 4PM,
Sergey
Goncharov, Siberian Branch of the Russian Academy of Sciences and
Novosibirsk State University, Russia
Title: Some results and questions in computable
numberings
I will present some new results and open problems in the theory of computable
numberings, generalizing results by Goncharov-Sorbi on classical computable
numberings for the hierarchies of analytical and arithmetical sets, and
functional and the Ershov hierarchy.
I will discuss some open problems in the classical theory of
computable numberings.
Dinner: Maharani
Restaurant (380 W. Washington Ave.) at 6PM
- 2/5/2019 4PM,
Caroline Terry,
University of Chicago, Illinois
Title: A stable arithmetic regularity lemma in finite
abelian groups
The arithmetic regularity lemma for
Fnp (first proved by Green
in 2005) states that given A ⊆
Fnp, there exists H ≤
Fnp of bounded index such
that A is Fourier-uniform with respect to almost all cosets of H. In general,
the growth of the index of H is required to be of tower type depending on the
degree of uniformity, and must also allow for a small number of non-uniform
elements. Previously, in joint work with Wolf, we showed that under a natural
model-theoretic assumption, called stability, the bad bounds and non-uniform
elements are not necessary. In this talk, we present results extending this
work to stable subsets of arbitrary finite abelian groups.
This is joint work with Julia Wolf.
Lunch: leaving from 5th floor of Van Vleck Hall at 11:30am,
place TBA
- 2/12/2019 4PM,
Omer Mermelstein,
UW
Title: Closed ordinal Ramsey numbers
In this talk, we will discuss the closed ordinal variant of Ramsey theory.
We will restrict ourselves to questions pertaining to triangle-free graphs on
ordinals below ωω, explain how to reduce these graphs
to 'canonical' graphs, and present some precise calculations.
- 2/19/2019 4PM,
James Hanson,
UW
Title: Strongly minimal sets in continuous logic
The precise structural understanding of uncountably categorical theories given
by the Baldwin-Lachlan theorem is known to fail in continuous logic in the
context of inseparably categorical theories. The primary obstacle is the
absence of strongly minimal sets in some inseparably categorical theories.
We will develop the concept of strongly minimal sets in continuous logic and
discuss some common conditions under which they are present in an
ω-stable metric theory. Finally, we will examine the extent to which we
recover the Baldwin-Lachlan theorem in the presence of strongly minimal sets.
- 2/26/2019 4PM,
Jun Le Goh,
Cornell University
Title: A theorem of Halin and hyperarithmetic
analysis
In 1965, Halin showed that if a graph contains k many disjoint rays for every k,
then it contains infinitely many disjoint rays. We show that a natural
formalization of Halin's theorem (which we call IRT) is closely connected to
the notion of hyperarithmetic reduction, namely, IRT is a theorem of
hyperarithmetic analysis. We also introduce a
Σ11-axiom
of finite choice and show how it is related to IRT.
Dinner: Tavernakaya
(27 E. Main St.) at 6PM
- 3/5/2019 4PM,
Steffen Lempp,
UW
Title: Toward deciding the AE-theory of the
enumeration degrees
I will outline an approach, in joint work with Slaman and M. Soskova, toward
deciding the ∀∃-theory of the enumeration degrees. The procedure
is necessarily more difficult than for the Turing degrees since the
enumeration degrees are downward dense; however, by a result of Calhoun and
Slaman, even the
Π02-enumeration degrees
are not dense. Kent and Lewis have extended this to show that there is a
strong minimal cover in the
Π02-enumeration degrees,
and our work builds on extending that result.
- 3/12/2019 4PM,
Gabe Conant,
University of Notre Dame, Indiana
Title: Arithmetic regularity with forbidden bipartite
configurations
Szemerédi's regularity lemma is a fundamental result in graph theory,
which says that sufficiently large finite graphs can be partitioned into a
small number of pieces so that the edges between most pairs of pieces are
randomly distributed. In other words, the regularity lemma processes finite
graphs into ingredients that are either highly structured (namely, the
partition of the graph) or highly random (namely, the edges between regular
pairs). In 2005, Green introduced arithmetic regularity, which is a
group-theoretic analogue of Szemerédi's result. Green's work involves
decompositions of finite abelian groups into algebraically structured pieces,
which behave randomly with respect to some chosen subset of the group.
In this talk, I will consider subsets A of arbitrary groups G, such that the
bipartite graph determined by x · y in A omits some bipartite graph of
a fixed finite size. I will present strengthened versions arithmetic regularity
in this setting, which yield algebraic structure theorems for sets A as above.
This work combines tools from model theory, additive combinatorics, and the
structure of compact topological groups. Joint with A. Pillay and C. Terry.
Dinner: The Old
Fashioned Tavern (23 N. Pinckney St.)
at 6PM
- 3/26/2019 4PM,
Noah Schweber,
UW
Title: Topology, games, and reverse mathematics
"Reverse mathematics" is (roughly) the analysis of classical theorems of
mathematics in terms of their computability-theoretic content: Some theorems
are "computably true" in that all the constructions required in their proofs
can be done computably, while others have nontrivial computational strength.
This can be thought of as analogous to the study of the role of the Axiom of
Choice, but at a more fine-grained level.
In this talk, I'll present some results on the reverse mathematics of topology.
Any "reasonable" set X of reals has the Baire property, which is to say that
such an X is either meager (i.e., a countable union of nowhere dense sets) or
comeager on some open interval; it turns out that there is a game (the
Banach-Mazur game), the determinacy of which captures this dichotomy.
I'll show how this gives us a satisfying way of analyzing the complexity of
principles of the form "Every [complexity-level] set has the Baire property,"
and in particular demonstrates that such principles exhibit a strange
combination of strength and weakness, which seems new in reverse mathematics.
- 4/3/2019 4PM in room B115,
Johanna
Franklin, Hofstra University, Hempstead, New York
Title: Effective measures for algebraic
structures
R. Miller has introduced a method for defining an effective measure on the
spaces of the isomorphism types of computable structures such as field
extensions of the rationals and finitely branching trees. This allows us to
determine whether certain properties of computable structures are null or
conull for these classes. Furthermore, if a property is conull, we can often
effectivize our answer and say that every random structure has this property
for some notion of randomness. I will discuss the definitions of these
measures and the applications of these ideas to the property of computable
categoricity.
This work is joint with R. Miller.
Dinner: Himal Chuli Restaurant (318 State St.)
at 6PM
- 4/9/2019 4PM,
Tom Drucker, UW-Whitewater
Title: Von Platon zu von Plato: What have technical
results done for foundations?
Plato raised some objections to what mathematicians did 2400 years ago by way
of what he saw as the lack of relevance to understanding mathematics.
Current philosophers can ask the same question about the technical results of
the twentieth century. This talk will look at some of the results that provide
support for understanding how the foundations of mathematics work, especially
in light of Jan von Plato’s recent book on the twentieth century’s advances
in logic.
- 4/18/2019
Midwest Model Computability Seminar, University of Chicago
Lunch: in Ryerson 352 at noon
Speakers:
- 1PM, Wesley
Calvert, Southern Illinois University, Carbondale
Title: Probability, density, and structure
This talk will give account of some converging trends at the intersection of
logic and probability. Randomized computation, dense/generic/coarse
computability, theories of random graphs and structures, and theoretical
machine learning have subtle connections, and their points of contactpose
interesting problems for mathematical logic. In addition to an exposition on
several older results and their interactions, this talk will include some
recent results on categoricity in an environment of generic and coarse
computability.
- 2PM, Russell
Miller, Queens College, New York City
Title: Hilbert's Tenth Problem as an enumeration
operator
For a ring R, Hilbert's Tenth Problem is the set HTP(R) of polynomials f ∈
R[X0,X1,...] for which f = 0 has a solution in R. It has been known since the
work of Davis, Putnam, Robinson, and Matiyasevich in 1970 that HTP(Z) is as
hard as the Halting Problem, and indeed that every computably enumerable set
is diophantine in Z, i.e., definable in Z by an existential formula, and thus
decidable from HTP(Z). In contrast, the decidability of HTP(Q) is an open
question.
It is natural to view HTP as a pseudojump operator, mapping each set W of
prime numbers to the set HTP(Z[W-1]). (Every subring of Q is of this
form, for some W.) One might hope to relate it to the jump operator, which maps
W to its jump W'. In fact, though, HTP is an enumeration operator. We will
discuss ways in which this distinguishes it from the jump operator. There do
exist sets W (including the empty set) for which W' is diophantine in
HTP(Z[W-1]), and indeed they occur in every Turing degree; on the
other hand, under Lebesgue measure, they are quite rare. The weaker statement
that HTP(Z[W-1]) at least computes W' is known to be false in
certain cases, but remains open for most sets W. We will show that no single
oracle Turing machine can accomplish this reduction uniformly on a set of
rings of full Lebesgue measure.
- 4PM, Steffen
Lempp, UW
Title: Toward deciding the ∀∃-theory of
the enumeration degrees
I will outline an approach, in joint work with Slaman and M. Soskova, toward
deciding the ∀∃-theory of the enumeration degrees. The procedure
is necessarily more difficult than for the Turing degrees since the
enumeration degrees are downward dense; however, by a result of Calhoun and
Slaman, even the
Π02-enumeration degrees
are not dense. Kent and Lewis have extended this to show that there is a
strong minimal cover in the
Π02-enumeration degrees,
and our work builds on extending that result.
Dinner: Nella Pizza e Pasta
(1125 E. 55th St.) at 5:30PM
- 4/22/2019 4PM in room B239 (department
colloquium),
Justin Hsu,
UW computer science department
Title: From couplings to probabilistic relational
program logics
Many program properties are relational, comparing the behavior of a program
(or even two different programs) on two different inputs. While researchers
have developed various techniques for verifying such properties for standard,
deterministic programs, relational properties for probabilistic programs have
been more challenging. In this talk, I will survey recent developments
targeting a range of probabilistic relational properties, with motivations
from privacy, cryptography, machine learning. The key idea is to meld
relational program logics with an idea from probability theory, called
probabilistic couplings. The logics allow a highly compositional and
surprisingly general style of program analysis, supporting clean proofs for
a broad array of probabilistic relational properties.
- 4/23/2019
MidWest Model Theory Day, University of Illinois-Chicago
Lunch: in SEO 636 at noon
Speakers:
- 1PM, Nir
Avni, Northwestern University, Evanston, Illinois
Title: Rigidity and bi-interpretability with Z for
higher rank lattices
A lattice in a Lie group is a discrete subgroup with finite co-volume.
In many contexts, there is a dichotomy between lattices in Lie groups of rank
one and lattices in Lie groups of higher rank, where the two classes behave
in qualitatively different ways. I will talk about this dichotomy in the
context of model theory.
- 2:30PM, Rizos
Sklinos, Stevens Institute of Technology, Hoboken, New Jersey
Title: Fraïssé constructions in the free
group
In an influential paper Fraïssé obtained the ordered rationals as
a limit of finite linear orders through amalgamations. Furthermore, his
construction implied the (ultra)-homogeneity, the countability and universality
of the limit structure. Since then various adaptations of Fraïssé's
method had given very interesting examples in many mathematical disciplines.
The random graph in graph theory and Philip Hall's universally locally finite
group in group theory to name a few.
In joint work with Kharlampovich and Myasnikov, we look into the possibility
of applying Fraïssé constructions in classes of groups that played
a central role in answering Tarski's question on nonabelian free groups.
In particular, we modify Fraïssé's method to prove that nonabelian
limit groups form a ∀-Fraïssé class, and finitely generated
elementary free groups form an elementary-Fraïssé class.
- 4PM, Meng-Che
("Turbo") Ho, Purdue University, West Lafayette, Indiana
Title: Scott sentences of finitely-generated
groups
Scott showed that for every countable structure A, there is an
L
ω1,ω-sentence, called the Scott sentence,
whose countable models are the isomorphic copies of A. The quantifier
complexity of a Scott sentence can be thought of as a measure of the complexity
of the structure. Knight et al. have studied the Scott sentences of many
structures. In particular, Knight and Saraph showed that a finitely-generated
structure always has a Σ
3-Scott sentence. In this talk, we
will focus on finitely-generated groups. On the one hand, most "natural"
finitely-generated groups have a d-Σ
2-Scott sentence.
On the other hand, we give a characterization of finitely-generated structures
where the Σ
3-Scott sentence is optimal. We then give a
construction of a finitely-generated group where the Σ
3-Scott
sentence is optimal.
This is joint work with Matthew Harrison-Trainor.
Dinner: in SEO 300 at 6PM
- 4/30/2019 4PM,
Nick Ramsey,
University of California-Los Angeles
Title: Exact saturation in pseudo-elementary
classes
Suppose κ is your favorite singular cardinal and T is your favorite
complete theory. Now ask the question: Does T have a κ-saturated model
that is not κ+-saturated? Perhaps your favorite theory was
the theory of algebraically closed fields, in which case the answer is 'yes',
but maybe it was the theory of dense linear orders, in which case the answer
is 'no'. What's the difference? This turns out to be a question without a very
nice answer, but reformulated in the context of pseudo-elementary classes,
it connects to a number of interesting notions from classification theory.
We will describe some of these connections, bringing together techniques from
model theory, set theory, and (if you squint) a tiny bit of recursion theory.
This is joint work with Itay Kaplan and Saharon Shelah.
Dinner: Great Dane
Pub (123 E. Doty St.) at 6PM