Do you want to publish a course? Click here

A bounded jump for the bounded Turing degrees

107   0   0.0 ( 0 )
 Added by Bernard Anderson II
 Publication date 2010
  fields
and research's language is English




Ask ChatGPT about the research

We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate several properties of the bounded jump, including that it is strictly increasing and order preserving on the bounded Turing (bT) degrees (also known as the weak truth-table degrees). We show that the bounded jump is related to the Ershov hierarchy. Indeed, for n > 1 we have X <=_[bT] 0^[nb] iff X is omega^n-c.e. iff X <=_1 0^[nb], extending the classical result that X <=_[bT] 0 iff X is omega-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every X such that 0^b <=_[bT] X <=_[bT] 0^[2b], there is a Y <=_[bT] 0^b such that Y^b =_[bT] X.

rate research

Read More

The Posner-Robinson Theorem states that for any reals $Z$ and $A$ such that $Z oplus 0 leq_mathrm{T} A$ and $0 <_mathrm{T} Z$, there exists $B$ such that $A equiv_mathrm{T} B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus 0$. Consequently, any nonzero Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a Turing jump relative to some $B$. Here we prove the hyperarithmetical analog, based on an unpublished proof of Slaman, namely that for any reals $Z$ and $A$ such that $Z oplus mathcal{O} leq_mathrm{T} A$ and $0 <_mathrm{HYP} Z$, there exists $B$ such that $A equiv_mathrm{T} mathcal{O}^B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus mathcal{O}$. As an analogous consequence, any nonhyperarithmetical Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a hyperjump relative to some $B$.
121 - Mingyang Li , Jan Reimann 2019
We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the dissipation function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing degrees. In particular, we show that every $Delta^0_2$-degree contains an NCR element.
109 - Tomasz Rzepecki 2018
We study strong types and Galois groups in model theory from a topological and descriptive-set-theoretical point of view, leaning heavily on topological dynamical tools. More precisely, we give an abstract (not model theoretic) treatment of problems related to cardinality and Borel cardinality of strong types, quotients of definable groups and related objecets, generalising (and often improving) essentially all hitherto known results in this area. In particular, we show that under reasonable assumptions, strong type spaces are locally quotients of compact Polish groups. It follows that they are smooth if and only if they are type-definable, and that a quotient of a type-definable group by an analytic subgroup is either finite or of cardinality at least continuum.
We generalise the main theorems from the paper The Borel cardinality of Lascar strong types by I. Kaplan, B. Miller and P. Simon to a wider class of bounded invariant equivalence relations. We apply them to describe relationships between fundamental properties of bounded invariant equivalence relations (such as smoothness or type-definability) which also requires finding a series of counterexamples. Finally, we apply the generalisation mentioned above to prove a conjecture from a paper by the first author and J. Gismatullin, showing that the key technical assumption of the main theorem (concerning connected components in definable group extensions) from that paper is not only sufficient but also necessary to get the conclusion.
A definable set in a pair (K, k) of algebraically closed fields is co-analyzable relative to the subfield k of the pair if and only if it is almost internal to k. To prove this and some related results for tame pairs of real closed fields we introduce a certain kind of bounded pregeometry for such pairs.
comments
Fetching comments Fetching comments
Sign in to be able to follow your search criteria
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا