×

The arithmetical hierarchy of real numbers. (English) Zbl 0968.03075

This is the complete version of the report in Lect. Notes Comput. Sci. 1672, 23-33 (1999; Zbl 0955.03066). In particular, all results are proved in detail here. The computable real numbers are the limits of computable rational-number sequences converging effectively, i.e., computably fast. The suprema (infima) of computable sequences of rational numbers give the left (right) computable numbers which build the class \(\Sigma_1\) (\(\Pi_1\)). More general, \(\Sigma_n\) (\(\Pi_n\)) consists of the reals obtained by applying the supremum and infimum operation \(n\) times alternately to computable multiple sequences of rational numbers. These classes together with the related intersections \(\Delta_n\) build the so-called arithmetical hierarchy of real numbers for which some other characterizations and examples are discussed and the usual hierarchy properties are shown.

MSC:

03F60 Constructive and recursive analysis
03D55 Hierarchies of computability and definability
26E40 Constructive real analysis

Citations:

Zbl 0955.03066
Full Text: DOI