Categorical theory

In mathematical logic, a theory is categorical if it has exactly one model (up to isomorphism).[1] Such a theory can be viewed as defining its model, uniquely characterizing its structure.

Not to be confused with Category theory.

In first-order logic, only theories with a finite model can be categorical. Higher-order logic contains categorical theories with an infinite model. For example, the second-order Peano axioms are categorical, having a unique model whose domain is the set of natural numbers ℕ.

In model theory, the notion of a categorical theory is refined with respect to cardinality. 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 Michael D. Morley (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.

Saharon Shelah (1974) 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 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 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 κ:

  • T is totally categorical, i.e. T is κ-categorical for all infinite cardinals κ.
  • 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'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.

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 fields 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 spaces over a given countable field. This includes abelian groups 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 numbers 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.

Properties

Every categorical theory is complete. However, the converse does not hold.[2]

Any theory T categorical in some infinite cardinal κ 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 κ 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. The assumption that the theory have no finite models is necessary.[3]

gollark: I think there's a thing called PiFS.
gollark: I think the calculators we have for school store numbers as either rationals, surds (multiples of square roots, or something like that), or multiples of pi.
gollark: You miss out on those pesky infinitely long numbers.
gollark: Correctness is correct. Floats are mostly okayish.
gollark: I think you mean "5 haskell programmers".

See also

Notes
  1. 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.
  2. Mummert, Carl (2014-09-16). "Difference between completeness and categoricity".
  3. Marker (2002) p. 42

References
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.