Publications and preprints

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.

Argumentation frameworks, consisting of arguments and an attack relation representing conflicts, are fundamental for formally studying reasoning under conflicting information. We use methods from mathematical logic, specifically computability and set theory, to analyze the grounded extension, a widely-used model of maximally skeptical reasoning, defined as the least fixed-point of a natural defense operator. Without additional constraints, finding this fixed-point requires transfinite iterations. We identify the exact ordinal number corresponding to the length of this iterative process and determine the complexity of deciding grounded acceptance, showing it to be maximally complex. This shows a marked distinction from the finite case where the grounded extension is polynomial-time computable, thus simpler than other reasoning problems explored in formal argumentation.

Dialectical systems are a mathematical formalism for modeling an agent updating a knowledge base seeking consistency. Introduced in the 1970s by Roberto Magari, they were originally conceived to capture how a working mathematician or a research community refines beliefs in the pursuit of truth. Dialectical systems also serve as natural models for the belief change of an automated agent, offering a unifying, computable framework for dynamic belief management.

The literature distinguishes three main models of dialectical systems: (d-)dialectical systems based on revising beliefs when they are seen to be inconsistent, p-dialectical systems based on revising beliefs based on finding a counterexample, and q-dialectical systems which can do both.

We answer an open problem in the literature by proving that q-dialectical systems are strictly more powerful than p-dialectical systems, which are themselves known to be strictly stronger than (d-)dialectical systems. This result highlights the complementary roles of counterexample and contradiction in automated belief revision, and thus also in the reasoning processes of mathematicians and research communities.

Argumentation frameworks (AFs) are a foundational tool in artificial intelligence for modeling structured reasoning and conflict. SCC-recursiveness is a well-known design principle in which the evaluation of arguments is decomposed according to the strongly connected components (SCCs) of the attack graph, proceeding recursively from "higher" to "lower" components. While SCC-recursive semantics such as cf2 and stg2 have proven effective for finite AFs, Baumann and Spanring showed the failure of SCC-recursive semantics to generalize reliably to infinite AFs due to issues with well-foundedness.

We propose two approaches to extending SCC-recursiveness to the infinite setting. We systematically evaluate these semantics using Baroni and Giacomin’s established criteria, showing in particular that directionality fails in general. We then examine these semantics' behavior in finitary frameworks, where we find some of our semantics satisfy directionality. These results advance the theory of infinite argumentation and lay the groundwork for reasoning systems capable of handling unbounded or evolving domains.

We employ the Hrushovski Amalgamation Construction to generate strongly minimal examples of interesting recursive model theoretic phenomena. We show that there exists a strongly minimal theory whose only recursively presentable models are prime or saturated. We show that there exists a strongly minimal theory in a language with finite signature whose only recursively presentable model is the saturated model.Similarly, we show that for every $k\in \omega +1$ there exists a strongly minimal theory in a language with finite signature whose recursively presentable models are those with dimension less than $k$. Finally, we characterize the complexity of strongly minimal or ${\mathrm{\aleph }}_0$-categorical theories that have only recursively presentable models by generating examples in every possible tt-degree.

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.

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.

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 ${\mathrm{\aleph }}_1$-categorical and ${\mathrm{\aleph }}_0$-categorical theories in finite languages all of whose countable models have recursive presentations.

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 ${\mathrm{\Pi }}_2$ sets with ${\mathrm{\Sigma }}_2$ sets.

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.

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.

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

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.

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.

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.

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.

We study Turing degrees $a$ for which there is a countable structure $\mathcal{A}$ whose degree spectrum is the collection $\{x:x\nleqq a\}$. In particular, for degrees $a$ from the interval $[0^{\prime },0^{″}]$, such a structure exists if $a^{\prime }=0^{″}$, and there are no such structures if $a^{″}>0^{‴}$.

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

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.

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\ge 1$, $T\cap {\mathrm{\exists }}_{n+2}$ is ${\mathrm{\Delta }}_n^0$, 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 ${\mathrm{\Delta }}_4^0$ copy.

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 {\mathrm{\exists }}_n$ is uniformly ${\mathrm{\Sigma }}_n^0$. 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}$ $\ge {\mathbf{0}}^{″}$ and ${\mathbf{d}}^{\prime }$ $\ge {\mathbf{0}}^{(4)}$.

We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel quotient of the reals reduces to it.

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.

We show that for a model complete strongly minimal theory whose pregeometry is flat, the recursive spectrum (SRM($T$)) is either of the form $[0,\alpha )$ for $\alpha \in \omega +2$ or $[0,n)\cup \{\omega \}$ for $n\in \omega$, or contained in $\{0,1,2,\omega \}$.

Combined with previous results, this leaves precisely 8 sets for which it is not yet determined whether they are spectra of a model complete strongly minimal theory with a flat pregeometry.

We say that a theory $T$ satisfies arithmetic-is-recursive if any $X^{\prime }$-computable model of $T$ has an $X$-computable copy; that is, the models of $T$ satisfy a sort of jump inversion. We give an example of a theory satisfying arithmetic-is-recursive non-trivially and prove that the theories satisfying arithmetic-is-recursive on a cone are exactly those theories with countably many $\omega$-back-and-forth types.

We study the relative computational complexity of expansions of Cantor and Baire space in terms of generic Muchnik reducibility. We show that no expansion of Cantor space by countably many unary or closed relations can give a generic Muchnik degree strictly between the degree of Cantor space and the degree of Baire space. Similarly, assuming ${\mathbf{\Delta }}_{\mathbf{2}}^{\mathbf{1}}$-Wadge determinacy we show that no expansion of Baire space by countably many unary or closed relations can give a generic Muchnik degree strictly between the degree of Baire space and the Borel complete degree. On the other hand, we provide a construction of a degree strictly between $\mathcal{C}$ and $\mathcal{B}$ and also between $\mathcal{B}$ and $\mathcal{BC}$.

We answer two questions on the complexities of decision problems of groups, each related to a classical result. First, C.\ Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the isomorphism problem for recursively presented groups. Second, the fact that every Turing degree appears as the degree of the word problem of a finitely presented group is shown independently by multiple people in the 1960s. We answer the analogous question for degrees of ceers instead of Turing degrees. We show that the set of ceers which are computably equivalent to a finitely presented group is ${\mathrm{\Sigma }}_3^0$-complete, which is the maximal possible complexity.

We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Knight and Solovay, we give a sharp condition for complete theories to have a ${\mathbf{\Pi }}_{\omega }^0$-complete set of models. We also give sharp conditions for theories to have a ${\mathbf{\Pi }}_n^0$-complete set of models. Finally, we determine the Turing degrees needed to witness the completeness.

The study of the word problems of groups dates back to Dehn in 1911, and has been a central topic of study in both group theory and computability theory. As most naturally occurring presentations of groups are recursive, their word problems can be thought of as a computably enumerable equivalence relation (ceer). In this paper, we study the word problem of groups in the framework of ceer degrees, introducing a new metric with which to study word problems. This metric is more refined than the classical context of Turing degrees.

Classically, every Turing degree is realized as the word problem of some c.e.\ group, but this is not true for ceer degrees. This motivates us to look at the classical constructions and show that there is a group whose word problem is not universal, but becomes universal after taking any nontrivial free product, which we call *-universal. This shows that existing constructions of the Higman embedding theorem do not preserve ceer degrees. We also study the index set of various classes of groups defined by their properties as a ceer: groups whose word problems are dark (equivalently, algorithmically finite as defined by Miasnikov and Osin), universal, and *-universal groups.

We study computably enumerable equivalence relations (ceers) under the reducibility $R\le 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 $\le$ is a bounded poset that is neither a lower semilattice, 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^{\prime }\le R$, where $R^{\prime }$ denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); 3) the index set of universal ceers is ${\mathrm{\Sigma }}_3^0$-complete (answering an open question of Gao and Gerdes), and the index set of uniformly universal ceers is ${\mathrm{\Sigma }}_3^0$-complete.

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 ${\mathrm{\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.

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

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\mid R_i{\le }_{c}R\}$ (with $R$non-universal), $\{i\mid R_i{\ge }_{c}R\}$, and $\{i\mid R_i{\equiv }_{c}R\}$ are${\mathrm{\Sigma }}_3^0$ complete, whereas in case $R$ has only finitely many equivalence classes, we have that $\{i\mid R_i{\le }_{c}R\}$ is ${\mathrm{\Pi }}_2^0$complete, and $\{i\mid R_i{\ge }_{c}R\}$ (with $R$ having at least two distinct equivalence classes) is ${\mathrm{\Sigma }}_2^0$ complete. Next, solving an open problem from [ALMNSS] , we prove that the index set of the effectively inseparable ceers is ${\mathrm{\Pi }}_4^0$ complete. Finally, we prove that the $1$-reducibility pre-ordering on c.e. sets is a ${\mathrm{\Sigma }}_3^0$ complete pre-ordering relation, a fact that is used to show that the pre-ordering relation ${\le }_c$ on ceers is a ${\mathrm{\Sigma }}_3^0$ complete pre-ordering relation.

We review the literature on universal computably enumerable equivalencerelations, i.e. the computably enumerable equivalence relations (ceers)which are ${\mathrm{\Sigma }}_1^0$-complete with respect to computable reducibility one quivalence 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.

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 ${\mathbf{d}}_{\mathbf{1}}\mathbf{>}{\mathbf{d}}_{\mathbf{2}}\mathbf{>}\mathbf{0}$ forms a double bubble if all d.c.e. degrees below ${\mathbf{d}}_{\mathbf{1}}$ are comparable with ${\mathbf{d}}_{\mathbf{2}}$.

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)}\ngeqq {\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$.

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 $\underset{\mathcal{U}}{lim}(A)=\{x\mid \{i\mid x\in A_i\}\in \mathcal{U}\}$. This can be extended to the Turing degrees, by defining ${\delta }_{\mathcal{U}}($$\mathbf{a}$$)=\{\underset{\mathcal{U}}{lim}(A)\mid A=(A_i{)}_{i\in \omega }\in$$\mathbf{a}$$\}$. The ${\delta }_{\mathcal{U}}$ --- which we call "ultrafilter jumps" --- resemble classical limit computability in certain ways. In particular, ${\delta }_{\mathcal{U}}($$\mathbf{a}$$)$ is always a Turing ideal containing ${\mathrm{\Delta }}_2^0($$\mathbf{a}$$)$. However, they are also closely tied to Scott sets: ${\delta }_{\mathcal{U}}($$\mathbf{a}$$)$ is always a Scott set containing ${\mathbf{a}}^{\prime }$.

Our main result is that the converse also holds: if $\mathcal{S}$ is a countable Scott set containing ${\mathbf{a}}^{\prime }$, then there is some ultrafilter $\mathcal{U}$ with ${\delta }_{\mathcal{U}}($$\mathbf{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 "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.

A set $A\subseteq \omega$ is cototal if it is enumeration reducible to its complement, $\overline{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.

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.

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

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,\dots ,E_n$ in $d$ so that any ceer $R$ in $d$ is isomorphic to $E_i\oplus D$ for some $i\le 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 ${\mathrm{\Pi }}_3^0$-hard, though the definition is ${\mathrm{\Sigma }}_4^0$. We close the gap by showing that the index set is ${\mathrm{\Sigma }}_4^0$-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 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\le 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.

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

We examine the property of self-fullness of computably enumerablee quivalence 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.

It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self-full degrees. We show that the poset $⟨{\omega }^{<\omega },\subseteq ⟩$ can be embedded as an initial segment of the degrees of ceers with infinitely many classes. A further refinement of the proof shows that one can also embed the free distributive lattice generated by the lower semilattice $⟨{\omega }^{<\omega },\subseteq ⟩$ as an initial segment of the degrees of ceers with infinitely many classes.

We generalize the analysis of Andrews, Schweber and Sorbi of the first-order theory of the partial order of degrees of c.e. equivalence relations to higher computability theory, specifically to the setting of a regular cardinal.

Combinatorial operations on sets are almost never well-defined on Turing degrees, a fact so obvious that counterexamples are worth exhibiting. The case we focus on is the symmetric difference operator; there are pairs of (nonzero) degrees for which the symmetric difference operation is well-defined. Some examples can be extracted from the literature, for example, from the existence of nonzero degrees with strong minimal covers. We focus on the case of incomparable r.e. degrees for which the symmetric difference operation is well-defined.

We examine the degree structure $\mathbf{ER}$ of equivalence relations on $\omega$ under computable reducibility. We examine when pairs of degrees have a join. In particular, we show that sufficiently incomparable pairs of degrees do not have a join but that some incomparable degrees do, and we characterize the degrees which have a join with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in $\mathbf{ER}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf{d}\oplus {\mathbf{\text{Id}}}_{\mathbf{1}}$ needn't be a strong minimal cover of a self-full degree $\mathbf{d}$. Finally, we show that the theory of the degree structure $\mathbf{ER}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second order arithmetic.

We answer several questions about the computable Friedman-Stanley jump on equivalence relations. This jump, introduced by Clemens, Coskey, and Krakoff, deepens the natural connection between the study of computable reduction and its Borel analog studied deeply in descriptive set theory.

Coskey, Hamkins, and Miller [CHM] proposed two possible analogues of the class of countable Borel equivalence relations in the setting of computable reducibility of equivalence relations on the computably enumerable (c.e.) sets. The first is based on effectivizing the Lusin/Novikov theorem while the latter is based on effectivizing the Feldman/Moore theorem. They asked for an analysis of which degrees under computable reducibility are attained under each of these notions. We investigate these two notions, in particular showing that the latter notion has a strict dichotomy theorem: Every such equivalence relation is either equivalent to the relation of equality (${=}^{ce}$) or almost equality ($E_0^{ce}$) between c.e. sets. For the former notion, we show that this is not true, but rather there are both chains and antichains of such equivalence relations on c.e. sets which are between ${=}^{ce}$ and $E_0^{ce}$. This gives several strong answers to Question 3.5 of [CHM] showing that in general there is no analogue of the Glimm-Efros dichotomy for equivalence relations on the c.e. sets.

A partial order $(P,\le )$ admits a jump operator if there is a map $j:P\to P$ that is strictly increasing and weakly monotone. Despite its name, the jump in the Weihrauch lattice fails to satisfy both of these properties: it is not degree-theoretic and there are functions $f$ such that $f{\equiv }_{\mathrm{W}}{f}^{\prime }$. This raises the question: is there a jump operator in the Weihrauch lattice? We answer this question positively and provide an explicit definition for an operator on partial multi-valued functions that, when lifted to the Weihrauch degrees, induces a jump operator. This new operator, called the totalizing jump , can be characterized in terms of the total continuation, a well-known operator on computational problems. The totalizing jump induces an injective endomorphism of the Weihrauch degrees. We study some algebraic properties of the totalizing jump and characterize its behavior on some pivotal problems in the Weihrauch lattice.

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.

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

We show VC-minimality is ${\mathrm{\Pi }}_4^0$-complete. In particular, we give a local characterization of VC-minimality. We also show dp-smallness is ${\mathrm{\Pi }}_1^1$-complete.

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.

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.

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.

In the paper "Randomizations of Scattered Sentences", Keisler showed that if Martin’s axiom for ${\mathrm{\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.

Cai introduced the provability degrees as the degree structure of the computable algorithms under the reduction $f\le 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.

We study effectively inseparable (abbreviated as e.i.) pre-lattices (i.e.structures of the form $L=⟨\omega ,\wedge ,\vee ,0,1,{\le }_L⟩$ where $\omega$ denotes the set of natural numbers and the following four conditions hold: (1) $\wedge ,\vee$ are binary computable operations; (2) ${\le }_L$ is a computably enumerable pre-ordering relation, with $0{\le }_{L}x{\le }_{L}1$ for every $x$; (3) the equivalence relation${\equiv }_L$ originated by ${\le }_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 ${\le }_L$, i.e. $xRy$ if and only if $f(x){\le }_{L}f(y)$, for all $x,y$. In fact ${\le }_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\mid a{\le }_{L}x{\le }_{L}b\}$. Also ${\le }_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}^{\prime }$ and $b{\equiv }_L{b}^{\prime }$ then $f(a,b){\equiv }_{L}f(a^{\prime },b^{\prime })$. Some consequences and applications of these results are discussed: in particular for$n\ge 1$ the c.e. pre-ordering relation on ${\mathrm{\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.