A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. (...) Various notions of boundedness are discussed and classified. For example, the index set of the recursively bounded classes is Σ03 complete and the index set of the recursively bounded classes which have infinitely many recursive members is Π04 complete. Consideration of the Cantor-Bendixson derivative leads to index sets in the transfinite levels of the hyperarithmetic hierarchy. (shrink)

In this paper we study essential hereditary undecidability. Theories with this property are a convenient tool to prove undecidability of other theories. The paper develops the basic facts concerning essentially hereditary undecidability and provides salient examples, like a construction of essentially hereditarily undecidable theories due to Hanf and an example of a rather natural essentially hereditarily undecidable theory strictly below. We discuss the (non-)interaction of essential hereditary undecidability with recursive boolean isomorphism. We develop a reduction relation essential tolerance, or, in (...) the converse direction, lax interpretability that interacts in a good way with essential hereditary undecidability. We introduce the class of $$\Sigma ^0_1$$ Σ 1 0 -friendly theories and show that $$\Sigma ^0_1$$ Σ 1 0 -friendliness is sufficient but not necessary for essential hereditary undecidability. Finally, we adapt an argument due to Pakhomov, Murwanashyaka and Visser to show that there is no interpretability minimal essentially hereditarily undecidable theory. (shrink)

In this work, we aim at understanding incompleteness in an abstract way via metamathematical properties of formal theories. We systematically examine the relationships between the following twelve important metamathematical properties of arithmetical theories: Rosser, EI (effectively inseparable), RI (recursively inseparable), TP (Turing persistent), EHU (essentially hereditarily undecidable), EU (essentially undecidable), Creative, $\textbf{0}^{\prime }$ (theories with Turing degree $\textbf{0}^{\prime }$), REW (all RE sets are weakly representable), RFD (all recursive functions are definable), RSS (all recursive sets are strongly representable), RSW (all (...) recursive sets are weakly representable). Given any two properties $P$ and $Q$ in the above list, we examine whether $P$ implies $Q$. (shrink)

In the language \(\lbrace 0, 1, \circ, \preceq \rbrace \), where 0 and 1 are constant symbols, \(\circ \) is a binary function symbol and \(\preceq \) is a binary relation symbol, we formulate two theories, \( \textsf {WD} \) and \( {\textsf {D}}\), that are mutually interpretable with the theory of arithmetic \( {\textsf {R}} \) and Robinson arithmetic \({\textsf {Q}} \), respectively. The intended model of \( \textsf {WD} \) and \( {\textsf {D}}\) is the free semigroup generated (...) by \(\lbrace {\varvec{0}}, {\varvec{1}} \rbrace \) under string concatenation extended with the prefix relation. The theories \( \textsf {WD} \) and \( {\textsf {D}}\) are purely universally axiomatised, in contrast to \( {\textsf {Q}} \) which has the \(\varPi _2\) -axiom \(\forall x \; [ \ x = 0 \vee \exists y \; [ \ x = Sy \ ] \ ] \). (shrink)

In this paper, we examine the limit of applicability of Gödel’s first incompleteness theorem. We first define the notion “$\textsf {G1}$ holds for the theory $T$”. This paper is motivated by the following question: can we find a theory with a minimal degree of interpretation for which $\textsf {G1}$ holds. To approach this question, we first examine the following question: is there a theory T such that Robinson’s $\mathbf {R}$ interprets T but T does not interpret $\mathbf {R}$ and $\textsf (...) {G1}$ holds for T? In this paper, we show that there are many such theories based on Jeřábek’s work using some model theory. We prove that for each recursively inseparable pair $\langle A,B\rangle $, we can construct a r.e. theory $U_{\langle A,B\rangle }$ such that $U_{\langle A,B\rangle }$ is weaker than $\mathbf {R}$ w.r.t. interpretation and $\textsf {G1}$ holds for $U_{\langle A,B\rangle }$. As a corollary, we answer a question from Albert Visser. Moreover, we prove that for any Turing degree $\mathbf {0}< \mathbf {d}<\mathbf {0}^{\prime }$, there is a theory T with Turing degree $\mathbf {d}$ such that $\textsf {G1}$ holds for T and T is weaker than $\mathbf {R}$ w.r.t. Turing reducibility. As a corollary, based on Shoenfield’s work using some recursion theory, we show that there is no theory with a minimal degree of Turing reducibility for which $\textsf {G1}$ holds. (shrink)