Arithmetical Hierarchy - Examples

Examples

• The sets of numbers are those definable by a formula of the form where has only bounded quantifiers. These are exactly the recursively enumerable sets.

• The set of natural numbers that are indices for Turing machines that compute total functions is . Intuitively, an index falls into this set if and only if for every "there is an such that the Turing machine with index halts on input after steps”. A complete proof would show that the property displayed in quotes in the previous sentence is definable in the language of Peano arithmetic by a formula.

• Every subset of Baire space or Cantor space is an open set in the usual topology on the space. Moreover, for any such set there is a computable enumeration of Gödel numbers of basic open sets whose union is the original set. For this reason, sets are sometimes called effectively open. Similarly, every set is closed and the sets are sometimes called effectively closed.

• Every arithmetical subset of Cantor space of(or?) Baire space is a Borel set. The lightface Borel hierarchy extends the arithmetical hierarchy to include additional Borel sets. For example, every subset of Cantor or Baire space is a set (that is, a set which equals the intersection of countably many open sets). Moreover, each of these open sets is and the list of Gödel numbers of these open sets has a computable enumeration. If is a formula with a free set variable X and free number variables then the set is the intersection of the sets of the form as n ranges over the set of natural numbers.