Up to Equimorphism, Hyperarithmetic Is Recursive
Journal of Symbolic Logic 70 (2):360 - 378 (2005)
| 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 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,631 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesC. J. Ash (1991). A Construction for Recursive Linear Orderings. Journal of Symbolic Logic 56 (2):673-683.
Antonio Montalbán (2007). On the Equimorphism Types of Linear Orderings. Bulletin of Symbolic Logic 13 (1):71-99.
Juha Oikkonen (1992). A Recursion Principle for Linear Orderings. Journal of Symbolic Logic 57 (1):82-96.
Antonio Montalbán (2006). Indecomposable Linear Orderings and Hyperarithmetic Analysis. Journal of Mathematical Logic 6 (01):89-120.
Stanley S. Wainer (1999). Accessible Recursive Functions. Bulletin of Symbolic Logic 5 (3):367-388.
Juha Oikkonen (1990). On Ehrenfeucht-Fraïssé Equivalence of Linear Orderings. Journal of Symbolic Logic 55 (1):65-73.
Dev K. Roy & Richard Watnick (1988). Finite Condensations of Recursive Linear Orders. Studia Logica 47 (4):311 - 317.
Serge Grigorieff (1990). Every Recursive Linear Ordering has a Copy in Dtime-Space (N, Log(N)). Journal of Symbolic Logic 55 (1):260-276.
Peter Clote (1986). A Generalization of the Limit Lemma and Clopen Games. Journal of Symbolic Logic 51 (2):273-291.
E. Grädel & A. Malmström (forthcoming). 0-1 Laws for Recursive Structures. Archive for Mathematical Logic.
Richard Watnick (1984). A Generalization of Tennenbaum's Theorem on Effectively Finite Recursive Linear Orderings. Journal of Symbolic Logic 49 (2):563-569.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2010-08-24Total downloads0Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
