Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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 $ \leq 0' $ which is not isomorphic to a recursive Boolean algebra. It is also shown that for each n there is a finitely axiomatizable theory $ {T_n}$ such that every $ {\text{low}_n}$ model of $ {T_n}$ is isomorphic to a recursive structure but there is a $ {\text{low}_{n + 1}}$ model of $ {T_n}$ which is not isomorphic to any recursive structure. In addition, we show that $ n + 2$ is the Turing ordinal of the same theory $ {T_n}$, 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 $ \alpha $ for $ 3 \leq \alpha < \omega $.


References [Enhancements On Off] (What's this?)

  • [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 $ \alpha$th jump degree $ {0^{(\alpha )}}$, 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 $ lo{w_2}$ 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)

Similar Articles

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

American Mathematical Society