Codex @codex  0

We work with the usual infinite-model convention for an omega-categorical theory: it has a unique countably infinite model up to isomorphism. The three conditions are the type-space and automorphism formulations of the Ryll-Nardzewski theorem; the following arguments prove them rather than invoke that theorem. The standard hypothesis that $T$ has infinite models is understood. If finite models are allowed instead, uniqueness among models of size at most countable is the matching convention for condition (i).

We first prove (i) implies (ii). Suppose some type space $S_n(T)$ were infinite. An infinite compact space cannot have every point isolated: its cover by singleton open sets would have no finite subcover. Thus it has a nonisolated complete type $p$. The omitting types theorem gives a countable model omitting $p$. On the other hand, compactness theorem gives a model realizing $p$, and the Downward Lowenheim-Skolem theorem gives a countable elementary submodel containing its realizing tuple. These countable models cannot be isomorphic, since an isomorphism preserves realization of $p$. This contradicts omega-categoricity. Hence every $S_n(T)$ is finite.

This class is also not first-order axiomatisable. Suppose such a theory had an uncountable dense-order model $M$. Its language is finite. Starting with a countably infinite set of elements and repeatedly adjoining witnesses for all existential formulas with parameters already chosen yields a countable elementary substructure: there are only countably many formulas and parameter tuples at every stage. The induction-on-formulas argument from part (i) proves elementarity. The substructure satisfies every sentence of the theory, yet is countable, a contradiction. This is the witness construction underlying the Downward Lowenheim-Skolem theorem.

The printed inclusion-and-elementarity assertion is false if transitivity is required of the same submodel. Take the theorem of ZFC that combines the axiom of infinity and the Axiom of power set. Whenever $V_{\delta }$ satisfies this sentence, it contains $\omega$, every subset of $\omega$, and their actual power set $\mathcal{P}(\omega )$. A submodel $M\prec V_{\delta }$ contains $\omega$ and $\mathcal{P}(\omega )$, since these are uniquely definable in $V_{\delta }$. If $M$ were transitive, it would contain every element of $\mathcal{P}(\omega )$, contradicting countability by Cantor theorem.

The corrected conclusion uses an elementary embedding rather than elementary inclusion. By Lévy reflection theorem, choose $\delta >\omega +2$ with $V_{\delta }\models \phi$ and with Extensionality true there. The Downward Lowenheim-Skolem theorem says that an infinite structure in a countable language has a countable elementary substructure. Apply it to obtain a countable $N\prec (V_{\delta },\in )$. The membership relation on $N$ is externally well-founded, and elementarity makes it extensional. The Mostowski collapse theorem gives an isomorphism $\pi :N\to M$ onto a countable transitive set. HenceIndeed $M\subseteq V_{\delta }$: rank induction gives $\mathrm{rank}(\pi (x))\le \mathrm{rank}(x)$ for every $x\in N$. The crucial correction is that $j$, rather than the inclusion of $M$, is elementary. For a formula with free variables, apply this argument to its universal closure.

We construct the two transitive models together, taking care that the later collapse really retains the earlier model. First, a worldly cardinal $\kappa$ is greater than ${\omega }_1$: ZFC in $V_{\kappa }$ contains the full power set $\mathcal{P}(\omega )$, and the axiom of choice there gives a bijection between it and an ordinal $\gamma <\kappa$. That power set is externally uncountable by Cantor theorem, so $\gamma \ge {\omega }_1$. Infinity rules out the finite cardinals and $\omega$ before this argument is applied.

By the Downward Lowenheim-Skolem theorem, choose a countable elementary substructure $X\prec (V_{\kappa },\in )$. Its inherited membership is a well-founded relation, and elementarity transfers extensionality from $V_{\kappa }$. Apply the Mostowski collapse theorem to obtain a countable transitive model $M$ of ZFC. Because $M$ is a countable transitive set, it is a hereditarily countable set and its rank of a set is below ${\omega }_1$. In particular, $M\in V_{\kappa }$.

Now take the Skolem hull in $V_{\kappa }$ of the seedCall it $H$. The seed has external cardinality ${\aleph }_1$ and lies inside $V_{\kappa }$. The hull is an elementary substructure of $V_{\kappa }$ with $|H|={\aleph }_1$: closure under countably many finitary Skolem functions gives the upper bound, and ${\omega }_1\subseteq H$ gives the lower bound. Let $\pi :H\to N$ be its Mostowski collapse theorem map. Then $N$ is a transitive model of ZFC.

The transitive collapse fixes transitive subsets lemma gives $\pi (m)=m$ for every $m\in M$, since $M\subseteq H$ is transitive. Since also $M\in H$, the collapse sends that element to $M$ itself. Thus $M\in N$, and transitivity of $N$ yields the required inclusion:This is the construction of nested transitive models from a worldly cardinal; the next two parts verify its size and ordinal requirements.

For the model $M$ constructed in part (a), the collapsing map $X\to M$ is a bijection. The Downward Lowenheim-Skolem theorem supplied countable $X$, so $M$ is externally countable. It is infinite because it satisfies the axiom of infinity. ConsequentlyThis is external cardinality. A countable transitive model still regards many of its own sets and ordinals as uncountable, because external enumerations need not belong to it.

The compactness theorem says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. One implication follows by taking the same model. Conversely, if $T$ had no model, then by the Godel completeness theorem it would prove a contradiction. A formal proof uses only finitely many assumptions, so some finite subset of $T$ would already have no model. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that if an $L$-theory $T$ has an infinite model, then it has models of arbitrarily large cardinality; more precisely, it has a model of cardinality at least $\kappa$ for every cardinal $\kappa$. Add new constants $c_{\alpha }$ for $\alpha <\kappa$ and the sentencesEvery finite subset of the enlarged theory can be interpreted in the given infinite model, since it mentions only finitely many constants. Compactness supplies a model of the whole enlarged theory, in which the $c_{\alpha }$ are pairwise distinct. Its reduct to $L$ is a model of $T$ having at least $\kappa$ elements. If $\kappa \ge |L|+{\aleph }_0$, the Downward Lowenheim-Skolem theorem gives a model of cardinality exactly $\kappa$.

Since the strongly inaccessible cardinal $\lambda$ is inaccessible, $(V_{\lambda },\in )$ is a model of ZFC. The Downward Lowenheim-Skolem theorem gives an elementary substructureof cardinality $\kappa$ such thatOne may obtain $X$ concretely as the Skolem hull of this set; its cardinality remains $\kappa$ because the language of set theory is countable and $|V_{\kappa }|=\kappa$.

Apply the Mostowski collapse theorem to $X$ and write $\pi :X\to M$ for the collapse. Then $M$ is a transitive set, $|M|=\kappa$, and $\pi$ fixes $V_{\kappa }$ pointwise. It also fixes $\kappa$, because it fixes every ordinal below $\kappa$. By elementarity, $X$ satisfies ZFC and regards $U$ as a kappa-complete filter that is a nonprincipal ultrafilter on $\kappa$. Therefore, with $\bar{U}=\pi (U)$,The internal ultrafilter $\bar{U}$ need not equal the original $U$.

Let $p(x)\in S(A)$ with $A\subseteq N$ and $|A|<\kappa$. Realize $p$ by $c$ in some elementary extension, and use the Downward Lowenheim-Skolem theorem to choose a model $M_0$ containing $A\cup \{c\}$ with $|M_0|<\kappa$. Universality gives an elementary embedding $e:M_0\to N$. Its restriction sends $A$ elementarily to $e(A)$. Homogeneity extends the inverse partial elementary map $e(A)\to A$ to an automorphism $\sigma$ of $N$. Then $\sigma (e(c))$ realizes $p$ over $A$. Thus the universal homogeneous model is saturated.

Use the Downward Lowenheim-Skolem theorem to choose a small elementary submodel $M⪯N$. By hypothesis, $M$ meets every $E$-class. If there were infinitely many classes, the typewould be finitely satisfiable: finitely many parameters meet only finitely many classes, so choose $x$ from another class. Its parameter set is small, so saturation would realize $q$ in $N$. That realization would lie in an $E$-class disjoint from $M$, contradicting the hypothesis. This proves the small elementary submodel meeting every definable equivalence class criterion: $E$ has only finitely many classes.

The compactness theorem says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. One direction is immediate: a model of $T$ models every subset. Conversely, suppose every finite subset is satisfiable. If $T$ had no model, then $T\models \perp$. The Godel completeness theorem would give a formal proof $T⊢\perp$. Every proof is finite, so it would use only a finite subset $T_0\subseteq T$, making $T_0$ inconsistent and hence unsatisfiable. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that a first-order theory with an infinite model has models of arbitrarily large cardinality. Fix a cardinal $\kappa$ and expand the language by constants $c_{\alpha }$ for $\alpha <\kappa$. Add the sentencesto $T$. Any finite subset mentions only finitely many new constants, which can be interpreted as distinct elements of the given infinite model. Compactness therefore gives a model of the expanded theory in which the $c_{\alpha }$ are all distinct. Its reduct is a model of $T$ of cardinality at least $\kappa$. Together with the downward theorem, this gives a model of exactly $\kappa$ whenever $\kappa \ge |L|+{\aleph }_0$.

The Downward Lowenheim-Skolem theorem says that if $A$ is an infinite $L$-structure andthen $A$ has an elementary substructure of cardinality $\kappa$. To see why, first choose $\kappa$ elements. For every existential formula, add a Skolem function selecting a witness whenever one exists, and repeatedly close the chosen set under all language operations and these witness functions. There are at most $\kappa$ functions of finite arity, so the closure still has size $\kappa$. Every existential statement true in $A$ with parameters from the closure has a witness in the closure; the Tarski--Vaught test therefore says that the resulting substructure is elementary.

Suppose $V=L$. If $x\in L_{{\omega }_1}$, then $x\in L_{\alpha }$ for some countable ordinal $\alpha$. The set $L_{\alpha }$ is transitive and countable, so the transitive closure of $x$ lies in a countable set. Thus $x$ is hereditarily countable, proving

Conversely, let $x\in H_{{\aleph }_1}$ and choose a sufficiently large $L_{\theta }$ containing $x$. By the Downward Lowenheim-Skolem theorem, there is a countable elementary substructure $N\prec L_{\theta }$ that contains every member of $\mathrm{TC}(\{x\})$. The Mostowski collapse theorem gives a transitive collapse of $N$, and the condensation lemma for the constructible universe identifies it with $L_{\beta }$ for a countable ordinal $\beta$. Because $N$ contains the transitive closure of $x$ pointwise, the collapse fixes $x$. Thus $x\in L_{\beta }\subseteq L_{{\omega }_1}$. Hence

Let $S$ be a finite subset of $\mathrm{ZFC}+\phi$, and let $T$ be the finite collection of axioms of $\mathrm{ZFC}$ occurring in $S$. Choose the finite fragment $T^{\ast }$ supplied by the hypothesis. The Lévy reflection theorem gives a level $V_{\alpha }$ satisfying $T^{\ast }$; the Downward Lowenheim-Skolem theorem gives a countable elementary substructure of that level, and the Mostowski collapse theorem turns it into a countable transitive model $M$ of $T^{\ast }$. By the assumed extension property, $M$ is contained in a countable transitive model $N$ of $T+\phi$, so $N$ satisfies $S$.

This argument is formalizable over $\mathrm{ZFC}$ for each finite $T$. Hence, if $\mathrm{ZFC}$ is consistent, every finite subset of $\mathrm{ZFC}+\phi$ is consistent. The compactness theorem now gives

Under $V=L$, the structure $L_{{\omega }_1}$ contains a well-order code for every countable ordinal and the representation of every well-order code that it contains. Given any $\alpha <{\omega }_1$, apply the Downward Lowenheim-Skolem theorem to choose a countable elementary substructurecontaining $\alpha$. The Mostowski collapse theorem and condensation identify the transitive collapse of $X$ with $L_{\lambda }$, where $\lambda =X\cap {\omega }_1$ is a limit ordinal greater than $\alpha$.

Elementarity now verifies both coding properties. If a well-order code belongs to $L_{\lambda }$, its representation is carried into $L_{\lambda }$ by the collapse. Conversely, every $\beta <\lambda$ belongs to $X$, and elementarity supplies in $X$ a well-order code for $\beta$; the collapse fixes this code because it is a relation on $\omega$. Hence $L_{\lambda }$ is a coding level of the constructible hierarchy. Such $\lambda$ occur unboundedly below ${\omega }_1$, so $\Gamma$ has at least ${\aleph }_1$ elements; since $\Gamma \subseteq {\omega }_1$, it has exactly

The theory $\mathrm{Th}(\mathbb{Z},+,0)$ is not aleph-zero-categorical. Introduce a constant $c$ and add the formulasEvery finite subset is realized in $\mathbb{Z}$ by taking $c$ to be a nonzero common multiple of the finitely many displayed integers. The compactness theorem therefore gives a model of $\mathrm{Th}(\mathbb{Z},+,0)$ containing a nonzero infinitely divisible element of an abelian group. The Downward Lowenheim-Skolem theorem gives such a model that is countable.

No nonzero integer is divisible by every positive integer, so this countable model is not isomorphic to $\mathbb{Z}$. This is the nonstandard model of the additive integers obstruction to categoricity.

The recursive theory $T=P{A}^{-}+\phi$ is consistent because $\mathbb{N}\models T$. By the Gödel-Rosser theorem it has an undecidable sentence $\rho$, so both $T+\rho$ and $T+\neg \rho$ are consistent. Exactly one of $\rho ,\neg \rho$ is false in $\mathbb{N}$; add that one to $T$. The first-order completeness theorem gives a model, and the Downward Lowenheim-Skolem theorem gives a countable model $M$. Then $M\models P{A}^{-}+\phi$, but $M$ disagrees with $\mathbb{N}$ on the chosen sentence and is therefore not elementarily equivalent to it.

Start with the countable model $M_0$. There are countably many finite tuples and formulas. For every pair $\bar{a},\bar{b}\in M_i$ having the same type and every $c\in M_i$, use compactness to realize over $\bar{b}$ the transported type $\mathrm{tp}(c/\bar{a})$. Realize all these countably many requirements in an elementary extension and use the Downward Lowenheim-Skolem theorem to choose it countable; call it $M_{i+1}$.

The elementary union $M_{\omega }={\bigcup }_{i<\omega }{M}_i$ is countable. Any finite tuples and element in it occur at one stage, and their required matching element appears at the next. Thus $M_{\omega }$ is an aleph-zero-homogeneous elementary extension of $M_0$.

The Downward Lowenheim-Skolem theorem says that for an $L$-structure $M$ and a subset $S\subseteq M$, there is an elementary substructure $N\preccurlyeq M$ containing $S$ withIf an infinite cardinal $\kappa$ satisfies $\max (|L|,{\aleph }_0)\le \kappa \le |M|$, one can in particular obtain size exactly $\kappa$ by starting with a subset of that size.

Choose a default element $a_0\in M$. For every logical formula $\exists x\varphi (x,\vec{y})$ choose a Skolem function $F_{\varphi }$ which returns a witness in $M$ when one exists, and returns $a_0$ otherwise. Begin with $S$, the interpretations of the first-order language's constants, and $a_0$. Successively adjoin the values of all the original functions and these Skolem functions on finite tuples already chosen. Let $N$ be the union of the resulting countable sequence of closure stages.

There are at most $\max (|L|,{\aleph }_0)$ logical formulas, and each function has finite arity. With $\kappa =\max (|S|,|L|,{\aleph }_0)$, each closure stage has size at most $\kappa$, and so does their countable union. Closure under the original functions makes $N$ an $L$-substructure. Whenever $M\models \exists x\varphi (x,\vec{a})$ for parameters in $N$, its chosen Skolem witness belongs to $N$, since the finitely many parameters lie in some common stage. The Tarski–Vaught test therefore gives $N\preccurlyeq M$.

For the exact-cardinality version, choose an initial set of $\kappa$ elements, enlarged to contain any prescribed subset of size at most $\kappa$. The construction gives an upper bound $\kappa$ while containment gives the matching lower bound.

Take a countable elementary substructure ${\mathcal{B}}^{\prime }$ of ${\mathcal{A}}^{\prime }$ containing the named constant, using the Downward Lowenheim-Skolem theorem. Its reduct $\mathcal{B}$ has infinitely many singleton and doubleton classes. In particular it contains the partner of each of its non-singleton elements, and its interpretation of $P$ is exactly the singleton-class predicate.

Choose new distinct elements $u,v\notin B$. DefineIn $\mathcal{C}$, make $u$ a new singleton class. In $\mathcal{D}$, make $\{u,v\}$ a new doubleton class; keep every old class of $\mathcal{B}$ unchanged. All three reducts are first-order models of the complete theory, and $\mathcal{B}\subseteq \mathcal{C}\subseteq \mathcal{D}$.

Expand $\mathcal{C},\mathcal{D}$ by interpreting $P$ as singleton-class membership and retaining the original named constant from $B$. The resulting countable first-order structures ${\mathcal{C}}^{\prime },{\mathcal{D}}^{\prime }$ are each isomorphic to ${\mathcal{B}}^{\prime }$: all have infinitely many classes of each size, and the bijections of classes can be chosen to preserve the constant and its class. Hence they are first-order models of $\mathrm{Th}({\mathcal{A}}^{\prime })$. Both inclusions ${\mathcal{B}}^{\prime }\subseteq {\mathcal{C}}^{\prime }$ and ${\mathcal{B}}^{\prime }\subseteq {\mathcal{D}}^{\prime }$ are genuine structure embeddings, since no class meeting $B$ was changed. The given quantifier elimination, together with the preceding implication to first-order model completeness, yieldsTaking reducts gives $\boxed{\mathcal{B}⪯\mathcal{C},\mathcal{B}⪯\mathcal{D}}$. Butso $\boxed{\mathcal{C}⋠\mathcal{D}}$. There is no conflict with quantifier elimination in the expanded language: $P(u)$ changes truth value, so ${\mathcal{C}}^{\prime }$ is not a substructure of ${\mathcal{D}}^{\prime }$.

WriteThese are first-order formulas in the original language, not new predicate symbols. An axiomatization consists of the equivalence relation axioms for $E$, the boundand, for every $n\ge 1$, the two sentencesThe first scheme supplies infinitely many singleton classes. The second supplies infinitely many distinct non-singleton classes; the size bound makes these doubletons.

Every countable first-order model has countably infinitely many classes of each size. A bijection between singleton classes, and another between doubleton classes followed by a bijection inside each matched pair, gives an isomorphism between any two countable first-order models. To infer completeness, suppose a sentence had different truth values in two arbitrary first-order models. The Downward Lowenheim-Skolem theorem supplies countable elementary substructures of those first-order models, which would still disagree on the sentence, contradicting the isomorphism just constructed. Thus all first-order models satisfy the same sentences. Since the original first-order structure satisfies the axioms, these axioms form a complete axiomatization of its first-order theory. This is the theory of infinitely many singleton and doubleton equivalence classes.

In the language containing one binary equivalence relation $E$, require all classes to have size at most two and infinitely many classes of each of the two sizes. This is a complete theory: every countable model has countably many singleton classes and countably many doubleton classes, giving a class-by-class isomorphism; Downward Lowenheim-Skolem theorem then rules out a sentence separating arbitrary models. It is also an aleph-zero-categorical theory.

It is not finitely axiomatizable. Any finite fragment of the explicit infinitude schemes has a finite model with sufficiently many classes of each size; compactness theorem would make such a finite fragment suffice if any finite axiomatization existed. It is not model-complete: adjoining a new singleton preserves the theory, and subsequently giving that new point a partner also preserves the theory, while changing the existential partner formula at that point. Naming the singleton-class predicate removes this particular obstruction to elementary embeddings.