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 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,701 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesAmir Leshem (2000). On the Consistency of the Definable Tree Property on ℵ. Journal of Symbolic Logic 65 (3):1204 - 1214.
David Lippel (2005). Finitely Axiomatizable Ω-Categorical Theories and the Mazoyer Hypothesis. Journal of Symbolic Logic 70 (2):460 - 472.
Michael A. Jahn (1999). Implicit Measurements of Dynamic Complexity Properties and Splittings of Speedable Sets. Journal of Symbolic Logic 64 (3):1037-1064.
Roland SH Omanadze (2004). Splittings of Effectively Speedable Sets and Effectively Levelable Sets. Journal of Symbolic Logic 69 (1):143-158.
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.
Peter A. Cholak, Rodney Downey & Leo A. Harrington (2008). The Complexity of Orbits of Computably Enumerable Sets. The Bulletin of Symbolic Logic 14 (1):69 - 87.
Marcus Kracht (1993). Splittings and the Finite Model Property. Journal of Symbolic Logic 58 (1):139-157.
Kevin Wald (2002). On Orbits of Prompt and Low Computably Enumerable Sets. Journal of Symbolic Logic 67 (2):649-678.
Leo Harrington & Robert I. Soare (1998). Codable Sets and Orbits of Computably Enumerable Sets. Journal of Symbolic Logic 63 (1):1-28.
Todd Hammond (1999). Friedberg Splittings in Σ03 Quotient Lattices of E. Journal of Symbolic Logic 64 (4):1403 - 1406.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
