In
mathematical logic
Mathematical logic is the study of 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 formal ...
, 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 ...
that has exactly one
countably infinite 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 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 i ...
. 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 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 Uni ...
and
Lars Svenonius, 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 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 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 \ ...
.
* 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 ...
.
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
*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