On the structure of sw-degrees of c.e. reals sets: some observations
by
Yun fan
Nanjing University

This talk will go on further with the structure of sw-degrees of c.e. reals (sets).

Motivated by the shortcomings of Solovay reducibility, Downey, Hirschfeldt and LaForte [] introduced the strong weak truth table reducibility or sw-reducibility for short, which it might serve as a measure of relative randomness. We say a ≤ _sw b if there is a Turing functional G and a constant c such that a = G^b and the use of G on any argument n is bounded by n+c.

The structure of the sw-degrees of c.e. reals is not a lower semi-lattice. However, it is also not an upper semi-lattice. This property was first proved directly by Downey, LaForte, and Hirschfeldt [], but follows from the next result by Yu and Ding []: there are two c.e. reals a and b such that there is no c.e. real g with a ≤ _sw g and b ≤ _swg. Thus we say the sw-degree a is sw-cuppable if there exists an sw-degree b of c.e. reals such that no sw-degrees of c.e. reals can sw-compute both of them.

On sw-cuppable, there exist sw-cuppable sw-degrees of c.e. reals (an sw-cuppable version: Yu and Ding []); there exist sw-cuppable sw-degrees of c.e. sets (Fan []). Different from the no injury method proving such results, we show that by a genuine finite injury method:

[Fan and Yu []] Every sw-degree [a\tilde] ≠ [0\tilde] of D₂⁰ reals is sw-cuppable. That is, for a given non-computable D₂⁰ real a, there is a c.e. real b so that no c.e. real can sw-compute both of them.

We say a pair of c.e. sets A and B is a sw-maximal pair if ¬C c.e.[A ≤ _sw C & B ≤ _sw C]. By the following theorem, it shows that whether a c.e. set is half of a sw-maximal pair or not depends on how complex it is.

[Ambos-spies et al.[]] For a c.e. wtt-degree [a\tilde], [a\tilde] is array non-computable if and only there exists a c.e. set A ∈ [a\tilde] such that A is half of a sw-maximal pair.

[Ambos-spies et al.[]] Every wtt-complete c.e. set is half of a sw-maximal pair; there exists a T-complete c.e. set which is not half of a sw-maximal pair.

Although the sw-degrees present such difficulties, the structure of the sw-degrees is very interesting from a wider perspective.

References

[]

Klaus Ambos-spies, Decheng Ding, Wolfgang Merkle, Yun Fan. On the sw-Degrees of the Computably Enumerable Sets: Some Observations and Open Problems. To be submitted.

[]

Rodney G. Downey, Denis Hirschfeldt. Randomness and reducibility. Springer-Verlag Monographs in Computer Science. Preparation.

[]

Yun Fan. There is an sw-cuppable strongly c.e. real. Lecture Notes of Compute Scinece, TAMC 2007.

[]

Yun Fan and Liang Yu. Every cl-degree of non-computable D₂⁰ reals is cl-cuppable. To be submitted.

[]

Liang Yu and Decheng Ding. There is no SW-complete c.e. real. J. Symbolic Logic, 2004, 69 (4), 1163-1170.

PDF

Date received: April 16, 2008