# Papers

## Publications and Preprints

1. Amalgamation Constructions and Recursive Model Theory
Thesis

2. A New Spectrum of Recursive Models Using An Amalgamation Construction
J. Symbolic Logic, 76 (2011), 883-896

Abstract: We employ an infinite-signature Hrushovski amalgamation construction to yield two results in recursive model theory. The first result, that there exists a strongy minimaltheory whose only recursively presentable models are the prime and saturated models, add a new spectrum to the list of known possible spectra. The second result,that there exists a strongly minimal theory in a finite language whose only recursively presentable model is saturated, gives the second non-trivial example of a spectrum produced in a finite language.

3. New Spectra of Strongly Minimal Theories in Finite Languages
Annals of Pure and Applied Logic, 162 (2011), 367-372

Abstract: We describe strongly minimal theories $T_n$ with finite languages such that in the chain of countable models of $T_n$, only the first n models have recursive presentations. Also, we describe a strongly minimal theory with a finite language such that every non-saturated model has a recursive presentation.

4. The Degrees of Categorical Theories with Recursive Models
To appear in Proceedings of The AMS

Abstract: We show that even for categorical theories, recursiveness of the models guarantees no information regarding the complexity of the theory. In particular, we show that every tt-degree reducible to $0^{(\omega)}$ contains both $\aleph_1$-categorical and $\aleph_0$-categorical theories in finite languages all of whose countable models have recursive presentations.

5. The Index Set of Uncountably Categorical Theories (with Tamvana Makuluni)
To appear in Israel Journal of Mathematics

Abstract: We classify the complexity of the index set of uncountably categorical theories. We show that this index set surprisingly falls at the intermediate stage of being complete for intersections of $\Pi_2$ sets with $\Sigma_2$ sets.

6. Recursive spectra of strongly minimal theories satisfying the Zilber trichotomy (with Alice Medvedev)
To appear in Transactions of The AMS

Abstract: We conjecture that for a strongly minimal theory $T$ in a finite signature satisfying the Zilber Trichotomy, there are only three possibilities for the recursive spectrum of $T$: all countable models of $T$ are recursively presentable; none of them are recursively presentable; or only the zero-dimensional model of $T$ is recursively presentable. We prove this conjecture for disintegrated (formerly, trivial) theories and for modular groups. The conjecture also holds via known results for fields. The conjecture remains open for finite covers of groups and fields.

7. Decidable Models of ω-stable Theories
To appear in Journal of Symbolic Logic

Abstract: We characterize $\omega$-stable theories all of whose countable models admit decidable presentations. In particular, we show that for countable $\omega$-stable $T$, every countable model of $T$ admits a decidable presentation if and only if all $n$-types in $T$ are recursive and $T$ has only countably many countable models.

8. Spectra of Theories and Structures (with Joseph S. Miller)
To appear in Proceeding of the AMS

Abstract: We introduce the notion of a degree spectrum of a theory to be the set of Turing degrees which compute some model of the theory. We generate examples showing that not all degree spectra of theories are degree spectra of structures and vice-versa. To this end, we give a new necessary condition on the degree spectrum of a structure, specifically showing that the set of PA degrees is not a degree spectrum of a structure but is a degree spectrum of a theory.

9. Spectra of Atomic Theories (with Julia F. Knight)
To appear in Journal of Symbolic Logic

Abstract: For a countable structure $A$, the spectrum is the set of Turing degrees of isomorphic copies of $A$. For a complete elementary first order theory $T$, the spectrum is the set of Turing degrees of models of $T$. We answer a question from [Andrews and Miller], showing that there is an atomic theory $T$ whose spectrum does not match the spectrum of any structure.

10. Randomizations of Theories With Countably Many Countable Models (with H. Jerome Keisler)
submitted for publication

Abstract: The randomization of a complete first order theory $T$ is the complete continuous theory $T^R$ with two sorts, a sort for random elements of models of $T$, and a sort for events in an underlying probability space. We show what the separable models of $T^R$ look like when $T$ has at most countably many countable models. In that case, each separable model of $T^R$ is uniquely characterized by a probability density function on the set of isomorphism types of countable models of $T$.

11. Universal Computably Enumerable Equivalence Relations(with Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro, and Andrea Sorbi)
submitted for publication

Abstract: We study computably enumerable equivalence relations (ceers) under the reducibility $R\leq S$ if there exists a computable function $f$ such that, for every $x,y$, $xRy$ if and only if $f(x)Sf(y)$. We show that the degrees of ceers under the relation generated by $\leq$ is a bounded poset that is neither a lowersemilattice, nor an upper semilattice, and its first order theory is undecidable. We then study the universal ceers. We show: 1) the uniformly effectively inseparable ceers are universal (in fact they coincide with the uniformly finitely precomplete ceers, and with the uniformly universal ceers, already known inthe literature), but there are effectively inseparable ceers that are not universal; 2) a ceer $R$ is universal if and only if $R'\leq R$, where $R'$ denotes the halting jump operatorintroduced by Gao and Gerdes (answering an open question of Gao and Gerdes); 3) the index set of universal ceers is $\Sigma^0_3$-complete (answering an open question of Gao and Gerdes), and the index set of uniformly universal ceers is $\Sigma^0_3$-complete.

12. The Degrees of Bi-hyperhyperimmune Sets (with Peter Gerdes and Joseph S. Miller)
submitted for publication

Abstract: We study the degrees of bi-hyperhyperimmune (bi-hhi) sets. Our main result characterizes these degrees as those that compute a function that is not dominated by any $\Delta_2$ function, and equivalently, those that compute a weak 2-generic. These characterizations imply that the collection of bi-hhi Turing degrees is closed upwards.

13. Computing a Ryll-Nardzewski Function (with Asher Kach)
submitted for publication

Abstract: We study, for a countably categorical theory T, the complexy of computing and the complexity of dominating the function specifying the number of different n-types consistent with T.

14. Definable Closure in Randomizations (with Isaac Goldbring and H. Jerome Keisler)
submitted for publication

Abstract: The randomization of a complete first order theory $T$ is the complete continuous theory $T^R$ with two sorts, a sort for random elements of models of $T$, and a sort for events in an underlying probability space. We give necessary and sufficient conditions for an element to be definable over a set of parameters in a model of $T^R$.

## Papers in preparation

1. On One-point Extensions in the $\Sigma_2$ Enumeration Degrees (with Steffen Lempp, Keng Meng Ng, and Andrea Sorbi)

Abstract: Working toward showing the decidability of the $\forall\exists$ theory ofthe $\Sigma_2$ enumeration degrees, we provide a necessary and sufficient criterion for a disjunction of one-point extensions of embeddings of arbitrary finite antichains into the $\Sigma_2$ enumeration degrees to be possible.
In a nutshell, the criterion shows that a lemma in an Ahmad/Lachlan paper provides the only possible kind of extension, and that all other extensions can be blocked.

2. Hrushovski Fusions and Computability (with Steffen Lempp)

Abstract: We examine the computable content of the Hrushovski fusion construction. We show that two recursive strongly minimal theories with DMP have a recursive fusion, even if each theory does not have recursive DMP. We also show that this analysis does not carry through on the level of structures. In particular, there are two recursive strongly minimal structures $M$ and $N$ so that no fusion of $\text{Th}(M)$ and $\text{Th}(N)$ has a recursive model.

3. VC-minimality: Examples and Observations (with Sarah Cotter, James Freitag, and Alice Medvedev)

Abstract: We show that $(\mathbb{Z},+,<)$ is an example of a dp-minimal theory which is not VC-minimal, giving the first natural example of such a theory. We also answer a question of Adler by showing that there are strictly stable VC-minimal theories, but stability implies $\omega$-stability for finitely VC-minimal theories. We also note that VC-minimality is not closed under reducts, even after allowing parameters. In particular, this separates VC-minimality from convex orderability.

4. Yet More New Spectra of Recursive Models

Abstract: We continue the program of examining which subsets of $\omega+1$ are recursive spectra of strongly minimal theories with special interest in those subsets of $\omega+1$ which are recursive spectra of strongly minimal theories in finite signatures. We show that for any $n$ in $\omega$, $\{0,...,n,\omega\}$ is a recursive spectrum of a strongly minimal theory with a finite signature.

5. The structure of the provability degrees (with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller)

Abstract: Cai introduced the provability degrees as the degree structure of the computable algorithms under the reduction $f \leq g$ if PA + totality of $g$ implies totality of $f$. Cai also introduced a jump operator. We answer several open questions of Cai's; introduce two other natural operators: the hop and the skip; and determine several facts about this degree structure. In particular, we show that every degree is the top of a diamond though there are cappable and non-cappable degrees, we characterize the 0-dominated degrees, show jump and hop inversion, and determine the structure and all inferences between the domination heierarchy and the high-low heierarchy.

6. Theory spectra and classes of theories (with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller)

Abstract: We analyse the spectra of theories which are $\omega$-stable, those whose spectra include almost every degree, and theories with uniformly arithmetical $n$-quantifier fragments. We answer a question from Andrews-Miller by showing that there are $\omega$-stable theories whose spectra are not structure spectra. We show that the spectrum created in Andrews-Knight is not the spectrum of an ω-stable theory, but is the minimal spectrum of any theory with uniformly arithmetical n-quantifier fragments. Additionally, we give examples of theory spectra which contain almost every degree, including ones which are known not to be structure spectra.