The Block Relation in Computable Linear Orders

Notre Dame Journal of Formal Logic 52 (3):289-305 (2010)
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
Keywords computable linear order   block relation   self-embedding
Categories (categorize this paper)
DOI 10.1215/00294527-1435465
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 24,453
External links
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.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
M. Moses (1988). Decidable Discrete Linear Orders. Journal of Symbolic Logic 53 (2):531-539.
Russell Miller (2001). The Δ02-Spectrum of a Linear Order. Journal of Symbolic Logic 66 (2):470 - 486.
Jeremy Avigad (2012). Uncomputably Noisy Ergodic Limits. Notre Dame Journal of Formal Logic 53 (3):347-350.

Monthly downloads

Added to index


Total downloads

14 ( #313,209 of 1,925,265 )

Recent downloads (6 months)

2 ( #308,589 of 1,925,265 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.