Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-20T01:01:44.962Z Has data issue: false hasContentIssue false

Co-hypersimple structures

Published online by Cambridge University Press:  12 March 2014

J. B. Remmel*
Affiliation:
University of California, San Diego, La Jolla, California 92037

Extract

Priority arguments have been used to produce r.e. sets whose complements have various properties (e.g., maximal sets, hyperhypersimple sets, etc.). In this paper we use the priority method in the context of certain recursively presented models (e.g., dense unbordered linear orderings, countable atomless Boolean algebras, infinite dimensional vector spaces over a finite field) to produce hypersimple subsets of these models whose complements are closed under algebraic operations and/or whose complements are elementarily isomorphic to certain algebraic substructures. For example, it follows from the results of §3 that there are hypersimple subsets of a countable atomless Boolean algebra (of an infinite dimensional vector space over a finite field) in every nonzero r.e. degree whose complement is a subalgebra (subspace). Also, it follows from the same result that, given any subset P of the rationals Q, there is a hypersimple subset of Q whose complement is order isomorphic to P.

A model M of a theory T in a countable language L is said to be recursively presented if the universe ∣M∣ of M is an initial segment of the natural numbers and the satisfaction relation “a satisfies Φ in M” is recursive (where a is a finite sequence of elements of ∣M∣ and Φ is a formula in L).

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1976

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Crossley, J. N. and Nerode, A., Combinatorial functors, Springer-Verlag, Berlin, 1974.CrossRefGoogle Scholar
[2] Eisenberg, E., Effective isomorphisms of algebraic systems, Ph.D. Thesis, Cornell University, 1974.Google Scholar
[3] Feiner, Lawrence, Degrees of non-recursively presentability, Proceedings of the American Mathematical Society, vol. 38 (1973), pp. 621624.CrossRefGoogle Scholar
[4] Hay, L. S., The co-simple isols, Annals of Mathematics, vol. 83 (1966), pp. 231256.CrossRefGoogle Scholar
[5] Metakides, G. and Nerode, A., Recursion theory and algebra, Algebra and logic, Springer-Verlag Lecture Notes, 450 (1975), pp. 209219.CrossRefGoogle Scholar
[6] Metakides, G. and Nerode, A., Recursively enumerable vector spaces, Annals of Mathematics , (to appear).Google Scholar
[7] Remmel, J. B., Maximal and cohesive subspaces, this Journal, (to appear).Google Scholar
[8] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar