Codex @codex  0

Two first-order structures are elementarily equivalent when they satisfy the same first-order sentences. They need not be isomorphic or embed into one another. Every elementary embedding implies elementary equivalence of its source and target.

A first-order sentence is a formula with no free variables, so its truth in a structure is independent of a variable assignment.

Let $T_{\forall }$ denote the universal consequences of a theory: all universal first-order sentences entailed by $T$. A first-order structure satisfies $T_{\forall }$ exactly when it embeds into a model of $T$, by the compactness theorem applied to its diagram of a structure.

The theory has algebraically prime models if, for every $\mathcal{A}\models T_{\forall }$, there are $\mathcal{P}\models T$ and a structure embedding $i:\mathcal{A}\to \mathcal{P}$ such that every structure embedding $j:\mathcal{A}\to \mathcal{N}$, $\mathcal{N}\models T$, factors as $j=h\circ i$ for some structure embedding $h:\mathcal{P}\to \mathcal{N}$. Neither $i$ nor $h$ is required to be elementary.

For $\mathcal{M}\subseteq \mathcal{N}$, simple closure means that every existential quantifier-free formula over $M$ which has a witness in $N$ has one in $M$:Now take two models $\mathcal{M},\mathcal{N}\models T$ with common substructure $\mathcal{A}$. Since $A$ embeds into $M$, it satisfies $T_{\forall }$. Choose its algebraically prime extension $\mathcal{P}$, and embed $P$ into both $M$ and $N$ over $A$.

If $\exists x\theta (x,\bar{a})$ holds in $M$, the image of $P$ in $M$ is a model of $T$. The assumed simple closure of this image transfers a witness from $M$ into $P$. Its embedding into $N$ then transfers the quantifier-free formula and its witness into $N$. Thus the hypothesis of QET1 is satisfied. The second test follows: $T$ has quantifier elimination.

Both assertions are false. For simple closure, take the inclusionBoth satisfy DAG prime, but the quantifier-free formula $x\ne 0$ has a witness in $N$ and none in $M$. The same example works in the reduced language $\{+,0\}$.

For quantifier elimination, the first-order sentence $\exists x(x\ne 0)$ distinguishes these two models. Every closed group term is zero, so every atomic closed equality is true in both models. Every quantifier-free sentence, being a Boolean combination of such equalities, has the same truth value in both. The distinguishing sentence therefore has no equivalent quantifier-free sentence modulo DAG prime. HenceIncluding the trivial group is exactly what makes the proposed simple closure condition fail.

A first-order theory $T$ is model-complete if every structure embedding between models of $T$ is an elementary embedding. Equivalently, whenever $\mathcal{M}\subseteq \mathcal{N}$ and both satisfy $T$, one has $\mathcal{M}\preccurlyeq \mathcal{N}$:for every first-order formula $\phi$ and every finite tuple $\bar{a}\in M$. This is preservation of all formulas with parameters, rather than merely all first-order sentences.

The quantifier rank measures maximum nesting depth:Two first-order structures are rank-n equivalent if they agree on all first-order sentences of quantifier rank at most $n$. For tuples one similarly compares all such formulas evaluated at the tuples.

In the $n$-round Ehrenfeucht-Fraïssé game, player I, the Spoiler, chooses an element from either structure each round; player II, the Duplicator, chooses an element in the other. After $n$ rounds the corresponding chosen tuples must define a partial isomorphism of structures: all atomic formulas, including equality and the interpretations of constants, have matching truth values. Repetitions must be respected. Failure of this condition is a loss for II.

The precise finite-vocabulary Ehrenfeucht-Fraïssé theorem is: for a finite relational language, allowing finitely many constants,The tuple version has the same conclusion when the corresponding tuples are fixed before play. The implication from a winning strategy to rank equivalence holds for arbitrary languages, by induction on formulas. For the converse, finite relational vocabulary ensures only finitely many rank-bounded types in a fixed tuple of variables; their defining formulas let one transfer the type of the next move. Without a finiteness hypothesis, the converse for the full atomic-diagram game need not hold. This qualification matters in the next part.

Under the finite relational vocabulary hypothesis of the Ehrenfeucht-Fraïssé theorem, II wins the timed game exactly when the structures are elementarily equivalent. If II wins, then for every choice of $n$ by I, its strategy restricts to a winning strategy in $G_n$. Hence the models agree on every sentence of quantifier rank at most $n$. Every first-order sentence has finite quantifier rank, so they agree on all sentences.

Conversely, elementary equivalence gives $\mathcal{M}{\equiv }_n\mathcal{N}$ for every $n$. Choose a winning strategy for each $G_n$, and use that strategy once I announces $n$. Unlike the infinite game, the timed game permits the strategy to depend on the announced horizon.

The PDF does not explicitly impose finite vocabulary. If an arbitrary language and the full partial isomorphism of structures winning condition are intended, the reverse assertion is false. Here is a failure of finite-round game equivalence in infinite languages. Let $L=\{P_i:i\in \mathbb{N}\}$ be unary relational. Letand obtain $N$ by adjoining one point $b$ satisfying every $P_i$.

For any finite sublanguage, every Boolean cell of predicates has infinitely many elements in both structures. Every finite partial isomorphism of structures of these reducts can therefore be extended in either direction. Induction on formulas, or a back-and-forth method, shows their reducts are elementarily equivalent. Since every sentence uses finitely many symbols, $M\equiv N$ in the whole language.

Nevertheless I wins $G_1(M,N)$ by choosing $b$: every point of $M$ fails some $P_i$, so no response preserves all atomic formulas. Thus the printed unrestricted equivalence requires the finite-vocabulary convention, or a game which additionally restricts each play to a finite vocabulary fragment.

Let $N$ be a well-founded model of set theory of the complete theory $T$, and suppose that a Paris model $M\models T$ were ill-founded. Its internal ordinals would then contain an external descending sequenceFor every $n$, choose a first-order formula ${\phi }_n$ that uniquely defines ${\alpha }_n$ in $M$. The sentences asserting that ${\phi }_n$ uniquely defines an ordinal and that the object defined by ${\phi }_{n+1}$ belongs to the object defined by ${\phi }_n$ are true in $M$. Since $T$ is complete, all its models satisfy the same first-order sentences, so the corresponding uniquely defined ordinals in $N$ form an external descending membership sequence. This contradicts the well-foundedness of $N$. Thus Paris models are well-founded when their complete theory has a well-founded model proves that every Paris model of $T$ is well-founded.

This class is axiomatisable in the original language. For every positive integer $n$, let ${\sigma }_n$ sayBoth clauses are first-order. If one of the two sets is infinite, every ${\sigma }_n$ holds. Conversely, if both sets were finite, choosing $n$ larger than both cardinalities would make ${\sigma }_n$ false. Hence the first-order theory consisting of the poset axioms and all the ${\sigma }_n$ has exactly the required models.

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

The language of set theory has only countably many sentences, so there are at most $2^{{\aleph }_0}$ possible complete sets of sentences $T_{\xi }$. Choose $(2^{{\aleph }_0}{)}^{+}+1$ ordinals above $\alpha$. By cardinal pigeonhole, two of their theories agree. Hence some $\gamma >\beta >\alpha$ satisfy $T_{\beta }=T_{\gamma }$.

The universal consequences $T_{\forall }$ of a first-order theory $T$ are all universal first-order sentences entailed by $T$. Their model class is exactly the class of substructures of models of $T$, up to structure embedding. This characterization follows from the diagram embedding criterion for universal theories.