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
    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
    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
    Proceedings of the AMS, 141 (2013), 2501-2514
    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)
    Israel Journal of Mathematics, 196 (2013), 491--498
    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)
    Transactions of The AMS, 366 (2014), 2393--2417,
    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 $\omega$-stable Theories
    Journal of Symbolic Logic, 79 (2014), 186--192
    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)
    Proceeding of the AMS, 143 (2015), 1283--1298
    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)
    Journal of Symbolic Logic, 78 (2013), 1189--1198
    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. 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
    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.

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

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

  13. Computing a Ryll-Nardzewski Function (with Asher Kach)
    Algebra and Logic, 53 (2014), no. 2, 176--183
    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. Separable Models of Randomizations (with H. Jerome Keisler)
    Journal of Symbolic Logic, 80 (2015) 1149-1181
    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.

  15. Spectra of Recursive Models of Disintegrated Strongly Minimal Theories
    Lobachevskii Journal of Mathematics, 2014, Volume 35, Issue 4, 287-291
    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.

  16. Definable Closure in Randomizations (with Isaac Goldbring and H. Jerome Keisler)
    Annals of Pure and Applied Logic, Volume 166, Issue 3, 2015, 325-341
    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$.

  17. A Local Characterization of VC-minimality (with Vincent Guingona)
    Proceedings of the American Mathematical Society, 144 (2016), 2241-2256
    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.

  18. 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 Montalban)
    Journal of Symbolic Logic, 81 (2016), 997–1006
    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'''$.

  19. Asymptotic density, computable traceability and 1-randomness (with Mingzhong Cai, David Diamondstone, Carl Jockusch and Steffen Lempp)
    Fundamenta Mathematicae, 234 (2016), 41–53
    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.

  20. Theory Spectra and Classes of Theories (with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller)
    Transactions of The AMS, 369 (2017), 6493-6510
    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.

  21. Comparing Classes of Finite Sums (with Dmitriy Dushenin, Cameron Hill, Julia F. Knight, and Alexander Melnikov)
    Algebra and Logic, Vol. 54, No. 6, January, 2016, 489--501
    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.

  22. Strongly Minimal Theories with Recursive Models (with Julia F. Knight)
    Journal of the European Mathematical Society, 20 (2018), 1561-1594
    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.

  23. The Complexity of Index Sets of Classes of Computably Enumerable Equivalence Relations (with Andrea Sorbi)
    Journal of Symbolic Logic, 81 (2016), 1375–1395
    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.

  24. Nondensity of Double Bubbles in the d.c.e. degrees (with Rutger Kuyper, Steffen Lempp, Mariya I. Soskova, and Mars M. Yamaleev)
    A chapter in the book Computability and Complexity, in the Lecture Notes in Computer Science series, 547--562
    In this paper, we show that the so-called "double bubbles" are not downward dense in the d.c.e. degrees. Here, a pair of d.c.e. degrees ${\bf d}_1 > {\bf d}_2 > {\bf 0}$ forms a double bubble if all d.c.e. degrees below ${\bf d}_1$ are comparable with ${\bf d}_2$.

  25. A Survey on Universal Computably Enumerable Equivalence Relations (with Serikzhan Badaev and Andrea Sorbi)
    A chapter in the book Computability and Complexity, in the Lecture Notes in Computer Science series, 418–451
    We review the literature on universal computably enumerable equivalence relations, i.e. the computably enumerable equivalence relations (ceers) which are $\Sigma^0_1$-complete with respect to computable reducibility on equivalence relations. Special attention will be given to the so-called uniformly effectively inseparable (u.e.i.) ceers, i.e. the nontrivial ceers yielding partitions of the natural numbers in which each pair of distinct equivalence classes is effectively inseparable (uniformly in their representatives). The u.e.i. ceers comprise infinitely many isomorphism types. The relation of provable equivalence in Peano Arithmetic plays an important role in the study and classification of the u.e.i. ceers.

  26. On Cototality and the Skip Operator in the Enumeration Degrees (with Hristo A. Ganchev, Rutger Kuyper, Steffen Lempp, Joseph S. Miller, Alexandra A. Soskova, and Mariya I. Soskova)
    Transactions of the American Mathematical Society, 372 (2019), no. 3, 1631-1670.
    A set $A\subseteq\omega$ is cototal if it is enumeration reducible to its complement, $\bar{A}$. The skip of $A$ is the uniform upper bound of the complements of all sets enumeration reducible to $A$. These are closely connected: $A$ has cototal degree if and only if it is enumeration reducible to its skip. We study cototality and related properties, using the skip operator as a tool in our investigation. We give many examples of classes of enumeration degrees that either guarantee or prohibit cototality. We also study the skip for its own sake, noting that it has many of the nice properties of the Turing jump, even though the skip of $A$ is not always above $A$ (i.e., not all degrees are cototal). In fact, there is a set that is its own double skip.

  27. Jumps of computably enumerable equivalence relations (with Andrea Sorbi)
    Annals of Pure and Applied Logic, 169 (2018), 243–259
    We study computably enumerable equivalence relations (or, ceers), under computable reducibility $\le$, and the halting jump operation on ceers. We show that every jump is uniform join-irreducible, and thus join-irreducible. Therefore, the uniform join of two incomparable ceers is not equivalent to any jump. On the other hand there exist ceers that are not equivalent to jumps, but are uniform join-irreducible: in fact above any non-universal ceer there is a ceer which is not equivalent to a jump, and is uniform join-irreducible. We also study transfinite iterations of the jump operation. If $a$ is an ordinal notation, and $E$ is a ceer, then let $E^{(a)}$ denote the ceer obtained by transfinitely iterating the jump on $E$ along the path of ordinal notations up to $a$. In contrast with what happens for the Turing jump and Turing reducibility, where if a set $X$ is an upper bound for the $A$-arithmetical sets then $X^{(2)}$ computes $A^{(\omega)}$, we show that there is a ceer $R$ such that $R\ge \text{Id}^{(n)}$, for every finite ordinal $n$, but, for all $k$, $R^{(k)} \ngeq \text{Id}^{(\omega)}$ (here $\text{Id}$ is the identity equivalence relation). We show that if $a,b$ are notations of the same ordinal less than $\omega^2$, then $E^{(a)}\equiv E^{(b)}$, but there are notations $a,b$ of $\omega^{2}$ such that $\text{Id}^{(a)}$ and $\text{Id}^{(b)}$ are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form $\text{Id}^{(a)}$ where $a$ is a notation for $\omega^2$.

  28. Indepndence in Randomizations (with Isaac Goldbring and H. Jerome Keisler)
    Journal of Mathematical Logic, Vol. 19, No. 01, (2019)
    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 atomless probability space. We study independence relations and related ternary relations on the randomization of $T$. We show that if $T$ has the exchange property and $\text{acl} = \text{dcl}$, then $T^R$ has a strict independence relation in the home sort, and hence is real rosy. In particular, if $T$ is o-minimal, then $T^R$ is real rosy.

  29. Hindman's theorem and idempotent types (with Isaac Goldbring)
    Semigroup Forum 2018, Volume 97, Issue 3, pp 471–477
    Motivated by a question of Di Nasso, we show that Hindman's Theorem is equivalent to the existence of idempotent types in countable complete extensions of Peano Arithmetic.

  30. Definable sets containing productsets in expansions of groups (with Gabriel Conant and Isaac Goldbring)
    Journal of Group Theory, Volume 22 (2019), 63-82.
    We consider the question of when sets definable in first-order expansions of groups contain the product of two infinite sets (we refer to this as the "productset property"). We show that the productset property holds for any definable subset $A$ of an expansion of a discrete amenable group such that $A$ has positive Banach density and the formula $x\cdot y\in A$ is stable. For arbitrary first-order expansions of groups, we consider a "$1$-sided" version of the productset property, which is characterized in various ways using coheir independence. For stable groups, the productset property is equivalent to this $1$-sided version, and behaves as notion of largeness for definable sets, which can be characterized by a natural weakening of model-theoretic genericity.

  31. Characterizing the continuous degrees (with Gregory Igusa, Joseph S. Miller, and Mariya I. Soskova)
    Israel Journal of Mathematics, to appear
    The continuous degrees measure the computability-theoretic content of elements of computable metric spaces. They properly extend the Turing degrees and naturally embed into the enumeration degrees. Although nontotal (i.e., non-Turing) continuous degrees exist, they are all very close to total: joining a continuous degree with a total degree that is not below it always results in a total degree. We call this property almost totality. We prove that the almost total degrees coincide with the continuous degrees. Since the total degrees are definable in the partial order of enumeration degrees (citation), we see that the continuous degrees are also definable. Applying earlier work on the continuous degrees (citation), this shows that the relation "PA above" on the total degrees is definable in the enumeration degrees. In order to prove that every almost total degree is continuous, we pass through another characterization of the continuous degrees that slightly simplifies one of Kihara and Pauly (citation). We prove that the enumeration degree of $A$ is continuous if and only if $A$ is codable, meaning that $A$ is enumeration above the complement of an infinite tree, every path of which enumerates $A$.

  32. Scattered Sentences Have Few Separable Randomizations (with Isaac Goldbring, Sherwood Hachtman, H. Jerome Keisler, and David Marker)
    Archive for Mathematical Logic, to appear.
    In the paper "Randomizations of Scattered Sentences", Keisler showed that if Martin’s axiom for $\aleph_1$ holds, then every scattered sentence has few separable randomizations, and asked whether the conclusion could be proved in ZFC alone. We show here that the answer is "yes". It follows that the absolute Vaught conjecture holds if and only if every $L_{\omega_1,\omega}$-sentence with few separable randomizations has countably many countable models.

  33. Joins and meets in the structure of ceers (with Andrea Sorbi)
    Computability, vol. 8, no. 3-4, 193-241, 2019, Issue "Oberwolfach Workshop on Computability Theory 2018"
    We study computably enumerable equivalence relations (abbreviated as ceers under computable reducibility, and we investigate the resulting degree structure $\mathbf{Ceers}$, which is a poset with a smallest and a greatest element. We point out a partition of the ceers into three classes: the finite ceers, the light ceers, and the dark ceers. These classes yield a partition of the degree structure as well, and in the language of posets the corresponding classes of degrees are first order definable within $\mathbf{Ceers}$. There is no least, no maximal, no greatest dark degree, but there are infinitely many minimal dark degrees. We study joins and meets in $\mathbf{Ceers}$, addressing the cases when two incomparable degrees of ceers $X,Y$ have or do not have a join or a meet according to where $X,Y$ are located in the classes of the aforementioned partition: in particular no pair of dark ceers has a join, and no pair in which at least one ceer is dark has a meet. We also exhibit examples of ceers $X,Y$ having as a join their uniform join $X \oplus Y$, but also examples with a join which is strictly less than $X \oplus Y$. We study join-irreducibility and meet-irreducibility: every dark ceer is both join-, and meet-irreducible. In particular we characterize the property of being meet-irreducible for a ceer $E$, by showing that it coincides with the property of $E$ being self-full, meaning that every reducibility from $E$ to itself is in fact surjective on its equivalence classes (this property properly extends darkness). We then study the quotient structure obtained by dividing the poset $\mathbf{Ceers}$ by the degrees of the finite ceers, and study joins and meets in this quotient structure: interestingly, contrary to what happens in the structure of ceers, here there are pairs of incomparable equivalence classes of dark ceers having a join, and every element different from the greatest one is meet-reducible. In fact in this quotient structure, every degree different from the greatest one has infinitely many strong minimal covers, whereas in $\mathbf{Ceers}$ every degree different from the greatest one has either infinitely many strong minimal covers, or the cone strictly above it has a least element: this latter property characterizes the self-full degrees. We look at automorphisms of $\mathbf{Ceers}$, and show that there are continuum many automorphisms fixing the dark ceers, and continuum many automorphisms fixing the light ceers. Finally, we compute the complexity of the index sets of the classes of ceers studied in the paper.

  34. On Isomorphism Classes of Computably Enumerable Equivalence Relations (with Serikzhan Badaev)
    Journal of Symbolic Logic, to appear.
    We examine how degrees of computably enumerable equivalence relations (ceers) under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of $\omega$ which reduces one to the other. As a method of focusing on non-trivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the degree. We show that the number of isomorphism types must be 1 or $\omega$, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of $[0,\omega]$. In fact, for any $n\in [0,\omega]$, there is a degree $d$ and weakly precomplete ceers $E_1,\ldots , E_n$ in $d$ so that any ceer $R$ in $d$ is isomorphic to $E_i\oplus D$ for some $i\leq n$ and $D$ a ceer with domain either finite or $\omega$ comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree $d$ splits into exactly $n$ classes.

    We conclude by answering some lingering open questions from the literature: Gao and Gerdes (citation) define the collection of essentially FC ceers to be those which are reducible to a ceer all of whose classes are finite. They show that the index set of essentially FC ceers is $\Pi^0_3$-hard, though the definition is $\Sigma^0_4$. We close the gap by showing that the index set is $\Sigma^0_4$-complete. They also use index sets to show that there is a ceer all of whose classes are computable, but which is not essentially FC, and they ask for an explicit construction, which we provide.

    Andrews and Sorbi (citation) examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $(E_i)$ is a uniform c.e. sequence of non-universal ceers, then $\{\oplus_{i\leq j} E_i\mid j\in \omega\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from (citation).

    Lastly, we show that there exists an infinite antichain of weakly precomplete ceers.


  35. Effective inseparability, lattices, and pre-ordering relations (with Andrea Sorbi)
    Reviews of Symbolic Logic, to appear.
    We study effectively inseparable (abbreviated as e.i.) pre-lattices (i.e. structures of the form $L=\langle \omega, \wedge, \lor, 0, 1, \leq_L\rangle$ where $\omega$ denotes the set of natural numbers and the following four conditions hold: (1) $\wedge, \lor$ are binary computable operations; (2) $\leq_L$ is a computably enumerable pre-ordering relation, with $0 \leq_{L} x \leq_{L} 1$ for every $x$; (3) the equivalence relation $\equiv_L$ originated by $\leq_L$ is a congruence on $L$ such that the corresponding quotient structure is a non-trivial bounded lattice; (4) the $\equiv_L$-equivalence classes of $0$ and $1$ form an effectively inseparable pair of sets). Solving a problem in (citation) we show that if $L$ is an e.i. pre-lattice then $\le_{L}$ is universal with respect to all c.e. pre-ordering relations, i.e. for every c.e. pre-ordering relation $R$ there exists a computable function $f$ reducing $R$ to $\leq_L$, i.e. $x R y$ if and only if $f(x) \le_{L} f(y)$, for all $x,y$. In fact $\leq_L$ is locally universal, i.e. for every pair $a<_{L} b$ and every c.e. pre-ordering relation $R$ one can find a reducing function $f$ from $R$ to $\le_{L}$ such that the range of $f$ is contained in the interval $\{x: a \leq_{L} x \leq_{L} b\}$. Also $\leq_L$ is uniformly dense, i.e. there exists a computable function $f$ such that for every $a,b$ if $a<_{L} b$ then $a<_{L} f(a,b) <_{L} b$, and if $a\equiv_{L} a'$ and $b \equiv_{L} b'$ then $f(a,b)\equiv_{L} f(a',b')$. Some consequences and applications of these results are discussed: in particular for $n \ge 1$ the c.e. pre-ordering relation on $\Sigma_{n}$ sentences yielded by the relation of provable implication of any c.e. consistent extension of Robinson's system $R$ or $Q$ is locally universal and uniformly dense; and the c.e. pre-ordering relation yielded by provable implication of any c.e. consistent extension of Heyting Arithmetic is locally universal and uniformly dense.

  36. Trial and error mathematics: dialectical systems and completions of theories (with Jacopo Amidei, Duccio Pianigiani, Luca San Mauro, and Andrea Sorbi)
    Journal of Logic and Computation, 29 (2019), no. 1, 157-184.
    This paper is part of a project that is based on the notion of a dialectical system, introduced by Magari as a way of capturing trial and error mathematics. In Amidei et al. (2016, Rev. Symb. Logic, 9, 1–26) and Amidei et al. (2016, Rev. Symb. Logic, 9, 299–324), we investigated the expressive and computational power of dialectical systems, and we compared them to a new class of systems, that of quasi-dialectical systems, that enrich Magari’s systems with a natural mechanism of revision. In the present paper we consider a third class of systems, that of $p$-dialectical systems, that naturally combine features coming from the two other cases. We prove several results about $p$-dialectical systems and the sets that they represent. Then we focus on the completions of first-order theories. In doing so, we consider systems with connectives, i.e. systems that encode the rules of classical logic. We show that any consistent system with connectives represents the completion of a given theory. We prove that dialectical and $q$-dialectical systems coincide with respect to the completions that they can represent. Yet, $p$-dialectical systems are more powerful; we exhibit a $p$-dialectical system representing a completion of Peano Arithmetic that is neither dialectical nor $q$-dialectical.

  37. Limit computability and ultrafilters on $\omega$ (with Mingzhong Cai, David Diamondstone, and Noah Schweber)
    To appear at Computability
    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.


  38. Spectra of Computable Models of Strongly Minimal Disintegrated Theories in Languages of Bounded Arity (with Steffen Lempp)
    submitted for publication
    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.

  39. VC-minimality: Examples and Observations (with Sarah Cotter Blanset, James Freitag, and Alice Medvedev)
    submitted for publication
    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.

  40. The theory of ceers computes true arithmetic (with Noah Schweber and Andrea Sorbi)
    submitted
    We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure comprised of the light ceers. We also show the same for the structure of $\mathcal I$-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of $(\mathbb{N},+,\cdot)$.

  41. Self-Fullness for Ceers (with Noah Schweber and Andrea Sorbi)
    submitted
    We examine the property of self-fullness of computably enumerable equivalence relations (ceers) and its relation to the uniform join operation. We answer a question from (citation) by showing that there are self-full ceers $X$ and $Y$ so that $X\oplus Y$ is non-self-full. We then define and examine the collection of hereditarily self-full ceers, which are the self-full ceers $X$ so that for any self-full $Y$, $X\oplus Y$ is also self-full. We show that every dark ceer is hereditarily self-full, and that there are light ceers which are hereditarily self-full.

  42. Building models of strongly minimal theories (with Steffen Lempp and Noah Schweber)
    submitted
    What information does one need to know in order to build the models of a strongly minimal theory? To answer this question, we first formalize it in two ways. Note that if a theory~$T$ has a computable model, then $T \cap \exists_{n}$ is uniformly~$\Sigma^0_n$. We call such theories Solovay theories. A degree is strongly minimal computing if it computes a copy of every model of every strongly minimal Solovay theory. A second notion, introduced by Lempp in the mid-1990's, is that of a strongly minimal relatively computing degree. A degree ${\mathbf d}$ is strongly minimal relatively computing if whenever $T$ is a strongly minimal theory with one computable model, ${\mathbf d}$ computes a copy of every model of $T$. We characterize both classes of degrees as exactly the degrees which are high over ${\mathbf 0}''$, i.e., ${\mathbf d} \geq {\mathbf 0}''$ and ${\mathbf d}' \geq {\mathbf 0}^{(4)}$.

  43. $[0,n]\cup \{\omega\}$ is a spectrum of a non-disintegrated flat strongly minimal model complete theory in a language with finite signature (with Omer Mermelstein)
    submitted
    We build a new spectrum of recursive models ($\text{SRM}(T)$) of a strongly minimal theory. This theory is non-disintegrated, flat, model complete, and in a language with a finite signature.