Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T12:36:49.706Z 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 {θn∣n < ω} of all sentences in the language of Th() augmented by new constant symbols i*, i < ω, {n ∣〈, i〉i<ω ⊨ θ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ω.

Information

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

Article purchase

Temporarily unavailable