Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-28T17:10:48.111Z Has data issue: false hasContentIssue false

Vaught's theorem recursively revisited1

Published online by Cambridge University Press:  12 March 2014

Terrence Millar*
Affiliation:
University of Wisconsin, Madison, Wisconsin 53706

Extract

In this paper we investigate the relationship between the number of countable and decidable models of a complete theory. The number of decidable models will be determined in two ways, in §1 with respect to abstract isomorphism type, and in §2 with respect to recursive isomorphism type.

Definition 1. A complete theory is (α, β) if the number of countable models of T, up to abstract isomorphism, is β, and similarly the number of decidable models of T is α.

Definition 2. A model is ω-decidable if ∣∣= ω and for an effective listing {θnn < ω} of all sentences in the language of Th() augmented by new constant symbols i*, i < ω, {n ∣〈, ii<ωθn} is recursive, where i interprets i* (in these terms, is decidable if is abstractly isomorphic to an ω-decidable model).

Definition 3. A complete theory is (α, β)r if it is (γ, β) for some γ and it has exactly αω-decidable models up to recursive isomorphism.

Specifically we will show in §1 that there is a (2, ω) theory, and in §2 that although there is a (2, 2ω) theory, there is no (2, β)r theory for any β, β < 2ω.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1981

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

Footnotes

1

The preparation of this paper was partially supported by Grant NSF-MCS 77-00802.

References

REFERENCES

[1]Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[2]Sacks, G. E., Saturated model theory, Benjamin, New York, 1972.Google Scholar
[3]Chang, C. C. and Keisler, H. J., Model theory, North-Holland, Amsterdam, 1973.Google Scholar
[4]Millar, T., Foundations of recursive model theory, Annals of Mathematical Logic, no. 13, North-Holland, Amsterdam, 1978, pp. 4572.Google Scholar
[5]Millar, T., A complete, decidable theory with exactly two decidable models, this Journal, vol. 44 (1979), pp. 307312.Google Scholar
[6]Nurtazin, A. T., Strong and weak constructivization and computable families, Algebra i Logika, vol. 13 (1974), pp. 311323.Google Scholar