Vaught conjecture
Encyclopedia
The Vaught conjecture is a conjecture
in the mathematical field of model theory
originally proposed by Robert Lawson Vaught
in 1961. It states that the number of countable models of a first-order complete theory in a countable language is finite or ℵ0 or 2ℵ0. Morley showed that number of countable models is finite or ℵ0 or ℵ1 or 2ℵ0, which solves the conjecture except for the case of ℵ1 models when the continuum hypothesis fails. For this remaining case, has announced a counterexample to the Vaught conjecture and the topological Vaught conjecture.
be a first-order, countable, complete theory with infinite models. Let 
denote the number of models of T of cardinality 
up to isomorphism, the spectrum
of the theory
. Morley proved that if I(T,ℵ0) is infinite then it must be ℵ0 or ℵ1 or the cardinality of the continuum. The Vaught conjecture is the statement that it is not possible for 
. The conjecture is a trivial consequence of the continuum hypothesis
; so this axiom is often excluded in work on the conjecture. Alternatively there is a sharper form of the conjecture which states that any countable complete T with uncountably many countable models will have a perfect set of uncountable models (as pointed out by John Steel, in On Vaught's conjecture. Cabal Seminar 76—77 (Proc. Caltech-UCLA Logic Sem., 1976—77), pp. 193–208, Lecture Notes in Math., 689, Springer, Berlin, 1978, this form of the Vaught conjecture is equiprovable with the original).
The idea of the proof of Vaught's theorem is as follows. If there are at most countably many countable models, then there is a smallest one: the atomic model, and a largest one, the saturated model
, which are different if there is more than one model. If they are different, the saturated model must realize some n-type omitted by the atomic model. Then one can show that an atomic model of the theory of structures realizing this n-type (in a language expanded by finitely many constants) is a third model, not isomorphic to either the atomic or the saturated model. In the example above with 3 models, the atomic model is the one where the sequence is unbounded, the saturated model is the one where the sequence does not converge, and an example of a type not realized by the atomic model is an element greater than all elements of the sequence.
, A. Mostowski, C. Ryall-Nardzewski, "Definability of sets of models of axiomatic theories", Bulletin of the Polish Academy of Sciences (series Mathematics, Astronomy, Physics), vol. 9(1961), pp. 163–7 that the resulting space is Polish. There is a continuous action of the infinite symmetric group (the collection of all permutations of the natural numbers with the topology of point wise convergence) which gives rise to the equivalence relation of isomorphism. Given a complete first order theory T, the set of structures satisfying T is a minimal, closed invariant set, and hence Polish in its own right.
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
in the mathematical field of model theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
originally proposed by Robert Lawson Vaught
Robert Lawson Vaught
Robert Lawson Vaught was a mathematical logician, and one of the founders of model theory.-Life:Vaught was a bit of a musical prodigy in his youth, in his case the piano. He began his university studies at Pomona College, at age 16. When World War II broke out, he enlisted US Navy which assigned...
in 1961. It states that the number of countable models of a first-order complete theory in a countable language is finite or ℵ0 or 2ℵ0. Morley showed that number of countable models is finite or ℵ0 or ℵ1 or 2ℵ0, which solves the conjecture except for the case of ℵ1 models when the continuum hypothesis fails. For this remaining case, has announced a counterexample to the Vaught conjecture and the topological Vaught conjecture.
Statement of the conjecture
Let be a first-order, countable, complete theory with infinite models. Let denote the number of models of T of cardinality up to isomorphism, the spectrumSpectrum of a theory
In model theory, a branch of mathematical logic, the spectrum of a theoryis given by the number of isomorphism classes of models in various cardinalities. More precisely,...
of the theory
. Morley proved that if I(T,ℵ0) is infinite then it must be ℵ0 or ℵ1 or the cardinality of the continuum. The Vaught conjecture is the statement that it is not possible for . The conjecture is a trivial consequence of the continuum hypothesisContinuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
; so this axiom is often excluded in work on the conjecture. Alternatively there is a sharper form of the conjecture which states that any countable complete T with uncountably many countable models will have a perfect set of uncountable models (as pointed out by John Steel, in On Vaught's conjecture. Cabal Seminar 76—77 (Proc. Caltech-UCLA Logic Sem., 1976—77), pp. 193–208, Lecture Notes in Math., 689, Springer, Berlin, 1978, this form of the Vaught conjecture is equiprovable with the original).
Vaught's theorem
Vaught proved that the number of countable models of a theory cannot be 2. It can be any finite number other than 2, for example:- Any complete theory with a finite model has no countable models.
- The theories with just one countable model are the ω-categorical theories. There are many examples of these, such as the theory of an infinite set.
- Ehrenfeucht gave the following example of a theory with 3 countable models: the language has a relation ≥ and a countable number of constants c0, c1, ...with axioms stating that ≥ is a dense unbounded total order, and c0< c1<c2... The three models differ according to whether this sequence is unbounded, or converges, or is bounded but does not converge.
- Ehrenfeucht's example can be modified to give a theory with any finite number n≥3 of model by adding n−2 unary relations Pi to the language, with axioms stating that for every x exactly one of the Pi is true, the values of y for which Pi(y) is true are dense, and P1 is true for all ci. Then the models for which the sequence of elements ci converge to a limit c split into n−2 cases depending on for which i the relation Pi(c) is true.
The idea of the proof of Vaught's theorem is as follows. If there are at most countably many countable models, then there is a smallest one: the atomic model, and a largest one, the saturated model
Saturated model
In mathematical logic, and particularly in its subfield model theory, a saturated model M is one which realizes as many complete types as may be "reasonably expected" given its size...
, which are different if there is more than one model. If they are different, the saturated model must realize some n-type omitted by the atomic model. Then one can show that an atomic model of the theory of structures realizing this n-type (in a language expanded by finitely many constants) is a third model, not isomorphic to either the atomic or the saturated model. In the example above with 3 models, the atomic model is the one where the sequence is unbounded, the saturated model is the one where the sequence does not converge, and an example of a type not realized by the atomic model is an element greater than all elements of the sequence.
Topological Vaught conjecture
The topological Vaught conjecture is the statement that whenever a Polish group acts continuously on a Polish space, there are either countably many orbits or continuum many orbits. The topological Vaught conjecture is more general than the original Vaught conjecture: Given a countable language we can form the space of all structures on the natural numbers for that language. If we equip this with the topology generated by first order formulas, then it is known from A. GregorczykAndrzej Grzegorczyk
Andrzej Grzegorczyk is a Polish mathematician. He is known for his work in computability, logic, and the foundations of mathematics...
, A. Mostowski, C. Ryall-Nardzewski, "Definability of sets of models of axiomatic theories", Bulletin of the Polish Academy of Sciences (series Mathematics, Astronomy, Physics), vol. 9(1961), pp. 163–7 that the resulting space is Polish. There is a continuous action of the infinite symmetric group (the collection of all permutations of the natural numbers with the topology of point wise convergence) which gives rise to the equivalence relation of isomorphism. Given a complete first order theory T, the set of structures satisfying T is a minimal, closed invariant set, and hence Polish in its own right.
See also
- Spectrum of a theorySpectrum of a theoryIn model theory, a branch of mathematical logic, the spectrum of a theoryis given by the number of isomorphism classes of models in various cardinalities. More precisely,...
- Morley's categoricity theoremMorley's categoricity theoremIn model theory, a branch of mathematical logic, a theory is κ-categorical if it has exactly one model of cardinality κ up to isomorphism....