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