View source for Categorical theory

{{Short description|Type of theory in mathematical logic}}
{{redirect-distinguish2|Vaught's test|the [[Tarski–Vaught test]]}}
{{distinguish|Category theory}}
In [[mathematical logic]], a [[theory (mathematical logic)|theory]] is '''categorical''' if it has exactly one [[model (mathematical logic)|model]] ([[up to isomorphism]]).{{efn|Some authors define a theory to be categorical if all of its models are isomorphic.  This definition makes the inconsistent theory categorical, since it has no models and therefore vacuously meets the criterion.}} Such a theory can be viewed as ''defining'' its model, uniquely characterizing the model's structure.

In [[first-order logic]], only theories with a [[Finite set|finite]] model can be categorical.  [[Higher-order logic]] contains categorical theories with an [[Infinite set|infinite]] model.  For example, the second-order [[Peano axioms]] are categorical, having a unique model whose domain is the [[Set (mathematics)|set]] of natural numbers <math>\mathbb{N}.</math>

In [[model theory]], the notion of a categorical theory is refined with respect to [[cardinal number|cardinality]].  A theory is {{math|''κ''}}-'''categorical''' (or '''categorical in {{math|''κ''}}''') if it has exactly one model of cardinality {{math|''κ''}} up to isomorphism. '''Morley's categoricity theorem''' is a theorem of {{harvs|txt|authorlink=Michael D. Morley|first=Michael D. |last=Morley|year=1965}} stating that if a [[first-order theory]] in a [[countable]] language is categorical in some [[uncountable]] [[cardinality]], then it is categorical in all uncountable cardinalities.

{{harvs|txt|authorlink=Saharon Shelah|first=Saharon |last=Shelah|year=1974}} extended Morley's theorem to uncountable languages: if the language has cardinality {{math|''κ''}} and a theory is categorical in some uncountable cardinal greater than or equal to {{math|''κ''}} then it is categorical in all cardinalities greater than&nbsp;{{math|''κ''}}.

==History and motivation==
[[Oswald Veblen]] 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 [[cardinal number|cardinality]] cannot be categorical. One is then immediately led to the more subtle notion of {{math|''κ''}}-categoricity, which asks: for which cardinals {{math|''κ''}} is there exactly one model of cardinality {{math|''κ''}} 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 theory|complete theories]] ''T'' over countable [[formal language|languages]] with at least one infinite model, he could only find three ways for ''T'' to be {{math|''κ''}}-categorical at some&nbsp;{{math|''κ''}}:

*''T'' is '''totally categorical''', ''i.e.'' ''T'' is {{math|''κ''}}-categorical for all infinite [[cardinal number|cardinal]]s&nbsp;{{math|''κ''}}.
*''T'' is '''uncountably categorical''', ''i.e.'' ''T'' is {{math|''κ''}}-categorical if and only if {{math|''κ''}} is an [[countable|uncountable]] cardinal.
*''T'' is [[Omega-categorical theory|'''countably categorical''']], ''i.e.'' ''T'' is {{math|''κ''}}-categorical if and only if {{math|''κ''}} is a countable cardinal.

In other words, he observed that, in all the cases he could think of, {{math|''κ''}}-categoricity at any one uncountable cardinal implied {{math|''κ''}}-categoricity at all other uncountable cardinals. This observation spurred a great amount of research into the 1960s, eventually culminating in [[Michael D. Morley|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 (model theory)|stability theory]] and Shelah's more general programme of [[spectrum of a theory|classification theory]].

==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 field|algebraically closed]] [[Field (mathematics)|fields]] of a given [[Characteristic (algebra)|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|''p''-adic]] closures '''C'''<sub>''p''</sub> 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 a given characteristic is '''not''' categorical in {{math|''ω''}} (the countable infinite cardinal); there are models of [[transcendence degree]] 0, 1, 2, ..., {{math|''ω''}}.
* [[Vector space]]s over a given countable field. This includes [[abelian group]]s of given [[Prime number|prime]] [[Torsion group|exponent]] (essentially the same as vector spaces over a finite field) and [[Divisible group|divisible]] [[torsion-free abelian group]]s (essentially the same as vector spaces over the [[Rational number|rationals]]).
* The theory of the set of [[natural number]]s with a successor function.

There are also examples of theories that are categorical in {{math|''ω''}} but not categorical in uncountable cardinals. 
The simplest example is the theory of an [[equivalence relation]] with exactly two [[equivalence class]]es, both of which are infinite. Another example is the theory of [[Dense order|dense]] [[linear order]]s with no endpoints; [[Georg Cantor|Cantor]] proved that any such countable linear order is isomorphic to the rational numbers: see [[Cantor's isomorphism theorem]].

==Properties==

Every categorical theory is [[complete theory|complete]].{{sfn|Monk|1976|p=349}} However, the converse does not hold.<ref>{{cite web |url=https://math.stackexchange.com/q/933632 |title=Difference between completeness and categoricity |last=Mummert |first=Carl |date=2014-09-16}}</ref>

Any theory ''T'' categorical in some infinite cardinal {{math|''κ''}} is very close to being complete. More precisely, the [[Łoś–Vaught test]] states that if a satisfiable theory  has no finite models and is categorical in some infinite cardinal {{math|''κ''}} at least equal to the cardinality of its language, then the theory is complete.  The reason is that all infinite models are first-order equivalent to some model of cardinal {{math|''κ''}} by the [[Löwenheim–Skolem theorem]], and so are all equivalent as the theory is categorical in {{math|''κ''}}. Therefore, the theory is complete as all models are equivalent.  The assumption that the theory have no finite models is necessary.<ref>Marker (2002) p. 42</ref>

==See also==
*[[Spectrum of a theory]]

==Notes==
{{notelist}}
{{reflist}}

==References==
* {{Citation | last1=Chang | first1=Chen Chung |author1-link=Chen Chung Chang| last2=Keisler | first2=H. Jerome | author2-link=Howard Jerome Keisler | title=Model Theory | orig-year=1973 | publisher=Elsevier | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-88054-3 | year=1990}}
* {{Citation | last1=Corcoran | first1=John | author1-link=John Corcoran (logician) | title=Categoricity  | year=1980 | journal= History and Philosophy of Logic | volume=1 | issue=1-2 | pages=187–207 | doi=10.1080/01445348008837010}}
* [http://plato.stanford.edu/archives/sum2005/entries/modeltheory-fo Hodges, Wilfrid, "First-order Model Theory", The Stanford Encyclopedia of Philosophy (Summer 2005 Edition), Edward N. Zalta (ed.).]
* {{citation | last=Marker | first=David | title=Model theory: An introduction | series=[[Graduate Texts in Mathematics]] | volume=217 | location=New York, NY | publisher=[[Springer-Verlag]] | year=2002 | isbn=0-387-98760-6 | zbl=1003.03034 }}
* {{citation |last=Monk |first=J. Donald |title=Mathematical Logic |date=1976 |publisher=Springer-Verlag |doi=10.1007/978-1-4684-9452-5}}
* {{Citation | last1=Morley | first1=Michael | author1-link=Michael D. Morley | title=Categoricity in Power | doi=10.2307/1994188 | year=1965 | journal=[[Transactions of the American Mathematical Society]] | issn=0002-9947 | volume=114 | issue=2 | pages=514–538 | jstor=1994188 | publisher=[[American Mathematical Society]], Vol. 114, No. 2| doi-access=free }}
*{{springer|id=c/c020730|title=Categoricity in cardinality|first=E.A.|last= Palyutin
}}
*{{Citation | last1=Shelah | first1=Saharon | author1-link=Saharon Shelah | title=Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. of California, Berkeley, Calif., 1971) | volume=25 | publisher=American Mathematical Society| location=Providence, R.I. | mr=0373874  | year=1974 | chapter=Categoricity of uncountable theories | pages=187–203 | doi=10.1090/pspum/025/0373874| series=Proceedings of Symposia in Pure Mathematics | isbn=9780821814253 }}
* {{Citation | last1=Shelah | first1=Saharon | author1-link=Saharon Shelah | title=Classification theory and the number of nonisomorphic models | orig-year=1978 | publisher=Elsevier | edition=2nd | series=Studies in Logic and the Foundations of Mathematics | isbn=978-0-444-70260-9 | year=1990 | url-access=registration | url=https://archive.org/details/classificationth0092shel }} (IX, 1.19, pg.49)
* {{Citation | last1=Veblen | first1=Oswald | author1-link=Oswald Veblen | title=A System of Axioms for Geometry  | doi=10.2307/1986462 | year=1904 | journal=[[Transactions of the American Mathematical Society]] | issn=0002-9947 | volume=5 | issue=3 | pages=343–384 | jstor=1986462 | publisher=American Mathematical Society, Vol. 5, No. 3| doi-access=free }}

{{Mathematical logic}}

[[Category:Mathematical logic]]
[[Category:Model theory]]
[[Category:Theorems in the foundations of mathematics]]