The Block Relation in Computable Linear Orders

Notre Dame Journal of Formal Logic 52 (3):289-305 (2011)
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)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 29,841
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
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.
The Δ02-Spectrum of a Linear Order.Russell Miller - 2001 - Journal of Symbolic Logic 66 (2):470 - 486.
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. Herrman - 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.
Added to PP index

Total downloads
15 ( #345,349 of 2,210,291 )

Recent downloads (6 months)
1 ( #387,753 of 2,210,291 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature