Categorical theory

Last updated

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.

Contents

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.

SaharonShelah  ( 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 κ:

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:

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. [2] However, the converse does not hold. [3]

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. [4]

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. ↑ Monk 1976, p. 349.
  3. ↑ Mummert, Carl (2014-09-16). "Difference between completeness and categoricity".
  4. ↑ Marker (2002) p. 42

Related Research Articles

In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem.

In mathematical logic, and particularly in its subfield model theory, a saturated modelM is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is -saturated, meaning that every descending nested sequence of internal sets has a nonempty intersection.

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 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.

Rami Grossberg is a full professor of mathematics at Carnegie Mellon University and works in model theory.

In the mathematical field of set theory, the proper forcing axiom (PFA) is a significant strengthening of Martin's axiom, where forcings with the countable chain condition (ccc) are replaced by proper forcings.

In mathematical logic, a non-standard model of arithmetic is a model of (first-order) Peano arithmetic that contains non-standard numbers. The term standard model of arithmetic refers to the standard natural numbers 0, 1, 2, …. The elements of any model of Peano arithmetic are linearly ordered and possess an initial segment isomorphic to the standard natural numbers. A non-standard model is one that has additional elements outside this initial segment. The construction of such models is due to Thoralf Skolem (1934).

Rado graph infinite graph containing all countable graphs

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

In set theory, an Aronszajn tree is an uncountable tree with no uncountable branches and no uncountable levels. For example, every Suslin tree is an Aronszajn tree. More generally, for a cardinal κ, a κ-Aronszajn tree is a tree of cardinality κ in which all levels have size less than κ and all branches have height less than κ. They are named for Nachman Aronszajn, who constructed an Aronszajn tree in 1934; his construction was described by Kurepa (1935).

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 the 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, Robin Knight has announced a counterexample to the Vaught conjecture and the topological Vaught conjecture. As of 2021, the counterexample has not been verified.

In model theory, a branch of mathematical logic, a complete first-order theory T is called stable in λ, if the Stone space of every model of T of size ≤ λ has itself size ≤ λ. T is called a stable theory if there is no upper bound for the cardinals κ such that T is stable in κ. The stability spectrum of T is the class of all cardinals κ such that T is stable in κ.

In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose models are too complicated to classify, and to classify all models in the cases where this can be done. Roughly speaking, if a theory is not stable then its models are too complicated and numerous to classify, while if a theory is stable there might be some hope of classifying its models, especially if the theory is superstable or totally transcendental.

A timeline of mathematical logic. See also History of logic.

In the mathematical field of set theory, the Solovay model is a model constructed by Robert M. Solovay (1970) in which all of the axioms of Zermelo–Fraenkel set theory (ZF) hold, exclusive of the axiom of choice, but in which all sets of real numbers are Lebesgue measurable. The construction relies on the existence of an inaccessible cardinal.

In model theory, a discipline within mathematical logic, an abstract elementary class, or AEC for short, is a class of models with a partial order similar to the relation of an elementary substructure of an elementary class in first-order model theory. They were introduced by Saharon Shelah.

This is a glossary of set theory.

In mathematical set theory, Baumgartner's axiom (BA) can be one of three different axioms introduced by James Earl Baumgartner.

In model theory, a discipline within the field of mathematical logic, a tame abstract elementary class is an abstract elementary class (AEC) which satisfies a locality property for types called tameness. Even though it appears implicitly in earlier work of Shelah, tameness as a property of AEC was first isolated by Grossberg and VanDieren, who observed that tame AECs were much easier to handle than general AECs.

In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. It is named after Georg Cantor, and can be proved by the back-and-forth method sometimes attributed to Cantor, but Cantor's original proof only used the "going forth" half of this method.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.