David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 67 (2):679-696 (2002)
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
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Amir Leshem (2000). On the Consistency of the Definable Tree Property on ℵ. Journal of Symbolic Logic 65 (3):1204 - 1214.
Leo Harrington & Robert I. Soare (1998). Codable Sets and Orbits of Computably Enumerable Sets. Journal of Symbolic Logic 63 (1):1-28.
Kevin Wald (2002). On Orbits of Prompt and Low Computably Enumerable Sets. Journal of Symbolic Logic 67 (2):649-678.
Marcus Kracht (1993). Splittings and the Finite Model Property. Journal of Symbolic Logic 58 (1):139-157.
Peter A. Cholak, Rodney Downey & Leo A. Harrington (2008). The Complexity of Orbits of Computably Enumerable Sets. Bulletin of Symbolic Logic 14 (1):69 - 87.
Robert A. Di Paola (1981). A Lift of a Theorem of Friedberg: A Banach-Mazur Functional That Coincides with No Α-Recursive Functional on the Class of Α-Recursive Functions. Journal of Symbolic Logic 46 (2):216 - 232.
Roland SH Omanadze (2004). Splittings of Effectively Speedable Sets and Effectively Levelable Sets. Journal of Symbolic Logic 69 (1):143-158.
Michael A. Jahn (1999). Implicit Measurements of Dynamic Complexity Properties and Splittings of Speedable Sets. Journal of Symbolic Logic 64 (3):1037-1064.
David Lippel (2005). Finitely Axiomatizable Ω-Categorical Theories and the Mazoyer Hypothesis. Journal of Symbolic Logic 70 (2):460 - 472.
Todd Hammond (1999). Friedberg Splittings in Σ03 Quotient Lattices of E. Journal of Symbolic Logic 64 (4):1403 - 1406.
Sorry, there are not enough data points to plot this chart.
Added to index2009-01-28
Total downloads4 ( #247,637 of 1,096,771 )
Recent downloads (6 months)4 ( #73,973 of 1,096,771 )
How can I increase my downloads?