Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-20T00:43:25.995Z Has data issue: false hasContentIssue false
  • English
  • Français

Hierarchies over recursive well-orderings

Published online by Cambridge University Press:  12 March 2014

Herbert Enderton  and
David Luckham
Herbert Enderton
Affiliation:
Massachusetts Institute of Technology
David Luckham
Affiliation:
Massachusetts Institute of Technology
Get access Rights & Permissions [Opens in a new window]

Extract

In the original example of a transfinite hierarchy of degrees of unsolvability, a predicate Ha is associated with each a in the set 0 of ordinal notations. (See Kleene [K1], Spector [S1], and the references there to Davis and Mostowski.) The predicates are defined by means of induction over the partial well-ordering relation ≤0 on the set 0 of notations for the recursive ordinals. The usefulness of this hierarchy of predicates is enhanced by Spector's proof [S1] of the “uniqueness” property: viz. that the degree of Ha depends only on the ordinal |a| for which a is a notation.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 29 , Issue 4 , December 1964 , pp. 183 - 190
Copyright
Copyright © Association for Symbolic Logic 1964

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[E]Enderton, H., Hierarchies in recursive function thjeory, Transactions of the American Mathematical Society, vol. III (1964), pp. 457–471.CrossRefGoogle Scholar
[IM]Kleene, S. C., Introduction to Metamathematics, Van Nostrana, New York, 1952.Google Scholar
[K1]Kleene, S. C., Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955) pp. 193–213.CrossRefGoogle Scholar
[K2]Kleene, S. C., Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955) pp. 312–340.CrossRefGoogle Scholar
[R]Rogers, H. Jr., Recursive functions over well ordered partial orderings, Proceedings of the American Mathematical Society, vol. 10 (1959) pp. 847–853.CrossRefGoogle Scholar
[S1]Spector, C., Recursive well-orderings, this Journal, vol. 20 (1955) pp. 151–163.Google Scholar
[S2]Spector, C., Strongly invariant hierarchies (abstract), Notices of the American Mathematical Society, vol. 5 (1958) p. 851.Google Scholar