The Length Problem for Co-R.E. Sets

✍ Scribed by Martin Kummer

• Publisher: John Wiley and Sons
• Year: 1988
• Tongue: English
• Weight: 306 KB
• Volume: 34
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19880340311

✦ Synopsis

Let Fin be the set of finite functions defined on initial segments of o),

The length problem is stated as follows: "Characterize the sets L E cc) which satisfy R, u Fin@) r.e." [9]. It growed out of the work of W. MENZEL and V. SPERSCHNEIDER on r.e. extensions of R, by finite functions [a], [9J If L is r.e., then R, w Fin@) is r.e. iff L is infinite. Much more interesting is the case where L is co-r.e. V. SPERSCHNEIDER showed that if A is r.e. and not hypersimple then R, u Pin(A) is r.e,, but there are hypersimple sets A such that R, w Fin(A) is r.e., too. Especially, he constructed a maximal such set [9]. Constructions of r.e. coinfinite sets A such that R, w Fin(A) is not r.e. were given independently by

J. MOHRHERR [7] and the author [4].

Rather pathological situations arise if one considers sets L from Zg which are neither r.e. nor co-r.e.