Hostname: page-component-7c8c6479df-hgkh8 Total loading time: 0 Render date: 2024-03-29T14:02:02.626Z Has data issue: false hasContentIssue false

Recursive isomorphism types of recursive Boolean algebras

Published online by Cambridge University Press:  12 March 2014

J. B. Remmel*
Affiliation:
University of California, San Diego, La Jolla, California 92093

Extract

A Boolean algebra is recursive if B is a recursive subset of the natural numbers N and the operations ∧ (meet), ∨ (join), and ¬ (complement) are partial recursive. Given two Boolean algebras and , we write if is isomorphic to and if is recursively isomorphic to , that is, if there is a partial recursive function f: B1B2 which is an isomorphism from to . will denote the set of atoms of and () will denote the ideal generated by the atoms of .

One of the main questions which motivated this paper is “To what extent does the classical isomorphism type of a recursive Boolean algebra restrict the possible recursion theoretic properties of ?” For example, it is easy to see that must be co-r.e. (i.e., N is an r.e. set), but can be immune, not immune, cohesive, etc? It follows from a result of Goncharov [4] that there exist classical isomorphism types which contain recursive Boolean algebras but do not contain any recursive Boolean algebras such that is recursive. Thus the classical isomorphism can restrict the possible Turing degrees of , but what is the extent of this restriction? Another main question is “What is the recursion theoretic relationship between and () in a recursive Boolean algebra?” In our attempt to answer these questions, we were led to a wide variety of recursive isomorphism types which are contained in the classical isomorphism type of any recursive Boolean algebra with an infinite set of atoms.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1981

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]Crossley, J. N. and Nerode, A., Combinatorial functors (monograph), North-Holland, Amsterdam, 1969.Google Scholar
[2]Dekker, J. C. E. and Myhill, J., Recursive equivalence types (monograph), University of California Publications in Mathematics, vol. 3 (1960).Google Scholar
[3]Ershov, Y. L., Theorie der Numerierungen. III, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 23 (1977), pp. 289371.Google Scholar
[4]Goncharov, S. S., Constructivizable superatomic Boolean algebras, Algebra i Logika, vol. 12(1973), pp. 3140.Google Scholar
[5]Goncharov, S. S., Some properties of the constructivization of Boolean algebras, Sibirskiǐ Matematičeskiǐ Žurnal, vol. 16 (1975), pp. 264278.Google Scholar
[6]Goncharov, S. S. and Nurtazin, A. T., Constructive models of complete solvable theories, Algebra i Logika, vol. 12 (1973), pp. 125142.Google Scholar
[7]La Roche, P., Recursively presented Boolean algebras, Notices of the American Mathematical Society, vol. 24 (1977) p. A552.Google Scholar
[8]Läuchli, H. and Leonard, J., On the elementary theory of linear order, Fundament a Mathe-maticae, vol. 59 (1966), pp. 109116.CrossRefGoogle Scholar
[9]Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295310.CrossRefGoogle Scholar
[10]Remmel, J. B., Realizing partial orderings by classes of co-simple sets, Pacific Journal of Mathematics, vol. 76(1978), pp. 169184.CrossRefGoogle Scholar
[11]Remmel, J. B., Recurisively enumerable Boolean algebras, Annals of Mathematical Logic, vol. 14 (1978), pp. 75107.CrossRefGoogle Scholar
[12]Remmel, J. B., Recursive Boolean algebras with recursive atoms, this Journal vol. 46 (1981), pp. 595616.Google Scholar
[13]Rogers, H. J. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[14]Sacks, G. E., The recursively enumerable degrees are dense, Annals of Mathematics, vol. 80(1964), pp. 300312.CrossRefGoogle Scholar
[15]Sikorski, R., Boolean algebras, Academic Press, New York, 1964.Google Scholar
[16]Vauoht, R. L., Topics in the theory of arithmetical classes and Boolean algebras, Ph.D. Thesis, University of California, Berkeley, 1954.Google Scholar