Logic Archives for Fall 2020 to Spring 2021
Monadic stability and growth rates of omega-categorical structures
When: Tue, September 3, 2019 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Samuel Braunfeld (UMCP) -
From computability to counting siblings
When: Tue, September 10, 2019 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Chris Laskowski (UMCP) -
Borel reducibility and symmetric models
When: Tue, September 24, 2019 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Assaf Shani (Carnegie Mellon) -
Abstract: We develop a correspondence between Borel equivalence relations induced by closed subgroups of $S_\infty$ and symmetric models of set theory without choice, and apply it to prove a conjecture of Hjorth-Kechris-Louveau (1998).
For example, we show that the equivalence relation $\cong^\ast_{\omega+1,0}$ is strictly below $\cong^\ast_{\omega+1,
Computing VC-Density in NIP-Theories
When: Tue, October 1, 2019 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Vince Guingona (Towson University ) -
Abstract: I discuss the question of computing Vapnik-Chervonenkis density (VC-density) in NIP theories. I survey a few older results, including results for weakly o-minimal theories and strongly minimal theories by Aschenbrenner, Dolich, Haskell, MacPherson, and Starchenko. Focusing on VC-minimal theories in particular, I briefly examine a new result by Basu and Patel for the case of algebraically closed valued fields. Finally, I discuss some of my results towards computing VC-density in VC-minimal theories in general. In particular, I show that the VC-codensity of formulas with two free variables in a VC-minimal theory is at most 2. Under certain conditions, we can extend this to all n. At the end, we discuss potential future directions of this work.
Model Completeness and Relative Decidability
When: Tue, October 8, 2019 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Russell Miller (CUNY- Queens College) -
Abstract: Model-completeness is a standard notion in model theory, and it is well-known that a theory $T$ is model complete if and only if $T$ has quantifier elimination down to existential formulas. From the quantifier elimination, one quickly sees that every computable model of a computably enumerable, model-complete theory $T$ must be decidable. We call a structure \emph{relatively decidable} if this holds more broadly: if for all its copies $\mathcal{A}$ with domain $\omega$, the elementary diagram of $\mathcal{A}$ is Turing-reducible to the atomic diagram of $\mathcal{A}$. In some cases, this reduction can be done uniformly by a single Turing functional for all copies of $\mathcal{A}$, or even for all models of a theory $T$.
We discuss connections between these notions. For a c.e.\ theory, model completeness is equivalent to uniform relative decidability of all countable models of the theory, but this fails if the condition of uniformity is excluded. On the other hand, for relatively decidable structures where the reduction is not uniform, it can be made uniform by expanding the language by finitely many constants to name certain specific elements. This is shown by a priority construction related to forcing. We had conjectured that a similar result might hold for theories T such that every model of T is relatively decidable, but in separate work, Matthew Harrison-Trainor has now shown relative decidability to be a $\Pi^1_1$-complete property of a theory, which is far more complicated than our conjectured equivalent property.
This is joint work with Jennifer Chubb and Reed Solomon.
Nonequational stable groups
When: Tue, November 26, 2019 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Rizos Sklinos (Stevens Institute of Technology) -
Abstract: Equationality resembles a notion of Notherianity in the abstract setting of model theory. It was introduced by Srour (1984) and further developed by Pillay-Srour. It is a notion strictly stronger than stability, but until recently only an artificial unpublished example (due to Hrushovski-Srour) existed witnessing the difference between the two notions. In 2006 Sela proved that the theory of nonabelian free groups is not equational but stable, making it the first natural example of a stable nonequational theory. His proof used the complicated machinery developed in a series of 10 papers for answering Tarski's question.
In this talk I will present an elementary transparent proof for the nonequationality of the free group. As a matter of fact this proof extends to any free product of groups (apart from Z_2*Z_2). This is joint work with Isabel Müller.
Stability theory for concrete categories
When: Wed, December 4, 2019 - 12:00pmWhere: Kirwan Hall 3206
Speaker: Sebastien Vasey (Harvard) - http://math.harvard.edu/~sebv/
Abstract: Ramsey's theorem says that for each natural number n, there exists a natural number N so that each graph with N vertices contains either a clique or an independent set of size n. A theorem of Erdős and Rado generalizes it to infinite cardinals. Ramsey himself showed that one can take n = N if n is the first infinite cardinal but in most other uncountable cases N must be much bigger than n. Stability theory is a branch of model theory studying certain definability conditions allowing us to take n = N for a large number of infinite cardinals. Historically, stability theory was first developed by Shelah for classes axiomatized by first-order formulas. In this talk, I will describe a generalization to a large class of concrete categories: abstract elementary classes. I will also talk about recent progresses on the field's main test question, the eventual categoricity conjecture, resolved by Morley and Shelah for first-order but still open for abstract elementary classes.
Organizational Meeting
When: Tue, January 28, 2020 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Organizational Meeting () -
A diversity of Kim's Lemmas
When: Tue, February 11, 2020 - 3:30pmWhere: Kirwan Hall 1311
Speaker: Alex Kruckman (Wesleyan University) -
Abstract: One of the most important steps in the development of simplicity theory by Kim and Pillay in the 1990s was a result now known as Kim's Lemma: In a simple theory, if a formula divides, then this dividing is witnessed by every Morley sequence in the appropriate type. More recently, variants on Kim's Lemma have been shown (by Chernikov, Kaplan, and Ramsey) to follow from, and in fact characterize, two generalizations of simplicity in different directions: the combinatorial dividing lines NTP2 and NSOP1. After surveying the Kim's Lemmas of the past, I will speculate about a new combinatorial dividing line, generalizing both NTP2 and NSOP1 and characterized by a new variant of Kim's Lemma. This is joint speculation with Nick Ramsey.