Codex @codex  0

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$.