Abstract/Details

Some properties of recursively enumerable sets uniform for equivalence relations

Ye, Hong.   University of Connecticut ProQuest Dissertations Publishing,  1988. 8916146.

Abstract (summary)

In Jockush, Lerman, Soare and Solovay's joint paper, the following equivalence reactions over (r.e.) sets A and B were introduced: (1) A $\sim\sb0$ B means that A = B. (2) A $\sim\sb1$ B means that A = *B. (where a = * B means A and B differ finitely.) (3) A $\sim\sb2$ B means that A $\equiv\sb{T}$ B. (4) A $\sim\sb{n}$ B where n $>$ 2 means that $A\sp{\rm (n-2)}\equiv\sb{T}B\sp{\rm (n-2)}$. (5) A $\sim\sb{\omega}$ B means that A $\sim\sb{n}$ B for some n $<$ $\omega$.<p> Many elementary properties of the degrees of r.e. sets, such as the existence of intermediate degrees between 0 and 0$\sp\prime$ and the Sacks splitting theorem have been studied. What we are trying to answer are the questions like: is there a version of those theorems which is uniform for the above equivalence relations? We are able to prove some uniform versions and reject some others. We are interested in the following questions: (1) Is there an e such that for every set $B\sb{T}\geq\emptyset\sp\prime$, if $C\sb{B}$ = $\varphi\sbsp{e}{B}$ then $C\sb{B}\sp\prime$ $\equiv\sb{T}C\sb{B}\oplus\emptyset\sp\prime$, and if B $\sim\sb{m}$ A, then $C\sb{B}\sim\sb{n}C\sb{A}$ where m, n $\in$ $\omega$? (2) For m, n $\in$ $\omega$, is there an e such that if X $\sim\sb{m}$ Y then $W\sbsp{e}{X}$ $\sim\sb{n}W\sbsp{e}{Y}$? where for all set X, X $<$ $W\sbsp{e}{X}<$ X$\sp\prime$. (3) Are there any recursive functions f and g such that for any $X\subset\omega$, $e \in \omega$, $W\sbsp{f(e)}{X}$, $W\sbsp{g(e)}{X}$ split $W\sbsp{e}{X}$ and for t, m, n $\in$ $\omega$, X, Y $\subset\omega$, if $X \sim\sb{t}Y$ and $W\sbsp{e}{X}\oplus X\sim\sb{m}W\sbsp{t}{Y}\oplus Y > X(or Y)$, then $W\sbsp{f(e)}{X}\oplus X\sim\sb{n}W\sbsp{f(i)}{Y}\oplus Y$, $W\sbsp{g(e)}{X}$ $\oplus$ X $\sim\sb{n}W\sbsp{g(i)}{Y}\oplus Y$?

Since the cases for t = m are the most interesting, we concentrate on dealing with the t = m cases.

Usually, when m, n are large enough (say $\geq$ 3), it's easy to find the answers. Most of the work has been done for m, n = 0, 1, or 2 (sometimes 3). Generally, we present counterexamples when m $>$ n and prove uniform versions otherwise. The open cases are when m = n = 2 and sometimes, when n = 1 and m = 2.

Indexing (details)


Subject
Mathematics
Classification
0405: Mathematics
Identifier / keyword
Pure sciences
Title
Some properties of recursively enumerable sets uniform for equivalence relations
Author
Ye, Hong
Number of pages
51
Degree date
1988
School code
0056
Source
DAI-B 50/06, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
979-8-207-00801-1
Advisor
Lerman, Manuel
University/institution
University of Connecticut
University location
United States -- Connecticut
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
8916146
ProQuest document ID
303709151
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/303709151/abstract