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

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

MathSciNet review:
1203984

Full-text PDF

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 the arithmetical degrees*, Ann. Pure Appl. Logic**32**(1986), 113-135. MR**863330 (88j:03021)****[2]**C. J. Ash, C. Jockusch, and J. F. Knight,*Jumps of orderings*, Trans. Amer. Math. Soc.**319**(1991), 573-599. MR**955487 (90j:03081)****[3]**R. G. Downey,*Every recursive Boolean algebra is isomorphic to one with incomplete atoms*, Ann. Pure Appl. Logic**60**(1993), 193-206. MR**1216669 (94c:03059)****[4]**-,*Recursion theory and linear orderings*, Handbook of Recursive Algebra (A. Nerode and J. Remmel, eds.) (to appear).**[5]**R. G. Downey and J. F. Knight,*Orderings with**th jump degree*, Proc. Amer. Math. Soc.**114**(1992), 545-552. MR**1065942 (92e:03063)****[6]**R. G. Downey and M. F. Moses,*Recursive linear orderings with incomplete successivities*, Trans. Amer. Math. Soc.**326**(1991), 653-668. MR**1005933 (91k:03115)****[7]**L. J. Feiner,*Orderings and Boolean algebras not isomorphic to recursive ones*, Thesis, MIT, Cambridge, MA, 1967.**[8]**-,*Hierarchies of Boolean algebras*, J. Symbolic Logic**35**(1970), 365-374. MR**0282805 (44:39)****[9]**-,*The strong homogeneity conjecture*, J. Symbolic Logic**35**(1970), 375-377. MR**0286655 (44:3864)****[10]**-,*Degrees of non-recursive presentability*, Proc. Amer. Math. Soc.**38**(1973), 621-624. MR**0327494 (48:5836)****[11]**S. S. Goncharov,*Some properties of the constructivization of Boolean algebras*, Sibirski Mat. Zh.**16**(1975), 264-278. MR**0381957 (52:2846)****[12]**C. G. Jockusch and R. I. Soare,*Degrees of orderings not isomorphic to recursive linear orderings*, Ann. Pure Appl. Logic**52**(1991), 39-64. MR**1104053 (92c:03051)****[13]**C. G. Jockusch and R. I. Soare,*Boolean algebras, Stone spaces, and the iterated Turing jump*, preprint.**[14]**J. F. Knight,*Degrees coded in jumps of orderings*, J. Symbolic Logic**51**(1986), 1034-1042. MR**865929 (88j:03030)****[15]**-,*A metatheorem for finitely many workers*, J. Symbolic Logic**55**(1990), 787-804. MR**1056389 (91i:03089)****[16]**M. Lerman,*On recursive linear orders*, Logic Year 1979-80 (Lerman, Schmerl, and Soare, eds.), Lecture Notes in Math., vol. 859, Springer-Verlag, New York, 1981, pp. 132-142. MR**619867 (82i:03059)****[17]**W. Magnus, A. Karrass, and D. Solitar,*Combinatorial group theory*, Academic Press, New York, 1965.**[18]**D. Monk,*Handbook of Boolean algebras*, Vol. 3, North-Holland, Amsterdam, 1989. MR**991607 (90k:06004)****[19]**S. Oates,*Jump degrees of groups*, Ph.D. thesis, Univ. of Notre Dame, 1989.**[20]**J. B. Remmel,*Recursive Boolean algebras with recursive atoms*, J. Symbolic Logic**46**(1981), 595-616. MR**627908 (82j:03055)****[21]**-,*Recursive isomorphism types of recursive Boolean algebras*, J. Symbolic Logic**46**(1981), 572-594. MR**627907 (83a:03042)****[22]**L. J. Richter,*Degrees of unsolvability of models*, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1977.**[23]**-,*Degrees of structures*, J. Symbolic Logic**46**(1981), 723-731. MR**641486 (83d:03048)****[24]**H. J. Rogers,*Theory of recursive functions and effective computability*, McGraw-Hill, New York, 1967. MR**0224462 (37:61)****[25]**J. Rosenstein,*Linear orderings*, Academic Press, New York, 1982. MR**662564 (84m:06001)****[26]**R. I. Soare,*Recursively enumerable sets and degrees*, Springer-Verlag, New York, 1987. MR**882921 (88m:03003)****[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]**R. Watnick,*A generalization of Tennenbaum's theorem on effectively finite linear orderings*, J. Symbolic Logic**49**(1984), 563-569. MR**745385 (85i:03152)**

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:
https://doi.org/10.1090/S0002-9939-1994-1203984-4

Article copyright:
© Copyright 1994
American Mathematical Society