Complete theory

A consistent first-order theory is complete when it decides every sentence in its language.

The first-order theory of a bijection $f$ with named inverse $g$ and no finite cycles has first-order models consisting of disjoint integer orbits. Atomic logical formulas reduce to $x_j=f^k(x_i)$ for integer $k$. An existential logical variable is either fixed by such a logical equality or must avoid finitely many points. This proves quantifier elimination and completeness. There is one complete one-type; the complete two-types are the integer offsets and the nonprincipal different-orbit partial type. There are countably many finite-arity partial types but countable first-order models with different numbers of orbits are not isomorphic.

In the first-order language of logical equality, assert that there are at least $n$ elements for every positive integer $n$. Eliminating one existential logical variable either substitutes a logical equality or avoids finitely many points, so this first-order theory has quantifier elimination and is complete. It is categorical in every infinite cardinal. Its complete $n$-types are the logical equality partitions of $n$ coordinates and are counted by the Bell numbers.

The complete theory of the standard successor structure is axiomatized by injectivity of $s$, $0$ outside its range, a predecessor for every nonzero element, and the sentences $s^n(x)\ne x$ for each positive integer $n$. Its models have a single distinguished one-sided chain generated by zero and any collection of two-sided integer chains. The classification of models of the successor theory proves completeness and explains why the theory is categorical at every uncountable cardinal but not at the countable cardinal.

In a model of the axioms for the theory of successor, repeatedly taking successor and predecessor partitions the domain into components. Injectivity and the predecessor axiom leave only the zero-generated one-sided chain and two-sided chains; the no-cycle axioms exclude finite components. Choosing one origin in each remaining component gives the displayed structure.

These axioms have quantifier elimination. To eliminate one existential quantification, put its quantifier-free matrix in disjunctive normal form. In a conjunction, an equality between a successor iterate of the bound variable and a parameter term fixes at most one candidate, by injectivity. Existence of the finitely many necessary predecessors excludes only finitely many initial zero iterates; the other equalities and inequalities then translate to conditions on the parameters by cancellation of successor iterates. If there is no such fixing equality, only finitely many candidates are excluded, so some point on the infinite zero chain works. Equalities between two different iterates of the same variable are false by absence of cycles. Thus the existential formula reduces to a quantifier-free formula.

Every closed quantifier-free sentence is decided by the distinct zero iterates, proving completeness. A one-variable formula over the empty set is a Boolean combination of finitely many equalities $x=s^n(0)$, modulo this theory. All points in added integer chains therefore realize the same nonisolated complete type over the empty set. At an uncountable cardinal $\kappa$ a model has exactly $\kappa$ integer components, proving categoricity there. A countable model with infinitely many integer components is an omega-saturated model because finite parameters involve only finitely many components, leaving a fresh one for every new-component type.

A theory is $\kappa$-categorical when all of its models of cardinality $\kappa$ are isomorphic.

For any infinite cardinal $\kappa$, insert a dense order without endpoints of size $\kappa$ into an irrational cut of the named rationals. Compare it with an order of the same size having a dense tail above every named rational. Both models satisfy the complete named rational diagram by quantifier elimination, but only the second realizes the type of being above every named rational. This is an isomorphism invariant over the constants, even though it is an infinite type rather than one defining sentence. Thus the diagram is categorical in no cardinal with a model.

If a theory without finite models is categorical in an infinite cardinal at least the language size, it is complete. Otherwise its two consistent extensions deciding a sentence oppositely have infinite models. The Löwenheim-Skolem theorems produce models of both of the specified cardinality, contradicting their forced isomorphism. Categoricity includes existence at that cardinality, so it is not vacuous.

An aleph-zero-categorical theory has, up to isomorphism, exactly one countably infinite model.

For a complete theory with infinite models in a countable language, the following are equivalent: the theory is aleph-zero-categorical; every type space $S_n(T)$ is finite; and for every $n$ there are only finitely many formulas in $n$ variables modulo the theory.

Every reduct of an aleph-zero-categorical theory to a sublanguage is aleph-zero-categorical. There can only be fewer formulas in each arity, so the finite-formula characterization in the Ryll-Nardzewski theorem is preserved.

This theorem is the uncountable categoricity theorem for a categorical theory. If a countable first-order theory is categorical in one uncountable cardinal, then it is categorical in every uncountable cardinal.

Let a language partition the universe into two infinite unary predicates and include a bijection between them. Its complete theory is categorical in every infinite cardinal. The reduct forgetting the bijection is not categorical in any uncountable cardinal, because the two infinite parts can have different cardinalities.

Compactness gives a countable model elementarily equivalent to $(\mathbb{Z},+,0)$ that contains a nonzero element divisible by every positive standard integer. It is not isomorphic to $\mathbb{Z}$, so $\mathrm{Th}(\mathbb{Z},+,0)$ is not aleph-zero-categorical.

The complete theory of infinite-dimensional vector spaces over a fixed finite field is aleph-zero-categorical: every countably infinite model has countably infinite dimension and is therefore isomorphic to every other such model.