Strong Enumeration Reducibilities

Boris Solon (solon@icti.ivanovo.su)
Ivanovo University (Russia)

We will call a binary relation ú a on the 2w by the redusibility of sets if it is reflexive and transitive. If A ú aB« A ú eB for any sets A and B then ú a is called enumeration reducibility and if A ú aB« A ú T B then ú a is called decision reducibility. We will say that ú a is stronger than ú b if A ú aB« A ú bB for any sets A and B. It is clear that there are such different reducibilities at least 22w. Naturally we consider such reducibilities which have a intuitive base communicated with the effective computability. Some reducibilities are enumerable and decidable simmultaneously. For example the reducibilities of the truth-table type ú m, ú c, ú q, ú p, and also corresponding bounded redusibilities ú bc, ú bq, ú bp are the same.

In the article  [1] is constructed the digraph of enumeration reducibilities in which an oriented edge joins more and less strong reducibilies. In addition the new reducibilities ú fe, ú be, ú btte are located in this Cooper's digraph.

We note if ú a,..., ú b is a finite sequence of reducibilities from which at least one is a enumeration reducibility then the relation ú a...b on the 2w such that for any A and B

A ú a...bB<=> A ú a ... A ú bB
is the enumeration reducibility. In the article  [2] are formed 19 new reducibility by such way.

S. D. Zaharov proposed yet two enumeration redusibilities:

A ú npmB <=>$A1,  A2[A2-c.eA = A1+A2  A1 ú pmB]
and ú nm which results as ú npm by replacement ú pm on ú m.

In  [3] was introduced new enumeration reducibility ú wpmwhich was called as weak partial m-reducibility

A ú wpmB <=>($A1,...,Ak)[A = +A1+...+Ak  A1 ú pmB ...  Ak ú pmB].
Obviously ú pm is more strong reducibility than ú wpm, conversely it is not true. Let Dfpm = {dwpm(A):A - w} be the partialle ordered set of wpm-degrees.

Theorem 1. Dfpm is the upper semilattice with the least element 0 = dwpm(W) where W ¦ ãis c.e.

Theorem 2. Dfpm is not elementary equivalent Dpm.

Theorem 3. The reducibility ú wpm is located in Cooper's digraph.

With the help of such "weakening" of pm - reducibility it is possible to attempt to define new reducibilities. More exactly, let ú a be a reducibility, we define

A ú faB<=>($A1,...,Ak)[A = A1+...+Ak   A1 ú aB  ...  Ak ú aB].
It appears that in the case ú s and ú q new reducibilities will not be, and ú wpc is not a reducibility.

References

[1]
S.B. Cooper, e-reducibility using bounded information: counting minimal covers, Z.fur math.Logik und Grundlagen der Math. Bd.33(1987), 537-560
[2]
A.N.Degtev, About intersection of some classes of reducibilities, Mathematics, the Program Üniversities of Russia", MGU, 1994, 303-304.
[3]
B. Solon, The weak pm-reducibility, XI Conf. of Math. Logic, Abstract, Kazan, 1992, 131.