In
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, an omega-categorical theory is a
theory
A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, ...
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 numbe ...
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 , .
Models can be divided in ...
up to Two Mathematical object, mathematical objects and are called "equal up to an equivalence relation "
* if and are related by , that is,
* if holds, that is,
* if the equivalence classes of and with respect to are equal.
This figure of speech ...
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping or morphism 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 the ...
. 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.
Life and career
Born in Wilno, Second Polish Republic (now Vilnius, Lithuania), he was a student of Hugo Steinhaus. At the age of 26 he became profe ...
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 Univ ...
, 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 ''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 \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 a ...
.
Examples
The theory of any countably infinite structure which is homogeneous over a finite relational language is omega-categorical.[Macpherson, p. 1607.] More generally, the theory of the Fraïssé limit of any uniformly locally finite Fraïssé class is omega-categorical.[Hodges, Model theory, Thm. 7.4.1.] Hence, the following theories are omega-categorical:
*The theory of dense linear orders without endpoints ( Cantor's isomorphism theorem)
*The theory of the Rado graph
In the mathematics, mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a Countable set, countably infinite graph that can be constructed (with probability one) by choosing independently at random for eac ...
*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 (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
*The theory of atomless Boolean algebras
Notes
References
*
*
*
*
*
*
*
Model theory
Mathematical theorems
{{mathlogic-stub