The block relation in computable linear orders

DOI10.1215/00294527-1435465MaRDI QIDQ645746zbMATH OpenOpenAlexFDO

Authors Michael Moses

Publication date 10 November 2011

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.4286

zbMATH Keywords

block relationcomputable linear orderself-embedding

Mathematics Subject Classification ID

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

Abstract: A block in a linear order is an equivalence class when factored by the block relation B(x,y), satisfied by elements that are finitely far apart. 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 non-block relation eg B(x,y) computably enumerable. This implies that every computable linear order has a computable copy with a computable non-trivial self-embedding, and that the long-standing conjecture characterizing those computable linear orders every computable copy of which has a computable non-trivial self-embedding (as precisely those that contain an infinite, strongly eta-like interval) holds for all linear orders with dense condensation-type.

Recommendations

• On computable self-embeddings of computable linear orderings
• On maximal block functions of computable \(\eta \)-like linear orderings
• Computable choice functions for computable linear orderings
• Initial segments of computable linear orders with computable natural relations
• On Kierstead’s conjecture

Cited in

(5)

• A computably enumerable partial ordering without computably enumerable maximal chains and antichains
• Computable linear orders and limitwise monotonic functions
• Codings on linear orders and algorithmic independence of natural relations
• On limitwise monotonicity and maximal block functions
• The complexity of the successor and the block relations on computable linear orders

This page was built for publication: The block relation in computable linear orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645746)