Editing Definable real number (section)

== Definability in arithmetic ==
Another notion of definability comes from the formal theories of arithmetic, such as [[Peano arithmetic]]. The [[Peano arithmetic|language of arithmetic]] has symbols for 0, 1, the successor operation, addition, and multiplication, intended to be interpreted in the usual way over the [[natural number]]s. Because no variables of this language range over the [[real number]]s, a different sort of definability is needed to refer to real numbers. A real number <math>a</math> is ''definable in the language of arithmetic'' (or ''[[arithmetical hierarchy|arithmetical]]'') if its [[Dedekind cut]] can be defined as a [[Predicate (logic)|predicate]] in that language; that is, if there is a first-order formula <math>\varphi</math> in the language of arithmetic, with three free variables, such that
<math display=block>\forall m \, \forall n \, \forall p \left (\varphi(n,m,p)\iff\frac{(-1)^p\cdot n}{m+1}<a \right ).</math>
Here ''m'', ''n'', and ''p'' range over nonnegative integers.

The [[second-order arithmetic|second-order language of arithmetic]] is the same as the first-order language, except that variables and quantifiers are allowed to range over sets of naturals. A real that is second-order definable in the language of arithmetic is called ''[[analytical hierarchy|analytical]]''.

Every computable real number is arithmetical, and the arithmetical numbers form a subfield of the reals, as do the analytical numbers. Every arithmetical number is analytical, but not every analytical number is arithmetical. Because there are only countably many analytical numbers, most real numbers are not analytical, and thus also not arithmetical.

Every computable number is arithmetical, but not every arithmetical number is computable. For example, the limit of a [[Specker sequence]] is an arithmetical number that is not computable.

The definitions of arithmetical and analytical reals can be stratified into the [[arithmetical hierarchy]] and [[analytical hierarchy]]. In general, a real is computable if and only if its Dedekind cut is at level <math>\Delta^0_1</math> of the arithmetical hierarchy, one of the lowest levels.  Similarly, the reals with arithmetical Dedekind cuts form the lowest level of the analytical hierarchy.