Spectrum of a theory

Spectrum of a theory

In model theory, a branch of mathematical logic, the spectrum of a theory is given by the number of isomorphism classes of models in various cardinalities. More precisely, for any complete theory T in a language we write I(T, α) for the number of models of T (up to isomorphism) of cardinality α. The spectrum problem is to describe the possible behaviors of I(T, α) as a function of α. It has been almost completely solved for the case of a countable theory T.

Early results

In this section T is a countable complete theory.

The Löwenheim–Skolem theorem shows that if I(T, α) is nonzero for one infinite cardinal then it is nonzero for all of them.

Morley's categoricity theorem was the first main step in solving the spectrum problem: it states that if I(T, α) is 1 for some uncountable α then it is 1 for all uncountable α.

Robert Vaught showed that I(T,ω) cannot be 2. It is easy to find examples where it is any given non-negative integer other than 2. Morley proved that if I(T,ω) is infinite then it must be ℵ0 or ℵ1 or the cardinality of the continuum. It is not known if it can be ℵ1 if the continuum hypothesis is false: this is called the Vaught conjecture and is the main remaining open problem (in 2005) in the theory of the spectrum.

Morley's problem is a conjecture (first proposed by Michael D. Morley) in mathematical logic that I(T, α) is nondecreasing in α for uncountable α. This was proved by Saharon Shelah. For this, he proved a very deep dichotomy theorem.

Saharon Shelah gave an almost complete solution to the spectrum problem. For a given complete theory T, either I(T, α) = 2α for all uncountable α, or  I(T, \aleph_\xi) < \beth_{\omega_1}(|\xi|) (See aleph number and beth number for an explanation of the notation) for all ordinals ξ, which is usually much smaller than the bound in the first case. Roughly speaking this says that either there are the maximum possible number of models in all uncountable cardinalities, or there are only "few" models in all uncountable cardinalities. Shelah also gave a description of the possible spectra in the case when there are few models.

List of possible spectra of a countable theory

By extending Shelah's work, Bradd Hart, Ehud Hrushovski, Michael C. Laskowski gave the following complete solution to the spectrum problem for countable theories in uncountable cardinalities. If T is a countable complete theory, then the number I(T, ℵα) of isomorphism classes of models is given for ordinals α>0 by the minimum of 2α and one of the following maps:

  1. 2α. Examples: there are many examples, in particular any unclassifiable or deep theory, such as the theory of the random graph.
  2. \beth_{d+1}(|\alpha+\omega|) for some countable infinite ordinal d. (For finite d see case 8.) Examples: The theory with equivalence relations Eβ for all β with β+1<d, such that every Eγ class is a union of infinitely many Eβ classes, and each E0 class is infinite.
  3. \beth_{d-1}(|\alpha+\omega|^{2^{\aleph_0}}) for some finite positive ordinal d. Example (for d=1): the theory of countably many independent unary predicates.
  4. \beth_{d-1}(|\alpha+\omega|^{\aleph_0}+\beth_2) for some finite positive ordinal d.
  5. \beth_{d-1}(|\alpha+\omega|+\beth_2) for some finite positive ordinal d;
  6. \beth_{d-1}(|\alpha+\omega|^{\aleph_0}) for some finite positive ordinal d. Example (for d=1): the theory of countable many disjoint unary predicates.
  7. \beth_{d-1}(|\alpha+\omega|+\beth_1) for some finite ordinal d≥2;
  8. \beth_{d-1}(|\alpha+\omega|) for some finite positive ordinal d;
  9. \beth_{d-2}(|\alpha+\omega|^{|\alpha+1|}) for some finite ordinal d≥2; Examples: similar to case 2.
  10. \beth_2. Example: the theory of the integers viewed as an abelian group.
  11. | (α + 1)n / G | − | αn / G | for finite α, and |α| for infinite α, where G is some subgroup of the symmetric group on n ≥ 2 elements. Here, we identify αn with the set of sequences of length n of elements of a set of size α. G acts on αn by permuting the sequence elements, and |αn/G| denotes the number of orbits of this action. Examples: the theory of the set ω×n acted on by the wreath product of G with all permutations of ω.
  12. 1. Examples: theories that are categorical in uncountable cardinals, such as the theory of algebraically closed fields in a given characteristic.
  13. 0. Examples: theories with a finite model, and the inconsistent theory.

Moreover, all possibilities above occur as the spectrum of some countable complete theory.

The number d in the list above is the depth of the theory. If T is a theory we define a new theory 2T to be the theory with an equivalence relation such that there are infinitely many equivalence classes each of which is a model of T. We also define theories \beth_n(T) by \beth_0(T)=T, \beth_{n+1}(T)=2^{\beth_n(T)}. Then I(\beth_n(T), \lambda)= \min(\beth_n(I(T,\lambda)), 2^\lambda) . This can be used to construct examples of theories with spectra in the list above for non-minimal values of d from examples for the minimal value of d.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Spectrum (disambiguation) — A spectrum is a condition or value that is not limited to a specific set of values but can vary infinitely within a continuum.Spectrum may refer to:In physical sciences: * electromagnetic spectrum ** visible spectrum or optical spectrum, a subset …   Wikipedia

  • Theory of mind — is the ability to attribute mental states beliefs, intents, desires, pretending, knowledge, etc. to oneself and others and to understand that others have beliefs, desires and intentions that are different from one s own.[1] Though there are… …   Wikipedia

  • Spectrum analysis — also known as Emission Spectrochemical Analysis is the original scientific method of charting and analyzing the chemical properties of matter and gases by looking at the bands in their optical spectrum. The empirical laws of spectrum analysis are …   Wikipedia

  • Theory of Colours — Infobox Book name = Theory of Colours title orig = Zur Farbenlehre translator = Charles Eastlake [http://findarticles.com/p/articles/mi m0422/is 2 82/ai 64573524/pg 6] image caption = Light spectrum, from Theory of Colours – Goethe observed that… …   Wikipedia

  • Spectrum (homotopy theory) — In algebraic topology, a branch of mathematics, a spectrum is an object representing a generalized cohomology theory. There are several different constructions of categories of spectra, all of which give the same homotopy category.Suppose we… …   Wikipedia

  • Spectrum (functional analysis) — In functional analysis, the concept of the spectrum of a bounded operator is a generalisation of the concept of eigenvalues for matrices. Specifically, a complex number λ is said to be in the spectrum of a bounded linear operator T if… …   Wikipedia

  • Spectrum of a C*-algebra — The spectrum of a C* algebra or dual of a C* algebra A, denoted Â, is the set of unitary equivalence classes of irreducible * representations of A. A * representation π of A on a Hilbert space H is irreducible if, and only if, there is no closed… …   Wikipedia

  • Spectrum analyzer — A spectrum analyzer Spectrum analyzer display A spectrum analyzer measures the magnitude of an input signal versus frequency with …   Wikipedia

  • Spectrum management — The spectrum is a conceptual tool used to organize and map the physical phenomena of electromagnetic waves. These waves propagate through space at different frequencies, and the set of all possible frequencies is called the electromagnetic… …   Wikipedia

  • Theory of multiple intelligences — Human intelligence Abilities and Traits Abstract thought Communication · Creativity Emotional Intelligence Kn …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”