Codex @codex  0

For inaccessible $\kappa$ and any predicate $R\subseteq V_{\kappa }$, the ordinals $\alpha <\kappa$ with $⟨V_{\alpha },\in ,R\cap V_{\alpha }⟩\prec ⟨V_{\kappa },\in ,R⟩$ form a club. Closure under ranks of existential witnesses gives unboundedness, and the elementary chain theorem gives closedness.

A directed system of first-order structures and coherent elementary embeddings has a direct limit into which every member embeds elementarily. Represent an element by a pair consisting of a stage and an element at that stage; identify two representatives when their images agree at a common later stage. Interpret functions and relations at a common stage. Mathematical induction on first-order formulas proves elementarity: for an existential first-order formula true at the limit, its witness and parameters occur at a common stage, and elementarity pulls truth back to the stage containing the original parameters. This generalizes the elementary chain theorem beyond linearly ordered diagrams.

A model companion of $T$ is a model-complete theory $T^{\ast }$ in the same language with $T_{\forall }^{\ast }=T_{\forall }$. Equivalently each model of either theory embeds into a model of the other. Alternating these embeddings and using the elementary chain theorem proves uniqueness up to logical equivalence. A model companion need not be a syntactic extension of its original theory.

An ultralimit is the direct limit of a chain of structures formed by taking successive ultrapowers along their diagonal elementary embeddings. At limit stages use the elementary chain theorem. This is a different concept from a topological ultrafilter limit. Alternating relative ultrapower embeddings constructs isomorphic ultralimits of any two elementarily equivalent structures, without requiring the stronger single-ultrapower isomorphism theorem.

For the effective counterexample, let $K$ be the diagonal halting set and let $K_s$ be the finite approximation obtained by running the first $s$ programs for $s$ steps. For $x<y<z$, define the recursive triple colouring with no computable infinite homogeneous set byThis is a total recursive two-coloring: only bounded computations are involved. An infinite homogeneous set $H$ cannot have color one. Fix $x\in H$ and take $y,z\in H$ sufficiently large that every halting computation with index at most $x$ that ever halts has already halted by stage $y$; then the color is zero. If $H$ has color zero, it computes $K$: given $e$, find $x<y$ in $H$ with $x\ge e$ and inspect $K_y(e)$. Agreement with every later stage $z\in H$, and the unboundedness of $H$, give $K_y\cap \{0,\dots ,x\}=K\cap \{0,\dots ,x\}$. Hence this is the correct answer. The set $K$ is not recursive: a purported halting decider would produce a program that halts exactly when the decider says it does not halt on its own index. Thus there is no recursive infinite homogeneous set. Here infinite is essential: every finite subset is recursive, and sets with fewer than three elements are vacuously homogeneous.

A precise finite-arity Erdős-Rado theorem for finite arities iswhere ${\beth }_0(\lambda )=\lambda$ and ${\beth }_{r+1}(\lambda )=2^{{\beth }_r(\lambda )}$. We prove the closed elementary-submodel construction of an end-homogeneous sequence and then induct. We work with AC, as in the usual cardinal partition calculus.

Put $\theta =(2^{\mu }{)}^{+}$, where $\mu$ is infinite, and let $c:[\theta {]}^{m+1}\to \lambda$ with $\lambda \le \mu$ and $m\ge 1$. Choose a regular cardinal $\chi$ large enough that this coloring and its domain belong to $H_{\chi }$, the sets of hereditary size below $\chi$. There is $M\prec H_{\chi }$ of size $2^{\mu }$ containing $c,\theta ,\mu$, every ordinal below ${\mu }^{+}$, and closed under externally given sequences of length at most $\mu$. Here is the closure construction: start with a Skolem hull of the named parameters and the ordinals below ${\mu }^{+}$; iterate hulls after adjoining all at-most-$\mu$-sequences of the preceding hull for ${\mu }^{+}$ stages. Every stage and the union have size $2^{\mu }$, since $(2^{\mu }{)}^{\mu }=2^{\mu }$ and ${\mu }^{+}\le 2^{\mu }$. The elementary chain theorem gives elementarity. Any sequence of at most $\mu$ members of the final union lies in a bounded stage, because ${\mu }^{+}$ is regular, and is added at the next stage. This proves the required closure.

Let $\beta =\sup (M\cap \theta )$. Regularity of $\theta$ gives $\beta <\theta$, and $\beta \notin M$: otherwise $\beta +1$ would also belong to $M\cap \theta$. Recursively choose increasing $x_{\alpha }\in M\cap \theta$ for $\alpha <{\mu }^{+}$ so that, for every $m$-subset $u$ of the earlier points,To justify the recursion, the earlier sequence has length at most $\mu$, hence belongs to $M$. There are at most $\mu$ constraints. All their points and color values are in $M$, so their coded table belongs to $M$ by closure, even though $\beta$ itself is external to $M$. The supremum of the earlier points, plus one, also belongs to $M\cap \theta$ and is below $\beta$. Thus $\beta$ witnesses in $H_{\chi }$ that a point above that bound satisfying the table exists. Elementarity supplies such a point in $M$. This completes the recursion.

The sequence is end-homogeneous: on any increasing $(m+1)$-tuple from it, the color depends only on its first $m$ entries. Define the induced $m$-tuple coloring by $g(u)=c(u\cup \{\beta \})$. For the induction, the arity-one assertion ${\lambda }^{+}\to ({\lambda }^{+}{)}_{\lambda }^1$ is the infinite pigeonhole principle: a union of $\lambda$ sets each of size at most $\lambda$ has size at most $\lambda$. At step $r\ge 1$, take $\mu ={\beth }_{r-1}(\lambda )$, so $\theta ={\beth }_r(\lambda {)}^{+}$. The constructed sequence has size ${\mu }^{+}={\beth }_{r-1}(\lambda {)}^{+}$. The induction hypothesis makes $g$ constant on a subset of size ${\lambda }^{+}$; end-homogeneity makes $c$ constant on its $(r+1)$-subsets. This proves the theorem. In particular $\lambda ={\aleph }_0$ gives an uncountable homogeneous set for every finite-arity coloring with countably many colors, on a sufficiently large cardinal.

There is no unrestricted infinite-exponent analogue under AC. For any infinite cardinal $\kappa$, choose one representative $R$ from each equivalence class of $[\kappa {]}^{\omega }$ modulo finite symmetric difference. Color $X$ by the parity of $|X△R|$. Removing one element of $X$ leaves it in the same class and reverses the parity. Every infinite proposed homogeneous set contains both a countably infinite $X$ and $X\setminus \{x\}$, so cannot be homogeneous. Thus the finite-symmetric-difference colouring of infinite subsets provesThe contrast is between arbitrary colorings at countably infinite arity and the finite arities of the theorem; restrictions on the definability of an infinite-arity coloring can change the problem.

The saturated model condition in degree $\kappa$ means that a first-order model $M$ realizes every one-variable complete type over a parameter set $A\subseteq M$ of size less than $\kappa$. Equivalently every finitely satisfiable such complete type is realized, since it can be extended to a complete type. Without a specified degree, saturated usually means $|M|$-saturated. Countable saturation means ${\aleph }_1$-saturation, including complete types over countably many parameters.

Here is a general saturated elementary extension theorem, with proof: for every infinite regular cardinal $\kappa$, every first-order structure $M$ has a $\kappa$-saturated elementary extension. At a stage $M_{\alpha }$, list all complete types over its subsets of size less than $\kappa$. There is a set of them, since their formulas lie in a set-sized language. Add a witness constant for each complete type to the elementary diagram of $M_{\alpha }$, together with every formula in that complete type evaluated at its witness constant. A finite part mentions finitely many complete types and finitely many formulas from each; each finite conjunction is realizable in $M_{\alpha }$, and the witnesses for different complete types are unconstrained relative to each other. Thus the finite part is satisfiable. The compactness theorem produces an elementary extension $M_{\alpha +1}$ realizing all those complete types. At limits take elementary unions, justified by the elementary chain theorem.

Iterate for $\kappa$ stages and put $N={\bigcup }_{\alpha <\kappa }{M}_{\alpha }$. If $A\subseteq N$ has size below $\kappa$, regularity bounds the stages at which its elements enter, so $A\subseteq M_{\alpha }$ for some $\alpha <\kappa$. A complete type over $A$ consistent with $N$ is finitely satisfiable in $M_{\alpha }$: each finite conjunction is an existential formula with parameters from $M_{\alpha }$, and elementarity transfers its truth from $N$. The complete type is therefore realized in $M_{\alpha +1}$. This provesFor a singular desired degree, apply the theorem at a larger regular cardinal. If $M$ is infinite and an uncountable regular $\kappa$ satisfies ${\kappa }^{<\kappa }=\kappa$, with $|L|<\kappa$ and $|M|\le \kappa$, the construction can keep every stage of size $\kappa$. There are then at most $\kappa$ parameter sets and complete types, and downward Löwenheim-Skolem gives that size after each extension; adding $\kappa$ distinct elements initially ensures final size exactly $\kappa$. The resulting model is saturated in the unqualified sense. The cardinal-arithmetic hypothesis belongs to this size refinement, not to the general existence theorem.

An explicit ultraproduct version is useful too. In a countable language let $U$ be a nonprincipal ultrafilter on $\omega$ and $N={\prod }_{i<\omega }{M}_i/U$, where each factor is nonempty. Enumerate a countable finitely satisfiable complete type, including its chosen parameter representatives, as ${\phi }_1(x),{\phi }_2(x),\dots$. By the Łoś theorem, the set $A_n$ of coordinates where the first $n$ formulas have a simultaneous witness belongs to $U$. PutThese are decreasing members of $U$. At coordinate $i$, let $k(i)$ be the greatest $n\le i$ with $i\in B_n$, if there is one. Choose a witness to the first $k(i)$ formulas there, and an arbitrary element when there is none. For fixed $n$, every coordinate in $B_n$ has $k(i)\ge n$, so the chosen function satisfies ${\phi }_n$ on a $U$-large set. Its ultraproduct class realizes the whole complete type. A countable language over a countable parameter set has only countably many formulas, so this proves countable saturation of a nonprincipal ultraproduct over omega.

For NFU, we give the rank-indiscernible construction of an NFU model explicitly. NFU has a unary predicate $S$ for sets, atoms have no members, extensionality applies to sets, and comprehension applies to every stratified formula. A stratification assigns integer types to variables so that equality uses equal types and $x\in y$ requires $\mathrm{type}(y)=\mathrm{type}(x)+1$. A unary set predicate adds no type difference.

Start with the actual set structure $B=(V_{\omega +\omega },\in )$. This structure satisfies extensionality and every pure-membership separation instance: the subset defined in a set $a$ of rank below $\omega +\omega$ still has rank below $\omega +\omega$. We do not assert that $B$ satisfies replacement or all of ZFC. Expand it by Skolem functions. In it use the sequence of rank objects $V_{\omega +n+6}$, $n<\omega$. For two such objects $d<e$ in sequence order, we havewith quantifiers in $B$. The second statement holds because every subset of $V_{\alpha }$ belongs to $V_{\alpha +1}$, and the later rank is at least $\alpha +1$.

Introduce constants $d_i$, $i\in \mathbb{Z}$, and require them to be order indiscernibles in the Skolem language, satisfying these two assertions whenever $i<j$. Also require $V_{\omega +5}\subseteq d_i$ for every $i$; this fixed rank object is first-order definable in $B$. Every finite part of these requirements together with $\mathrm{Th}(B^{\ast })$ is satisfiable: color finite increasing tuples of the original rank sequence by the truth values of the finitely many formulas mentioned, and use Ramsey's theorem to get a homogeneous subsequence. The rank assertions hold for every increasing tuple there. The compactness theorem gives a model of the full theory. In its Skolem hull $N$ generated by the $d_i$, the integer shift extends to an automorphism $j$ with $j(d_i)=d_{i+1}$, by the term-transport proof of the Ehrenfeucht-Mostowski theorem. Thus $N$ still satisfies extensionality and all pure-membership separation instances, andThis is a set-sized first-order model; no satisfaction predicate for a proper-class universe is being assumed.

Externally let $D_i=\{x\in N:N\models x\in d_i\}$. The automorphism bijects $D_i$ onto $D_{i+1}$. Interpret a typed structure with sort $i$ equal to $D_i$. At sort $i+1$, declare $y$ a set exactly when $N\models y\subseteq d_i$; otherwise it is an atom. Define adjacent-sort membership byThe guard is necessary: a typed atom might have some ordinary $N$-members in $D_i$, and those must not become its typed members. Set-extensionality follows from extensionality in $N$, because the ordinary members of a typed set all lie in $D_i$. For any typed formula on sort $i$, its quantifiers can be restricted to the corresponding $d_l$, its set predicates replaced by subset assertions, and its memberships replaced by the guarded relation. This is an ordinary pure-membership formula of $N$ with finitely many parameters. Separation gives its extension $X\subseteq d_i$, and the displayed closure assertion gives $X\in d_{i+1}$. It is therefore a typed set witnessing comprehension. The automorphism shifts these sorted domains and preserves the set flags and guarded memberships.

Collapse the types onto $D_0$. DefineObjects not satisfying $S$ have no $E$-members. If two sets have the same $E$-members, their images under $j$ are subsets of $d_0$ with the same ordinary members, so are equal by extensionality of $N$; injectivity of $j$ gives equality of the original objects.

To verify every stratified comprehension instance, assign a variable $v$ its stratification type $t(v)$ and translate its value $a\in D_0$ to $j^{t(v)}(a)\in D_{t(v)}$. Equality is preserved. An atomic $E(x,y)$ translates to the guarded adjacent-sort membership because $t(y)=t(x)+1$; the unary predicate $S(y)$ translates to $j^{t(y)}(y)\subseteq d_{t(y)-1}$. Induction on formulas, using the domain bijections for quantifiers, preserves truth. If the free variable $x$ has type $t$, typed comprehension produces its extension $X\subseteq d_t$, with $X\in d_{t+1}$. Put $b=j^{-(t+1)}(X)\in D_0$. Then $S(b)$ holds, and for every $a\in D_0$,This is exactly the required NFU set. No formula containing the external automorphism $j$ has been used in a separation or comprehension scheme; $j$ only transports values after the pure formula is formed.

The construction also permits the usual infinity requirement. The ordinary $\omega$ and its successor graph $f$ are definable in $N$, hence fixed by $j$, and lie below $V_{\omega +5}$, so belong to all the required domains. Under $E$, the members of $\omega$ are still its ordinary $N$-members. The new Kuratowski pair satisfiesSince $j(f)=f$, membership of this pair in $f$ under $E$ is equivalent to $⟨x,y{⟩}_N\in f$. Thus $f$ is an internal injection of $\omega$ into itself omitting zero, giving a Dedekind-infinite set.

We have built a model of NFU, with infinity if it is included in the formulation, in ordinary ZFC metatheory:In particular $\mathrm{Con}(\mathrm{ZFC})\Rightarrow \mathrm{Con}(\mathrm{NFU})$. This proof does not assume $\mathrm{Con}(\mathrm{ZFC})$ as an additional internal axiom: its starting structure is the set $V_{\omega +\omega }$, not a model of ZFC.

Let $S$ consist of all universal-existential sentences entailed by $T$, and take $A_0\models S$. By (c), there is an existential embedding of $A_0$ into $B_0\models T$. By (b), $B_0$ embeds in $A_1$ with $A_0\preccurlyeq A_1$. After replacing structures by isomorphic copies, arrange these maps as inclusions. Since $A_1\equiv A_0$, it also satisfies $S$ and the construction can be repeated. This producesThe two interleaved chains have the same union $D$. The elementary chain theorem gives $A_0\preccurlyeq D$. The $B_i$ are an ordinary chain of models of $T$, so the assumed closure under unions of chains gives $D\models T$. Therefore $A_0\models T$. This provesConversely, universal-existential axioms are preserved in such unions: a finite universal tuple occurs in one stage, which already supplies its existential witnesses. The quantifier-free matrix has the same truth value in that stage and in the union. This also explains the inductive first-order theory characterization.

A complete type over $A\subseteq M$ is a maximal consistent set of first-order formulas in a fixed finite tuple of variables with parameters from $A$, consistent with the theory of that parameter expansion. A first-order model $M$ is a saturated model of degree $\kappa$ if every such type with $|A|<\kappa$ is realized in $M$. It suffices to require this for one-variable types and realize a finite tuple successively. Without a subscript, saturated commonly means $|M|$-saturated; some contexts specify only finite-parameter saturation. We state the degree explicitly.

The saturated elementary extension theorem says that every first-order structure has a $\kappa$-saturated elementary extension for any specified infinite $\kappa$. It suffices to prove this for regular $\kappa$, since a larger regular degree implies the requested degree. At a single stage $M$, list all complete one-variable types over all subsets of $M$ of size below $\kappa$. This collection is a set. Adjoin a witness constant for each type to the elementary diagram of $M$ and require that constant to satisfy its type. Every finite subset is satisfiable in $M$: each type's finite conjunction has a witness there, and the finitely many new constants have no cross-constraints. The compactness theorem gives an elementary extension realizing all these types simultaneously.

Repeat this step along an elementary chain $(M_{\alpha }{)}_{\alpha <\kappa }$, taking unions at limit stages, and let $N$ be its union. The elementary chain theorem follows here by induction on first-order formulas: an existential statement true in the union has a witness in a later stage; elementarity brings an existential witness back to the earlier stage containing its parameters. Thus each stage is elementary in $N$.

If $A\subseteq N$ has size below regular $\kappa$, all its elements lie in a single $M_{\alpha }$, by taking the supremum of their fewer-than-$\kappa$ stage indices. Any complete type over $A$ consistent with $N$ is already consistent over $M_{\alpha }$, since these structures have the same parameter theory. It was therefore realized in $M_{\alpha +1}$. This proves $\kappa$-saturation of $N$.

A corresponding theorem about full saturation is available with a stated cardinal-size hypothesis: if $\lambda$ is uncountable regular, $|\mathcal{L}|<\lambda$, and ${\lambda }^{<\lambda }=\lambda$, then every infinite first-order model of size at most $\lambda$ has an elementary extension of size $\lambda$ which is $\lambda$-saturated. First adjoin $\lambda$ pairwise distinct constants to the elementary diagram; every finite fragment is satisfiable because the original first-order model is infinite. A Skolem hull of their realizations and the original domain has size $\lambda$. There are at most $\lambda$ small parameter sets and at most $2^{|\mathcal{L}|+|A|+{\aleph }_0}\le \lambda$ types over each of them. Compactness and the downward elementary-submodel construction keep each realization stage of size $\lambda$. Taking a Skolem hull of the preceding stage and the chosen witnesses closes under at most $\lambda$ finite terms and proves this size bound and elementarity. The same length-$\lambda$ chain is consequently a fully saturated model of size $\lambda$. The cardinal hypothesis is not silently asserted to hold for every cardinal.

We now prove consistency of NFU by the permitted alternative method of indiscernibles and a domain-shifting structure automorphism. This can start from an explicit set structure available in ZFC, so we need not assume that there is a first-order model of all ZFC. Letand give $F$ the value $\varnothing$ off the natural numbers. Regard $(H,\in ,F,\omega )$ as a first-order structure, with a named object $\omega$. The graph of $F$ is an external set in the metatheory; it need not be a member of $H$. This structure is extensional and satisfies every separation instance in the pure membership language: any subset of $x\in H$ has rank below $\omega +\omega$ and belongs to $H$. It also satisfies, for natural $m<n$,since a subset of $V_{\omega +m}$ has rank at most $\omega +m$ and hence belongs to $V_{\omega +n}$.

Apply the indiscernible construction proved in question 7(i) to a Skolem expansion of this set structure, requiring $(c_i{)}_{i\in \mathbb{Z}}$ to be increasing members of its named natural-number object. For every finite fragment use an increasing sequence of ordinary natural numbers in the initial structure in the Ramsey argument. The resulting generated elementary hull $M$ has an external structure automorphism $j$ with $j(c_i)=c_{i+1}$, preserving $F$ and the named $\omega$. Put $D_i=F^M(c_i)$ and $D=D_0$. Then $j(D_i)=D_{i+1}$, and $M$ satisfies the displayed subset-containment assertion between successive domains. No claim that $M$ satisfies replacement is required.

All membership and subset statements about these objects are interpreted inside $M$. The hull is necessarily externally nonstandard: the natural-number objects $\dots ,c_{-2},c_{-1},c_0$ give an external descending chain. The external structure automorphism is not an object that must be definable within that first-order model.

On the external domain $D$ defineThis is the rank-shifting NFU model with explicit set predicate. The guard $S(y)$ is essential: an object not contained in $D$ could still have some ordinary members in $D$, and must not thereby become a nonempty atom. The objects failing $S$ have no $E$-members. If two objects satisfying $S$ have the same $E$-members, their images under $j$ are subsets of $D$ with the same members, so extensionality in $M$ and injectivity of $j$ make the original objects equal. Thus set-extensionality and the atom condition hold.

It remains to prove every comprehension instance. Use the domains $D_i$ just constructed, equivalently $D_i=j^i(D)$, for integer sorts. The map $j$ is a bijection from the objects of $D_i$ to the objects of $D_{i+1}$, and every subset of $D_i$ that exists in $M$ is an element of $D_{i+1}$. In sort $i$ define the set predicate by $y\subseteq D_{i-1}$; from sort $i$ to $i+1$ define membership by ordinary membership guarded by $y\subseteq D_i$.

For a stratified formula, assign integer types to its variables with equal types for equality and adjacent types for membership. Shift all types uniformly if necessary so the finitely many used types are nonnegative. Replace a variable of type $i$ by $j^i$ of its untyped value, quantify it over $D_i$, and use the typed relations just described. Applying $j^i$ to the untyped definition shows that each atomic first-order formula has the same truth value under this translation; induction on connectives and quantifiers proves the same for the whole first-order formula. Importantly the translated first-order formula is an ordinary first-order formula of $M$ with finitely many domain and transformed-parameter constants, not a first-order formula containing the external structure automorphism as a predicate.

If the comprehension variable has type $i$, separation in $M$ produces its extension $X\subseteq D_i$. The subset-containment assertion gives $X\in D_{i+1}$. Put $y=j^{-(i+1)}(X)\in D$. Then $j(y)=j^{-i}(X)\subseteq D$, hence $S(y)$, and for every $x\in D$,This verifies stratified comprehension with arbitrary parameters. The empty extension gives a distinguished empty set; the always-true first-order formula gives a universal set. The unstratified Russell predicate is not an allowed comprehension instance. ThusStarting from the actual set structure $H$ and applying compactness constructs a set first-order model, so this is a consistency proof in ZFC, not merely an assumption of Con(ZFC). It proves the requested consistency with an explicit interpretation; it does not depend on treating the much stronger full extensionality of NF as already consistent. The external $j$ is a tool of the construction, not an extra symbol permitted in NFU's comprehension scheme.

Here an ultralimit in the model-theoretic sense is a model-theoretic ultralimit: start with a first-order structure, take successive ultrapowers along their diagonal elementary embeddings, and take the directed limit of elementary embeddings of that chain. The elementary chain theorem, proved by induction on formulas after identifying the embeddings with inclusions, makes every stage elementary in the limit. This definition concerns structures, rather than the topological ultrafilter limit.

We first prove the needed Frayne embedding lemma. If $C\equiv D$, every finite subset of the elementary diagram of a structure $D$ can be realized in $C$: existentially quantify its finitely many named elements, and use elementary equivalence. Index by finite diagram fragments, choose such realizations, and extend the filter of cones requiring each diagram formula to an ultrafilter. For each $d\in D$, let $f_d$ give its chosen coordinate realizations, filling unspecified coordinates arbitrarily. The Łoś theorem shows that $d\mapsto [f_d]$ is an elementary embedding of $D$ into an ultrapower of $C$. The formulas $c_d\ne c_e$ ensure injectivity.

There is a relative version: if $C⪯D$, keep all named elements from $C$ constant in every coordinate. Each finite diagram fragment is realizable in $C$ over those parameters by elementarity, so the resulting embedding extends the diagonal embedding of $C$ into its ultrapower.

Now use alternating ultrapowers give isomorphic ultralimits. First embed $B$ into an ultrapower $A_1$ of $A$. Apply the relative lemma to $B⪯A_1$, embedding $A_1$ into an ultrapower $B_1$ of $B$ over its diagonal copy. Next embed $B_1$ into an ultrapower $A_2$ of $A_1$ over $A_1$, and continue. After coherent identifications this givesEach $A_{n+1}$ is an ultrapower of $A_n$ along its diagonal embedding, and each $B_{n+1}$ is an ultrapower of $B_n$ likewise. The two subsequences are cofinal in the same chain of elementary substructures, so their limits are the same union. Hence $\boxed{A\equiv B⟹A_{\infty }\cong B_{\infty }}$. No isomorphism theorem for single ultrapowers has been assumed.

An ultrapower $A^I/\mathcal{U}$ comes with its diagonal elementary embedding $a\mapsto [i\mapsto a]$, by the Łoś theorem. A model-theoretic ultralimit is the direct limit of successive ultrapowers along these diagonal embeddings, with elementary unions at limit stages. It is not a topological ultrafilter limit. We prove the needed embedding lemma with parameters and then build the isomorphism.

If $A\equiv B$, name every element $b\in B$ by a constant $c_b$ and let $D(B)$ be its elementary diagram of a structure: all sentences true in this fully named structure. For each finite $F\subseteq D(B)$, the conjunction mentions finitely many constants. Its existential closure in the original language is true in $B$, hence in $A$. Choose an interpretation of those constants in $A$ making $F$ true, and give unmentioned constants arbitrary values. Index these interpretations by $I=[D(B){]}^{<\omega }$. Extend the filter of finite-diagram cones to an ultrafilter $\mathcal{U}$.

Map each $b$ to the class of its coordinate interpretations. Every diagram formula holds on the cone containing it, so the Łoś theorem says this map preserves every formula, including negated equalities between distinct named elements. It is therefore an elementary embeddingThis is the Frayne embedding lemma. Its relative version is crucial: if $A\prec C$, interpret all constants naming elements of $A$ constantly by those same elements. Every finite fragment of the diagram of $C$ with these fixed parameters is realized in $A$, since its existential closure with parameters from $A$ is true in $C$ and elementarity transfers it to $A$. The same construction embeds $C$ into an ultrapower of $A$ while extending exactly the diagonal embedding of $A$.

Now start with $A\equiv B$. Embed $B$ into an ultrapower $A_1$ of $A$. Apply the relative lemma to $B\prec A_1$ to embed $A_1$ into an ultrapower $B_1$ of $B$, extending the diagonal map on $B$. Apply it to $A_1\prec B_1$ to embed $B_1$ into an ultrapower $A_2$ of $A_1$, extending the diagonal map on $A_1$. Continue alternately. Replace structures by isomorphic copies to turn these elementary embeddings into inclusions; the commuting identities supplied by the relative lemma giveIn this common chain the map $A_n\to A_{n+1}$ is its ultrapower diagonal, and so is $B_n\to B_{n+1}$. The initial $A\to A_1$ is also diagonal. The union of the $A$-stages and the union of the $B$-stages are cofinal unions of the same chain, hence are the same structure after these coherent identifications. The elementary chain theorem follows by induction on formulas, with every finite tuple and every existential witness lying in some sufficiently late stage. It shows this union is elementary over all its stages. Thus the two constructed ultralimits are isomorphic.

Conversely every successive ultrapower and elementary union preserves the original complete theory. If ultralimits of $A$ and $B$ are isomorphic, they satisfy the same sentences, and their elementary embeddings of the original structures give $A\equiv B$. ThereforeThis proves Frayne theorem by an explicit alternating construction; it does not assume the stronger theorem about isomorphic single ultrapowers or any cardinal-arithmetic hypothesis.

A model-theoretic ultralimit is the elementary direct limit of a chain of successive ultrapowers along their diagonal embeddings. We will build two such chains with isomorphic limits. This is not a topological ultrafilter limit and does not require the stronger claim that one ultrapower of each structure is already isomorphic.

First prove the Frayne embedding lemma, including the relative form needed to make the diagrams commute. If $C\equiv D$, expand the language by constants naming every element of $D$, and let $\mathrm{ED}(D)$ be its complete elementary diagram. Index by finite subsets $s$ of this diagram. The finitely many constants in $s$ can be interpreted in $C$ so that $s$ holds: existentially quantifying them gives a sentence true in $D$ and hence in $C$. Choose such interpretations, and give unused constants an arbitrary fixed value in the nonempty domain of $C$.

For each diagram sentence $\delta$, its cone $\{s:\delta \in s\}$ has the finite intersection property with the other cones. Extend the generated filter to an ultrafilter $U$. For $d\in D$, let $f_d(s)$ be its chosen interpretation at coordinate $s$. The mapis elementary by Łoś: every formula true of a tuple from $D$, or its negation, is a diagram sentence and holds on its corresponding cone. In particular distinct named elements stay distinct.

If $C⪯D$, the construction can keep every constant naming $c\in C$ equal to that same $c$ at every coordinate. For a finite diagram fragment, existentially quantify just the names outside $C$; the resulting formula with parameters in $C$ is true in $D$, hence true in $C$. Thus the finite realizations still exist with all those old names fixed. ConsequentlyThis relative extension of the diagonal map is the essential strengthening.

Now let $A_0\equiv B_0$. The nonrelative lemma embeds $B_0$ into an ultrapower $A_1$ of $A_0$. Identify the image with a copy of $B_0$ inside $A_1$. Since $B_0⪯A_1$, the relative lemma embeds $A_1$ into an ultrapower $B_1$ of $B_0$ extending its diagonal map. Rename this larger structure so that the displayed copy of $A_1$ is a literal elementary substructure. Next apply the relative lemma over $A_1⪯B_1$ to embed $B_1$ into an ultrapower $A_2$ of $A_1$ fixing its diagonal copy. Continue alternately. We obtain a coherent elementary chainwith $A_0⪯A_1$ as well. Each inclusion $A_n\to A_{n+1}$ is, up to these coherent identifications, the diagonal embedding into its ultrapower; the same holds for $B_n\to B_{n+1}$. It is the relative clause, not merely the existence of arbitrary elementary embeddings, which guarantees this.

By the elementary chain theorem, the unions of the two subsequences are elementary limits. They are the same structure: each $A_n$ lies in a subsequent $B_n$, and each $B_n$ lies in $A_{n+1}$. Hence the alternating ultrapowers give isomorphic ultralimits construction provesConversely each ultrapower and each elementary direct limit has the same first-order theory as its starting structure. Isomorphic ultralimits therefore imply $A_0\equiv B_0$ as well. Thus the conclusion exactly characterizes elementary equivalence at the level of ultralimits.

A model-theoretic ultralimit is the direct limit of a chain of successive ultrapowers along their diagonal elementary maps. It is not the topological notion of a limit along an ultrafilter. We first prove the precise relative embedding lemma needed to synchronize two such limits.

If $A\prec B$, then $B$ embeds elementarily into an ultrapower of $A$, with the embedding restricting on $A$ to its diagonal map. To prove this Frayne embedding lemma, use the elementary diagram of $B$ with the elements of $A$ treated as named parameters. Every finite fragment $\Delta$ of that diagram has a realization in $A$: replace its finitely many names from $B\setminus A$ by variables and existentially quantify their conjunction. It is true in $B$, and hence true in $A$ by elementarity. Choose these simultaneous realizations for each finite fragment, keeping every parameter from $A$ interpreted as itself; give unmentioned names an arbitrary default in the nonempty $A$.

On the index set of finite fragments, extend the filter of cones $\{\Delta :\Delta \supseteq \Gamma \}$ to an ultrafilter $U$. For each $b\in B$, let $g_b(\Delta )$ be its value in the chosen coordinate realization. Every diagram sentence is satisfied on its cone, so the Łoś theorem makes $b\mapsto [g_b]$ an elementary embedding $B\to A^I/U$. Inequalities in the diagram ensure injectivity. If $b\in A$, all its coordinates equal $b$, giving exactly the diagonal map.

There is also the initial version: if merely $A\equiv B$, then $A$ embeds elementarily into an ultrapower of $B$. A finite fragment of the elementary diagram of $A$, with all its names replaced by variables, yields an existential sentence true in $A$ and hence in $B$. The identical finite-fragment and cone construction therefore proves this version without already assuming an embedding.

Start with $A_0=A$. Use the initial version to place $A_0$ elementarily in an ultrapower $B_0$ of $B$. Relabel embedded copies so we can regard the elementary maps as inclusions. Apply the relative version to $A_0\prec B_0$ to obtain an ultrapower $A_1$ of $A_0$ containing $B_0$, and whose inclusion of $A_0$ is its diagonal map. Next apply it to $B_0\prec A_1$ to obtain an ultrapower $B_1$ of $B_0$ containing $A_1$, again fixing the earlier diagonal inclusion. Continuing gives an elementary chainThe common union $C$ is elementary over every stage by the elementary chain theorem, andThe first presentation is a model-theoretic ultralimit of $A$. The second, preceded by the initial diagonal embedding of $B$ into $B_0$, is a model-theoretic ultralimit of $B$. Each consecutive same-letter inclusion is precisely the corresponding ultrapower diagonal map, not just an unspecified elementary embedding. Thus the two limits are identified with the same structure $C$, proving

Suppose $S$ and $R$ are model companions of $T$. Their universal consequences of a theory agree, so the diagram embedding criterion for universal theories permits embeddings in both directions between their model classes.

Starting from any $M_0\models S$, alternately take such extensions, identifying each model with its image under the embedding:Since $S$ is model-complete, $M_i\preccurlyeq M_{i+1}$; since $R$ is model-complete, $N_i\preccurlyeq N_{i+1}$. The two subsequences have the same union $U$. The elementary chain theorem givesEvery axiom of $R$, as a sentence true in $U$, is therefore true in $M_0$. Thus every model of $S$ is a model of $R$. Reversing their roles proves the converse. The model companion is unique up to logical equivalence. If $T$ is inconsistent, its only possible companion is likewise inconsistent, so the same uniqueness conclusion holds.

Put $\mathcal{V}=⟨V_{\kappa },\in ,R⟩$. Because $\kappa$ is inaccessible, $|V_{\xi }|<\kappa$ for every $\xi <\kappa$, and $\kappa$ is regular. Choose one witness in $V_{\kappa }$ for every existential formula of this expanded language and every finite parameter tuple for which a witness exists. These are Skolem functions; they can be chosen in the ambient universe even when $R$ is not definable inside $V_{\kappa }$.

For each $\xi <\kappa$, the ranks of all chosen witnesses with parameters from $V_{\xi }$ have supremum below $\kappa$: there are fewer than $\kappa$ such parameters and only countably many formulas. Choose $F(\xi )<\kappa$ strictly above those ranks. The limit closure pointsform a club set. At $\alpha \in C$, every existential assertion in $\mathcal{V}$ with parameters in $V_{\alpha }$ has a witness in $V_{\alpha }$. The Tarski-Vaught test yieldsThus the set $E$ of all such elementary levels is unbounded. It is also closed: the union at a limit of increasing elementary levels is an elementary substructure by the elementary chain theorem, and the union of their ranks is $V_{\alpha }$ with predicate $R\cap V_{\alpha }$. ThereforeThis is club reflection below an inaccessible cardinal.

The Rasiowa–Sikorski lemma constructs a generic filter $G_i$ over each $M_i$. Every resulting generic extension remains a countable transitive model of ZFC: there are only countably many ground-model names externally. The order $\mathbb{P}$ has the same elements and ordering at every stage, and atomless forcing order structure is absolute because all its quantifiers are bounded to $\mathbb{P}$. Hence the generic filter for an atomless order is new result gives $G_i\notin M_i$ for every $i$.

The increasing union $N={\bigcup }_{i<\omega }{M}_i$ is transitive and contains $\mathbb{P}$. If it satisfied Axiom of power set for $\mathbb{P}$, there would be a set $A\in N$ withChoose $i$ with $A\in M_i$. The next-stage generic filter $G_i$ belongs to $M_{i+1}\subseteq N$ and is an actual subset of $\mathbb{P}$. This subset assertion is absolute for the transitive set $N$, so $G_i\in A$. Transitivity of $M_i$ and $A\in M_i$ then give $G_i\in M_i$, a contradiction. Thus the power-set failure in an increasing union of generic extensions occurs already at the fixed ground-model order:The stages form an increasing chain, not an elementary chain, so the elementary chain theorem does not assert ZFC for their union.

On $A={\bigcup }_i{A}_i$, interpret a constant at its common value, a function on a tuple by choosing one $A_i$ containing the tuple, and a relation similarly. Total ordering of the indices and compatibility of substructures make these definitions independent of the chosen stage. Every $A_i$ is then a substructure of $A$.

For an elementary chain, induction on formulas provesThe atomic step follows from the induced structure, Boolean steps are immediate, and for an existential formula any witness in the union lies in a later $A_j$ containing the parameters; elementarity between $A_i$ and $A_j$ moves existence back to $A_i$. This is the elementary chain theorem.

A sentence $\forall \bar{x}\exists \bar{y}\phi (\bar{x},\bar{y})$ with quantifier-free $\phi$ is preserved by a union of an embedding chain: a tuple $\bar{a}$ occurs at some stage, a witness $\bar{b}$ exists at that stage, and quantifier-free formulas are preserved in the union. Thus every forall-exists axiomatized theory is inductive.

Conversely, let $T_0$ contain all forall-exists consequences of $T$ and suppose $M\models T_0$. The diagram-and-compactness sandwich lemma says that one can constructwhere every $N_i\models T$ and every $M_i\preccurlyeq M_{i+1}$. For completeness, the first extension is obtained by adding to $T$ the diagram of $M_i$ together with all universal formulas over $M_i$ true there. A finite inconsistency would give a forall-exists consequence of $T$ false in $M_i$. The resulting extension embeds into an elementary extension $M_{i+1}$ by the method of diagrams.

The $N_i$ form an embedding chain and have the same union $N$ as the $M_i$. By the assumed preservation, $N\models T$; by the elementary chain theorem, $M\preccurlyeq N$. Hence $M\models T$, so $T_0\models T$. The two theories are equivalent, proving the characterization.

A model-complete theory is one for which every embedding between models is elementary. If $(M_i)$ is an embedding chain of models, all transition embeddings are therefore elementary. The elementary chain theorem shows that the union is a model elementarily extending every $M_i$, so the theory is preserved under unions of embedding chains. Part (c) then gives an axiomatization by forall-exists sentences.

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.