Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). This (...) result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration. From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory. (shrink)

This paper investigates the algebraic structure of the Medvedev lattice M. We prove that M is not a Heyting algebra. We point out some relations between M and the Dyment lattice and the Mucnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

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 L-degrees in the dark, light, or complete structure. In each case, we show that there is an interpretable copy of (N, +, \times) .

We prove the following three theorems on the enumeration degrees of ∑20 sets. Theorem A: There exists a nonzero noncuppable ∑20 enumeration degree. Theorem B: Every nonzero Δ20enumeration degree is cuppable to 0′e by an incomplete total enumeration degree. Theorem C: There exists a nonzero low Δ20 enumeration degree with the anticupping property.

We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, (...) we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well. (shrink)

We investigate the initial segments of the Medvedev lattice as Brouwer algebras, and study the propositional logics connected to them.

We give an algorithm for deciding whether an embedding of a finite partial order [Formula: see text] into the enumeration degrees of the [Formula: see text]-sets can always be extended to an embedding of a finite partial order [Formula: see text].

We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice (...) of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space. (shrink)

Using properties of${\cal K}$-pairs of sets, we show that every nonzero enumeration degreeabounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump asa. Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree is high; every nonzero low enumeration degree can be (...) capped by degrees of any possible local jump ; every enumeration degree that bounds a nonzero element of strictly smaller jump, is bounding; every low enumeration degree below a non low enumeration degreeacan be capped belowa. (shrink)

Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence relations. (...) A special focus of our work is on the existence of infima and suprema of c-degrees. (shrink)

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. (shrink)

We consider some nonprincipal filters of the Medvedev lattice. We prove that the filter generated by the nonzero closed degrees of difficulty is not principal and we compare this filter, with respect to inclusion, with some other filters of the lattice. All the filters considered in this paper are disjoint from the prime ideal generated by the dense degrees of difficulty.

We show that every nonzero $\Sigma _{2}^{0}$ enumeration degree bounds a nonsplitting nonzero enumeration degree.

We study effectively inseparable prelattices $\wedge, \vee$ are binary computable operations; ${ \le _L}$ is a computably enumerable preordering relation, with $0{ \le _L}x{ \le _L}1$ for every x; the equivalence relation ${ \equiv _L}$ originated by ${ \le _L}$ is a congruence on L such that the corresponding quotient structure is a nontrivial bounded lattice; the ${ \equiv _L}$ -equivalence classes of 0 and 1 form an effectively inseparable pair of sets). Solving a problem in we show, that if (...) L is an e.i. prelattice then ${ \le _L}$ is universal with respect to all c.e. preordering relations, i.e., for every c.e. preordering relation R there exists a computable function f reducing R to ${ \le _L}$, i.e., $xRy$ if and only if $f\left{ \le _L}f\left$, for all $x,y$. In fact ${ \le _L}$ is locally universal, i.e., for every pair $a{ < _L}b$ and every c.e. preordering 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 $\left\{ {x:a{ \le _L}x{ \le _L}b} \right\}$. 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\left{ < _L}b$, and if $a{ \equiv _L}a\prime$ and $b{ \equiv _L}b\prime$ then $f\left{ \equiv _L}f\left$. Some consequences and applications of these results are discussed: in particular for $n \ge 1$ the c.e. preordering relation on ${{\rm{\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. preordering relation yielded by provable implication of any c.e. consistent extension of Heyting Arithmetic is locally universal and uniformly dense. (shrink)

Logicians and theoretical physicists will also benefit from this book.

We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by ≤be, which is a natural extension of s-reducibility ≤s. We show that ≤s, ≤be, and enumeration reducibility do not coincide on the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Pi^0_1}$$\end{document} –sets, and the structure \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} of the be-degrees is not elementarily equivalent to the structure of the s-degrees. We show also that the first order theory (...) of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{\mathcal{D}_{\rm be}}}$$\end{document} is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper (Z Math Logik Grundlag Math 33:537–560, 1987). (shrink)

We show that the Δ0 2 enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree.

We show that for every enumeration degree $a there exists an e-degree c such that $a \leq c , and all degrees b, with $c \leq b , are properly Σ 0 2.

We show that every nonzero Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Delta^{0}_{2}}$$\end{document} enumeration degree bounds the enumeration degree of a 1-generic set. We also point out that the enumeration degrees of 1-generic sets, below the first jump, are not downwards closed, thus answering a question of Cooper.

Let $\mathfrak{M}$ be the Medvedev lattice: this paper investigates some filters and ideals (most of them already introduced by Dyment, [4]) of $\mathfrak{M}$ . If $\mathfrak{G}$ is any of the filters or ideals considered, the questions concerning $\mathfrak{G}$ which we try to answer are: (1) is $\mathfrak{G}$ prime? What is the cardinality of ${\mathfrak{M} \mathord{\left/ {\vphantom {\mathfrak{M} \mathfrak{G}}} \right. \kern-0em} \mathfrak{G}}$ ? Occasionally, we point out some general facts on theT-degrees or the partial degrees, by which these questions can be (...) answered. (shrink)

We prove that there exists a noncappable enumeration degree strictly below 0' e.

We study a class of formulas generalizing the weak law of the excluded middle and provide a characterization of these formulas in terms of Kripke frames and Brouwer algebras. We use these formulas to separate logics corresponding to factors of the Medvedev lattice.

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f:ω→ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. (...) In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous. (shrink)

Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers, that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always (...) contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ3‐complete, whereas the index set of the weakly precomplete ceers is Π3‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ3‐complete. (shrink)

We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.

We show that every nonzero $\Delta _{2}^{0}$ e-degree bounds a minimal pair. On the other hand, there exist $\Sigma _{2}^{0}$ e-degrees which bound no minimal pair.

We give an alternative and more informative proof that every incomplete ${\Sigma^{0}_{2}}$ -enumeration degree is the meet of two incomparable ${\Sigma^{0}_{2}}$ -degrees, which allows us to show the stronger result that for every incomplete ${\Sigma^{0}_{2}}$ -enumeration degree a, there exist enumeration degrees x 1 and x 2 such that a, x 1, x 2 are incomparable, and for all b ≤ a, b = (b ∨ x 1 ) ∧ (b ∨ x 2 ).

Let A be an infinite Δ₂⁰ set and let K be creative: we show that K≤Q A if and only if K≤Q₁ A. (Here ≤Q denotes Q-reducibility, and ≤Q₁ is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x)∩ Wf(y)=∅, if x \not= y.) Using this result we prove that A is hyperhyperimmune if and only if no Δ⁰₂ subset B of A is s-complete, i.e., there is no Δ⁰₂ subset (...) B of A such that \overline{K}≤s B, where ≤s denotes s-reducibility, and \overline{K} denotes the complement of K. (shrink)

Recent new paradigms of computation, based on biological and physical models, address in a radically new way questions of efficiency and challenge assumptions ...

We make some beginning observations about the category Eq of equivalence relations on the set of natural numbers, where a morphism between two equivalence relations R and S is a mapping from the set of R-equivalence classes to that of S-equivalence classes, which is induced by a computable function. We also consider some full subcategories of Eq, such as the category Eq(Σ01) of computably enumerable equivalence relations (called ceers), the category Eq(Π01) of co-computably enumerable equivalence relations, and the category Eq(Dark*) (...) whose objects are the so-called dark ceers plus the ceers with finitely many equivalence classes. Although in all these categories the monomorphisms coincide with the injective morphisms, we show that in Eq(Σ01) the epimorphisms coincide with the onto morphisms, but in Eq(Π01) there are epimorphisms that are not onto. Moreover, Eq, Eq(Σ01), and Eq(Dark*) are closed under finite products, binary coproducts, and coequalizers, but we give an example of two morphisms in Eq(Π01) whose coequalizer in Eq is not an object of Eq(Π01). (shrink)

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the (...) other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element. (shrink)

Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set ℐ of the sentences that get limit probability 1 is a Π3—theory, in fact ℐ can be a Π3—complete set. We prove incompleteness results for this setting, by showing for instance that for every k > 0 there are true Π3—sentences that get limit probability less than 1/2k. No set (...) ℐ as above can contain the set of all true Π3—sentences, although we exhibit some ℐ containing all the true Σ2—sentences. We also consider an approach based on the notions of inner probability and outer probability, and we compare this approach with the one based on trial and error probabilistic functions. Although the two approaches are shown to be different, we single out an important case in which they are equivalent. (shrink)

In this paper we study the reducibility order m (defined in a natural way) over n 0 -equivalence relations. In particular, for every n> 0 we exhibit n 0 -equivalence relations which are complete with respect to m and investigate some consequences of this fact (see Introduction).

We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\rm ss} B}$$\end{document} (respectively, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}\not\le_{\overline{\rm s}} B}$$\end{document}): here \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm (...) s}}}$$\end{document} is the finite-branch version of s-reducibility, ≤ss is the computably bounded version of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\le_{\overline{\rm s}}}$$\end{document}, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\overline{K}}$$\end{document} is the complement of the halting set. Restriction to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} sets provides a similar characterization of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document} hyperhyperimmune sets in terms of s-reducibility. We also show that no \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${A \geq_{\overline{\rm s}}\overline{K}}$$\end{document} is hyperhyperimmune. As a consequence, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\deg_{\rm s}(\overline{K})}$$\end{document} is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed. (shrink)

We show that every finite lattice is embeddable into the Σ 0 2 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

We introduce a notion of relative efficiency for axiom systems. Given an axiom system Aβ for a theory T consistent with S12, we show that the problem of deciding whether an axiom system Aα for the same theory is more efficient than Aβ is II2-hard. Several possibilities of speed-up of proofs are examined in relation to pairs of axiom systems Aα, Aβ, with Aα ⊇ Aβ, both in the case of Aα, Aβ having the same language, and in the case (...) of the language of Aα extending that of Aβ: in the latter case, letting Prα, Prβ denote the theories axiomatized by Aα, Aβ, respectively, and assuming Prα to be a conservative extension of Prβ, we show that if Aα — Aβ contains no nonlogical axioms, then Aα can only be a linear speed-up of Aβ; otherwise, given any recursive function g and any Aβ, there exists a finite extension Aα of Aβ such that Aα is a speed-up of Aβ with respect to g. (shrink)