One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. (...) J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

A real X is defined to be relatively c.e. if there is a real Y such that X is c.e.(Y) and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X \not\leq_T Y}$$\end{document}. A real X is relatively simple and above if there is a real Y (...) nonempty \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} class contains a member which is not relatively c.e. and that every 1-generic real is relatively simple and above. (shrink)

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 computably enumerable random real is provable in Peano Arithmetic to be c.e. random. A major step in the proof is to show that the theorem stating that “a real is c.e. and random iff it is the halting probability of a universal prefix-free Turing machine” can be proven in PA. Our proof, which is simpler than the standard one, can also be used for the original theorem. Our positive result can be contrasted with the (...) case of computable functions, where not every computable function is provably computable in PA, or even more interestingly, with the fact that almost all random finite strings are not provably random in PA. We also prove two negative results: a) there exists a universal machine whose universality cannot be proved in PA, b) there exists a universal machine U such that, based on U, PA cannot prove the randomness of its halting probability. The paper also includes a sharper form of the Kraft-Chaitin Theorem, as well as a formal proof of this theorem written with the proof assistant Isabelle. (shrink)

We study connections between classical asymptotic density, computability and computable enumerability. In an earlier paper, the second two authors proved that there is a computably enumerable set A of density 1 with no computable subset of density 1. In the current paper, we extend this result in three different ways: The degrees of such sets A are precisely the nonlow c.e. degrees. There is a c.e. set A of density 1 with no computable subset of nonzero density. There (...) is a c.e. set A of density 1 such that every subset of A of density 1 is of high degree. We also study the extent to which c.e. sets A can be approximated by their computable subsets B in the sense that A\B has small density. There is a very close connection between the computational complexity of a set and the arithmetical complexity of its density and we characterize the lower densities, upper densities and densities of both computable and computably enumerable sets. We also study the notion of "computable at density r" where r is a real in the unit interval. Finally, we study connections between density and classical smallness notions such as immunity, hyperimmunity, and cohesiveness. (shrink)

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing (...) degrees of c.e. sets are not dense [2]), however the problem for the computable Lipschitz degrees is more complex. (shrink)

We study the approximation properties of computably enumerable reals. We deal with a natural notion of approximation representation and study their wtt-degrees. Also, we show that a single representation may correspond to a quite diverse variety of reals.

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.

We propose a lexical account of event nouns, in particular of deverbal nominalisations, whose meaning is related to the event expressed by their base verb. The literature on nominalisations often assumes that the semantics of the base verb completely defines the structure of action nominals. We argue that the information in the base verb is not sufficient to completely determine the semantics of action nominals. We exhibit some data from different languages, especially from Romance language, which show that nominalisations focus (...) on some aspects of the verb semantics. The selected aspects, however, seem to be idiosyncratic and do not automatically result from the internal structure of the verb nor from its interaction with the morphological suffix. We therefore propose a partially lexicalist approach view of deverbal nouns. It is made precise and computable by using the Montagovian generative lexicon, a type theoretical framework introduced by Bassac, Mery and Retoré in this journal in 2010. This extension of Montague semantics with a richer type system easily incorporates lexical phenomena like the semantics of action nominals in particular deverbals, including their polysemy and felicitous copredications. (shrink)

We propose a lexical account of event nouns, in particular of deverbal nominalisations, whose meaning is related to the event expressed by their base verb. The literature on nominalisations often assumes that the semantics of the base verb completely defines the structure of action nominals. We argue that the information in the base verb is not sufficient to completely determine the semantics of action nominals. We exhibit some data from different languages, especially from Romance language, which show that nominalisations focus (...) on some aspects of the verb semantics. The selected aspects, however, seem to be idiosyncratic and do not automatically result from the internal structure of the verb nor from its interaction with the morphological suffix. We therefore propose a partially lexicalist approach view of deverbal nouns. It is made precise and computable by using the Montagovian generative lexicon, a type theoretical framework introduced by Bassac, Mery and Retoré in this journal in 2010. This extension of Montague semantics with a richer type system easily incorporates lexical phenomena like the semantics of action nominals in particular deverbals, including their polysemy and felicitous copredications. (shrink)

A real α is called a c. e. real if it is the halting probability of a prefix free Turing machine. Equivalently, α is c. e. if it is left computable in the sense that L = {q ∈ ℚ : q ≤ α} is a computably enumerable set. The natural field formed by the c. e. reals turns out to be the field formed by the collection of the d. c. e. reals, which are of (...) the form α—β, where α and β are c. e. reals. While c. e. reals can only be found in the c. e. degrees, Zheng has proven that there are Δ02 degrees that are not even n-c. e. for any n and yet contain d. c. e. reals, where a degree is n-c. e. if it contains an n-c. e. set. In this paper we will prove that every ω-c. e. degree contains a d. c. e. real, but there are ω + 1-c. e. degrees and, hence Δ02 degrees, containing no d. c. e. real. (shrink)

Say that α is an n-strongly c. e. real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n-strongly c. e. for some n. Let Sn be the set of all n-strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then we have: S1 ⊂ S2 ⊂ · · · ⊂ Sn ⊂ · · (...) · ⊂ ⊂ Reg ⊂ CE. This gives a hierarchy of the c. e. reals. We also study the regularity of the d. c. e. reals. (shrink)

We show that for any real number, the class of real numbers less random than it, in the sense of rK-reducibility, forms a countable real closed subfield of the real ordered field. This generalizes the well-known fact that the computable reals form a real closed field. With the same technique we show that the class of differences of computably enumerable reals (d.c.e. reals) and the class of computably approximable reals (c.a. reals) form (...) real closed fields. The d.c.e. result was also proved nearly simultaneously and independently by Ng (Keng Meng Ng. Master's Thesis. National University of Singapore, in preparation). Lastly, we show that the class of d.c.e. reals is properly contained in the class or reals less random than Ω (the halting probability), which in turn is properly contained in the class of c.a. reals, and that neither the first nor last class is a randomness class (as captured by rK-reducibility). (shrink)

The importance of non-codifying DNA polymorphism for the administration of justice is now well known. In Spain, however, this type of test has given rise to questions in recent years: Should consent be obtained before biological samples are taken from an individual for DNA analysis? Does society perceive these techniques and methods of analysis as being reliable? There appears to be lack of knowledge concerning the basic norms that regulate databases containing private or personal information and the protection that information (...) of this type must be given. This opinion survey and the subsequent analysis of the results in ethical terms may serve to reveal the criteria and the degree of information that society has with regard to DNA databases. In the study, 73.20% of the population surveyed was in favour of specific legislation for computer files in which DNA analysis results for forensic purposes are stored. (shrink)

Continuing the paper [7], in which the Blum-Shub-Smale approach to computability over the reals has been generalized to arbitrary algebraic structures, this paper deals with computability and recognizability over structures of infinite signature. It begins with discussing related properties of the linear and scalar real structures and of their discrete counterparts over the natural numbers. Then the existence of universal functions is shown to be equivalent to the effective encodability of the underlying structure. Such structures even have universal functions (...) satisfying the s-m-n theorem and related features. The real and discrete examples are discussed with respect to effective encodability. Megiddo structures and computational extensions of effectively encodable structures are encodable, too. As further variants of universality, universal functions with enumerable sets of program codes and such ones with constructible codes are investigated. Finally, the existence of m-complete sets is shown to be independent of the effective encodability of structures, and the linear and scalar structures are discussed once more, under this aspect. (shrink)

Several researchers have recently established that for every Turing degree \, the real closed field of all \-computable real numbers has spectrum \. We investigate the spectra of real closed fields further, focusing first on subfields of the field \ of computable real numbers, then on archimedean real closed fields more generally, and finally on non-archimedean real closed fields. For each noncomputable, computably enumerable set C, we produce a real closed C-computable subfield of \ with no computable copy. (...) Then we build an archimedean real closed field with no computable copy but with a computable enumeration of the Dedekind cuts it realizes, and a computably presentable nonarchimedean real closed field whose residue field has no computable presentation. (shrink)

Defenders of educational frog dissection tend to emphasize the claim that computer-simulated alternatives cannot replicate the same exact experience of slicing open a frog, with all its queasy and visceral impact. Without denying that point, I argue that this is not the only educational standard against which computer-simulated dissection should be evaluated. When real-world frog dissection is analyzed as a concrete technological practice rather than an assumed ideal, the particular educational advantages distinct to real-world dissection and virtual dissection can be (...) enumerated and compared. Building on the work of John Dewey and Don Ihde, I explore the still-expanding advantages of computer-simulated dissection, and in this proper context of comparison it becomes clear that virtual alternatives are increasingly the more educationally beneficial option. (shrink)

In [5] it has been shown that for first-order definability over the reals there exists an effective procedure which by a finite formula with equality defining an open set produces a finite formula without equality that defines the same set. In this paper we prove that there exists no such procedure for Σ-definability over the reals. We also show that there exists even no uniform effective transformation of the definitions of Σ-definable sets into new definitions of Σ-definable sets (...) in such a way that the results will define open sets, and if a definition defines an open set, then the result of this transformation will define the same set. These results highlight the important differences between Σ-definability with equality and Σ-definability without equality. (shrink)

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.

We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation.

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)

We prove that every non-computable incomplete computably enumerable degree is locally non-cappable, and use this result to show that there is no maximal non-bounding computably enumerable degree.

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)

For semi-continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi-computable of type one, if its open hypograph hypo is recursively enumerably open in dom × ℝ; we call f lower semi-computable of type two, if its closed epigraph Epi is recursively enumerably closed in dom × ℝ; we call f lower semi-computable of type three, if Epi is recursively closed in dom × ℝ. We show that (...) type one and type two semi-computability are independent and that type three semi-computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi-computable real function on a computable interval is not necessarily computable. (shrink)

We extend the limitwise monotonicity notion to the case of arbitrary computable linear ordering to get a set which is limitwise monotonic precisely in the non‐computable degrees. Also we get a series of connected non‐uniformity results to obtain new examples of non‐uniformly equivalent families of computable sets with the same enumeration degree spectrum.

We show that the identity bounded Turing degrees of computably enumerable sets are not dense.

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.

We examine how degrees of computably enumerable equivalence relations 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$ 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. (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)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...) a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (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.

Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets $B<_{\rm T}A$ such (...) that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B. (shrink)

We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).

Post in 1944 began studying properties of a computably enumerable set A such as simple, h-simple, and hh-simple, with the intent of finding a property guaranteeing incompleteness of A . From the observations of Post and Myhill , attention focused by the 1950s on properties definable in the inclusion ordering of c.e. subsets of ω, namely E = . In the 1950s and 1960s Tennenbaum, Martin, Yates, Sacks, Lachlan, Shoenfield and others produced a number of elegant results relating (...) ∄-definable properties of A , like maximal, hh-simple, atomless, to the information content of A . Harrington and Soare gave an answer to Post's program for definable properties by producing an ∄-definable property Q which guarantees that A is incomplete and noncomputable, but developed a new Δ 3 0 -automorphism method to prove certain other properties are not ∄-definable. In this paper we introduce new ∄-definable properties relating the ∄-structure of A to deg, which answer some open questions. In contrast to Q we exhibit here an ∄-definable property T which allows such a rapid flow of elements into A that A must be complete even though A may possess many other properties such as being promptly simple. We also present a related property NL which has a slower flow but fast enough to guarantee that A is not low, even though A may possess virtually all other related lowness properties and A may simultaneously be promptly simple. (shrink)

We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree d if d is the degree of its elementary diagram. We show that if a CAD theory T has a prime model of c.e. degree c, then T has a prime model of strictly lower c.e. degree b, where, in addition, b is low (b' = 0'). This extends Csima's result that every CAD theory has a low prime (...) model. We also prove a density result for c.e. degrees of prime models. In particular, if c and d are c.e. degrees with d < c and c not low₂ (c" > 0"), then for any CAD theory T, there exists a c.e. degree b with d < b < c such that T has a prime model of degree b, where b can be chosen so that b' is any degree c.e. in c with d' ≤ b'. As a corollary, we show that for any degree c with 0 < c < 0', every CAD theory has a prime model of low c.e. degree incomparable with c. We show also that every CAD theory has prime models of low c.e. degree that form a minimal pair, extending another result of Csima. We then discuss how these results apply to homogeneous models. (shrink)

On definable filters in computably enumerable degrees.

We consider the ower semilattice [MATHEMATICAL SCRIPT CAPITAL D] of differences of c.e. sets under inclusion. It is shown that [MATHEMATICAL SCRIPT CAPITAL D] is not distributive as a semilattice, and that the c.e. sets form a definable subclass.

We give a first-order coding without parameters of a copy of in the computably enumerable weak truth table degrees. As a tool, we develop a theory of parameter definable subsets.

Say a set Gω is 1-generic if for any eω, there is a string σG such that {e}σ↓ or τσ↑). It is known that can be split into two 1-generic degrees. In this paper, we generalize this and prove that any nonzero computably enumerable degree can be split into two 1-generic degrees. As a corollary, no two computably enumerable degrees bound the same class of 1-generic degrees.

The purpose of this communication is to announce some recent results on the computably enumerable sets. There are two disjoint sets of results; the first involves invariant classes and the second involves automorphisms of the computably enumerable sets. What these results have in common is that the guts of the proofs of these theorems uses a new form of definable coding for the computably enumerable sets.We will work in the structure of the computably (...) enumerable sets. The language is just inclusion, ⊆. This structure is called ε.All sets will be computably enumerable non-computable sets and all degrees will be computably enumerable and non-computable, unless otherwise noted. Our notation and definitions are standard and follow Soare [1987]; however we will warm up with some definitions and notation issues so the reader need not consult Soare [1987]. Some historical remarks follow in Section 2.1 and throughout Section 3.We will also consider the quotient structure ε modulo the ideal of finite sets, ε*. ε* is a definable quotient structure of ε since “Χ is finite” is definable in ε; “Χ is finite” iff all subsets of Χ are computable. We use A* to denote the equivalent class of A under the ideal of finite sets. (shrink)

We investigate the orbit of a low computably enumerable set under automorphisms of the partial order of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of mapping A to a set B such that CTB. Thus, the orbit in of the low set A cannot be contained in the upper cone above C. This complements a result (...) of Harrington, who showed that the orbit of a noncomputable c.e. set cannot be contained in the lower cone below any incomplete c.e. set. (shrink)

If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by (...) showing that every tt-incomplete computably enumerable truth-table degree a is branching in ? tt . The fact that every Turing-incomplete computably enumerable truth-table degree is branching has been known for some time. This fact can be shown using a technique of Ambos-Spies and, as noticed by Nies, also follows from a relativization of a result of Degtev. We give a proof here using the Ambos-Spies technique because it has not yet appeared in the literature. The proof uses an infinite injury argument. Our main result is the proof when a is Turing-complete but tt-incomplete. Here we are able to exploit the Turing-completeness of a in a novel way to give a finite injury proof. (shrink)

In this paper, we prove that there exist computably enumerable degrees a and b such that $\mathbf{a} > \mathbf{b}$ and for any degree x, if x ≤ a and x is a minimal degree, then $\mathbf{x}.

It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best (...) possible in various senses. (shrink)

Given a class ℱ oft otal functions in the set oft he natural numbers, one could study the real numbers that have arbitrarily close rational approximations explicitly expressible by means of functions from ℱ. We do this for classes ℱsatisfying certain closedness conditions. The conditions in question are satisfied for example by the class of all recursive functions, by the class of the primitive recursive ones, by any of the Grzegorczyk classes ℰnwith n ≥ 2, by the class of all (...) functions recursive in a given function and by the class of the functions primitive recursive in it, as well as by the class of all total functions in the set of the natural numbers. (shrink)