We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...) n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0. (shrink)
We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for recursive formulas. (...) We also show that Ramsey's Theorem for Pairs is strong enough to prove some sentences in first order arithmetic which are not provable within . In particular, Ramsey's Theorem for Pairs is not conservative over for -sentences. (shrink)
We show that every nontrivial interval in the recursively enumerable degrees contains an incomparable pair which have an infimum in the recursively enumerable degrees.
We investigate the question “To what extent can random reals be used as a tool to establish number theoretic facts?” Let $\text{2-\textit{RAN\/}}$ be the principle that for every real $X$ there is a real $R$ which is 2-random relative to $X$. In Section 2, we observe that the arguments of Csima and Mileti [3] can be implemented in the base theory $\text{\textit{RCA}}_0$ and so $\text{\textit{RCA}}_0+\text{2-\textit{RAN\/}}$ implies the Rainbow Ramsey Theorem. In Section 3, we show that the Rainbow Ramsey Theorem is (...) not conservative over $\text{\textit{RCA}}_0$ for arithmetic sentences. Thus, from the Csima—Mileti fact that the existence of random reals has infinitary-combinatorial consequences we can conclude that $\text{2-\textit{RAN\/}}$ has non-trivial arithmetic consequences. In Section 4, we show that $\text{2-\textit{RAN\/}}$ is conservative over $\text{\textit{RCA}}_0+\text{\textit{B\/}$\,\Sigma$}_2$ for $\Pi^1_1$-sentences. Thus, the set of first-order consequences of $\text{2-\textit{RAN\/}}$ is strictly stronger than $P^-+I\Sigma_1$ and no stronger than $P^-+\text{\textit{B\/}$\,\Sigma$}_2$. (shrink)
We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.
We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.
We show there is a non-recursive r.e. set A such that if W is any low r.e. set, then the join W $\oplus$ A is also low. That is, A is "almost deep". This answers a question of Jockusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.).
We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P -) together with Σ 2 -collection (BΣ 2 ). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither low n nor (...) high n - 1 , while true, cannot be established in P - + BΣ n + 1 . Consequently, no bounded fragment of first order arithmetic establishes the facts that the high n and low n jump hierarchies are proper on the recursively enumerable degrees. (shrink)
Posner [6] has shown, by a nonuniform proof, that every ▵ 0 2 degree has a complement below 0'. We show that a 1-generic complement for each ▵ 0 2 set of degree between 0 and 0' can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above $\varnothing'$ . In the second half of the paper, we show that the complementation (...) of the degrees below 0' does not extend to all recursively enumerable degrees. Namely, there is a pair of recursively enumerable degrees a above b such that no degree strictly below a joins b above a. (This result is independently due to S. B. Cooper.) We end with some open problems. (shrink)
We show that if there is a nonconstructible real, then every perfect set has a nonconstructible element, answering a question of K. Prikry. This is a specific instance of a more general theorem giving a sufficient condition on a pair $M\subset N$ of models of set theory implying that every perfect set in N has an element in N which is not in M.
J. Łoś raised the following question: Under what conditions can a countable partially ordered set be extended to a dense linear order merely by adding instances of comparability ? We show that having such an extension is a Σ 1 l -complete property and so there is no Borel answer to Łoś's question. Additionally, we show that there is a natural Π 1 l -norm on the partial orders which cannot be so extended and calculate some natural ranks in that (...) norm. (shrink)
Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no (...) deep degrees other than the recursive one. Given a set W, we enumerate a set A and approximate its jump. The construction of A is governed by strategies, indexed by the Turning functionals Φ. Simplifying the situation, a typical strategy converts a failure to recursively compute W into a constraint on the enumeration of A, so that $(W \bigoplus A)'$ is forced to disagree with Φ(-; A'). The conversion has some ambiguity; in particular, A cannot be found uniformly from W. We also show that there is a "moderately" deep degree: There is a low nonzero degree whose join with any other low degree is not high. (shrink)
There is a comeager set C contained in the set of 1-generic reals and a first order structure M such that for any real number X, there is an element of C which is recursive in X if and only if there is a presentation of M which is recursive in X.
E -recursive enumerability is compared via forcing to Σ 1 definability. It is shown that for every countable E -closed ordinal κ there is a set of reals, X , so that L κ [ X ] is the least E -closed structure over X.
We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.
The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.
Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about (...) when these degrees are trivial, and when the degrees are omniscient. (shrink)
We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.
We consider questions related to the rigidity of the structure R, the PTIME-Turing degrees of recursive sets of strings together with PTIME-Turing reducibility, pT, and related structures; do these structures have nontrivial automorphisms? We prove that there is a nontrivial automorphism of an ideal of R. This can be rephrased in terms of partial relativizations. We consider the sets which are PTIME-Turing computable from a set A, and call this class PTIMEA. Our result can be stated as follows: There is (...) an oracle, A, relative to which the PTIME-Turing degrees are not rigid . Furthermore, the automorphism can be made to preserve the complexity classes DTIMEA for all k 1, or to move any DTIMEA for n 2. From the existence of such an automorphism we conclude as a corollary that there is an oracle A relative to which the classes DTIME are not definable over R. We carry out the corresponding partial relativization for the many-one degrees to construct an oracle, A, relative to which the PTIMA-many-one degrees relative to A have a nontrivial automorphism, and one relative to which the lattice of sets in PTIMEA under inclusion have a nontrivial automorphism. The proof is phrased as a forcing argument; we construct the set A to meet a particular collection of dense sets in our notion of forcing. Roughly, the dense sets will guarantee that if A meets these sets and we split A into two pieces, A0 and A1, in a simple way, and then switching the roles of A0 and A1 in all computations from A will produce an automorphism of the ideal of PTIMA-degrees below A. We force A0 and A1 to have different PTIME-Turing degree; this will then make the automorphism nontrivial. An appropriately generic set A is constructed using a priority argument. (shrink)
Let A and B be subsets of the reals. Say that A κ ≥ B, if there is a real a such that the relation "x ∈ B" is uniformly Δ 1 (a, A) in L[ ω x,a,A 1 , x,a,A]. This reducibility induces an equivalence relation $\equiv_\kappa$ on the sets of reals; the $\equiv_\kappa$ -equivalence class of a set is called its Kleene degree. Let K be the structure that consists of the Kleene degrees and the induced partial order (...) K ≥. A substructure of K that is of interest is P, the Kleene degrees of the Π 1 1 sets of reals. If sharps exist, then there is not much to P, as Steel [9] has shown that the existence of sharps implies that P has only two elements: the degree of the empty set and the degree of the complete Π 1 1 set. Legrand [4] used the hypothesis that there is a real whose sharp does not exist to show that there are incomparable elements in P; in the context of V = L, Hrbacek has shown that P is dense and has no minimal pairs. The Hrbacek results led Simpson [6] to make the following conjecture: if V = L, then p forms a universal homogeneous upper semilattice with 0 and 1. Simpson's conjecture is shown to be false by showing that if V = L, then Godel's maximal thin Π 1 1 set is the infimum of two strictly larger elements of P. The second main result deals with the notion of jump in K. Let A' be the complete Kleene enumerable set relative to A. Say that A is low-n if A (n) has the same degree as $\varnothing^{(n)}$ , and A is high-n if A (n) has the same degree as $\varnothing^{(n + 1)}$ . Simpson and Weitkamp [7] have shown that there is a high (high-1) incomplete Π 1 1 set in L. They have also shown that various other Π 1 1 sets are neither high nor low in L. Legrand [5] extended their results by showing that, if there is a real x such that x # does not exist, then there is an element of P that, for all n, is neither low-n nor high-n. In § 2, ZFC is used to show that, for all n, if A is Π 1 1 and low-n then A is Borel. The proof uses a strengthened version of Jensen's theorem on sequences of admissible ordinals that appears in [7, Simpson-Weitkamp]. (shrink)
We solve a question of McLaughlin by showing that if A is a regressive co-simple isol, there is a co-simple regressive isol B such that the intersection type of A and B is trivial. The proof is a nonuniform 0 priority argument that can be viewed as the execution of a single strategy from a 0-argument. We establish some limit on the properties of such pairs by showing that if AxB has low degree, then the intersection type of A and (...) B cannot be trivial. (shrink)
In this paper we study the question as to which computable algebras are isomorphic to non-computable $\Pi_{1}^{0}$ -algebras. We show that many known algebras such as the standard model of arithmetic, term algebras, fields, vector spaces and torsion-free abelian groups have non-computable $\Pi_{1}^{0}$ -presentations. On the other hand, many of this structures fail to have non-computable $\Sigma_{1}^{0}$ -presentation.
Theorem. There is a non-empty Π10 class of reals, each of which computes a real of minimal degree. Corollary. WKL “there is a minimal Turing degree”. This answers a question of H. Friedman and S. Simpson.
