As I understand, hyperarithmetical sets are defined according to the analytical hierarchy, that is, second-order-logic formulas. There is a generalization of hyperarithmetic theory named α-recursion theory. Do this extension generalizes the hyperarithmetical sets to sets definable with any arbitrary higher-order logic?

NOTE: I know that α-recursion theory extends the hyperarithmetical sets from ${\omega}_1^{CK} $ to any admissible ordinals, but I have no clue what that means or what is the relationship between ordinals and the number N in Nth-order logic). My question in the end is motivated by the fact that the hyperarithmetical sets can be defined using infinitely iterated Turing jumps, and I wonder if this can be generalized to sets defined by any arbitrary formula (by arbitrary I mean using any arbitrary higher-order logic formula).

  • $\begingroup$ The [arithmetic] tag is for questions about basic arithmetical operations, not about arithmetical hierarchies. :-) $\endgroup$
    – Asaf Karagila
    Nov 26, 2012 at 18:50
  • 1
    $\begingroup$ The analytical hierarchy is in second order arithmetic, not second order logic. $\endgroup$ Dec 28, 2012 at 2:20
  • $\begingroup$ A couple of books you could look at are Sacks's Higher Recursion Theory, and Chong and Yu's draft of their volume Recursion Theory: The Syntax and Structure of Definability. $\endgroup$ Dec 28, 2012 at 10:52
  • $\begingroup$ is this necessarily so? why cant you use full semantics? $\endgroup$ Jan 28, 2013 at 23:33
  • $\begingroup$ Second order logic is a logic: a syntax, a semantics, a set of inference rules and so on. Second order arithmetic is a language, namely a two-sorted language with constant symbols $0$ and $1$, function symbols $+$ and $\times$, and the relation symbol $<$. The point here is that the arithmetical hierarchy (and the other hierarchies I've discussed) are essentially concerned with definability: what sets can we define using only bounded quantifiers, with just numeric quantifiers, using set quantifiers, and so on. $\endgroup$ Feb 15, 2013 at 1:40

2 Answers 2


Asaf pointed you to some resources about the main question you asked, about the hierarchy of $\Sigma^2_n$ sets. I'm afraid I can't offer any further assistance on that, but since you also mentioned $\alpha$-recursion and hyperarithmetic but weren't clear on what they were, I thought I could at least give you a brief outline.

Let's begin by reviewing some basic definitions. We obtain the arithmetical hierarchy by finite iterations of the Turing jump operator, starting with the empty set. The $\Sigma^0_n$ sets are those which are recursively enumerable in $0^{(n-1)}$, the $\Pi^0_n$ sets those which are co-recursively enumerable in $0^{(n-1)}$, and the $\Delta^0_n$ sets those which are recursive in $0^{(n-1)}$ (for $n \geq 1$). A set is arithmetical just in case it is $\Sigma^0_n$ for some $n \in \mathbb{N}$.

Now, suppose we want to go further and define the $\omega$-jump, $0^{(\omega)}$. This is recursively isomorphic to the first order theory of the natural numbers, $Th(\mathbb{N})$. By Tarski's theorem $Th(\mathbb{N})$ can't be defined by any arithmetical sentence, so $0^{(\omega)}$ can't be arithmetical. If we want to talk about the definability of sets like $0^{(\omega)}$ (which is, remember, just a subset of the natural numbers) then we'll need to go beyond the arithmetical hierarchy and into hyperarithmetic.

The hyperarithmetical sets are obtained just as the arithmetical ones are, by iterating the Turing jump. It's just that now we iterate not along natural numbers but along recursive ordinals. An ordinal $\alpha$ is a recursive ordinal iff there exists a recursive relation $<_c$ on $X \subseteq \mathbb{N}$ which is a wellordering of order-type $\alpha$. And a set $Y \subseteq \mathbb{N}$ is hyperarithmetical iff $Y$ is recursive in $0^{(\delta)}$ for some recursive ordinal $\delta$.

You mention the analytical hierarchy at the beginning of your question in connection with hyperarithmetic, but in fact the hyperarithmetic sets are very low down in the analytical hierarchy: they are precisely the $\Delta^1_1$ sets. In terms of definability we can go much further with the analytical hierarchy than we can with hyperarithmetic. For instance, the set $\mathcal{O}$ of notations for recursive ordinals is a $\Pi^1_1$ complete set. The supremum of the ordinals which have notations in $\mathcal{O}$ is $\omega_1^{CK}$, the first non-recursive ordinal. So $\omega_1^{CK}$ plays the same role for the hyperarithmetical sets as $\omega$ does for the arithmetical sets.

This brings us to the next generalisation, $\alpha$-recursion. What happens when instead of $\omega_1^{CK}$ we consider some arbitrary ordinal $\alpha$? Clearly not just any $\alpha$ will do: it must have some of the nice closure properties enjoyed by $\omega$ and $\omega_1^{CK}$. This leads to the notion of an admissible ordinal: an ordinal $\alpha$ such that $L_\alpha$ is a transitive model of Kripke–Platek set theory. $\omega$ and $\omega_1^{CK}$ are the first two admissible ordinals. Given an admissible ordinal $\alpha$, $\alpha$-recursive is defined as $\Delta^0_1$ over $L_\alpha$ while $\alpha$-recursively enumerable is $\Sigma^0_1$ over $L_\alpha$. The definitions of relative recursiveness and the jump operation are more complex so there I'll leave you to Sacks's book.

  • $\begingroup$ I am just a physicist, so I still doesn't grasp the differences between, let's say, an admissible ordinal, and a Malho ordinal. I just "know" that the later is somewhat "larger" (sorry if this confession disappoint you). So, is there any "simple" way (I mean that I can understand) in which you can extend alpha recursion to Malho cardinal or any other larger one you could define in the future? Could this generalize the analytical hierarchy to any arbitrary N-order logic or beyond? $\endgroup$ Jan 27, 2013 at 6:00
  • $\begingroup$ All Mahlo ordinals are admissible (as are Mahlo cardinals: all cardinals are admissible ordinals), so this would be a restriction, not a generalisation. When you say "generalize the analytical hierarchy to any arbitrary N-order logic", do you mean adding further type structure so that we get $\Sigma^2_n$ sets (as in third-order arithmetic), and in general, $\Sigma^k_n$ sets for $n, k \in \mathbb{N}$? This is not higher order logic, since the semantics are still (many-sorted) first order. $\endgroup$ Jan 27, 2013 at 20:15
  • $\begingroup$ Are you sure about that? according to Wikipedia: "The analytical hierarchy of formulas includes formulas in the language of second-order arithmetic, which can have quantifiers over both the set of natural numbers, N, and over functions from N to N". I mean, doesnt second order arithmetic use use full semantics? $\endgroup$ Jan 28, 2013 at 17:42
  • $\begingroup$ sorry I just realized you mentioned in a previous comment taht "The analytical hierarchy is in second order arithmetic, not second order logic", but is this necessarily so? why cant you use full semantics? $\endgroup$ Jan 28, 2013 at 17:55

I don't know enough to give a full answer, but I did ask [at least] two prominent set theorists about this a year ago.

I was referred to papers of Abraham & Shelah about third-order well-orderings of the real numbers:

  1. A $\Delta^2_2$ Well-Order of the Reals And Incompactness of $L(Q^{MM})$. Annals of Pure and Applied Logic 59 (1993) 1--32.

  2. Martin's axiom and $\Delta^2_1$ well-ordering of the reals. Archive for Mathematical Logic, 35 (1996) 287--298.

  3. Coding with ladders a well-ordering of the reals. The Journal of Symbolic Logic, 67, Number 2 (2002) 579--597.

  • $\begingroup$ Thanks Asaf, I had a chance to look at the 1st and 3rd articles, and I have no clue about what they are talking about! I'm just a physicist, the answer I am looking for is very general, and should only contain non-esoteric terminology. $\endgroup$ Nov 26, 2012 at 21:17
  • $\begingroup$ I don't know much to tell you, but by the fact that these sort of hierarchies are not often mentioned in introductory parts to descriptive set theory and/or computability, I can imagine that any work you will find involving such sets will be relatively esoteric. And I'm saying relatively because I don't know what is in those papers, but knowing both writers first hand there is about a 50% chance that the terminology is esoteric. $\endgroup$
    – Asaf Karagila
    Nov 26, 2012 at 21:19
  • 1
    $\begingroup$ well, for me, anything about set theory is esoteric! $\endgroup$ Nov 26, 2012 at 21:25
  • $\begingroup$ Haha. Well, you asked a question tagged [set-theory] and expected a non-esoteric answer? :-) $\endgroup$
    – Asaf Karagila
    Nov 26, 2012 at 21:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .