The Block Relation in Computable Linear Orders

Notre Dame Journal of Formal Logic 52 (3):289-305 (2011)
  Copy   BIBTEX

Abstract

The block relation B(x,y) in a linear order is satisfied by elements that are finitely far apart; a block is an equivalence class under this relation. We show that every computable linear order with dense condensation-type (i.e., a dense collection of blocks) but no infinite, strongly η-like interval (i.e., with all blocks of size less than some fixed, finite k ) has a computable copy with the nonblock relation ¬ B(x,y) computably enumerable. This implies that every computable linear order has a computable copy with a computable nontrivial self-embedding and that the long-standing conjecture characterizing those computable linear orders every computable copy of which has a computable nontrivial self-embedding (as precisely those that contain an infinite, strongly η-like interval) holds for all linear orders with dense condensation-type

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,369

External links

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

Through your library

Similar books and articles

The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Decidable discrete linear orders.M. Moses - 1988 - Journal of Symbolic Logic 53 (2):531-539.
WHAT IS. . . a Halting Probability?Cristian S. Calude - 2010 - Notices of the AMS 57:236-237.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.
Infinite chains and antichains in computable partial orderings.E. Herrmann - 2001 - Journal of Symbolic Logic 66 (2):923-934.
Degree spectra of intrinsically C.e. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
Computable structures and the hyperarithmetical hierarchy.C. J. Ash - 2000 - New York: Elsevier. Edited by J. Knight.

Analytics

Added to PP
2011-07-29

Downloads
33 (#487,893)

6 months
3 (#984,149)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Hiearchies of Boolean algebras.Lawrence Feiner - 1970 - Journal of Symbolic Logic 35 (3):365-374.
Relations Intrinsically Recursive in Linear Orders.Michael Moses - 1986 - Mathematical Logic Quarterly 32 (25-30):467-472.
Relations Intrinsically Recursive in Linear Orders.Michael Moses - 1986 - Mathematical Logic Quarterly 32 (25‐30):467-472.
On Π 1-automorphisms of recursive linear orders.Henry A. Kierstead - 1987 - Journal of Symbolic Logic 52 (3):681-688.

View all 7 references / Add more references