Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-24T23:22:25.188Z Has data issue: false hasContentIssue false
  • English
  • Français

On recursively enumerable and arithmetic models of set theory

Published online by Cambridge University Press:  12 March 2014

Michael O. Rabin
Michael O. Rabin*
Affiliation:
Institute for Advanced Study and the Hebrew University, Jerusalem
Get access Rights & Permissions [Opens in a new window]

Extract

In this note we shall prove a certain relative recursiveness lemma concerning countable models of set theory (Lemma 5). From this lemma will follow two results about special types of such models.

Kreisel [5] and Mostowski [6] have shown that certain (finitely axiomatized) systems of set theory, formulated by means of the ϵ relation and certain additional non-logical constants, do not possess recursive models. Their purpose in doing this was to construct consistent sentences without recursive models. As a first corollary of Lemma 5, we obtain a very simple proof, not involving any formal constructions within the system of the notions of truth and satisfiability, of an extension of the Kreisel-Mostowski theorems. Namely, set theory with the single non-logical constant ϵ does not possess any recursively enumerable model. Thus we get, as a side product, an easy example of a consistent sentence containing a single binary relation which does not possess any recursively enumerable model; this sentence being the conjunction of the (finitely many) axioms of set theory.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 23 , Issue 4 , December 1958 , pp. 408 - 416
Copyright
Copyright © Association for Symbolic Logic 1958

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

REFERENCES

[1]Fraenkel, A., Über die Gleichheitsbeziehung in der Mengenlehre, Journal für Mathematik, vol. 157 (1927), pp. 79–81.Google Scholar
[2]Gödel, K., The consistency of the axiom of choice and of the generalized continuum hypothesis with the axioms of set theory, Annals of Mathematics Studies, No. 3, Princeton N.J. (Princeton University Press), second printing, 1951.Google Scholar
[3]Kleene, S. C., Introduction to metamathematics, Amsterdam (North Holland), Groningen (Noordhoff), New York and Toronto (Van Nostrand), 1952.Google Scholar
[4]Kleene, S. C., A symmetric form of Gödel's theorem, Koninklijke Nederlandsche Akademie van Wetenschappen, Proceedings of the section of sciences, vol. 53 (1950), pp. 800–802; also Indagationes mathematicae, vol. 12 (1950), pp. 244–246.Google Scholar
[5]Kreisel, G., Note on arithmetic models for consistent formulae of the predicate calculus II, Proceedings of the XIth International Congress of Philosophy, Bruxelles, August 20-26, 1953, vol. 14, pp. 39–49.Google Scholar
[6]Mostowski, A., On a system of axioms which has no recursively enumerable arithmetic model, Fundamenta mathematicae, vol. 40 (1953), pp. 56–61.CrossRefGoogle Scholar