Automorphisms of η-like computable linear orderings and Kierstead's conjecture

, &
Mathematical Logic Quarterly 62 (6):481-506 (2016)
  Copy   BIBTEX

Abstract

We develop an approach to the longstanding conjecture of Kierstead concerning the character of strongly nontrivial automorphisms of computable linear orderings. Our main result is that for any η-like computable linear ordering, such that has no interval of order type η, and such that the order type of is determined by a -limitwise monotonic maximal block function, there exists computable such that has no nontrivial automorphism.

Categories

Add categories

Keywords

Reprint years

DOI

10.1002/malq.201400109

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,853

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On Computable Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Bart Kastermans & Steffen Lempp - 2009 - Journal of Symbolic Logic 74 (4):1352 - 1366.
Computable choice functions for computable linear orderings.Manuel Lerman & Richard Watnick - 2003 - Mathematical Logic Quarterly 49 (5):485-510.
On Π 1-automorphisms of recursive linear orders.Henry A. Kierstead - 1987 - Journal of Symbolic Logic 52 (3):681-688.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Equivalence between Fraïssé’s conjecture and Jullien’s theorem.Antonio Montalbán - 2006 - Annals of Pure and Applied Logic 139 (1):1-42.
Partial automorphism semigroups.Jennifer Chubb, Valentina S. Harizanov, Andrei S. Morozov, Sarah Pingrey & Eric Ufferman - 2008 - Annals of Pure and Applied Logic 156 (2):245-258.
Degree spectra of the successor relation of computable linear orderings.Jennifer Chubb, Andrey Frolov & Valentina Harizanov - 2009 - Archive for Mathematical Logic 48 (1):7-13.
The metamathematics of scattered linear orderings.P. Clote - 1989 - Archive for Mathematical Logic 29 (1):9-20.
A recursion principle for linear orderings.Juha Oikkonen - 1992 - Journal of Symbolic Logic 57 (1):82-96.
Recursive automorphisms of recursive linear orderings.Steven Schwarz - 1984 - Annals of Pure and Applied Logic 26 (1):69-73.
Degrees of orderings not isomorphic to recursive linear orderings.Carl G. Jockusch & Robert I. Soare - 1991 - Annals of Pure and Applied Logic 52 (1-2):39-64.
Countably categorical coloured linear orders.Feresiano Mwesigye & John K. Truss - 2010 - Mathematical Logic Quarterly 56 (2):159-163.
A coding of the countable linear orderings.Patrick Dehornoy - 1990 - Studia Logica 49 (4):585 - 590.
On self-embeddings of computable linear orderings.Rodney G. Downey, Carl Jockusch & Joseph S. Miller - 2006 - Annals of Pure and Applied Logic 138 (1):52-76.
An Undecidable Linear Order That Is $n$-Decidable for All $n$.John Chisholm & Michael Moses - 1998 - Notre Dame Journal of Formal Logic 39 (4):519-526.

Analytics

Added to PP
2017-03-26

Downloads
29 (#550,776)

6 months
14 (#179,578)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Kierstead's Conjecture and limitwise monotonic functions.Guohua Wu & Maxim Zubkov - 2018 - Annals of Pure and Applied Logic 169 (6):467-486.

Add more citations

References found in this work

Computability Theory.Barry Cooper - 2010 - Journal of the Indian Council of Philosophical Research 27 (1).
Computability theory and linear orders.Rod Downey - 1998 - In I͡Uriĭ Leonidovich Ershov (ed.), Handbook of Recursive Mathematics. Elsevier. pp. 138--823.
Δ20-categoricity in Boolean algebras and linear orderings.Charles F. D. McCoy - 2003 - Annals of Pure and Applied Logic 119 (1-3):85-120.
< i> Δ_< sub> 2< sup> 0-categoricity in Boolean algebras and linear orderings.Charles F. D. McCoy - 2003 - Annals of Pure and Applied Logic 119 (1-3):85-120.
Η-representation of sets and degrees.Kenneth Harris - 2008 - Journal of Symbolic Logic 73 (4):1097-1121.

View all 11 references / Add more references