Every low Boolean algebra is isomorphic to a recursive one
HTML articles powered by AMS MathViewer
- by Rod Downey and Carl G. Jockusch PDF
- Proc. Amer. Math. Soc. 122 (1994), 871-880 Request permission
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
- C. J. Ash, Stability of recursive structures in arithmetical degrees, Ann. Pure Appl. Logic 32 (1986), no. 2, 113–135. MR 863330, DOI 10.1016/0168-0072(86)90048-5
- 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, DOI 10.1090/S0002-9947-1990-0955487-0
- 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, DOI 10.1016/0168-0072(93)90075-O —, Recursion theory and linear orderings, Handbook of Recursive Algebra (A. Nerode and J. Remmel, eds.) (to appear).
- Rodney Downey and Julia F. Knight, Orderings with $\alpha$th jump degree ${\bf 0}^{(\alpha )}$, Proc. Amer. Math. Soc. 114 (1992), no. 2, 545–552. MR 1065942, DOI 10.1090/S0002-9939-1992-1065942-0
- 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, DOI 10.1090/S0002-9947-1991-1005933-2 L. J. Feiner, Orderings and Boolean algebras not isomorphic to recursive ones, Thesis, MIT, Cambridge, MA, 1967.
- Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365–374. MR 282805, DOI 10.2307/2270692
- L. Feiner, The strong homogeneity conjecture, J. Symbolic Logic 35 (1970), 375–377. MR 286655, DOI 10.2307/2270693
- Lawrence Feiner, Degrees of nonrecursive presentability, Proc. Amer. Math. Soc. 38 (1973), 621–624. MR 327494, DOI 10.1090/S0002-9939-1973-0327494-8
- S. S. Gončarov, Certain properties of the constructivization of Boolean algebras, Sibirsk. Mat. Ž. 16 (1975), 264–278, 420. (loose errata) (Russian). MR 0381957
- 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, DOI 10.1016/0168-0072(91)90038-N C. G. Jockusch and R. I. Soare, Boolean algebras, Stone spaces, and the iterated Turing jump, preprint.
- Julia F. Knight, Degrees coded in jumps of orderings, J. Symbolic Logic 51 (1986), no. 4, 1034–1042. MR 865929, DOI 10.2307/2273915
- J. F. Knight, A metatheorem for constructions by finitely many workers, J. Symbolic Logic 55 (1990), no. 2, 787–804. MR 1056389, DOI 10.2307/2274665
- 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 W. Magnus, A. Karrass, and D. Solitar, Combinatorial group theory, Academic Press, New York, 1965.
- J. Donald Monk and Robert Bonnet (eds.), Handbook of Boolean algebras. Vol. 3, North-Holland Publishing Co., Amsterdam, 1989. MR 991607 S. Oates, Jump degrees of groups, Ph.D. thesis, Univ. of Notre Dame, 1989.
- Jeffrey B. Remmel, Recursive Boolean algebras with recursive atoms, J. Symbolic Logic 46 (1981), no. 3, 595–616. MR 627908, DOI 10.2307/2273758
- J. B. Remmel, Recursive isomorphism types of recursive Boolean algebras, J. Symbolic Logic 46 (1981), no. 3, 572–594. MR 627907, DOI 10.2307/2273757 L. J. Richter, Degrees of unsolvability of models, Ph.D. thesis, University of Illinois at Urbana-Champaign, 1977.
- Linda Jean Richter, Degrees of structures, J. Symbolic Logic 46 (1981), no. 4, 723–731. MR 641486, DOI 10.2307/2273222
- Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
- Joseph G. Rosenstein, Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662564
- 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, DOI 10.1007/978-3-662-02460-7 J. Thurber, Every $lo{w_2}$ Boolean algebra has a recursive copy (to appear). R. Vaught, Topics in the theory of arithmetical classes and Boolean algebras, Ph.D. thesis, University of California, Berkeley, 1954.
- 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, DOI 10.2307/2274189
Additional Information
- © Copyright 1994 American Mathematical Society
- 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