- Amalgamation Constructions and Recursive Model Theory

Thesis - 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. - 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. - The Degrees of Categorical Theories with Recursive Models

Proceedings of the AMS, 141 (2013), 2501-2514

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. - The Index Set of Uncountably Categorical Theories (with Tamvana Makuluni)

Israel Journal of Mathematics, 196 (2013), 491--498

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. - Recursive spectra of strongly minimal theories satisfying the Zilber
trichotomy (with Alice Medvedev)

Transactions of The AMS, 366 (2014), 2393--2417,

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. - Decidable Models of $\omega$-stable Theories

Journal of Symbolic Logic, 79 (2014), 186--192

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. - Spectra of Theories and Structures (with Joseph S. Miller)

Proceeding of the AMS, 143 (2015), 1283--1298

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. - Spectra of Atomic Theories (with Julia F. Knight)

Journal of Symbolic Logic, 78 (2013), 1189--1198

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. - Universal Computably Enumerable Equivalence Relations(with Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro, and Andrea Sorbi)

Journal of Symbolic Logic, 79 (2014), 60-88

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. - The Degrees of Bi-hyperhyperimmune Sets (with Peter Gerdes and Joseph S. Miller)

Annals of Pure and Applied Logic, 165 (2014), no. 3, 803--811

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. - On the Structure of the Degrees of Relative Provability (with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller)

Israel Journal of Mathematics, 207 (2015), 449-478

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. - Computing a Ryll-Nardzewski Function (with Asher Kach)

Algebra and Logic, 53 (2014), no. 2, 176--183

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. - Separable Models of Randomizations (with H. Jerome Keisler)

To appear in Journal of Symbolic Logic

Abstract: Every complete first order theory has a corresponding complete theory in continuous logic, called the randomization theory. It has two sorts, a sort for random elements of models of the first order theory, and a sort for events. In this paper we establish connections between properties of countable models of a first order theory and corresponding properties of separable models of the randomization theory. We show that the randomization theory has a prime model if and only if the first order theory has a prime model. And the randomization theory has the same number of separable homogeneous models as the first order theory has countable homogeneous models. We also show that when $T$ has at most countably many countable models, 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$. This yields an analogue for randomizations of the results of Baldwin and Lachlan on countable models of $\omega_1$-categorical first order theories. - Spectra of Recursive Models of Disintegrated Strongly Minimal Theories

Lobachevskii Journal of Mathematics, 2014, Volume 35, Issue 4, 287-291

Abstract: This paper gives an overview of results about the spectra of computable (or recursive) models of strongly minimal disintegrated theories. Spectra of strongly minimal disintegrated theories in finite languages and in languages consisting of binary relation symbols will be described. - Definable Closure in Randomizations (with Isaac Goldbring and H. Jerome Keisler)

Annals of Pure and Applied Logic, Volume 166, Issue 3, 2015, 325-341

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$. - A Local Characterization of VC-minimality (with Vincent Guingona)

To appear in Proceedings of the American Mathematical Society

Abstract: We show VC-minimality is $\Pi^0_4$-complete. In particular, we give a local characterization of VC-minimality. We also show dp-smallness is $\Pi^1_1$-complete. - The Complements of Lower Cones of Degrees and the Degree Spectra of Structures (with Mingzhong Cai, Iskander Sh. Kalimullin, Steffen Lempp, Joseph S. Miller, and Antonio Montalbán)

To appear in Journal of Symbolic Logic.

Abstract: We study Turing degrees $a$ for which there is a countable structure $\mathcal{A}$ whose degree spectrum is the collection $\{x:x\not\le a\}$. In particular, for degrees $a$ from the interval $[0',0'']$, such a structure exists if $a'=0''$, and there are no such structures if $a''>0'''$. - Asymptotic density, computable traceability and 1-randomness (with Mingzhong Cai, David Diamondstone, Carl Jockusch and Steffen Lempp)

submitted for publication

Abstract: Let $r$ be a real number in the unit interval $[0,1]$. A set $A \subseteq \omega$ is said to be*coarsely computable at density $r$*if there is a computable function $f$ such that $\{n \mid f(n) = A(n)\}$ has lower density at least $r$. Our main results are that $A$ is coarsely computable at density $1/2$ if $A$ is either computably traceable or truth-table reducible to a $1$-random set. In the other direction, we show that if a degree $\mathbf{a}$ is either hyperimmune or PA, then there is an $\mathbf{a}$-computable set which is not coarsely computable at any positive density. - Comparing Classes of Finite Sums (with Dmitriy Dushenin, Cameron Hill, Julia F. Knight, and Alexander Melnikov)

submitted for publication

Abstract: The notion of*Turing computable embedding*provides a computable analog of Borel embedding, and a way to effectively compare classes of countable structures, reducing the classification problem for one class to that for the other. Most of the known results on non-existence of Turing computable embeddings reflect differences in the complexity of the sentences needed to distinguish among non-isomorphic members of the two classes. Here we consider sum structures. We show that the $n$-fold sums of certain classes lie strictly below the $(n+1)$-fold sums. The differences reflect model theoretic considerations related to Morley degree, not differences in the complexity of the sentences. We consider three different kinds of sum structures: cardinal sums, in which the components are named by predicates; equivalence sums, in which the components are equivalence classes under an equivalence relation; and direct products of some groups. - Spectra of Computable Models
of Strongly Minimal Disintegrated Theories
in Languages of Bounded Arity (with Steffen Lempp)

submitted for publication

Abstract: In this paper, we consider the spectra of computable (or recursive) models of strongly minimal disintegrated theories. We conjecture that for any $m$, there are only finitely many spectra of computable models of strongly minimal disintegrated $\mathcal{L}$-theories $T$ in computable (but possibly infinite) relational languages $\mathcal{L}$ of arity at most $m$. We verify this conjecture here for binary and ternary languages and present some further partial results toward proving the general conjecture. We also determine the exactly seven spectra possible for binary languages and show that for ternary languages, there are at least nine but no more than eighteen spectra. - VC-minimality: Examples and Observations (with Sarah Cotter Blanset, James Freitag, and Alice Medvedev)

submitted for publication

Abstract: VC-minimality is a recent notion in model theory which generalizes strong minimality, o-minimality, weak o-minimality and c-minimality, but is strong enough to imply various other properties of interest such as NIP and dp-minimality. In this paper, we answer several questions posed by Adler about the relationship of VC-minimality and older stability-theoretic notions in model theory. We also give a proof that Presberger arithmetic is not VC-minimal and an example which separates local VC-minimality from convex orderability, answering a question posed by Guingona. - Indepndence Relations 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 study various notions of independence in models of $T^R$. - Theory Spectra and Classes of Theories (with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller)

submitted for publication

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 $\omega$-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. - Strongly Minimal Theories with Recursive Models (with Julia F. Knight)

submitted for publication

Abstract: We give effectiveness conditions on a strongly minimal theory $T$ guaranteeing that all models have computable copies. In particular, we show that if $T$ is strongly minimal and for $n\geq 1$, $T\cap\exists_{n+2}$ is $\Delta^0_n$, uniformly in $n$, then every model has a computable copy. Relativizing, we answer a long-standing question in computable model theory, showing that if a strongly minimal theory has a computable model, then every model is arithmetical; in fact, every model has a $\Delta^0_4$ copy. - The Complexity of Index Sets
of Classes of Computably Enumerable Equivalence Relations (with Andrea Sorbi)

submitted for publication

Abstract: Let $\le_{c}$ be computable reducibility on ceers. We show that for every computably enumerable equivalence relation (or ceer) $R$ with infinitely many equivalence classes, the index sets $\{i: R_{i}\le_{c} R\}$ (with $R$ non-universal), $\{i: R_{i}\ge_{c} R\}$, and $\{i: R_{i}\equiv_{c} R\}$ are $\Sigma^{0}_{3}$ complete, whereas in case $R$ has only finitely many equivalence classes, we have that $\{i: R_{i}\le_{c} R\}$ is $\Pi^{0}_{2}$ complete, and $\{i: R_{i}\ge_{c} R\}$ (with $R$ having at least two distinct equivalence classes) is $\Sigma^{0}_{2}$ complete. Next, solving an open problem from [ALMNSS], we prove that the index set of the effectively inseparable ceers is $\Pi^{0}_{4}$ complete. Finally, we prove that the $1$-reducibility pre-ordering on c.e.~sets is a $\Sigma^{0}_{3}$ complete pre-ordering relation, a fact that is used to show that the pre-ordering relation $\le_{c}$ on ceers is a $\Sigma^{0}_{3}$ complete pre-ordering relation. - Limit computability and ultrafilters on $\omega$ (with Mingzhong Cai, David Diamondstone, and Noah Schweber)

submitted for publication

Abstract: We study a class of operators on Turing degrees arising naturally from ultrafilters. Suppose $\mathcal{U}$ is a nonprincipal ultrafilter on $\omega$. We can then view a sequence of sets $A=(A_i)_{i\in\omega}$ as an ``approximation" of a set $B$ produced by taking the limits of the $A_i$ via $\mathcal{U}$: we set $\lim_\mathcal{U}(A)=\{x: \{i: x\in A_i\}\in\mathcal{U}\}.$ This can be extended to the Turing degrees, by defining $\delta_\mathcal{U}({\bf a})=\{\lim_\mathcal{U}(A): A=(A_i)_{i\in\omega}\in {\bf a}\}$. The $\delta_\mathcal{U}$ --- which we call ``ultrafilter jumps" --- resemble classical limit computability in certain ways. In particular, $\delta_\mathcal{U}({\bf a})$ is always a Turing ideal containing $\Delta_2^0({\bf a})$. However, they are also closely tied to Scott sets: $\delta_\mathcal{U}({\bf a})$ is always a Scott set containing ${\bf a'}$.

Our main result is that the converse also holds: if $\mathcal{S}$ is a countable Scott set containing ${\bf a'}$, then there is some ultrafilter $\mathcal{U}$ with $\delta_\mathcal{U}({\bf a})=\mathcal{S}$. We then turn to the problem of controlling the action of an ultrafilter jump $\delta_\mathcal{U}$ on two degrees simultaneously, and for example show that there are nontrivial degrees which are is ``low" for some ultrafilter jump. Finally, we study the structure on the set of ultrafilters arising from the construction $\mathcal{U}\mapsto\delta_\mathcal{U}$; in particular, we introduce a natural preordering on this set and show that it is connected with the classical Rudin-Keisler ordering of ultrafilters. We end by presenting two directions for further research.

- 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. - 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. - 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.