Maximal theories. (English) Zbl 0629.03019
This paper studies the concept of “maximality” in the lattice L of r.e. theories of proportions based on a fixed recursive set of literals \(\{P_ i:\) \(i\in \omega \}\) (or equivalently, the lattice of r.e. ideals in the recursive copy of the countable atomless Boolean algebra). D. A. Martin and M. B. Pour-El [‘Axiomatizable theories with few axiomatizable extensions’ J. Symb. Logic 35, 205-209 (1970; Zbl 0209.012)] constructed an r.e. theory T with few r.e. extensions: that is T is essentially undecidable and all r.e. extensions of T are principal over T. In fact, their T was also constructed as generated by \(\{P_ i:\) \(i\in A\}\cup \{\bar P_ j:\) \(j\in B\}\) for suitable A and B. We show such theories can exist in some but not all r.e. degrees, and they can have low degrees. Subsequent work of C. G. Jockusch, M. Stob and the author [“Array nonrecursive sets and multiple permitting arguments” (in preparation)] have shown that such T occur in exactly the “array nonrecursive” degrees. The paper also studies other concepts of maximality in L and also in L’ the lattice of r.e. sub-theories of a fixed deciable complete theory. The techniques are of course algebraic priority arguments.
MSC:
| 03D45 | Theory of numerations, effectively presented structures |
Citations:
Zbl 0209.012References:
| [1] | M. Bickford and C. Mills, Lowness properties of r.e. sets, J. Symbolic Logic, to appear.; M. Bickford and C. Mills, Lowness properties of r.e. sets, J. Symbolic Logic, to appear. |
| [2] | Downey, R. G., Abstract dependence, recursion theory and the lattice of recursively enumerable filters, (Ph.D. Thesis (1982), Monash University, Victoria: Monash University, Victoria Australia) · Zbl 0509.03021 |
| [3] | Downey, R. G., On the lattice of r.e. filters axiomatizable theories and /\( qP_1^0\) classes, Monash Logic series 36 (1981), Preprint |
| [4] | Downey, R. G., On a question of A. Retzlaff, Z. Math. Logik. Grundl. Math., 29, 379-384 (1983) · Zbl 0526.03028 |
| [5] | Downey, R. G.; Hird, G. R., Automorphisms of supermaximal subspaces, J. Symbolic Logic, 50, 1-9 (1985) · Zbl 0572.03024 |
| [6] | Downey, R. G., Nowhere simplicity in matroids, J. Austral. Math. Soc. (Ser. A), 28-45 (1983) · Zbl 0526.03027 |
| [7] | Downey, R. G., Co-immune subspaces and complementation in \(V_∞\), J. Symbolic Logic, 49, 528-538 (1984) · Zbl 0579.03032 |
| [8] | E. Hermann, Orbits of hyperhypersimple sets and the lattice of \(Σ_3^0\); E. Hermann, Orbits of hyperhypersimple sets and the lattice of \(Σ_3^0\) |
| [9] | E. Hermann, Definable structures in the lattice of recursively enumerable sets, to appear.; E. Hermann, Definable structures in the lattice of recursively enumerable sets, to appear. · Zbl 0579.03026 |
| [10] | E. Hermann, Definable boolean pairs in the lattice of recursively enumerable sets, to appear.; E. Hermann, Definable boolean pairs in the lattice of recursively enumerable sets, to appear. · Zbl 0517.03013 |
| [11] | Jockusch, C.; Shore, R. A., Pseudo jump operators I: the r.e. case, Trans. A.M.S., 275, 599-609 (1983) · Zbl 0514.03028 |
| [12] | Jockusch, C.; Soare, R. I., /\( qP_1^0\) classes and degrees of theories, Trans. A.M.S., 173, 33-56 (1972) · Zbl 0262.02041 |
| [13] | Jockusch, C.; Soare, R. I., Degrees of members of /\( qP_1^0\) classes, Pacific J. Math., 40, 605-616 (1972) · Zbl 0209.02201 |
| [14] | Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik. Grundl. Math., 12, 295-310 (1966) · Zbl 0181.30504 |
| [15] | Martin, D. A.; Pour-El, M. B., Axiomatizable theories with few axiomatizable extensions, J. Symbolic Logic, 35, 205-209 (1970) · Zbl 0209.01204 |
| [16] | Metakides, G.; Nerode, A., Recursion theory and algebra, (Crossley, J. N., Algebra and Logic, Lecture Notes in Math., 450 (1975), Springer: Springer Berlin), 209-219 · Zbl 0306.02038 |
| [17] | Metakides, G.; Nerode, A., Recursively enumerable vector spaces, Ann. Math. Logic, 11, 147-171 (1977) · Zbl 0389.03019 |
| [18] | Remmel, J. B., recursively enumerable boolean algebras, Ann. Math. Logic, 14, 75-107 (1978) · Zbl 0413.03027 |
| [19] | Remmel, J. B., recursion theory on algebraic structures with an independent set, Ann. Math. Logic, 18, 153-191 (1980) · Zbl 0471.03037 |
| [20] | Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401 |
| [21] | Soare, R. I., The infinite injury priority method, J. Symbolic Logic, 41, 513-530 (1976) · Zbl 0329.02019 |
| [22] | Smullyan, R., Theory of Formal Systems, (Ann. Math. Studies, 47 (1961), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 0097.24503 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
