On a Representation of Hyperarithmetical Predicates

Here we show that an arbitrary hyperarithmetical predicate P(x1, . . . , xk) is representable by a system of general form recursive equations (G.F.R.E.). On the other hand, it is shown that the class of hyperarithmetical predicates is the largest class of predicates representable by means of recursive equations. This presents a new characterization of hyperarithmetical sets “from outside”, where characteristic functions of hyperarithmetical sets are described as unique solutions of G.F.R.E. We also investigate the representation of number-theoretic functions and establish a characterization of J. Myhill’s finitely representable functions via effectively testable properties