In
mathematical logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...
, an omega-categorical theory is a
theory
A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may be s ...
that has exactly one
countably infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
model
A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure.
Models c ...
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
. Omega-categoricity is the special case κ =
= ω of
κ-categoricity, and omega-categorical theories are also referred to as ω-categorical. The notion is most important for countable
first-order
In mathematics and other formal sciences, first-order or first order most often means either:
* "linear" (a polynomial of degree at most one), as in first-order approximation and other calculus uses, where it is contrasted with "polynomials of high ...
theories.
Equivalent conditions for omega-categoricity
Many conditions on a theory are equivalent to the property of omega-categoricity. In 1959
Erwin Engeler,
Czesław Ryll-Nardzewski
Czesław Ryll-Nardzewski (; 7 October 1926 – 18 September 2015) was a Polish mathematician.
Born in Wilno, Second Polish Republic (now Vilnius, Lithuania), he was a student of Hugo Steinhaus. At the age of 26 he became professor at Warsaw Univ ...
and
Lars Svenonius
Lars Svenonius (June 16, 1927, Skellefteå – September 27, 2010, Silver Spring, Maryland) was a Swedish logician and philosopher.
He was a visiting professor at University of California at Berkeley in 1962–63, then held a position at the Uni ...
, proved several independently.
[Rami Grossberg, José Iovino and Olivier Lessmann]
''A primer of simple theories''
/ref> Despite this, the literature still widely refers to the Ryll-Nardzewski theorem as a name for these conditions. The conditions included with the theorem vary between authors.[Hodges, Model Theory, p. 341.][Rothmaler, p. 200.]
Given a countable complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
first-order theory ''T'' with infinite models, the following are equivalent:
* The theory ''T'' is omega-categorical.
* Every countable model of ''T'' has an oligomorphic automorphism group (that is, there are finitely many orbits on ''Mn'' for every ''n'').
* Some countable model of ''T'' has an oligomorphic automorphism group.[Cameron (1990) p.30]
* The theory ''T'' has a model which, for every natural number ''n'', realizes only finitely many ''n''-types, that is, the Stone space In topology and related areas of mathematics, a Stone space, also known as a profinite space or profinite set, is a compact totally disconnected Hausdorff space. Stone spaces are named after Marshall Harvey Stone who introduced and studied them in ...
''Sn''(''T'') is finite.
* For every natural number ''n'', ''T'' has only finitely many ''n''-types.
* For every natural number ''n'', every ''n''-type is isolated.
* For every natural number ''n'', up to equivalence modulo ''T'' there are only finitely many formulas with ''n'' free variables, in other words, for every ''n'', the ''n''th Lindenbaum–Tarski algebra
In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a logical theory ''T'' consists of the equivalence classes of sentences of the theory (i.e., the quotient, under the equivalence relation ~ defined such that ''p'' ...
of ''T'' is finite.
* Every model of ''T'' is atomic.
* Every countable model of ''T'' is atomic.
* The theory ''T'' has a countable atomic and saturated model
In mathematical logic, and particularly in its subfield model theory, a saturated model ''M'' 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 \al ...
.
* The theory ''T'' has a saturated prime model
In mathematics, and in particular model theory, a prime model is a model that is as simple as possible. Specifically, a model P is prime if it admits an elementary embedding into any model M to which it is elementarily equivalent (that is, into an ...
.
Examples
The theory of any countably infinite structure which is homogeneous over a finite relational language is omega-categorical.[Macpherson, p. 1607.] Hence, the following theories are omega-categorical:
*The theory of dense linear orders without endpoints (Cantor's isomorphism theorem
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. For instance, there is an isomorphism (a one-to-one order-preserving co ...
)
*The theory of the Rado graph
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 (with probability one) by choosing independently at random for each pair of its vertices whe ...
*The theory of infinite linear spaces over any finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
Notes
References
*
*
*
*
*
*
*
Model theory
Mathematical theorems
{{mathlogic-stub