Rayo's function is based on the language of first-order set theory, which is rather powerful. I think it would be interesting to take a step back to a weaker language: second-order arithmetic.
Let
be the standard model of second order arithmetic. We say that a formula
that takes one argument defines a natural number
if
. That is,
is the unique natural number that satisfies
in the standard model. We define the analytical beaver function
to be the the largest natural number definable by a formula that is less than
symbols long plus 1 (or 0 if there is no such number). Since there are only finitely many such formulas, and each formula defines at most one number, this is well defined. As to define a concrete number, we will define the analytical beaver number to be
. Now, you may be wondering what
is doing there? Well, that symbol denotes the set of all formulas in the language of second order arithmetic. In general, we define
to be the largest natural number definable definable by a formula in the set
that is less than
symbols plus 1 (or 0 if there is no such number). Some interesting sets of formulas are those in the analytical hierarchy (which includes the arithmetical hierarchy). We will also define the combination beaver
to be the largest natural number definable definable by a formula from each of the sets
that is less than
symbols plus 1 (or 0 if there is no such number). By convention, we define the analytical beaver for a
level to be the combination of the corresponding
and
levels. For example,
.
We can also consider analytical beavers based on expansions of second order arithmetic. By convention, the analytical beaver of a relativized level of the hierarchy is defined this way.
Question: It is clear that
is not in the analytical hierarchy itself. However,
is, for any other
in the analytical hierarchy. Where do such
fall in the hierarchy? We know they would not fall in
, for example.