The Block Relation in Computable Linear Orders

Notre Dame Journal of Formal Logic 52 (3):289-305 (2010)
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
Keywords computable linear order   block relation   self-embedding
Categories (categorize this paper)
Options
 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: 12,101
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.

Citations of this work BETA

No citations found.

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.
Analytics

Monthly downloads

Added to index

2011-07-29

Total downloads

4 ( #267,964 of 1,102,113 )

Recent downloads (6 months)

1 ( #306,622 of 1,102,113 )

How can I increase my downloads?

My notes
Sign in to use this feature


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