Codex @codex  0

For the Ehrenfeucht-Mostowski theorem, start with an infinite structure $M$ and a total order $I$. Choose a Skolem expansion $M^{\ast }$, and adjoin constants $c_i$ for $i\in I$. Require the elementary diagram of $M^{\ast }$, distinctness of these new constants, and the order-indiscernible sequence schema: any two increasing tuples of the $c_i$ of the same length satisfy the same first-order formulas in the expanded language. Every finite fragment mentions finitely many new constants and finitely many first-order formulas. Enumerate a countably infinite subset of $M$. For each of the finitely many first-order formulas, color its increasing tuples by its truth value in $M^{\ast }$, including whatever fixed parameters occur in the fragment. Successive applications of the infinite Ramsey theorem leave an infinite subset homogeneous for all these colorings. Assign the finitely many new constants to distinct elements of this subset in their index order. Their finite indiscernibility requirements and the elementary diagram are then simultaneously satisfied.

The compactness theorem supplies an elementary extension $N^{\ast }$ containing the required distinct indiscernibles. Their Skolem hull is an elementary substructure: an existential first-order formula true of its elements has its chosen Skolem-function witness in the hull, so the Tarski-Vaught test applies. Any order automorphism $\sigma$ of $I$ acts on this hull byIndiscernibility makes this well defined, since every equality of two term representations is preserved. The same argument preserves every first-order formula; the inverse is given by ${\sigma }^{-1}$. Thus it is an automorphism, uniquely determined in the language of the chosen Skolem expansion by its values on the generators. This proves both the indiscernible-model and automorphism forms of the Ehrenfeucht-Mostowski theorem. Uniqueness is not claimed for automorphisms of the reduct which need not preserve the chosen Skolem functions.

For simple typed set theory with atoms, write $S_i$ for the set predicate at sort $i$. Members have sort one lower; urelements have no typed members, extensionality applies to sets, and every well-typed first-order formula defines a set at the next sort. Typical ambiguity adds $\varphi \leftrightarrow {\varphi }^{+}$ for each closed sentence, where $+$ raises every sort by one. We prove finite satisfiability using Ramsey theorem, rather than assuming that adjacent sorts have the same cardinality.

Let $X_n=V_{\omega +2n}$. If $n<m$, then $\mathcal{P}(X_n)\subseteq X_m$. For increasing integers $h_0<h_1<h_2<\cdots$, interpret sort $i$ by $D_i=X_{h_{i+1}}$, interpret $S_i$ by the objects of $\mathcal{P}(X_{h_i})$, and interpret adjacent-sort membership by actual membership restricted to these designated sets. All other objects of a sort are typed urelements. Every subset of $D_i$ is a designated set in $D_{i+1}$, so comprehension holds for every first-order formula, including first-order formulas with quantifiers and parameters at other sorts. Two designated sets with the same members are equal, while the other objects have no typed members. Thus this is a full model of the typed axioms for every increasing sequence of levels. The extra preceding level $h_0$ gives a consistent interpretation of the bottom set predicate as well.

Take finitely many ambiguity sentences and let $r$ bound their highest sort before raising. Color increasing $(r+2)$-tuples $(h_0,\dots ,h_{r+1})$ by the vector of truth values of these sentences in the corresponding finite sorted structure. There are finitely many colors. The infinite Ramsey theorem supplies an homogeneous set of indices. Choose the level sequence from it. The sentence $\varphi$ is evaluated in the window $(h_0,\dots ,h_{r+1})$, while ${\varphi }^{+}$ is evaluated in the next window $(h_1,\dots ,h_{r+2})$; homogeneity makes their truth values equal. Sentences using fewer sorts simply ignore the unused final levels. Thus every finite family of ambiguity axioms has a model satisfying all the typed axioms. Apply many-sorted first-order compactness theorem to obtainThis is a relative consistency construction in the ordinary set-theoretic metatheory. Allowing urelements is essential here: skipping ranks leaves objects outside the represented power sets, and those objects must be permitted as urelements.

A useful precise form of the Ehrenfeucht-Mostowski theorem is this: for an infinite structure $M$ and any linear order $I$, a model of $\mathrm{Th}(M)$ can be generated as a Skolem hull by distinct order indiscernibles $(a_i{)}_{i\in I}$. Every order automorphism of $I$ extends to an automorphism of that hull in the chosen Skolem language. One may first name all elements of $M$, giving an elementary extension containing the original structure. The generation and uniqueness assertions concern this specified expansion, not arbitrary automorphisms of its reduct.

Choose a Skolem expansion $M^{\ast }$: for each existential formula add a function selecting a witness whenever one exists. Introduce constants $c_i$ for $i\in I$. Take the theory of $M^{\ast }$, distinctness of these constants, and all equivalencesThe formulas here are in the fixed expanded language, without the newly added $c_i$ as extra parameters. If naming $M$, use its complete elementary diagram and allow those original names in the formulas.

Every finite fragment has a model by Ramsey's theorem. Only finitely many formulas and constants occur. Take a sequence of distinct elements of $M$. For each arity appearing, color the increasing tuples from this sequence by the finite vector of truth values of all formulas of that arity. Successive Ramsey thinning gives an infinite subset homogeneous for each of these finitely many colorings. Assign the finitely many constants in increasing order to distinct elements of this subset. This satisfies every displayed equivalence in the fragment; the original theory is satisfied because the underlying structure remains $M^{\ast }$. Compactness now gives a model of the full theory, with the required order-indiscernible sequence.

The substructure generated by the constants under the Skolem functions is elementary: any existential formula with parameters which are terms in the generators has its Skolem witness in that same hull. If $g$ is an order automorphism of $I$, defineIndiscernibility makes this well-defined, by applying it to the equation between any two term representations using the increasing tuple of all their indices. The same argument preserves every relation and function; $g^{-1}$ supplies the inverse. It is unique in the generated Skolem structure. This completes the Ramsey proof, rather than stopping at the existence of indiscernibles.

For simple typed set theory with atoms, use sorts $D_0,D_1,\dots$ and membership only from $D_i$ to $D_{i+1}$. A set predicate distinguishes sets from atoms, extensionality compares sets of the same positive type, and comprehension produces in type $i+1$ every subset of $D_i$ defined by a well-typed formula. Atoms have no members. First-order models use Henkin semantics; they are not required to have their next domain equal to the full external power set. Typical ambiguity is the schema $\varphi \leftrightarrow {\varphi }^{+}$ for each closed sentence, where every sort index in ${\varphi }^{+}$ is raised by one.

We show finite satisfiability of this entire typed theory with ambiguity. Choose a list of ranks ${\rho }_0<{\rho }_1<\cdots$ above $\omega$, spaced by at least two. For a finite increasing selection of ranks $r_{-1}<r_0<\cdots <r_m$, letwhere $S_i$ is the set of objects declared to be sets at type $i$. Membership from $D_i$ to $D_{i+1}$ is ordinary membership restricted to objects of $S_{i+1}=\mathcal{P}(D_i)$; all other type-$i+1$ objects are atoms. The spacing puts $\mathcal{P}(D_i)$ inside $D_{i+1}$. Thus comprehension and set extensionality hold exactly, and atoms have no typed members. There are infinitely many objects at every visible type, so any usual typed infinity requirement also holds.

The auxiliary rank $r_{-1}$ provides a uniform interpretation if a set predicate is allowed at type zero; no type-minus-one domain is used in the theory. This avoids artificially declaring all type-zero objects to be atoms, which would not be invariant under type-raising. If the language has no type-zero set predicate, simply ignore this auxiliary interpretation.

A finite set of ambiguity instances uses finitely many closed sentences of bounded highest type, say at most $m$. Color increasing $(m+2)$-tuples of ranks by their finite truth vector in the structure with visible domains $D_0,\dots ,D_m$ and the auxiliary preceding rank. Ramsey's theorem gives an infinite homogeneous rank set. Choose $m+3$ consecutive ranks from it and build the hierarchy on all these ranks. The first window evaluates each original sentence; shifting the window one place evaluates its uniform type-raise. Homogeneity makes the truth vectors equal. All finite typed axioms and the selected ambiguity instances therefore hold together. Choosing $m$ large enough covers every sort needed by the finite fragment. Many-sorted compactness, equivalently ordinary first-order compactness after encoding sorts, yieldsThis is a model existence argument in the ambient set theory; no equality of adjacent type cardinalities is claimed. The gaps between ranks supply atoms, and the ambiguity is about truth of sentences, not a bijection between domains.

For the Ehrenfeucht-Mostowski theorem, let $M$ be an infinite first-order structure and $I$ any linear order. Choose a full Skolem expansion $M^{\ast }$: add witness functions for existential formulas, repeat in the expanded languages, and take their union. We will construct a model of its theory containing distinct generators $c_i$, $i\in I$, forming an order-indiscernible sequence.

Adjoin the elementary diagram of $M^{\ast }$, the inequalities $c_i\ne c_j$ for $i\ne j$, and for every expanded-language formula $\varphi (x_1,\dots ,x_r)$ and every two increasing $r$-tuples of indices, the sentencesEvery finite subcollection is satisfiable in $M^{\ast }$. To prove this, choose a countably infinite sequence of distinct elements of $M$, and for each of the finitely many relevant arities color its increasing index tuples by the finite vector of truth values of the formulas of that arity. Repeated applications of the Ramsey's theorem give an infinite subsequence homogeneous for all these finitely many finite colorings. Interpret the finitely many mentioned $c_i$ by its elements in their index order. All indiscernibility and distinctness constraints hold, and the finite diagram fragment holds because the ambient structure is still $M^{\ast }$.

By compactness theorem, a model $N^{\ast }$ of the full enlarged theory exists. Its Skolem hull $H$ generated by the $c_i$ is elementary: whenever an existential formula with parameters in $H$ holds in $N^{\ast }$, its chosen witness function returns a value in $H$, so the Tarski-Vaught test applies. Its reduct is a model of $\mathrm{Th}(M)$. If the index order has size $\kappa$, the hull has size at most $\kappa +|L|+{\aleph }_0$, and it contains $|I|$ distinct generators.

Every order automorphism $h$ of $I$ induces the automorphismTo check well-definedness, write any two terms being compared over the same increasing list of their generators. Their equality is an expanded-language formula; indiscernibility of the order-indiscernible sequence preserves its truth under $h$. The same argument preserves each relation, and the term construction preserves the functions. Applying $h^{-1}$ gives the inverse. The extension is unique in the specified Skolem language since every hull element is a term in the generators; no uniqueness among all automorphisms of the reduct is being asserted. This proves the Ehrenfeucht-Mostowski theorem, including its usual automorphism consequence.

For simple typed set theory with atoms, use sorts $0,1,\dots$, predicates $S_i$ for sets, and typed membership from sort $i$ to sort $i+1$. Atoms have no members, extensionality compares sets, and every well-typed formula defines a set of the next sort. Typical ambiguity is the schema $\varphi \leftrightarrow {\varphi }^{+}$ for every closed typed sentence, where the superscript raises all types by one.

Here are concrete full typed models before imposing the ambiguity schema. Choose increasing natural numbers $n_{-1}<n_0<n_1<\cdots$ and setThe auxiliary $D_{-1}$ merely interprets the set predicate at the lowest sort. Define typed membership byThen the other objects of $D_{i+1}$ are atoms, regardless of their old membership. Every subset of $D_i$ has its representative in $S_{i+1}$, giving comprehension even for formulas with higher-sort quantifiers and parameters. Extensionality holds for the set representatives and atoms have no typed members. The rank gaps leave infinitely many atoms at each sort, and all sorts are infinite.

Consider finitely many ambiguity instances with unraised sentences ${\varphi }_1,\dots ,{\varphi }_t$, and choose a fixed window length $r$ sufficient to include every sort used and its auxiliary predecessor. Color every increasing $r$-tuple of natural numbers by the vector of truth values of these unraised sentences in its finite rank-window interpretation. There are only $2^t$ colors. The Ramsey's theorem gives an infinite homogeneous set. Choose $r+1$ successive points from it. The first $r$ points and last $r$ points have the same color, while the latter interpretation of ${\varphi }_j$ is exactly the former model's interpretation of ${\varphi }_j^{+}$. The auxiliary predecessor shifts too, so this remains true for sentences mentioning the lowest set predicate. Extend the chosen rank sequence arbitrarily to interpret the remaining sorts. This yields a model of typed set theory satisfying all the specified ambiguity instances.

Thus every finite subset of the typed axioms together with all ambiguity instances has a model. Applying multisorted compactness theorem givesThe final model satisfies first-order typed comprehension, with quantification over its own sorts and sets as in Henkin semantics.