Every low Boolean algebra is isomorphic to a recursive one

Downey, Rod; Jockusch, Carl G.

doi:10.1090/S0002-9939-1994-1203984-4

Every low Boolean algebra is isomorphic to a recursive one
HTML articles powered by AMS MathViewer

by Rod Downey and Carl G. Jockusch

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

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

PDF | 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

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

Orderings and Boolean algebras not isomorphic to recursive ones

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

Boolean algebras, Stone spaces, and the iterated Turing jump

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

Combinatorial group theory

J. Donald Monk and Robert Bonnet (eds.), Handbook of Boolean algebras. Vol. 3, North-Holland Publishing Co., Amsterdam, 1989. MR 991607

Jump degrees of groups

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

Degrees of unsolvability of models

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-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

Every

Boolean algebra has a recursive copy

Topics in the theory of arithmetical classes and Boolean algebras

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