Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-11T14:55:07.419Z Has data issue: false hasContentIssue false
  • English
  • Français

Abstract Computability and Invariant Definability

Published online by Cambridge University Press:  12 March 2014

Yiannis N. Moschovakis
Yiannis N. Moschovakis*
Affiliation:
University of california, Los Angeles
Get access Rights & Permissions [Opens in a new window]

Extract

By language we understand a lower predicate calculus with identity and (perhaps) relation and function symbols. It is convenient to allow for more than one sort of variable. Now each individual constant (if there are any) is of a specified sort, the formal expressions R(t1, … tn), f(t1,…, tn) are well formed only if the terms t1, …, tn are of specified sorts determined by the relation symbol R and the function symbol f, and the term f(t1, …, tn) (if well formed) is of a sort determined by f. We admit s = t as well formed, no matter what the sorts of s and t.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 4 , February 1970 , pp. 605 - 633
Copyright
Copyright © Association for Symbolic Logic 1970

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.)

Footnotes

1

The author is a Guggenheim fellow. Preparation of this paper was sponsored in part by an N.S.F. grant.

References

[1] Feferman, S., Systems of predicative analysis, this Journal , vol. 29 (1964), pp. 1–30.Google Scholar
[2] Feferman, S., Autonomous transfinite progressions and the extent of predicative mathematics. Logic, methodology and philosophy of science. III, North-Holland, Amsterdam, 1968, pp. 121–136.CrossRefGoogle Scholar
[3] Fraïsse, R., Une notion de récursivité relative, Infinitistic methods. Proceedings of the Symposium on Foundations of Mathematics (Warsaw, 1959), Pergamon, Oxford; PWN, Warsaw, 1961, pp. 323–328.Google Scholar
[4] Gandy, R. O., General recursive functionals of finite type and hierarchies of functions, Mimeographed Notes, Symposium on Mathematical Logic, University of Clermont Ferrand, 1962.Google Scholar
[5] Gandy, R., Kreisel, G. and Tait, W., Set existence, Bulletin de l'Académie Polonaise des Sciences. Série des sciences mathématiques, astronomiques et physiques, vol. 8 (1960), pp. 577–582.Google Scholar
[6] Gödel, K., Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I, Monatschefte für Mathematik und Physik, vol. 38 (1931), pp. 173–178.CrossRefGoogle Scholar
[7] Grzegorczyk, A., Mostowski, A. and Ryll-Nardzewski, Cz., The classical and the ω-complete arithmetic, this Journal , vol. 23 (1958), pp. 188–205.Google Scholar
[8] Kleene, S. C., Introduction to metamathematics, Van Nostrana, New York, 1952.Google Scholar
[9] Kleene, S. C., On the forms of the predicates in the theory of constructive ordinals. II, American journal of mathematics, vol. 77 (1955), pp. 405–428.CrossRefGoogle Scholar
[10] Kleene, S. C., Arithmetic predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar
[11] Kleene, S. C., Hierarchies of number-theoretic predicates, Bulletin of the American Mathematical Society, vol. 61 (1955), pp. 193–213.CrossRefGoogle Scholar
[12] Kleene, S. C., Quantification of number-theoretic functions, Compositio Mathematica, vol. 14 (1959), pp. 23–40.Google Scholar
[13] Kreisel, G., Ordinal logics and the characterization of informal concepts of proof, Proceedings of the International Congress of Mathematicians, 1958, pp. 289–299.Google Scholar
[14] Kreisel, G., Set theoretic problems suggested by the notion of potential totality, Infinitistic methods, Proceedings cf the Symposium on Foundations of Mathematics (Warsaw, 1959), Pergamon, Oxford; PWN, Warsaw, 1961, pp. 103–140.Google Scholar
[15] Kreisel, G., La predicativité, Bulletin de la Société Mathématique de France, vol. 88 (1960), pp. 371–391.CrossRefGoogle Scholar
[16] Kreisel, G., The axiom of choice and the class of hyperarithmetic functions, Indagationes Mathematicae, vol. 24 (1962), pp. 307–319.CrossRefGoogle Scholar
[17] Kreisel, G., Model theoretic invariants: applications to recursive and hyperarithmetic operations, The Theory of Models, Proceedings of the 1963 International Symposium at Berkeley, North-Holland, Amsterdam, 1965, pp. 190–205.Google Scholar
[18] Kripke, S., Transfinite recursion, constructible sets and analogues of cardinals, Proceedings of the American Mathematical Society Summer Institute in Axiomatic Set Theory, Los Angeles, Calif., 1967.Google Scholar
[19] Lacombe, D., Deux généralisations de la notion de récursivité, Comptes Rendus de l'Academie des Sciences de Paris, vol. 258 (1964), pp. 3141–3143.Google Scholar
[20] Lacombe, D., Deux généralisations de la notion de récursivité relative, Comptes Rendus de l'Académie des Sciences de Paris, vol. 258 (1964), pp. 3410–3413.Google Scholar
[21] Moschovakis, Y. N., Hyperanalytic predicates, Transactions of the American Mathematical Society, vol. 129 (1967), pp. 249–282.CrossRefGoogle Scholar
[22] Moschovakis, Y. N., Abstract first order computability. I, Transactions of the American Mathematical Society, vol. 138 (1969), pp. 427–464.Google Scholar
[23] Moschovakis, Y. N., Abstract first order computability. II, Transactions of the American Mathematical Society, vol. 138 (1969) pp. 465–504.CrossRefGoogle Scholar
[24] Moschovakis, Y. N., Predicative classes, to appear in Proceedings of the American Mathematical Society Summer Institute in Axiomatic Set Theory, Los Angeles, Calif., 1967.Google Scholar
[25] Moschovakis, Y. N., Generalizations of the theory of recursive and hyperarithmetic relations to abstract domains (in preparation).Google Scholar
[26] Moschovakis, Y. N., Post's theorem in the analytic hierarchy (in preparation).Google Scholar
[27] Mostowski, A., Representability of sets in formal systems, Recursive Function Theory, Proceedings of Symposia in Pure Mathematics, Providence, R.I., vol. 5 (1962), pp. 29–48.CrossRefGoogle Scholar
[28] Spector, C., Recursive well-orderings, this Journal , vol. 20 (1955), pp. 151–163.Google Scholar