János Komlós (mathematician): Difference between revisions
en>Rjwilmsi m →Notable results: Format plain DOIs using AWB (7927) |
en>Waacstats →References: Add persondata short description using AWB |
||
| Line 1: | Line 1: | ||
In [[recursion theory]], a mathematical discipline, a '''PA degree''' is a [[Turing degree]] that computes a complete extension of [[Peano arithmetic]] (Jockusch 1987). These degrees are closely related to fixed-point-free (DNR) functions, and have been thoroughly investigated in recursion theory. | |||
== Background == | |||
In recursion theory, <math>\phi_e</math> denotes the [[computable function]] with index ''e'' in some standard numbering of computable functions, and <math>\phi^B_e</math> denotes the ''e''th computable function using a set ''B'' of natural numbers as an oracle. | |||
A set ''A'' of natural numbers is [[Turing reducibility|Turing reducible]] to a set ''B'' if there is a [[computable function]] that, given an oracle for set ''B'', computes the [[indicator function|characteristic function]] χ<sub>A</sub> of the set ''A''. That is, there is an ''e'' such that <math>\chi_A = \phi^B_e</math>. This relationship is denoted ''A'' ≤<sub>T</sub> ''B''; the relation ≤<sub>T</sub> is a [[preorder]]. | |||
Two sets are [[Turing degree|Turing equivalent]] if each is Turing reducible to the other. The notation ''A'' ≡<sub>T</sub> ''B'' indicates ''A'' and ''B'' are Turing equivalent. The relation ≡<sub>T</sub> is an equivalence relation known as Turing equivalence. A [[Turing degree]] is a collection of sets of natural numbers, such that any two sets in the collection are Turing equivalent. Equivalently, a Turing degree is an equivalence class of the relation ≡<sub>T</sub>. | |||
The Turing degrees are [[partial order|partially ordered]] by Turing reducibility. The notation '''a''' ≤<sub>T</sub> '''b''' indicates there is a set in degree '''b''' that computes a set in degree '''a'''. Equivalently, '''a''' ≤<sub>T</sub> '''b''' holds if and only if every set in '''b''' computes every set in '''a'''. | |||
A function ''f'' from the natural numbers to the natural numbers is said to be diagonally nonrecursive (DNR) if, for all ''n'', <math>f(n) \not = \phi_n(n)</math> (here inequality holds by definition if <math>\phi_n(n)</math> is undefined). If the range of ''f'' is the set {0,1} then ''f'' is a DNR<sub>2</sub> function. It is known that there are DNR functions that do not compute any DNR<sub>2</sub> function. | |||
== Completions of Peano arithmetic == | |||
A completion of [[Peano arithmetic]] is a set of formulas in the language of Peano arithmetic, such that the set is consistent in first-order logic and such that, for each formula, either that formula or its negation is included in the set. Once a Gödel numbering of the formulas in the language of PA has been fixed, it is possible to identify completions of PA with sets of natural numbers, and thus to speak about the computability of these completions. | |||
A Turing degree is defined to be a '''PA degree''' if there is a set in the degree that computes a completion of PA. This is equivalent to the proposition that every set in the degree computes a completion of PA. Because there are no computable completions of PA, the degree '''0''' consisting of the computable sets of natural numbers is not a PA degree. | |||
Because PA is an effective first-order theory, the completions of PA can be characterized as the infinite paths through a particular computable subtree of 2<sup><ω</sup>. Thus the PA degrees are exactly the degrees that compute an infinite path through this tree. | |||
== Properties == | |||
The PA degrees are upward closed in the Turing degrees: if '''a''' is a PA degree and '''a''' ≤<sub>T</sub> '''b''' then '''b''' is a PA degree. | |||
The Turing degree '''0'''‘, which is the degree of the [[halting problem]], is a PA degree. There are also PA degrees that are not above '''0'''‘. For example, the [[low basis theorem]] implies that there is a low PA degree. On the other hand, [[Antonín Kučera]] has proved that there is a degree less than '''0'''‘ that computes a DNR function but is not a PA degree (Jockusch 1989:197). | |||
[[Carl Jockusch]] and [[Robert Soare]] (1972) proved that the PA degrees are exactly the degrees of DNR<sub>2</sub> functions. | |||
By definition, a degree is PA if and only if it computes a path through the tree of completions of Peano arithmetic. A stronger property holds: a degree '''a''' is a PA degree if and only if '''a''' computes a path through every infinite computable subtree of 2<sup><ω</sup> (Simpson 1977). | |||
== See also == | |||
* [[König's lemma]] | |||
== References == | |||
* Carl Jockusch (1987), "Degrees of functions with no fixed points", ''Logic Colloquium '87'', Fenstad, Frolov, and Hilpinen, eds., North-Holland, ISBN 0-444-88022-4. | |||
* Carl Jockusch and Robert Soare (1972), "Π<sup>0</sup><sub>1</sub> classes and degrees of theories", ''[[Transactions of the American Mathematical Society]]'', v. 173, pp. 33–56. | |||
* Stephen G. Simpson (1977), "Degrees of unsolvability: a survey of results", ''Handbook of Mathematical Logic'', Barwise (ed.), North-Holland, pp. 631–652. | |||
[[Category:Computability theory]] | |||
Latest revision as of 13:53, 29 November 2013
In recursion theory, a mathematical discipline, a PA degree is a Turing degree that computes a complete extension of Peano arithmetic (Jockusch 1987). These degrees are closely related to fixed-point-free (DNR) functions, and have been thoroughly investigated in recursion theory.
Background
In recursion theory, denotes the computable function with index e in some standard numbering of computable functions, and denotes the eth computable function using a set B of natural numbers as an oracle.
A set A of natural numbers is Turing reducible to a set B if there is a computable function that, given an oracle for set B, computes the characteristic function χA of the set A. That is, there is an e such that . This relationship is denoted A ≤T B; the relation ≤T is a preorder.
Two sets are Turing equivalent if each is Turing reducible to the other. The notation A ≡T B indicates A and B are Turing equivalent. The relation ≡T is an equivalence relation known as Turing equivalence. A Turing degree is a collection of sets of natural numbers, such that any two sets in the collection are Turing equivalent. Equivalently, a Turing degree is an equivalence class of the relation ≡T.
The Turing degrees are partially ordered by Turing reducibility. The notation a ≤T b indicates there is a set in degree b that computes a set in degree a. Equivalently, a ≤T b holds if and only if every set in b computes every set in a.
A function f from the natural numbers to the natural numbers is said to be diagonally nonrecursive (DNR) if, for all n, (here inequality holds by definition if is undefined). If the range of f is the set {0,1} then f is a DNR2 function. It is known that there are DNR functions that do not compute any DNR2 function.
Completions of Peano arithmetic
A completion of Peano arithmetic is a set of formulas in the language of Peano arithmetic, such that the set is consistent in first-order logic and such that, for each formula, either that formula or its negation is included in the set. Once a Gödel numbering of the formulas in the language of PA has been fixed, it is possible to identify completions of PA with sets of natural numbers, and thus to speak about the computability of these completions.
A Turing degree is defined to be a PA degree if there is a set in the degree that computes a completion of PA. This is equivalent to the proposition that every set in the degree computes a completion of PA. Because there are no computable completions of PA, the degree 0 consisting of the computable sets of natural numbers is not a PA degree.
Because PA is an effective first-order theory, the completions of PA can be characterized as the infinite paths through a particular computable subtree of 2<ω. Thus the PA degrees are exactly the degrees that compute an infinite path through this tree.
Properties
The PA degrees are upward closed in the Turing degrees: if a is a PA degree and a ≤T b then b is a PA degree.
The Turing degree 0‘, which is the degree of the halting problem, is a PA degree. There are also PA degrees that are not above 0‘. For example, the low basis theorem implies that there is a low PA degree. On the other hand, Antonín Kučera has proved that there is a degree less than 0‘ that computes a DNR function but is not a PA degree (Jockusch 1989:197).
Carl Jockusch and Robert Soare (1972) proved that the PA degrees are exactly the degrees of DNR2 functions.
By definition, a degree is PA if and only if it computes a path through the tree of completions of Peano arithmetic. A stronger property holds: a degree a is a PA degree if and only if a computes a path through every infinite computable subtree of 2<ω (Simpson 1977).
See also
References
- Carl Jockusch (1987), "Degrees of functions with no fixed points", Logic Colloquium '87, Fenstad, Frolov, and Hilpinen, eds., North-Holland, ISBN 0-444-88022-4.
- Carl Jockusch and Robert Soare (1972), "Π01 classes and degrees of theories", Transactions of the American Mathematical Society, v. 173, pp. 33–56.
- Stephen G. Simpson (1977), "Degrees of unsolvability: a survey of results", Handbook of Mathematical Logic, Barwise (ed.), North-Holland, pp. 631–652.