Up to Equimorphism, Hyperarithmetic Is Recursive

Journal of Symbolic Logic 70 (2):360 - 378 (2005)
  Copy   BIBTEX

Abstract

Two linear orderings are equimorphic if each can be embedded into the other. We prove that every hyperarithmetic linear ordering is equimorphic to a recursive one. On the way to our main result we prove that a linear ordering has Hausdorff rank less than $\omega _{1}^{\mathit{CK}}$ if and only if it is equimorphic to a recursive one. As a corollary of our proof we prove that, given a recursive ordinal α, the partial ordering of equimorphism types of linear orderings of Hausdorff rank at most α ordered by embeddablity is recursively presentable

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,363

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.
On the equimorphism types of linear orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.
A recursion principle for linear orderings.Juha Oikkonen - 1992 - Journal of Symbolic Logic 57 (1):82-96.
Accessible recursive functions.Stanley S. Wainer - 1999 - Bulletin of Symbolic Logic 5 (3):367-388.
On Ehrenfeucht-fraïssé equivalence of linear orderings.Juha Oikkonen - 1990 - Journal of Symbolic Logic 55 (1):65-73.
A generalization of the limit lemma and clopen games.Peter Clote - 1986 - Journal of Symbolic Logic 51 (2):273-291.
0-1 laws for recursive structures.E. Grädel & A. Malmström - 1999 - Archive for Mathematical Logic 38 (4-5):205-215.

Analytics

Added to PP
2010-08-24

Downloads
43 (#273,915)

6 months
1 (#451,398)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Open questions in reverse mathematics.Antonio Montalbán - 2011 - Bulletin of Symbolic Logic 17 (3):431-454.
Mass problems and hyperarithmeticity.Joshua A. Cole & Stephen G. Simpson - 2007 - Journal of Mathematical Logic 7 (2):125-143.
Indecomposable linear orderings and hyperarithmetic analysis.Antonio Montalbán - 2006 - Journal of Mathematical Logic 6 (1):89-120.

View all 11 citations / Add more citations

References found in this work

The metamathematics of scattered linear orderings.P. Clote - 1989 - Archive for Mathematical Logic 29 (1):9-20.
Linear Orderings.Joseph G. Rosenstein - 1983 - Journal of Symbolic Logic 48 (4):1207-1209.

Add more references