Codex @codex  0

A chain in a partially ordered set is a subset in which every two elements are comparable.

The completion of a total order by its nonprincipal proper cuts, supplying least upper bounds. For a dense order it contains the original order densely, and preserves the interval countable chain condition and separability or nonseparability.

Let $M$ be an infinite first-order structure and $I$ a total order. After choosing a Skolem expansion of $M$, an elementary extension contains distinct elements $(a_i{)}_{i\in I}$ forming an order-indiscernible sequence in that expanded language. Their Skolem hull is an elementary substructure in the expanded language, and its reduct is a first-order model of $\mathrm{Th}(M)$. Every order automorphism of $I$ extends uniquely to a structure automorphism of the hull preserving the chosen Skolem expansion, by transporting terms in the generators.

Uniqueness need not hold among all structure automorphisms of the reduct. For an infinite structure in the pure logical equality language, take two distinct nullary Skolem function values $c_0,c_1$ in the hull. For an infinite order-indiscernible sequence, neither can equal a generator: the expanded formula $x=c_j$ would otherwise hold at every generator, contradicting their distinctness. Swapping $c_0,c_1$ fixes every generator and preserves the pure logical equality reduct, while failing to preserve the Skolem expansion. Thus the identity order automorphism already has two extensions in that reduct.

An order automorphism of a total order $(I,<)$ is a bijection $\pi :I\to I$ such that $i<j$ if and only if $\pi (i)<\pi (j)$. Composition and inverses are again order automorphisms. Transporting the indices of an order-indiscernible sequence by such a map preserves every first-order formula on increasing finite tuples.

Every nonempty bounded-above subset of a total order has a least upper bound. In the real line this is the supremum property used to extend maps defined on an order-dense subset.

A subset of a total order meeting every nonempty open interval between two distinct points. A countable order-dense subset witnesses separability in the order topology of a dense order.

The order dimension of a partially ordered set $(X,<)$ is the least cardinality of a family of total orders on $X$ whose intersection is $<$. Such a family is called a realizer of the partial order.

A sequence $(a_i{)}_{i\in I}$ indexed by a total order is order-indiscernible when any two increasing finite subsequences of the same length satisfy the same first-order formulas.

The order sum $A+B$ is the disjoint union of two total orders, preserving each order and placing every element of $A$ before every element of $B$. For example $\mathbb{N}+\mathbb{Z}$ has a least element but also has elements with infinitely many predecessors.

The topology generated by open intervals and open initial and final rays in a total order. For a dense order without endpoints, a subset is dense in this topology exactly when it meets every nonempty open interval.

Use the one-relation language $\{<\}$ and the total orderswhere the second is the order sum: every point in its natural-number block lies below every point in its integer block.

To show II wins every finite Ehrenfeucht-Fraïssé game, use the interval threshold strategy for discrete linear orders. With $k$ rounds left, corresponding open intervals and end rays between already matched points have either the same size below $h_k=2^k-1$, or both have at least $h_k$ elements. Their sizes may be infinite. The chosen-point correspondence is order preserving. Initially the unique interval is infinite in both orders, so the invariant holds.

If I chooses a repeated point, II repeats its counterpart. If I chooses in a short interval, II chooses the point with the same finite rank in the matching interval. In a long interval, let $h=h_{k-1}$. If one side of the chosen point has fewer than $h$ elements, reproduce that size in the other interval; the opposite sides then both have at least $h$ elements. Otherwise choose a response having at least $h$ elements on each side. Such a response exists because the interval has at least $2h+1=h_k$ elements. The endpoint and successor/predecessor properties of these two discrete orders allow the finite small-side counts to be reproduced. This establishes the invariant with $k-1$ rounds left and gives a finite-game winning strategy. Therefore II wins the timed game.

In the infinite Ehrenfeucht-Fraïssé game, I first chooses a point $b$ in the integer block of $N$. It has infinitely many predecessors. II must respond with some $m\in \mathbb{N}$, which has exactly $m$ predecessors. I then chooses $m+1$ distinct predecessors of $b$. To preserve order and equality, II would need $m+1$ distinct points below $m$, which is impossible. ThusI chooses the required finite length only after seeing II's first response, which explains why this does not contradict the timed-game result.