Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-12T22:25:47.908Z Has data issue: false hasContentIssue false

Hierarchies of Boolean algebras

Published online by Cambridge University Press:  12 March 2014

Lawrence Feiner*
Affiliation:
State University of New York at Stony Brook

Extract

A denumerable structure is said to be recursive iff its universe is a recursive subset of the natural numbers and its relations and operations are recursive. For example, the standard model of number theory is recursive. A structure is said to be recursively presentable iff it is isomorphic to a recursive structure. For example, a Boolean algebra generated by ℵ0 free generators is easily seen to be recursively presentable. (For basic facts concerning Boolean algebras, the reader is referred to R. Sikorski [9] and A. Tarski and A. Mostowski [10].)

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1971

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

[1]Davis, M., Computability and unsolvability, McGraw-Hill, New York, 1958.Google Scholar
[2]Feiner, L., Orderings and Boolean algebras not isomorphic to recursive ones, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1967.Google Scholar
[3]Hanf, W., Isomorphism in elementary logic, Notices of the American Mathematical Society, vol. 9 (1962), pp. 127128.Google Scholar
[4]Hanf, W., Model theoretic methods in the study of elementary logic, The theory of models, North-Holland, Amsterdam, 1965, pp. 133146.Google Scholar
[5]Hanf, W., On some fundamental problems concerning isomorphism of Boolean algebras, Mathematicae scandinavica, vol. 5 (1957), pp. 205217.CrossRefGoogle Scholar
[6]Lachlan, A., On the lattice of recursively enumerable sets, Transactions of the American Mathematical Society, vol. 130 (1968), pp. 137.CrossRefGoogle Scholar
[7]Rabin, M., On recursively enumerable and arithmetic models of set theory, this Journal, vol. 23 (1958), pp. 408416.Google Scholar
[8]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[9]Sikorski, R., Boolean algebra, Springer-Verlag, Berlin, 1964.Google Scholar
[10]Tarski, A. and Mostowski, C., Boolesche Ringe mit geordneter Basis, Fundamenta mathematicae, vol. 32 (1939).Google Scholar
[11]Tennenbaum, S., Non-Archimedean models for arithmetic, Notices of the American Mathematical Society, vol. 6 (1959), p. 207.Google Scholar