Affiliations: University of Notre Dame, Department of Mathematics, 255 Hurley Hall, Notre Dame, IN 46556 USA, [email protected] | Westfield State University, Department of Mathematics, 577 Western Avenue, Westfield, MA 01086 USA, [email protected] | University of Notre Dame, Department of Mathematics, 255 Hurley Hall, Notre Dame, IN 46556 USA, [email protected] | Wellesley College, Department of Mathematics, 106 Central Street, Wellesley, MA 02481 USA, [email protected] | University of Portland, 5000 N. Willamette Blvd., Portland, OR 97203-5798 USA, [email protected] | East Mennonite University, Department of Mathematical Sciences, 1200 Park Road, Harrisonburg, VA 22802 USA, [email protected]
Abstract: We continue work from (Greenberg and Knight) on computable structure theory in the setting of $\omega_1$, where the countable ordinals play the role of natural numbers, and countable sets play the role of finite sets. In the present paper, we define the arithmetical hierarchy through all countable levels (not just the finite levels). We consider two different ways of doing this—one based on the standard definition of the hyperarithmetical hierarchy, and the other based on the standard definition of the effective Borel hierarchy. For each definition, we define computable infinitary formulas through all countable levels, and we obtain analogues of the well-known results from (Ash and Knight, 1989) and (Chisholm, 1990) saying that a relation is relatively intrinsically $\Sigma^0_\alpha$ just in case it is definable by a computable $\Sigma_\alpha$ formula. Although we obtain the same results for the two definitions of the arithmetical hierarchy, we conclude that the definition resembling the standard definition of the hyperarithmetical hierarchy seems preferable.
DOI: 10.3233/COM-13022
Journal: Computability, vol. 2, no. 2, pp. 93-105, 2013