Every low Boolean algebra is isomorphic to a recursive one

Authors:
Rod Downey and Carl G. Jockusch

Journal:
Proc. Amer. Math. Soc. **122** (1994), 871-880

MSC:
Primary 03C57; Secondary 03D30, 03D45, 06E99

MathSciNet review:
1203984

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that every (countable) Boolean algebra with a presentation of low Turing degree is isomorphic to a recursive Boolean algebra. This contrasts with a result of Feiner (1967) that there is a Boolean algebra with a presentation of degree which is not isomorphic to a recursive Boolean algebra. It is also shown that for each *n* there is a finitely axiomatizable theory such that every model of is isomorphic to a recursive structure but there is a model of which is not isomorphic to any recursive structure. In addition, we show that is the *Turing ordinal* of the same theory , where, very roughly, the Turing ordinal of a theory describes the number of jumps needed to recover nontrivial information from models of the theory. These are the first known examples of theories with Turing ordinal for .

**[1]**C. J. Ash,*Stability of recursive structures in arithmetical degrees*, Ann. Pure Appl. Logic**32**(1986), no. 2, 113–135. MR**863330**, 10.1016/0168-0072(86)90048-5**[2]**C. J. Ash, C. G. Jockusch Jr., and J. F. Knight,*Jumps of orderings*, Trans. Amer. Math. Soc.**319**(1990), no. 2, 573–599. MR**955487**, 10.1090/S0002-9947-1990-0955487-0**[3]**Rod Downey,*Every recursive Boolean algebra is isomorphic to one with incomplete atoms*, Ann. Pure Appl. Logic**60**(1993), no. 3, 193–206. MR**1216669**, 10.1016/0168-0072(93)90075-O**[4]**-,*Recursion theory and linear orderings*, Handbook of Recursive Algebra (A. Nerode and J. Remmel, eds.) (to appear).**[5]**Rodney Downey and Julia F. Knight,*Orderings with 𝛼th jump degree 0^{(𝛼)}*, Proc. Amer. Math. Soc.**114**(1992), no. 2, 545–552. MR**1065942**, 10.1090/S0002-9939-1992-1065942-0**[6]**Rodney G. Downey and Michael F. Moses,*Recursive linear orders with incomplete successivities*, Trans. Amer. Math. Soc.**326**(1991), no. 2, 653–668. MR**1005933**, 10.1090/S0002-9947-1991-1005933-2**[7]**L. J. Feiner,*Orderings and Boolean algebras not isomorphic to recursive ones*, Thesis, MIT, Cambridge, MA, 1967.**[8]**Lawrence Feiner,*Hierarchies of Boolean algebras*, J. Symbolic Logic**35**(1970), 365–374. MR**0282805****[9]**L. Feiner,*The strong homogeneity conjecture*, J. Symbolic Logic**35**(1970), 375–377. MR**0286655****[10]**Lawrence Feiner,*Degrees of nonrecursive presentability*, Proc. Amer. Math. Soc.**38**(1973), 621–624. MR**0327494**, 10.1090/S0002-9939-1973-0327494-8**[11]**S. S. Gončarov,*Certain properties of the constructivization of Boolean algebras*, Sibirsk. Mat. Ž.**16**(1975), 264–278, 420. (loose errata) (Russian). MR**0381957****[12]**Carl G. Jockusch Jr. and Robert I. Soare,*Degrees of orderings not isomorphic to recursive linear orderings*, Ann. Pure Appl. Logic**52**(1991), no. 1-2, 39–64. International Symposium on Mathematical Logic and its Applications (Nagoya, 1988). MR**1104053**, 10.1016/0168-0072(91)90038-N**[13]**C. G. Jockusch and R. I. Soare,*Boolean algebras, Stone spaces, and the iterated Turing jump*, preprint.**[14]**Julia F. Knight,*Degrees coded in jumps of orderings*, J. Symbolic Logic**51**(1986), no. 4, 1034–1042. MR**865929**, 10.2307/2273915**[15]**J. F. Knight,*A metatheorem for constructions by finitely many workers*, J. Symbolic Logic**55**(1990), no. 2, 787–804. MR**1056389**, 10.2307/2274665**[16]**Manuel Lerman,*On recursive linear orderings*, Logic Year 1979–80 (Proc. Seminars and Conf. Math. Logic, Univ. Connecticut, Storrs, Conn., 1979/80) Lecture Notes in Math., vol. 859, Springer, Berlin, 1981, pp. 132–142. MR**619867****[17]**W. Magnus, A. Karrass, and D. Solitar,*Combinatorial group theory*, Academic Press, New York, 1965.**[18]**J. Donald Monk and Robert Bonnet (eds.),*Handbook of Boolean algebras. Vol. 3*, North-Holland Publishing Co., Amsterdam, 1989. MR**991607****[19]**S. Oates,*Jump degrees of groups*, Ph.D. thesis, Univ. of Notre Dame, 1989.**[20]**Jeffrey B. Remmel,*Recursive Boolean algebras with recursive atoms*, J. Symbolic Logic**46**(1981), no. 3, 595–616. MR**627908**, 10.2307/2273758**[21]**J. B. Remmel,*Recursive isomorphism types of recursive Boolean algebras*, J. Symbolic Logic**46**(1981), no. 3, 572–594. MR**627907**, 10.2307/2273757**[22]**L. J. Richter,*Degrees of unsolvability of models*, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1977.**[23]**Linda Jean Richter,*Degrees of structures*, J. Symbolic Logic**46**(1981), no. 4, 723–731. MR**641486**, 10.2307/2273222**[24]**Hartley Rogers Jr.,*Theory of recursive functions and effective computability*, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR**0224462****[25]**Joseph G. Rosenstein,*Linear orderings*, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR**662564****[26]**Robert I. Soare,*Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987. A study of computable functions and computably generated sets. MR**882921****[27]**J. Thurber,*Every**Boolean algebra has a recursive copy*(to appear).**[28]**R. Vaught,*Topics in the theory of arithmetical classes and Boolean algebras*, Ph.D. thesis, University of California, Berkeley, 1954.**[29]**Richard Watnick,*A generalization of Tennenbaum’s theorem on effectively finite recursive linear orderings*, J. Symbolic Logic**49**(1984), no. 2, 563–569. MR**745385**, 10.2307/2274189

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
03C57,
03D30,
03D45,
06E99

Retrieve articles in all journals with MSC: 03C57, 03D30, 03D45, 06E99

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1994-1203984-4

Article copyright:
© Copyright 1994
American Mathematical Society