Definable incompleteness and Friedberg splittings

Journal of Symbolic Logic 67 (2):679-696 (2002)

Abstract

We define a property R(A 0 , A 1 ) in the partial order E of computably enumerable sets under inclusion, and prove that R implies that A 0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A 0 and A 1 which we build satisfying R form a Friedberg splitting of their union A, with A 1 prompt and A promptly simple. We conclude that A 0 and A 1 lie in distinct orbits under automorphisms of E, yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,856

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2009-01-28

Downloads
23 (#498,366)

6 months
1 (#386,016)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 37 (8):113-120.
Jumps of Hemimaximal Sets.Rod Downey & Mike Stob - 1991 - Mathematical Logic Quarterly 37 (8):113-120.
Friedberg Splittings of Recursively Enumerable Sets.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 59 (3):175-199.

View all 6 references / Add more references

Citations of this work

No citations found.

Add more citations

Similar books and articles