Morley's categoricity theorem
Encyclopedia
In model theory
, a branch of mathematical logic
, a theory is κ-categorical (or categorical in κ) if it has exactly one model of cardinality
κ up to isomorphism.
Morley's categoricity theorem is a theorem of which states that if a first-order theory in a countable language is categorical in some uncountable cardinality, then it is categorical in all uncountable cardinalities.
extended Morley's theorem to uncountable languages: if the language has cardinality κ and a theory is categorical in some uncountable cardinal greater than or equal to κ then it is categorical in all cardinalities greater than κ.
in 1904 defined a theory to be categorical if all of its models are isomorphic. It follows from the definition above and the Löwenheim–Skolem theorem
that any first-order theory with a model of infinite cardinality
cannot be categorical. One is then immediately led to the more subtle notion of κ-categoricity, which asks: for which cardinals κ is there exactly one model of cardinality κ of the given theory T up to isomorphism? This is a deep question and significant progress was only made in 1954 when Jerzy Łoś noticed that, at least for complete theories
T over countable languages
with at least one infinite model, he could only find three ways for T to be κ-categorical at some κ:
In other words, he observed that, in all the cases he could think of, κ-categoricity at any one uncountable cardinal implied κ-categoricity at all other uncountable cardinals. This observation spurred a great amount of research into the 1960s, eventually culminating in Michael Morley
's famous result that these are in fact the only possibilities. The theory was subsequently extended and refined by Saharon Shelah
in the 1970s and beyond, leading to stability theory and Shelah's more general programme of classification theory
.
There are also examples of theories that are categorical in ω but not categorical in uncountable cardinals.
The simplest example is the theory of an equivalence relation with exactly two equivalence classes both of which are infinite. Another example is the theory of dense linear orders with no endpoints; Cantor proved that any such countable linear order is isomorphic to the rational numbers.
Any theory T categorical in some infinite cardinal κ is very close to being complete. More precisely, the Łoś–Vaught test states that if a theory has no finite models and is categorical in some infinite cardinal κ at least equal to the cardinality of its language, then the theory is complete. The reason is that all infinite models are equivalent to some model of cardinal κ by the Löwenheim–Skolem theorem
, and so are all equivalent as the theory is categorical in κ. Therefore the theory is complete as all models are equivalent.
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
, a branch of mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, a theory is κ-categorical (or categorical in κ) if it has exactly one model of cardinality
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
κ up to isomorphism.
Morley's categoricity theorem is a theorem of which states that if a first-order theory in a countable language is categorical in some uncountable cardinality, then it is categorical in all uncountable cardinalities.
extended Morley's theorem to uncountable languages: if the language has cardinality κ and a theory is categorical in some uncountable cardinal greater than or equal to κ then it is categorical in all cardinalities greater than κ.
History and motivation
Oswald VeblenOswald Veblen
Oswald Veblen was an American mathematician, geometer and topologist, whose work found application in atomic physics and the theory of relativity. He proved the Jordan curve theorem in 1905.-Life:...
in 1904 defined a theory to be categorical if all of its models are isomorphic. It follows from the definition above and the Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
that any first-order theory with a model of infinite cardinality
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
cannot be categorical. One is then immediately led to the more subtle notion of κ-categoricity, which asks: for which cardinals κ is there exactly one model of cardinality κ of the given theory T up to isomorphism? This is a deep question and significant progress was only made in 1954 when Jerzy Łoś noticed that, at least for complete theories
Complete theory
In mathematical logic, a theory is complete if it is a maximal consistent set of sentences, i.e., if it is consistent, and none of its proper extensions is consistent...
T over countable languages
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
with at least one infinite model, he could only find three ways for T to be κ-categorical at some κ:
- T is totally categorical, i.e. T is κ-categorical for all infinite cardinalCardinal numberIn mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
s κ. - T is uncountably categorical, i.e. T is κ-categorical if and only if κ is an uncountable cardinal.
- T is countably categorical, i.e. T is κ-categorical if and only if κ is a countable cardinal.
In other words, he observed that, in all the cases he could think of, κ-categoricity at any one uncountable cardinal implied κ-categoricity at all other uncountable cardinals. This observation spurred a great amount of research into the 1960s, eventually culminating in Michael Morley
Michael D. Morley
Michael Darwin Morley is an American mathematician, currently professor emeritus at Cornell University.His research is in advanced mathematical logic and model theory, and he is best known for Morley's categoricity theorem, which he proved in his Ph.D. thesis "Categoricity in Power" in 1962.His...
's famous result that these are in fact the only possibilities. The theory was subsequently extended and refined by Saharon Shelah
Saharon Shelah
Saharon Shelah is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.-Biography:...
in the 1970s and beyond, leading to stability theory and Shelah's more general programme of classification theory
Spectrum 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,...
.
Examples
There are not many natural examples of theories that are categorical in some uncountable cardinal. The known examples include:- Pure identity theory (with no functions, constants, predicates other than "=", or axioms).
- The classic example is the theory of algebraically closed fieldAlgebraically closed fieldIn mathematics, a field F is said to be algebraically closed if every polynomial with one variable of degree at least 1, with coefficients in F, has a root in F.-Examples:...
s of a given characteristic. Categoricity does not say that all algebraically closed fields of characteristic 0 as large as the complex numbers C are the same as C; it only asserts that they are isomorphic as fields to C. It follows that although the completed p-adic closures Cp are all isomorphic as fields to C, they may (and in fact do) have completely different topological and analytic properties. The theory of algebraically closed fields of given characteristic is not categorical in ω (the countable infinite cardinal); there are models of transcendence degree 0, 1, 2, ..., ω. - Vector spaceVector spaceA vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
s over a given countable field. This includes abelian groupAbelian groupIn abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
s of given prime exponent (essentially the same as vector spaces over a finite field) and divisible torsion-free abelian groups (essentially the same as vector spaces over the rationals). - The theory of the set of natural numberNatural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s with a successor function.
There are also examples of theories that are categorical in ω but not categorical in uncountable cardinals.
The simplest example is the theory of an equivalence relation with exactly two equivalence classes both of which are infinite. Another example is the theory of dense linear orders with no endpoints; Cantor proved that any such countable linear order is isomorphic to the rational numbers.
Any theory T categorical in some infinite cardinal κ is very close to being complete. More precisely, the Łoś–Vaught test states that if a theory has no finite models and is categorical in some infinite cardinal κ at least equal to the cardinality of its language, then the theory is complete. The reason is that all infinite models are equivalent to some model of cardinal κ by the Löwenheim–Skolem theorem
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ...
, and so are all equivalent as the theory is categorical in κ. Therefore the theory is complete as all models are equivalent.