In Dung-style abstract argumentation, various semantics capture notions of acceptability of arguments. The admissibility semantics capture the notion that an argument can be consistently defended from any potential counterargument. Weak semantics often relax the demands of admissibility by restricting which counterarguments must be taken seriously (e.g., discounting self-defeating or otherwise incoherent attacks). Many prominent proposals for weak semantics remain extension-based in a stronger sense. While these semantics discount attacks from arguments which are considered unreasonable, they still require a uniform defense against all reasonable arguments, even if they are collectively inconsistent. This uniformity can be too demanding when defensibility is inherently strategic, and thus the appropriate reply depends on the opponent's line of attack. We introduce tenability, a family of dialogue-based semantics that formalize when a designated argument (or a set of arguments) can be maintained in debate by a proponent against any conflict-free attack which the opponent may present. The approach is motivated by three natural benchmark patterns: self-defeating attack, floating assignment, and disjunctive reinstatement, on which tenability behaves differently from all weak semantics previously considered in the literature. We define three variants---static tenability, tenability, and strong tenability---via monotone commitment games over finite conflict-free moves, differing in the obligations imposed on the disputants. We establish the relative strength of these notions, prove implications and separations with previously studied weak semantics, and we analyze computational complexity on finite frameworks: deciding static tenability is Pi2P-complete, while deciding tenability and strong tenability is PSPACE-complete.

Abstract argumentation frameworks (AFs) provide a formal setting to analyze many forms of reasoning with conflicting information. While the expressiveness of general infinite AFs make them a tempting tool for modeling many kinds of reasoning scenarios, the computational intractability of solving infinite AFs limit their use, even in many theoretical applications. We investigate the complexity of computational problems related to infinite but finitary argumentations frameworks, that is, infinite AFs where each argument is attacked by only finitely many others. Our results reveal a surprising scenario. On one hand, we see that the assumption of being finitary does not automatically guarantee a drop in complexity. However, for the admissibility-based semantics, we find a remarkable combinatorial constraint which entails a dramatic decrease in complexity. We conclude that for many forms of reasoning, the finitary infinite AFs provide a natural setting for reasoning which balances well the competing goals of being expressive enough to be applied to many reasoning settings while being computationally tractable enough for the analysis within the framework to be useful.

Abstract The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $ , written ${\dotplus }$ , recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$ . In particular, we show that this jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$ .

Abstract We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are definable in $\operatorname {\mathrm {\mathbf {ER}}}$ . We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_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 $\operatorname {\mathrm {\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.

Abstract 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 [7]. 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.

Abstract 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 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 as an initial segment of the degrees of ceers with infinitely many classes.

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

Abstract We build a new spectrum of recursive models ( $ \operatorname {\mathrm {SRM}}(T)$ ) of a strongly minimal theory. This theory is non-disintegrated, flat, model complete, and in a language with a finite signature.

Abstract 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 ω which reduces one to the other. As a method of focusing on nontrivial 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 ω, 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 \le n$ and D a ceer with domain either finite or ω 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 [11] 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 ${\rm{\Pi }}_3^0$ -hard, though the definition is ${\rm{\Sigma }}_4^0$ . We close the gap by showing that the index set is ${\rm{\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 [4] examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $\left( {{E_i}} \right)$ is a uniform c.e. sequence of non universal ceers, then $\left\{ {{ \oplus _{i \le j}}{E_i}|j \in \omega } \right\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from [4]. Lastly, we show that there exists an infinite antichain of weakly precomplete ceers.

Abstract A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$, then the range of $f$ intersects all $X$-equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question from [ 4] by showing that there are self-full ceers $X$ and $Y$ so that their uniform join $X\oplus Y$ is non-self-full. We then define and examine the 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 they are closed under uniform join and that every non-universal degree in ${\operatorname{\textbf{Ceers}}}_{\operatorname{{\mathcal{I}}}}$ have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus, the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers, which is closed under $\oplus $.

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

Abstract We study Turing degrees a for which there is a countable structure ${\cal A}$ whose degree spectrum is the collection {x : x ≰ 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‴.

Abstract Let $ \le _c $ be computable the reducibility on computably enumerable equivalence relations (or ceers). We show that for every ceerRwith infinitely many equivalence classes, the index sets $\left\{ {i:R_i \le _c R} \right\}$ (withRnonuniversal), $\left\{ {i:R_i \ge _c R} \right\}$ , and $\left\{ {i:R_i \equiv _c R} \right\}$ are ${\rm{\Sigma }}_3^0$ complete, whereas in caseRhas only finitely many equivalence classes, we have that $\left\{ {i:R_i \le _c R} \right\}$ is ${\rm{\Pi }}_2^0$ complete, and $\left\{ {i:R \ge _c R} \right\}$ (withRhaving at least two distinct equivalence classes) is ${\rm{\Sigma }}_2^0$ complete. Next, solving an open problem from [1], we prove that the index set of the effectively inseparable ceers is ${\rm{\Pi }}_4^0$ complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a ${\rm{\Sigma }}_3^0$ complete preordering relation, a fact that is used to show that the preordering relation $ \le _c $ on ceers is a ${\rm{\Sigma }}_3^0$ complete preordering relation.

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 TR 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 ω1-categorical first order theories.

Abstract We characterize the ω-stable theories all of whose countable models admit decidable presentations. In particular, we show that for a countable ω-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 further characterize the decidable models of ω-stable theories with countably many countable models as those which realize only recursive types.

Abstract We study computably enumerable equivalence relations (ceers), under the reducibility $R \le S$ if there exists a computable function f such that $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$ , for every $x,y$ . We show that the degrees of ceers under the equivalence relation generated by $\le$ form 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 that 1) the uniformly effectively inseparable ceers are universal, 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); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are ${\rm{\Sigma }}_3^0$ -complete (the former answering an open question of Gao and Gerdes).

Abstract For a countable structure , the spectrum is the set of Turing degrees of isomorphic copies of . 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 [1] by showing that there is an atomic theory T whose spectrum does not match the spectrum of any structure.

Abstract We employ an infinite-signature Hrushovski amalgamation construction to yield two results in Recursive Model Theory. The first result, that there exists a strongly minimal theory whose only recursively presentable models are the prime and saturated models, adds 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.