The Journal of Symbolic Logic

Research Article

Up to equimorphism, hyperarithmetic is recursive

Antonio Montalbán

Department of Mathematics, Cornell University, Ithaca, NY 14853, USA, E-mail: antonio@math.cornell.edu URL: www.math.cornell.edu/~antonio

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 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.

(Received July 22 2004)

(Revised October 04 2004)