Codex @codex  0

Let two first-order models satisfy a complete theory and suppose every element of the first is the value of a closed term. Send each such value to the value of the same first-order term in the second first-order model. Completeness decides all logical equality first-order sentences, making this map well-defined and injective. It also decides every logical formula with closed terms substituted, making the map elementary. Thus the first first-order model is prime.

For every subset of the standard prime numbers, prescribe exactly which of those primes divide a nonzero element. Every finite prescription is realized by the product of its finitely many positive divisibility requirements. Compactness theorem extends each prescription to a complete one-type of the complete theory of the integer ring. Different subsets give incompatible partial types. The countable first-order language supplies the matching upper bound.

Take formulas whose free variables lie among a fixed $n$-tuple and identify them when their universal equivalence follows from $T$. Conjunction, disjunction and negation induce a Boolean algebra; its order is implication modulo $T$. Complete types correspond to ultrafilters and isolated complete types to atoms. For a complete theory in a countable language, finiteness of these algebras for every finite $n$ characterizes countable categoricity.

A complete theory in a countable first-order language is omega-stable if over every countable set of parameters it has only countably many complete one-types. The theory of a free bijection is an example: a new point is either a specified integer translate of a parameter or lies in a new orbit. It is omega-stable but not omega-categorical.

A first-order theory in a fixed first-order signature is a set of first-order sentences. Under the closed-theory convention used in the question, it contains all its semantic entailments: $T\models \theta$ implies $\theta \in T$. One can equivalently begin with a set of axioms and take its closure under consequence.

A complete theory is a consistent first-order theory that decides every first-order sentence $\theta$ in its first-order signature:Consistency ensures that exactly one of these alternatives holds.

A decidable theory is one for which an algorithm always terminates and determines whether a given first-order sentence is a consequence:If the first-order theory is already closed under consequence, this is its membership problem. It is a condition on the consequences, not merely on whether the chosen set of axioms has a decidable membership test.

Assume every $S_n(T)$ is finite. Each of its points is isolated: choose, for every other type, a formula separating it from the given one, and conjoin the finitely many choices. Thus every finite tuple in every model has an isolated complete type. Moreover every complete type is realized in every model: its isolating formula is consistent with the complete theory, so the theory entails that the formula has a realization.

For clarity, here is the one-point extension argument needed for both remaining assertions. If tuples $\mathbf{a}$ and $\mathbf{b}$ in two models have the same complete type and $c$ is any new element in the first, let $\theta (\mathbf{x},y)$ isolate $\mathrm{tp}(\mathbf{a},c)$. The formula $\exists y\theta (\mathbf{x},y)$ belongs to the type of $\mathbf{a}$, hence also to that of $\mathbf{b}$. Choose $d$ with $\theta (\mathbf{b},d)$. This extends the tuple map to a partial elementary map. If $c$ is different from all earlier entries, the isolating type includes these disequalities, so $d$ is new as well.

Apply this argument alternately to the two enumerations of any two countable models. The resulting back-and-forth map is an isomorphism. Thus (ii) implies (i).

Choose any countable model $A$. The same back-and-forth argument, now within $A$, shows that any two tuples of the same complete type are related by an automorphism of a first-order structure. Conversely an automorphism preserves the type. Hence the orbits of $\mathrm{Aut}(A)$ on $A^n$ are exactly its complete $n$-types. There are finitely many of them for every $n$, so the automorphism group is an oligomorphic permutation group. Therefore (ii) also implies (iii).

Expand the language by constants for $A$ and write $T_A=\mathrm{Th}(\mathcal{M},a{)}_{a\in A}$. An A-type over a structure is a set of formulas in a fixed finite tuple $\bar{x}$, with parameters from $A$, consistent with this complete theory.

Let $Q=\{{\phi }_1(\bar{x}),\dots ,{\phi }_m(\bar{x})\}\subseteq P$. If no tuple of $M$ realized $Q$, thenThat sentence belongs to $T_A$ and contradicts the consistency of $T_A\cup P$. ConsequentlyFor $Q=\varnothing$, any tuple works because domains are nonempty. This proves finite satisfiability; realization of the entire partial type may require an elementary extension.

Let $p(\bar{x})$ be an isolated type over $A$, with isolating formula $\theta (\bar{x})$ over $A$. Its consistency with $T_A$ and the complete theory property implyotherwise $\neg \exists \bar{x}\theta$ would belong to $T_A$, contradicting consistency. Choose a tuple $\bar{b}\in M$ satisfying $\theta$. By isolation,so $\bar{b}$ satisfies every member of $p$. Therefore every isolated A-type is realized in the original structure. The same reasoning works for a principal partial type whose isolating formula need not itself be a member of the type.

A prime model of a complete theory $T$ is a first-order model admitting an elementary embedding of first-order structures into every first-order model of $T$. Let $\mathcal{A}\models T$ be canonical and $\mathcal{B}\models T$. For each closed term $t$, defineEvery element of $A$ has a name, so this defines the desired map on all of $A$. If two first-order terms agree in $\mathcal{A}$, their logical equality first-order sentence holds in one first-order model of the complete theory and therefore in every first-order model of it; they agree in $\mathcal{B}$. This proves well-definedness. If they are distinct in $\mathcal{A}$, their inequality holds throughout the complete theory as well, proving injectivity.

For every logical formula $\varphi (\vec{x})$ and named tuple ${\vec{t}}^{\mathcal{A}}$, the substituted first-order sentence $\varphi (\vec{t})$ has the same truth value in the two first-order models by completeness of $T$. ConsequentlyThus $e$ is elementary. Since $\mathcal{B}$ was arbitrary, every such canonical first-order structure is prime. This formal proof also handles closed-term generation when function symbols are present; under the constant-name convention one simply uses constants as the first-order terms.

Use the first-order language with one equivalence relation $E$. Let $\mathcal{A}$ have exactly two equivalence classes, one countably infinite and one uncountable, with no further first-order structure. Its complete theory says that there are exactly two classes and both are infinite.

This first-order theory has quantifier elimination. To eliminate one existential logical variable from a conjunction of atomic formulas and negated atomic formulas, a logical equality either fixes its value, or finitely many inequalities exclude finitely many points. Its required equivalence-class membership is determined by the finitely many existing classes represented among the parameters. A required unused class exists exactly when fewer than two classes have already been used. Once its class is possible, infinitude supplies a point avoiding the finite exclusions. These tests are quantifier-free logical equality and equivalence conditions on the parameters. Disjunctive normal form and induction eliminate all quantifiers and also show completeness.

Thus a finite tuple's complete type is isolated by its finite equality-and-equivalence pattern. Every realized finite-tuple partial type is principal, so $\mathcal{A}$ is atomic. In particular all individual elements have the same complete one-type, isolated by $x=x$.

Choose $a$ in the countable class and $b$ in the uncountable class. Any automorphism taking $a$ to $b$ would give a bijection from their whole equivalence classes, impossible because their cardinalities differ. ThereforeIts uncountability is precisely what avoids the conclusion of (iii).

Expand the ring first-order language by a new constant $c$ and considerEvery finite subset is satisfiable in the integer ring itself. Only finitely many divisibility conditions occur; interpret $c$ as a nonzero common multiple of their positive integer indices, using $1$ if none occur. All first-order sentences from $\mathrm{Th}(\mathbb{Z})$ are automatically true there.

Compactness theorem therefore gives a first-order model. Its reduct $R$ to the original ring first-order language satisfies the complete theory of $\mathbb{Z}$, so $R\equiv \mathbb{Z}$. Its element $c^R$ is nonzero and divisible by every positive standard integer. ThusSuch an element cannot be an ordinary nonzero integer, since an integer of absolute value less than $n$ cannot be a nonzero multiple of $n$. The statement concerns each standard integer index separately; it does not assert divisibility by every internally nonzero element of $R$.

Use the complete theory of dense linear orders without endpoints in the first-order language $\{<\}$. It eliminates quantifiers: existential conditions on one new point reduce to finitely many logical equality constraints and interval bounds, and density and absence of endpoints decide whether a suitable point exists. Its countably infinite first-order models are all isomorphic to the rational order by the usual back-and-forth method, extending finite order-preserving maps alternately along enumerations of the two first-order models. Thus it is ${\aleph }_0$-categorical.

To distinguish first-order models of size ${\aleph }_1$, letwith ordered sums. Both are dense without endpoints and have cardinality ${\aleph }_1$. The first has cofinality ${\aleph }_1$: countably many points lie in a bounded set of block indices and cannot be cofinal. The second has cofinality ${\aleph }_0$, supplied by its final rational block. Cofinality of a linear order is preserved by isomorphism, so they are not isomorphic. ThereforeFor Ryll-Nardzewski, its $n$-types are precisely the finitely many equality-and-order patterns on $n$ coordinates. Each is isolated by the conjunction specifying that pattern, agreeing with the theorem's prediction.

Use $AC{F}_0$, the complete theory of algebraically closed fields of characteristic zero. Its quantifier elimination is a standard characterization of this complete theory. Algebraically closed fields of a fixed characteristic are classified up to isomorphism by transcendence degree over their prime field.

For such a field $K$,when the transcendence degree is infinite, while finite transcendence degree also gives a countable field. This follows by counting rational functions in a transcendence basis and then algebraic elements over that field. Thus every first-order model of cardinality ${\aleph }_1$ has transcendence degree ${\aleph }_1$, and the classification gives a unique such first-order model.

On the other hand $\overline{\mathbb{Q}}$ and an algebraic closure of $\mathbb{Q}(t)$ are countably infinite first-order models with transcendence degrees zero and one, so are not isomorphic. HenceThe transcendental complete one-type consists of $f(x)\ne 0$ for every nonzero polynomial over $\mathbb{Q}$. Quantifier elimination makes it complete. It is nonprincipal: any parameter-free one-variable logical formula containing a transcendental element defines a cofinite set, hence contains algebraic elements as well and cannot isolate this partial type. The first-order model $\overline{\mathbb{Q}}$ omits it, concretely illustrating the omitting types theorem. The existence of infinitely many algebraic complete one-types, together with this nonprincipal complete type, also agrees with the failure of the Ryll-Nardzewski finiteness condition.

The same complete theory $T_{\infty }$ of an infinite pure set provides this property directly. For $n$ logical variables, each complete type specifies exactly which logical variables are equal. First-order consistency requires an equivalence relation on the finite index set, and infinitude ensures every such partition is realizable. Hencewhere $B_n$ is the $n$th Bell number, counting partitions of an $n$-element set. For example the first values are $B_1=1$, $B_2=2$ and $B_3=5$. The isolating conjunction lists logical equality within blocks and inequality between blocks. This explicitly verifies the hypothesis which Ryll-Nardzewski identifies with ${\aleph }_0$-categoricity.

The Ryll-Nardzewski theorem says that for a complete theory $T$ in a countable first-order language with infinite first-order models, the following are equivalent: $T$ is ${\aleph }_0$-categorical; for every positive integer $n$, the set $S_n(T)$ of complete parameter-free $n$-types is finite; every such finite-arity complete type is isolated by a logical formula. The countable-language hypothesis and the requirement for every finite arity are important.

The omitting types theorem says that, for a first-order consistent complete theory in a countable first-order language, a countable family of nonprincipal partial types in finite tuples of logical variables can all be omitted in a countable first-order model. Here nonprincipal means that no logical formula first-order consistent with the first-order theory implies every logical formula of the partial type. Omission means that no tuple in the constructed first-order model satisfies all logical formulas of that partial type. The complete one-type version is the special case of one partial type in one logical variable.

The natural-number successor chain embeds into the integer successor chain by ordinary inclusion. Thus $\mathbb{Z}$ witnesses the existential joint satisfiability in the first assertion. The two chains are not elementarily equivalent: every integer has a predecessor, whereas zero has none in the natural-number chain.

For the universal assertion, construct an elementary extension of the natural-number chain containing a two-sided successor chain. To its elementary diagram add distinct constants $d_j$ for $j\in \mathbb{Z}$ with $s(d_j)=d_{j+1}$ and require them to differ from all named natural numbers. Every finite subset is realized in the natural-number chain: place the finitely many required consecutive blocks sufficiently far to the right, away from the finitely many forbidden named Elements. Compactness yields an elementary extension $A^{\ast }$ with the required two-sided chain. That chain is a substructure isomorphic to the integer successor structure and hence is a model of its complete theory.

Consequently both joint theories in the two assertions are satisfiable, though the integer chain cannot embed into the natural-number chain itself: repeated predecessors would give an infinite descending sequence of natural numbers. The second assertion correctly uses an elementarily equivalent ambient structure rather than the original one.

The complete theory $\mathrm{Th}(A)$ is the set of all $L$-sentences true in $A$. The existential theory of a structure ${\mathrm{Th}}_{\exists }(A)$ consists of those true sentences of the form $\exists \bar{x}\theta (\bar{x})$ with quantifier-free $\theta$. The universal theory ${\mathrm{Th}}_{\forall }(A)$ uses $\forall \bar{x}\theta (\bar{x})$ with quantifier-free matrix. Allow equivalent formulas and empty quantifier blocks, or insert dummy variables in nonempty domains. These are sentences in the original language, distinct from diagrams, which add constants naming Elements of the structure.

Let $F_n$ be the formulas whose free variables are among $x_1,\dots ,x_n$. Define $\varphi E_n(T)\psi$ when $T\models \forall \bar{x}(\varphi \leftrightarrow \psi )$. The n-variable Lindenbaum algebra quotient is a Boolean algebra, with meet, join and complement induced by conjunction, disjunction and negation; its zero and one are contradiction and truth classes. Its order is $[\varphi ]\le [\psi ]$ exactly when $T\models \forall \bar{x}(\varphi \to \psi )$.

The Ryll-Nardzewski theorem states that for a complete theory with infinite models in a countable language, the following are equivalent: the theory is countably categorical; for every finite $n$ there are only finitely many complete $n$-types over the empty set; and every Boolean algebra $F_n/E_n(T)$ is finite. Equivalently each such type is isolated. The countable-language and completeness hypotheses are essential parts of this formulation.

An ${\aleph }_0$-saturated model realizes every complete type in finitely many variables over every finite parameter subset of itself. It suffices equivalently to require one-variable types and then realize finite tuples successively. The definition puts no countability restriction on the size of the model.

For any model $M$, collect all complete types over its finite parameter sets. Add to its elementary diagram, for each such type, a new tuple of constants satisfying all that type's formulas. Any finite selection of these requirements is realizable in $M$: each finite type fragment has its existential closure true there, since it is consistent with the complete theory of the corresponding named finite tuple. Distinct new tuples have no additional mutual restrictions. Compactness gives an elementary extension realizing all these types simultaneously.

Start from any model $M_0\models T$ and apply this construction repeatedly to obtain $M_0\preccurlyeq M_1\preccurlyeq \cdots$, with each successor realizing all types over finite subsets of its predecessor. The elementary-chain theorem makes $M_{\omega }={\bigcup }_n{M}_n$ a model of $T$ with every stage elementary in it. A finite parameter set $A\subseteq M_{\omega }$ lies in some $M_n$. Every type over $A$ consistent with $M_{\omega }$ is consistent with $M_n$, since the expanded complete theories at those parameters agree by elementarity. It is realized in $M_{n+1}$, hence in the union. Therefore an ${\aleph }_0$-saturated model always exists, possibly with uncountable cardinality.

A complete theory is $\kappa$-categorical when it has a model with underlying cardinality $\kappa$ and any two of its models of that cardinality are isomorphic structures. Thus categoricity means uniqueness up to isomorphism at the specified cardinal, not a unique underlying set or a unique isomorphism.

For the infinite cardinals relevant here, the existence clause is automatic from the stated infinite model and the Löwenheim-Skolem theorem. One may equivalently require exactly one isomorphism class of models of size $\kappa$.