Hostname: page-component-7b7567c8c-w7t8q Total loading time: 0 Render date: 2026-11-17T21:21:28.867Z Has data issue: false hasContentIssue false

Definable incompleteness and Friedberg splittings

Published online by Cambridge University Press:  12 March 2014

Russell Miller*
Affiliation:
Department of Mathematics, University of Chicago, Chicago, Illinois 60637, USA
*
Department of Mathematics, Cornell University, Ithaca, New York 14853, USA, E-mail: russell@math.cornell.edu

Abstract

We define a property R(A0, A1) in the partial order of computably enumerable sets under inclusion, and prove that R implies that A0 is noncomputable and incomplete. Moreover, the property is nonvacuous. and the A0 and A1 which we build satisfying R form a Friedberg splitting of their union A, with A1 prompt and A promptly simple. We conclude that A0 and A1 lie in distinct orbits under automorphisms of , 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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable