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,
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.
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.
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.
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.
4176 Campus Drive - William E. Kirwan Hall
College Park, MD 20742-4015
P: 301.405.5047 | F: 301.314.0827