We show that many principles of first-order arithmetic, previously only known to lie strictly between [Formula: see text]-induction and [Formula: see text]-induction, are equivalent to the well-foundedness of [Formula: see text]. Among these principles are the iteration of partial functions of Hájek and Paris, the bounded monotone enumerations principle by Chong, Slaman, and Yang, the relativized Paris–Harrington principle for pairs, and the totality of the relativized Ackermann–Péter function. With this we show that the well-foundedness of [Formula: see text] is (...) a far more widespread than usually suspected. Further, we investigate the [Formula: see text]-iterated version of the bounded monotone iterations principle, and show that it is equivalent to the well-foundedness of the -height [Formula: see text]-tower [Formula: see text]. (shrink)

In one of his latest books, La pensée dérobée, Jean-Luc Nancy continues writing about the major themes of his work up until now: community, sense, being as being with, or singular plural being. These themes come together in a witnessing of the world “as such”: that is to say,the world here and now in which we are living in common. The sense of the world is nothing but this being-in-common. This makes Nancy a thinker of “globalization”, albeit in a very (...) specific way, one concerned with the way in which we are “world”. One way to argue this is to consider the way in which Nancy's workis larded with enumerations. Very often he “recites” our singular plural being by giving lists of the diversity of “things”. This is also the case for a few of the texts in La pensée dérobée. In trying to catch an echo of these “recitals”, I want to review the theme world in Nancy's oeuvre and ask the question if and how Nancy thinks of our global coexistence nowadays. A part of this text was presented at the 4th annual conference of The Society for European Philosophy at the Manchester Metropolitan University. (shrink)

This research partially answers the question raised by Goncharov about the size of the class of positive elements of a Roger's semilattice. We introduce a notion of effective infinity of classes of computable enumerations. Then, using finite injury priority method, we prove five theorems which give sufficient conditions to be effectively infinite for classes of all enumerations without repetitions, positive undecidable enumerations, negative undecidable enumerations and all computable enumerations of a family of r.e. sets. These (...) theorems permit to strengthen the results of Pour-El, Pour-El and Howard, Ershov and Khutoretskii about existence of enumerations without repetitions and positive undecidable enumerations. (shrink)

Refinement geometry defines a directed subdivision structure over history-prefix spaces generated by admissible stability predicates. This paper analyzes the effective realizability of that structure within represented-space semantics. Stability predicates are formalized in uniformly semi-decidable witness form, yielding certified fact sets that evolve monotonically under refinement. A partitioning functional Pi maps finite-information access to a history into the corresponding directed family of refinement partitions. We prove that Pi is Type-2 computable: every finite portion of refinement structure depends on only finitely many (...) oracle interactions. Refinement asymmetry arises as a direct consequence of witness-based predicate semantics. Certified distinctions accumulate monotonically and are never revoked, establishing irreversibility at the level of refinement structure independent of dynamical assumptions. We further show that the canonical maximal partition induced by admissible predicates is computably generable through directed refinement of finite certification stages. Worlds, defined as blocks of the canonical maximal partition, therefore form a recursively enumerable set. Worldhood need not be decidable, and maximality is not finitely certifiable, yet every world arises through effective generation of finite refinement prefixes. In the effective setting, each refinement stage induces a computably presented equivalence relation on a countable domain of names, and branching corresponds to monotone contraction of indistinguishability rather than enlargement of the underlying history space. These results provide a computability-theoretic classification of refinement geometry, establishing constructive generation of maximal distinction structure under finite-information semantics and clarifying the effective consequences of stability-based refinement. (shrink)

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)

Perhaps nowhere better than, "On the Names of God," can readers discern Laclau's appreciation of theology, specifically, negative theology, and the radical potencies of political theology. // It is Laclau's close attention to Eckhart and Dionysius in this essay that reveals a core theological strategy to be learned by populist reasons or social logics and applied in politics or democracies to come. // This mode of algorithmically informed negative political theology is not mathematically inert. It aspires to relate a fraction (...) or ratio to a series... It strains to reduce the decided determinateness of such seriality ever condemned to the naive metaphysics of bad infinity. // It is worth considering that it is the specific 'number' of Dionysius in differential identification with an ineffable god (and, as such, a singular becoming between theology and numbers) that is floating in at least two dimensions [of signification] (be it political Demand on the horizontal dimension or theological Desire on [a] floating dimension) that cannot but *perform the link that relinks* names of god with any political life, populist reason, social justice, or radical democracy straining toward peace. (shrink)

We investigate the upper semilattice Eq* of recursively enumerable equivalence relations modulo finite differences. Several natural subclasses are shown to be first-order definable in Eq*. Building on this we define a copy of the structure of recursively enumerable many-one degrees in Eq*, thereby showing that Th has the same computational complexity as the true first-order arithmetic.

We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.

Representations of the fingers are embodied in our cognition and influence performance in enumeration tasks. Among deaf signers, the fingers also serve as a tool for communication in sign language. Previous studies in normal hearing (NH) participants showed effects of embodiment (i.e., embodied numerosity) on tactile enumeration using the fingers of one hand. In this research, we examined the influence of extensive visuo‐manual use on tactile enumeration among the deaf. We carried out four enumeration task experiments, using 1–5 stimuli, on (...) a profoundly deaf group (n = 16) and a matching NH group (n = 15): (a) tactile enumeration using one hand, (b) tactile enumeration using two hands, (c) visual enumeration of finger signs, and (d) visual enumeration of dots. In the tactile tasks, we found salient embodied effects in the deaf group compared to the NH group. In the visual enumeration of finger signs task, we controlled the meanings of the stimuli presentation type (e.g., finger‐counting habit, fingerspelled letters, both or neither). Interestingly, when comparing fingerspelled letters to neutrals (i.e., not letters or numerical finger‐counting signs), an inhibition pattern was observed among the deaf. The findings uncover the influence of rich visuo‐manual experiences and language on embodied representations. In addition, we propose that these influences can partially account for the lag in mathematical competencies in the deaf compared to NH peers. Lastly, we further discuss how our findings support a contemporary model for mental numerical representations and finger‐counting habits. (shrink)

The article examines efforts by the Combined Joint Task Force—Operation Inherent Resolve (CJTF-OIR) to enumerate the harm its forces inflicted on Syrian and Iraqi civilians between 2014 and 2018. Drawing on more than 1,300 declassified civilian harm assessments, this article examines the rationale behind the decision to count civilian casualties, the policies that governed how civilian casualties were counted, and what CJTF-OIR officials did with the data collected. Although accurate counts are critical to ethical debates, we show that, on their (...) own, these counts are insufficient when it comes to recognizing the harm inflicted upon civilians and holding militaries accountable. We trace coalition metrics back to concerns about consequence management, showing how martial considerations about optimizing violence—rather than moral concerns about constraining violence—governed the enumerative enterprise. We argue that the way the coalition previously counted civilian casualties erased certain harms from view, including the indirect, cumulative, and reverberating violence that civilians suffered during this conflict. Furthermore, we contend that these numerical indicators tell us little about how civilians experience these harms, a lack of which can become an impediment to ethical consideration. Finally, we contrast the coalition count with Airwars figures to reveal both the numerical discrepancies between the different counts and differences in how these figures have been used. We contend that counting casualties is critical, but also complicated, contestable, and—at times—too constrictive. (shrink)

A set of natural numbers B is computably enumerable in and strictly above (or c.e.a. for short) another set C if C < T B and B is computably enumerable in C. A Turing degree b is c.e.a. c if b and c respectively contain B and C as above. In this paper, it is shown that if b is c.e.a. c then b is c.e.a. some 1-generic g.

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...) categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...) We introduce the notion of a promptly simple set. This describes the essential feature of r.e. generic sets with respect to automorphism constructions. (shrink)

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)

A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...) assigns to each string x its Kolmogorov complexity: • For every underlying universal machine U, there is a constant a such that C is k(n)-enumerable only if k(n) ≥ n/a for almost all n. • For any given constant k, the Kolmogorov function is k-enumerable relative to an oracle A if and only if A is at least as hard as the halting problem. • There exists an r.e., Turing-incomplete set A such for every non-decreasing and unbounded recursive function k, the Kolmogorov function is k(n)-enumerable relative to A. The last result is obtained by using a relativizable construction for a nonrecursive set A relative to which the prefix-free Kolmogorov complexity differs only by a constant from the unrelativized prefix-free Kolmogorov complexity. Although every 2-enumerator for C is Turing hard for K, we show that reductions must depend on the specific choice of the 2-enumerator and there is no bound on the quantity of their queries. We show our negative results even for strong 2-enumerators as an oracle where the querying machine for any x gets directly an explicit list of all hypotheses of the enumerator for this input. The limitations are very general and we show them for any recursively bounded function g: • For every Turing reduction M and every non-recursive set B, there is a strong 2-enumerator f for g such that M does not Turing reduce B to f. • For every non-recursive set B, there is a strong 2-enumerator f for g such that B is not wtt-reducible to f. Furthermore, we deal with the resource-bounded case and give characterizations for the class ${\rm S}_{2}^{{\rm P}}$ introduced by Canetti and independently Russell and Sundaram and the classes PSPACE, EXP. • ${\rm S}_{2}^{{\rm P}}$ is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time tt-reduction which reduces A to every strong 2-enumerator for g. • PSPACE is the class of all sets A for which there is a polynomially bounded function g such that there is a polynomial time Turing reduction which reduces A to every strong 2-enumerator for g. Interestingly, g can be taken to be the Kolmogorov function for the conditional space bounded Kolmogorov complexity. • EXP is the class of all sets A for which there is a polynomially bounded function g and a machine M which witnesses A ∈ PSPACEf for all strong 2-enumerators f for g. Finally, we show that any strong O(log n)-enumerator for the conditional space bounded Kolmogorov function must be PSPACE-hard if P = NP. (shrink)

We investigate and extend the notion of a good approximation with respect to the enumeration ${({\mathcal D}_{\rm e})}$ and singleton ${({\mathcal D}_{\rm s})}$ degrees. We refine two results by Griffith, on the inversion of the jump of sets with a good approximation, and we consider the relation between the double jump and index sets, in the context of enumeration reducibility. We study partial order embeddings ${\iota_s}$ and ${\hat{\iota}_s}$ of, respectively, ${{\mathcal D}_{\rm e}}$ and ${{\mathcal D}_{\rm T}}$ (the Turing degrees) into (...) ${{\mathcal D}_{\rm s}}$ , and we show that the image of ${{\mathcal D}_{\rm T}}$ under ${\hat{\iota}_s}$ is precisely the class of retraceable singleton degrees. We define the notion of a good enumeration, or singleton, degree to be the property of containing the set of good stages of some good approximation, and we show that ${\iota_s}$ preserves the latter, as also other naturally arising properties such as that of totality or of being ${\Gamma^0_n}$ , for ${\Gamma \in \{\Sigma,\Pi,\Delta\}}$ and n > 0. We prove that the good enumeration and singleton degrees are immune and that the good ${\Sigma^0_2}$ singleton degrees are hyperimmune. Finally we show that, for singleton degrees a s < b s such that b s is good, any countable partial order can be embedded in the interval (a s, b s). (shrink)

The problem of enumerating the types of Boolean functions under the group of variable permutations and complementations was first stated by Jevons in the 1870s. but not solved in a satisfactory way until the work of Pólya in 1940. This paper explains the details of Pólya's solution, and also the history of the problem from the 1870s to the 1970s.

We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.

Plants sense and respond to information present in their surrounding environment. Recent work has sought to characterize the limits of these information processing abilities. Here, we present evidence that the movements of Mimosa pudica plants are mediated by the number of illumination events to which they have been exposed. The plants were repeatedly presented with 2 days in which light was provided for half of the day, followed by a third day in which light was not provided. The nyctinastic movements (...) of the plants shifted to follow this light–light–dark pattern. During early, dark hours prior to light onset, the plants moved more on days in which light was likely to be provided and less on days in which light was unlikely. This movement tendency was not present during the initial weeks of the study. The plants altered their movement patterns over 15 days in a fashion that is well fit by a logarithmic function. To test whether plant movement was based on temporal factors, rather than event enumeration, we altered the lengths of day–night cycles in the second and third phases of the study. After accommodating their motion to follow a 3 × 24‐h light–light–dark cycle, the plants immediately generalized their performance after an abrupt shift to a 3 × 20‐h cycle. In Study Phase 3, the day length was randomly varied between 10 and 32 h after every light–light–dark cycle. The plants exhibited key movement patterns when randomly selected day durations were between 12 and 24 h. Although higher levels of variability were apparent, the movement levels of the plants seemed to be modulated by the number of light exposure events. The results provide evidence that plants, and perhaps other non‐neuronal tissues, may be capable of processing enumeration‐related information, although replication with additional controls is needed. (shrink)

We use Demuth randomness to study strong lowness properties of computably enumerable sets, and sometimes of Δ20 sets. A set A⊆N is called a base for Demuth randomness if some set Y Turing above A is Demuth random relative to A. We show that there is an incomputable, computably enumerable base for Demuth randomness, and that each base for Demuth randomness is strongly jump-traceable. We obtain new proofs that each computably enumerable set below all superlow Martin-Löf random sets is strongly (...) jump traceable, using Demuth tests. The sets Turing below each ω2-computably approximable Martin-Löf random set form a proper subclass of the bases for Demuth randomness, and hence of the strongly jump traceable sets. The c.e. sets Turing below each ω2-computably approximable Martin-Löf random set satisfy a new, very strong combinatorial lowness property called ω-traceability. (shrink)

We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d.

We generalize a result on True Arithmetic by Lachlan and Soare to certain other completions of Peano Arithmetic. If $\mathscr{T}$ is a completion of $\mathscr{PA}$, then Rep denotes the family of sets $X \subseteq \omega$ for which there exists a formula $\varphi$ such that for all $n \in \omega$, if $n \in X$, then $\mathscr{T} \vdash \varphi})$ ) and if $n \not\in X$, then $\mathscr{T} \vdash \neg\varphi})$. We show that if $\mathscr{S,J} \subseteq \mathscr{P}$ such that $\mathscr{S}$ is a Scott set, (...) $\mathscr{J}$ is a jump ideal, $\mathscr{S} \subset \mathscr{J}$ and for all $X \in \mathscr{J}$, there exists $C \in \mathscr{S}$ such that C is a "coding" set for the family of subtrees of 2$^{<\omega}$ computable in X, and if $\mathscr{T}$ is a completion of $\mathscr{PA}$ such that Rep = $\mathscr{S}$, then there exists a model $\mathscr{A}$ of $\mathscr{T}$ such that $\mathscr{J}$ is the Scott set of $\mathscr{A}$ and no enumeration of Rep is computable in $\mathscr{A}$. The model $\mathscr{A}$ of $\mathscr{T}$ is obtained via a new notion of forcing. Before proving our main result, we demonstrate the existence of uncountably many different pairs satisfying the conditions of our theorem. This involves a new characterization of 1-generic sets as coding sets for the computable subtrees of 2$^{<\omega}$. In particular, $C \subseteq \omega$ is a coding set for the family of subtrees of 2$^{<\omega}$ computable in X if and only if for all trees T $\subseteq 2^{<\omega}$ computable in X, if $\chi_C$ is a path through T, then there exists $\sigma \in T$ such that $\sigma \subset \chi_C$ and every extension of $\sigma$ is in T. Jockusch noted a connection between 1-generic sets and coding sets for computable subtrees of 2$^{<\omega}$. We show they are identical. (shrink)

A closed λ-term E is called an enumerator if M ε /gL/dg /gTn ε N E/drn/dl = β M. Here Λ° is the set of closed λ-terms, N is the set of natural numbers and the /drn/dl are the Church numerals λfx./tfnx. Such an E is called reducing if moreover M ε /gL/dg /gTn ε N E/drn/dl /a/gb M. In 1983 I conjectured that every enumerator is reducing. An ingenious recursion theoretic proof of this conjecture by Statman is presented in (...) Barendregt. The proof is not intuitionistically valid, however. Dirk van Dalen has encouraged me to find intuitionistic proofs whenever possible. In the lambda calculus this is usually not difficult. In this paper an intuitionistic version of Statmans proof will be given. It took me somewhat longer to find it than in other cases. (shrink)

Sacks [2] has asked whether there exists a uniform solution to Post's problem, i.e. an enumeration operation W such that $\mathbf{d} for every degree d. It is shown here that if such an operation W exists it cannot itself in a particular technical sense be uniform. In fact, the jump operation is characterized amongst such uniform enumeration operations by the condition: $\mathbf{d} for all d. In addition, it is proved that the only other uniform enumeration operations such that d ≤ (...) W (d) for all d are those which equal the identity operation above some fixed degrees. (shrink)

It has become commonplace to distinguish enumerative theories of welfare, which tell us which things are good for us, from explanatory theories, which tell us why the things that are good for us have that status. It has also been claimed that while hedonism and objective list theories are enumerative but not explanatory, desire satisfactionism is explanatory but not enumerative. In this paper, I argue that this is mistaken. When properly understood, every major theory of welfare is both enumerative and (...) explanatory. (shrink)

The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is hoped will (...) make this volume an invaluable resource for specialists and non-specialists alike. (shrink)

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e‐reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non‐deterministic polynomial time reducibility. We define the polynomial time e‐degrees as the equivalence classes under this reducibility and investigate their structure on the recursive (...) sets, showing in particular that the pe‐degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy. (shrink)

Agent communication languages (ACLs) invoke speech act theory and define individual message types by reference to particular combinations of beliefs and desires of the speaker (feasibility preconditions). Even when the mental states are restricted to a small set of nested beliefs, it seems that there might be a very large number of different possible preconditions, and therefore a very large number of different message types. With some constraints on the mental attitude of the speaker, we enumerate the possible belief states (...) that could serve as preconditions for individual message types, and we identify how these states correspond to different possible message types. We then compare these with FIPA’s primitive message types. Our approach clarifies the nature of core message types in an ACL, and perhaps settles issues concerning just how many, and what types of, speech acts should be seen as primitive in such languages. (shrink)

In the paper we introduce and study regular enumerations for arbitrary recursive ordinals. Several applications of the technique are presented.

We study the relationship between a computably enumerable real and its presentations. A set A presents a computably enumerable real α if A is a computably enumerable prefix-free set of strings such that equation image. Note that equation image is precisely the measure of the set of reals that have a string in A as an initial segment. So we will simply abbreviate equation image by μ. It is known that whenever A so presents α then A ≤wttα, where ≤wtt (...) denotes weak truth table reducibility, and that the wtt-degrees of presentations form an ideal ℐ in the computably enumerable wtt-degrees. We prove that any such ideal is equation image, and conversely that if ℐ is any nonempty equation image ideal in the computably enumerable wtt-degrees then there is a computable enumerable real α such that ℐ = ℐ. We also prove a kind of Rice Theorem for these ideals, namely that if the index set of such a equation image ideal is not empty or equal to ω then it is equation image-complete. (shrink)

We prove that every countable relation on the enumeration degrees, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\frak E}$\end{document}, is uniformly definable from parameters in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\frak E}$\end{document}. Consequently, 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} ${\frak E}$\end{document} is recursively isomorphic to the second order theory of arithmetic. By an effective version of coding lemma, we show that the first order (...) theory of the enumeration degrees 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} sets is not decidable. (shrink)

A set A is symmetric enumeration (se-) reducible to a set B (A ≤\sb se B) if A is enumeration reducible to B and \barA is enumeration reducible to \barB. This reducibility gives rise to a degree structure (D\sb se) whose least element is the class of computable sets. We give a classification of ≤\sb se in terms of other standard reducibilities and we show that the natural embedding of the Turing degrees (D\sb T) into the enumeration degrees (D\sb e) (...) translates to an embedding (ι\sb se) into D\sb se that preserves least element, suprema, and infima. We define a weak and a strong jump and we observe that ι\sb se preserves the jump operator relative to the latter definition. We prove various (global) results concerning branching, exact pairs, minimal covers, and diamond embeddings in D\sb se. We show that certain classes of se-degrees are first-order definable, in particular, the classes of semirecursive, Σ\sb n ⋃ Π\sb n, Δ\sb n (for any n \in ω), and embedded Turing degrees. This last result allows us to conclude that the theory of D\sb se has the same 1-degree as the theory of Second-Order Arithmetic. (shrink)

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

A longstanding question is to characterize the lattice of supersets (modulo finite sets), $\mathcal {L}^*(A)$, of a low $_2$ computably enumerable (c.e.) set. The conjecture is that $\mathcal {L}^*(A)\cong {\mathcal E}^*$. In spite of claims in the literature, this longstanding question/conjecture remains open. We contribute to this problem by solving one of the main test cases. We show that if c.e. A is low $_2$ then A has an atomless hyperhypersimple superset. In fact, if A is c.e. and low $_2$, (...) then for any $\Sigma _3$ -Boolean algebra B there is some c.e. $H\supseteq A$ such that $\mathcal {L}^*(H)\cong B$. (shrink)

Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...) to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the ${\left \langle {\text {self}\kern1pt}\right \rangle }$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $\Pi ^0_1$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question. (shrink)

Using only propositional connectives and the provability predicate of a Σ1-sound theory T containing Peano Arithmetic we define recursively enumerable relations that are complete for specific natural classes of relations, as the class of all r. e. relations, and the class of all strict partial orders. We apply these results to give representations of these classes in T by means of formulas.

In the present paper we concentrate on fundamental problems concerning ω-operations over partial enumerated sets. The notion of “HOM-lifts” seems to be an adequate tool for this kind of investigations. MSC: 03D45, 18A30.