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

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)
Reprint years 2011
DOI 10.1215/00294527-1435465
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,290
Through your library

References found in this work BETA

Hiearchies of Boolean Algebras.Lawrence Feiner - 1970 - Journal of Symbolic Logic 35 (3):365-374.
Relations Intrinsically Recursive in Linear Orders.Michael Moses - 1986 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 32 (25-30):467-472.
Relations Intrinsically Recursive in Linear Orders.Michael Moses - 1986 - Mathematical Logic Quarterly 32 (25‐30):467-472.

View all 7 references / 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.
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.

Analytics

Added to PP index
2011-07-29

Total views
26 ( #441,383 of 2,519,270 )

Recent downloads (6 months)
1 ( #407,861 of 2,519,270 )

How can I increase my downloads?

Downloads

My notes