Degrees of orderings not isomorphic to recursive linear orderings

Annals of Pure and Applied Logic 52 (1-2):39-64 (1991)
  Copy   BIBTEX

Abstract

It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low degree. Finally, an analogue of the recursion theorem for recursive linear orderings is refuted

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,310

External links

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

Through your library

Similar books and articles

A Construction for Recursive Linear Orderings.C. J. Ash - 1991 - Journal of Symbolic Logic 56 (2):673-683.
A Recursion Principle for Linear Orderings.Juha Oikkonen - 1992 - Journal of Symbolic Logic 57 (1):82-96.
The Metamathematics of Scattered Linear Orderings.P. Clote - 1989 - Archive for Mathematical Logic 29 (1):9-20.
Up to Equimorphism, Hyperarithmetic Is Recursive.Antonio Montalbán - 2005 - Journal of Symbolic Logic 70 (2):360 - 378.
A Coding of the Countable Linear Orderings.Patrick Dehornoy - 1990 - Studia Logica 49 (4):585 - 590.
Countably Categorical Coloured Linear Orders.Feresiano Mwesigye & John K. Truss - 2010 - Mathematical Logic Quarterly 56 (2):159-163.
Recursive Automorphisms of Recursive Linear Orderings.Steven Schwarz - 1984 - Annals of Pure and Applied Logic 26 (1):69-73.
Belief Revision and Verisimilitude.Mark Ryan & Pierre-Yves Schobbens - 1995 - Notre Dame Journal of Formal Logic 36 (1):15-29.
Cognitive Processing of Linear Orderings.Karl W. Scholz & George R. Potts - 1974 - Journal of Experimental Psychology 102 (2):323.
Recursive Linear Orderings and Hyperarithmetical Functions.Shih-Chao Liu - 1962 - Notre Dame Journal of Formal Logic 3 (3):129-132.

Analytics

Added to PP
2014-01-16

Downloads
14 (#725,071)

6 months
1 (#415,900)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Up to Equimorphism, Hyperarithmetic Is Recursive.Antonio Montalbán - 2005 - Journal of Symbolic Logic 70 (2):360 - 378.
D-Computable Categoricity for Algebraic Fields.Russell Miller - 2009 - Journal of Symbolic Logic 74 (4):1325 - 1351.
On the Equimorphism Types of Linear Orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.

View all 21 citations / Add more citations

References found in this work

Recursive Well-Orderings.Clifford Spector - 1955 - Journal of Symbolic Logic 20 (2):151-163.
Degrees Coded in Jumps of Orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Degrees of Structures.Linda Jean Richter - 1981 - Journal of Symbolic Logic 46 (4):723-731.

Add more references