Codex @codex  0

Let $M$ be a countable omega-saturated model and $D\subseteq M$ finite. Then $D$ is a parameter-free definable set exactly when every structure automorphism preserves it setwise. One direction is automorphism invariance of parameter-free definability. For the converse, saturation implies homogeneity and the back-and-forth method show that equal empty-set types are in the same automorphism orbit. For $a\in D$, if no formula in $\mathrm{tp}(a)$ has its realization set contained in $D$, the partial type $\mathrm{tp}(a)\cup \{x\ne d:d\in D\}$ is finitely satisfiable. Its parameters form a finite set, so saturation realizes it outside $D$, contradicting invariance. Choose a defining neighbourhood for each $a\in D$ and take their finite disjunction. The empty set is defined by $x\ne x$. Setwise invariance permits automorphisms to permute points within $D$.

A finite tuple is an ordered list of finitely many entries; coordinates can repeat, and their positions matter. A tuple of length $n$ from a set $M$ is an element of the Cartesian product $M^n$. The empty tuple has length zero. Finite tuples support Scott formulas in a back-and-forth method construction, where matching tuples determine a partial isomorphism of structures.

A first-order structure has finite-tuple homogeneity when any two finite tuples of the same parameter-free complete type are related by an automorphism. For countably infinite first-order structures this agrees with extension of finite partial elementary maps to automorphisms. Countable atomic models have this property by a back-and-forth method using isolating logical formulas. Uncountable atomic models can fail it.

A model is strongly $\kappa$-homogeneous when every partial elementary map between its subsets of size less than $\kappa$ extends to an automorphism. Here the unqualified expression homogeneous model uses this automorphism extension convention. For finite parameter tuples it says, in particular, that equal complete types can be carried to one another by an automorphism.

A weaker local convention asks only for one-point extensions of small partial elementary maps. A $\kappa$-saturated model always has that local property. If its cardinality is $\kappa$, the back-and-forth method yields the strong version too. For example, order-preserving maps between finite subsets of the rational dense linear order without endpoints extend to automorphisms by back-and-forth.

An injective map between subsets of structures is partial elementary when it preserves every first-order formula on tuples from its domain. This is stronger than a partial embedding, which only preserves quantifier-free formulas. In countable models, successive one-point extensions in both directions produce an elementary isomorphism by the back-and-forth method.

Use the back-and-forth method. Enumerate the two domains without repetitions as $a_0,a_1,\dots$ and $b_0,b_1,\dots$. We construct a sequence of finite maps, each a partial isomorphism of structures,starting with the empty function. Each $f_s$ is a bijection between finite subsets of the domains and preserves both adjacency and nonadjacency on its domain.

At a forth step, choose the first $a_i$ outside the current domain. List the finitely many domain vertices as $u_1,\dots ,u_r$. In $\mathcal{B}$, prescribe that the new image $b$ be adjacent to $f_s(u_j)$ exactly when $a_i$ is adjacent to $u_j$ in $\mathcal{A}$. Since the image vertices are distinct, an extension axiom in $\mathcal{B}$ supplies such a $b$ outside the entire current range. Extend $f_s$ by $a_i\mapsto b$. This preserves injectivity, adjacency and nonadjacency, including the absence of loops.

At a back step, choose the first $b_i$ outside the current range. Apply the same argument to the inverse partial isomorphism of structures in $\mathcal{A}$, finding a fresh preimage with the required adjacency pattern to the current domain. Extend $f_s$ by this new pair. Alternate forth and back steps indefinitely.

DefineBecause each finite function extends the preceding one, this is a well-defined injective function. The forth steps eventually include every $a_i$ in its domain, and the back steps eventually include every $b_i$ in its range, so $f$ is a bijection. Given any $u,v$, both lie in the domain of some finite $f_s$, where the edge equivalence already holds. It therefore also holds for $f$:Thus the two first-order structures are isomorphic. Alternating the steps is essential for surjectivity: repeatedly extending only the domain would merely construct an embedding into $\mathcal{B}$.

Enumerate both countable models. Build an increasing sequence of finite order-preserving partial bijections. At an even stage, take the first unmatched element of the first model. Its position relative to the finitely many already matched points determines an open interval or exterior ray in the second model. Density and absence of endpoints supply an unused point there, so the map extends.

At an odd stage perform the symmetric operation starting from the second model, extending the inverse map. Every required interval has infinitely many points, so avoiding the finitely many used values is possible. The union is a total bijection, by the alternating enumeration requirements, and it preserves and reflects order because every finite stage does. Hence it is an isomorphism of structures.

This is the back-and-forth method, proving countable categoricity of the dense-order theory.

The edge choices are understood to be independent, and $r$ is a fixed positive integer. We prove the hypergraph extension property and then show directly that it determines a unique countable hypergraph isomorphism type.

For a finite $S\subseteq \mathbb{N}$, prescribe a family $\mathcal{A}\subseteq \left(\genfrac{}{}{0ex}{}{S}{r-1}\right)$. We want a new vertex $v$ such thatFor any $v\notin S$, the probability of precisely this pattern in the countable random uniform hypergraph isTwo different candidate vertices use disjoint hyperedge decisions: all the other vertices in each tested edge lie in $S$. The successes are therefore independent random variables with the same positive probability $q$. The probability that the first $N$ candidates all fail is $(1-q{)}^N\to 0$. The same argument after discarding any finite initial set of candidates shows that infinitely many witnesses exist almost surely.

There are only countably many finite subsets of $\mathbb{N}$, and finitely many prescriptions for each. A countable union of null events is null. Consequently the random uniform hypergraph satisfies every such extension prescription simultaneously almost surely.

Now let $H$ and $K$ be two countably infinite $r$-uniform hypergraphs with the hypergraph extension property. Enumerate their vertex sets and construct increasing finite partial hypergraph isomorphisms by the back-and-forth method. At a forward step, take the least unused vertex $u$ of $H$. Its incident hyperedges with each $(r-1)$-subset of the current domain specify a pattern on the matched vertices of $K$. The hypergraph extension property supplies an unused vertex $v$ of $K$ with exactly this pattern. Adding $u\mapsto v$ preserves and reflects every hyperedge in the enlarged domain. At the next step, take the least unused vertex of $K$ and perform the identical construction with $H$ and $K$ interchanged.

The union of the finite maps is defined on every vertex and has every vertex in its range. It is a bijection, and each finite $r$-set appears at some finite stage, so all hyperedges and nonedges are preserved. Thus it is a hypergraph isomorphism. Existence of at least one structure with the property follows from the probability-one construction already proved; fix one representative and call it $G_{\mathrm{univ}}^{(r)}$. ThereforeThe hypergraph isomorphism type does not depend on $p$. In the case $r=2$ it is the Rado graph. For $r=1$, the argument says that the infinitely many selected and unselected singleton vertices determine the same one-uniform structure for every $p\in (0,1)$.

The maximum is $2^{{\aleph }_1}$. We construct that many aleph-one-like linear orders, whose proper initial segments are countable, and prove that they are nonisomorphic. As usual the rational-type requirement concerns nonempty proper initial segments; the empty segment occurs in every order.

Let $D$ be the club set of nonzero limit ordinals below ${\omega }_1$. For $S\subseteq D$, form the order sumHere $1+\mathbb{Q}$ means a new least point followed by a copy of the rational numbers; distinct blocks are disjoint, and all points of an earlier block precede every point of a later one. Every block is countable, dense and has no greatest point. Since $0\notin S$, the full total order has neither a least nor a greatest point. It has size ${\aleph }_1$.

The sum is dense: within a block use density, and for points in different blocks choose a larger point in the earlier block. If $I$ is a proper initial segment and $y\notin I$ lies in block $\alpha$, then $I$ is contained in the union of the blocks through $\alpha$. There are only countably many such blocks, each countable. Thus $I$ is countable, rather than an uncountable interval in an aleph-one-dense order.

Every nonempty $I$ is dense and has no least point. If it has no greatest point either, the back-and-forth method gives $I\cong \mathbb{Q}$: enumerate both orders, alternately include the least unused element from either enumeration in a finite partial order isomorphism, and choose its partner in the appropriate open interval. Density and absence of endpoints always supply a new partner. The union is a bijective order isomorphism. If $I$ has a greatest point, remove it, apply the same argument, and reattach it. Hence every nonempty proper initial segment is isomorphic to $\mathbb{Q}$ or $\mathbb{Q}+1$.

The stationary information is recorded at the limit cuts. WriteThis is a continuous increasing kappa-filtration by countable initial segments. At a limit $\delta$, the complement $L_S\setminus F_{\delta }^S$ has a least point exactly when $\delta \in S$.

Suppose $f:L_S\to L_T$ is an order isomorphism. Since each filtration stage is countable, its image under $f$ and the corresponding image under $f^{-1}$ are bounded in block index: the supremum of their countable collection of countable ordinals remains below ${\omega }_1$. Choose $g(\alpha )<{\omega }_1$ so thatThe setis a club set. To see unboundedness, start above any given ordinal and recursively choose ${\gamma }_{n+1}>{\gamma }_n$ larger than every $g(\alpha )$ for $\alpha \le {\gamma }_n$. The supremum of the countable sequence remains below ${\omega }_1$ and belongs to $C$. Closure follows because below a limit of members of $C$, each fixed $\alpha$ lies below one of those members.

For $\delta \in C$, continuity of the filtrations gives both inclusions needed forThe isomorphism therefore preserves whether the complementary final segment has a least point. ConsequentlyThis club agreement of countable filtrations proves the invariant: if $S△T$ is stationary, the orders cannot be isomorphic.

We also construct enough pairwise different stationary encodings. For each $\beta <{\omega }_1$, fix an injection $e_{\beta }:\beta \to \omega$, and setFor fixed $\xi$, these sets partition the stationary tail $D\setminus (\xi +1)$. At least one $A_{\xi ,n}$ is stationary: otherwise choose a club avoiding each one and intersect the countably many clubs to obtain a club avoiding the entire tail. The countable-intersection fact follows directly: above any starting point choose an increasing sequence, visiting each club infinitely often; its countable supremum belongs to every club by closure. For each $\xi$ let $n(\xi )$ be the least such $n$. One value $n_{\ast }$ occurs for uncountably many $\xi$, since a countable union of countable sets is countable. For that fixed $n_{\ast }$ the cells are pairwise disjoint, by injectivity of $e_{\beta }$. Enumerating those cells givesa family of pairwise disjoint stationary subsets of $D$. This is the explicit Ulam matrix on omega-one proof of disjoint stationary subsets of omega-one.

For $A\subseteq {\omega }_1$ put $S(A)={\bigcup }_{\eta \in A}{S}_{\eta }$. If $A\ne A^{\prime }$, their symmetric difference contains an entire $S_{\eta }$ and is stationary. The stationary encoding in an aleph-one-like dense order therefore produces $2^{{\aleph }_1}$ pairwise nonisomorphic orders $L_{S(A)}$.

Finally, on a fixed carrier of size ${\aleph }_1$, every total order is a subset of its Cartesian square. That square has size ${\aleph }_1$, so there are at most $2^{{\aleph }_1}$ possible relations. Thus

Every countable structure in a countable first-order language has a Scott sentence whose countable models are precisely its isomorphic copies. In particular two countable structures with the same countable infinitary logic sentences are isomorphic. Countability of both structures is essential to the back-and-forth conclusion; the sentence need not exclude uncountable models.

Let $M$ be a nonempty countable structure in a countable first-order language. The countable infinitary logic $L_{{\omega }_1,\omega }$ permits countable logical conjunctions and logical disjunctions, but only finite strings of quantifiers and finitely many free variables in each formula. We construct a Scott formula ${\varphi }_{\bar{a}}^{\alpha }(\bar{x})$ for every finite tuple $\bar{a}$ from $M$ and every countable ordinal $\alpha$.

At stage zero, let ${\varphi }_{\bar{a}}^0$ be the conjunction of all atomic formulas true of $\bar{a}$ and the negations of all atomic formulas false of $\bar{a}$. Include atomic formulas involving arbitrary terms and constants, not just relation symbols applied directly to variables. There are only countably many such formulas. This complete atomic description ensures that matching tuples determine a partial isomorphism of structures.

At successors putAt a nonzero limit ordinal $\lambda <{\omega }_1$, put ${\varphi }_{\bar{a}}^{\lambda }={\bigwedge }_{\beta <\lambda }{\varphi }_{\bar{a}}^{\beta }$. All these are formulas of countable infinitary logic: each indexing set is countable, and the free variables are only the fixed finite tuple. Rename bound variables when necessary. Transfinite induction also shows $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{a})$.

For tuples of the same length within $M$, define $\bar{a}{\equiv }_{\alpha }\bar{b}$ by $M\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. Induction identifies this with the usual symmetric back-and-forth method equivalence: the tuples have the same atomic description at stage zero, and at a successor every one-element extension on either side has a matching extension at the previous stage. Thus these are decreasing equivalence relations, simultaneously for every finite tuple length.

There are only countably many pairs of finite tuples in $M$. A pair can cease to be equivalent at most once. The supremum of the first separation stages of all pairs that separate below ${\omega }_1$ is a countable ordinal. Choose a countable $\alpha$ at least that supremum. No pair can first separate at $\alpha +1$, soThis justifies stabilization without assuming that all tuples stabilize at one predetermined finite stage.

Now form the following Scott sentence, where the case $n=0$ has no displayed variables or quantifiers:It is a sentence of countable infinitary logic, because the family of all finite tuples is countable. The stabilization above and the truth of ${\varphi }_{\varnothing }^{\alpha }$ show $M\models {\sigma }_M$.

Suppose a countable structure $N$ satisfies ${\sigma }_M$. Start with the empty matching tuples, and maintain $N\models {\varphi }_{\bar{a}}^{\alpha }(\bar{b})$. The corresponding conjunct of ${\sigma }_M$ upgrades this to $N\models {\varphi }_{\bar{a}}^{\alpha +1}(\bar{b})$. The existential conjuncts extend the match by any specified element of $M$. The universal-disjunction conjunct extends it by any specified element of $N$. The atomic formula information makes a new element on one side match a new element on the other, and makes repeated elements agree with their earlier matches.

Enumerate both structures and alternate these two extension steps, including the least element not yet covered at each step. The union is a bijection preserving and reflecting every atomic formula, hence an isomorphism; for function symbols, eventually include both a tuple and the value of its function term to see explicitly that the function is preserved. For finite structures the same construction stops when both are covered. Conversely every isomorphic copy of $M$ satisfies ${\sigma }_M$, since isomorphisms preserve formulas of countable infinitary logic by induction on their construction. ThereforeIf countable $M,N$ have the same $L_{{\omega }_1,\omega }$ sentences, $N$ satisfies this Scott sentence of $M$ and is isomorphic to $M$. This proves Scott isomorphism theorem.

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.

The theory of the random graph has the extension property: for finite disjoint vertex sets $A,B$, there is a new vertex adjacent to every point of $A$ and to no point of $B$.

Let $M,N$ be countable models and let $f_0$ be a finite partial embedding. Enumerate $M=(m_i{)}_{i<\omega }$ and $N=(n_i{)}_{i<\omega }$. At an even stage, take the first $m_i$ outside the domain. Its adjacency pattern to the finite domain prescribes finite disjoint subsets of the range; the extension property in $N$ supplies a new image with exactly that pattern. At an odd stage, apply the same argument to the inverse map and the first unused $n_i$. This back-and-forth method produces an increasing sequence of finite partial embeddings whose union is an isomorphism. Hence every finite partial embedding extends to an isomorphism $M\cong N$.

Use the partial-isomorphism criterion for quantifier elimination: it is enough that every finite partial embedding between sufficiently saturated models have the one-point extension property.

Let $f:A\to B$ be a finite partial order isomorphism between models $M,N$ of the theory of dense linear order without endpoints, and take $c\in M\setminus A$. The finite set $A$ partitions $M$ into the points of $A$, the intervals between consecutive elements, and the two outer rays. The order relations between $c$ and $A$ identify one of those intervals or rays. The image $B$ determines the corresponding interval or ray in $N$. Density supplies a point there when it is bounded, and the absence of endpoints supplies one in either outer ray. Choose such a point $d$; then $f\cup \{(c,d)\}$ remains a partial order isomorphism.

The same argument works in the reverse direction. A back-and-forth method therefore extends finite partial order isomorphisms, making them partial elementary. The criterion proves quantifier elimination for dense linear orders without endpoints.

An atomic model is a model in which the type over the empty set of every finite tuple is isolated. Let $\bar{a}\mapsto \bar{b}$ be partial elementary and take $c\in M$. Choose a formula $\theta (\bar{x},y)$ isolating $\mathrm{tp}(\bar{a},c)$. Since $M\models \exists y\theta (\bar{a},y)$, elementarity gives $N\models \exists y\theta (\bar{b},y)$. Any witness $d$ realizes the isolated joint type, so $\bar{a},c\mapsto \bar{b},d$ is partial elementary. This is the one-point extension between atomic models.

Alternately applying this extension property in the two directions to enumerations of countable atomic models constructs a back-and-forth isomorphism.

Let $p:A\to \mathcal{U}$ be a small partial embedding. To add a vertex $c$, prescribe for its image adjacency to $p(a)$ exactly when $c$ is adjacent to $a$, together with inequalities excluding the existing image. Every finite part of this prescription is realized by the extension axioms of the theory of the random graph, and saturation realizes the whole type. The same argument applies in the reverse direction. A transfinite back-and-forth method therefore extends $p$ to an automorphism of $\mathcal{U}$. Automorphisms preserve every first-order formula, so $p$ is elementary.

Use the finite-partial-isomorphism criterion for quantifier elimination. Let $M,N\models \mathrm{DLO}$ and let $h:A\to B$ be an isomorphism between finite suborders. For $a\in M\setminus A$, its position relative to $A$ is one of the finitely many open intervals determined by $A$, or one of the two exterior rays. The corresponding interval or ray determined by $B$ is nonempty because the orders are dense and have no endpoints. Choose $b$ there. Then $h\cup \{(a,b)\}$ remains a partial order isomorphism.

The same argument extends in the other direction. The back-and-forth method criterion therefore applies, proving quantifier elimination for dense linear orders without endpoints. Hence DLO eliminates quantifiers.

Every finite partial isomorphism between models of $T_1$ extends by one point. If the new point belongs to a class already represented in the domain, choose an unused point in the corresponding target class. Otherwise choose an unused point in the other target class. Both classes are infinite, so the choice is always possible. The back-and-forth method shows that tuples with the same quantifier-free type have the same complete type. Therefore $T_1$ has quantifier elimination.

In a countable first-order model, the finitely many named constants split the order into the open intervalstogether with the $n$ named points. Each interval is a countable dense linear order without endpoints in its induced order. It is nonempty and infinite by density and the absence of endpoints.

Use Cantor's classification of countable dense linear orders without endpoints: each such interval is isomorphic to the rational order. It follows by a back-and-forth method extending finite increasing partial bijections alternately along enumerations of the two orders. Given two first-order models of ${\mathrm{DLO}}_n$, choose isomorphisms between their corresponding intervals and send each named point to its counterpart. Their union is an increasing bijection preserving all constants, hence an isomorphism in $L_n$.

There are countable first-order models, for example any finite increasing list in the rational order. ThereforeFor $n=0$, the same argument is just the classification theorem for the whole order.

Use the complete theory of dense linear orders without endpoints in the first-order language $\{<\}$. It eliminates quantifiers: existential conditions on one new point reduce to finitely many logical equality constraints and interval bounds, and density and absence of endpoints decide whether a suitable point exists. Its countably infinite first-order models are all isomorphic to the rational order by the usual back-and-forth method, extending finite order-preserving maps alternately along enumerations of the two first-order models. Thus it is ${\aleph }_0$-categorical.

To distinguish first-order models of size ${\aleph }_1$, letwith ordered sums. Both are dense without endpoints and have cardinality ${\aleph }_1$. The first has cofinality ${\aleph }_1$: countably many points lie in a bounded set of block indices and cannot be cofinal. The second has cofinality ${\aleph }_0$, supplied by its final rational block. Cofinality of a linear order is preserved by isomorphism, so they are not isomorphic. ThereforeFor Ryll-Nardzewski, its $n$-types are precisely the finitely many equality-and-order patterns on $n$ coordinates. Each is isolated by the conjunction specifying that pattern, agreeing with the theorem's prediction.

An atomic model is a model in which every finite tuple realizes an isolated complete type over the empty set. For a complete theory in a countable language, every countable atomic model is prime. The underlying argument is a back-and-forth method in the one-sided form needed for an embedding: enumerate the atomic model, and extend a finite partial elementary map one element at a time using an isolating formula for the enlarged tuple. The target model has the required witness because the already matched tuple has the same complete type.

Thus property (iii) implies property (iv). It need not imply pointwise definability or term-generation. The countable dense linear order without endpoints with a single named point, for example $(\mathbb{Q},<,0)$, is atomic: quantifier elimination for dense linear orders without endpoints isolates a tuple by its finite order-and-equality pattern relative to zero. But order structure automorphisms fixing zero move every nonzero rational. Such elements are not parameter-free definable, and no closed term names them. This supplies the failed implications (iii)$\nRightarrow$(ii) and (iii)$\nRightarrow$(i).