The block relation in computable linear orders. (English) Zbl 1260.03085

Moses, Michael

Notre Dame J. Formal Logic 52, No. 3, 289-305 (2011).

Summary: 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 \(\eta \)-like interval (i.e., with all blocks of size less than some fixed, finite \(k\)) has a computable copy with the nonblock relation \(\lnot 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 \(\eta \)-like interval) holds for all linear orders with dense condensation-type.

MSC:

03D45	Theory of numerations, effectively presented structures
03C57	Computable structure theory, computable model theory

Keywords:

computable linear order; block relation; self-embedding