One useful form of the Ehrenfeucht-Mostowski theorem is this: for an infinite first-order structure and any total order , there is a first-order model of generated in a chosen Skolem expansion by an order-indiscernible sequence of distinct elements. Every order automorphism of induces an structure automorphism of this expanded hull. One can additionally obtain an elementary extension containing by including its elementary diagram. Uniqueness of the induced structure automorphism is asserted in the Skolem expansion, not among arbitrary structure automorphisms of the reduct.
Choose a Skolem expansion : for every existential first-order formula choose a witness function, satisfying . Iterate the expansion if necessary so witnesses are available for first-order formulas in the resulting language. Add constants and require for distinct indices. For every first-order formula of the expanded language and every two increasing index tuples, add
Together with , this is the indiscernibility theory.
Every finite fragment is satisfiable. It mentions only finitely many first-order formulas and index constants. Choose a countably infinite sequence of distinct elements of . For each relevant arity, colour increasing tuples from that sequence by the finite truth vector of all first-order formulas of that arity in the fragment. Successive applications of the infinite Ramsey theorem for r-sets leave an infinite subset homogeneous for each of these finitely many finite colourings. Interpret the finitely many index constants by distinct elements of that subset in increasing enumeration order. All the required truth-value equivalences then hold, and the original structure satisfies the finite part of its own theory.
If an actual elementary extension of is desired, include constants for its elements and the elementary diagram of . A finite fragment still contains only finitely many parameter instances; include those truth vectors in the same colourings. Thus finite satisfiability is unchanged. The compactness theorem now supplies a first-order model with the entire indiscernible sequence, and in the diagram version an elementary copy of .
Take the Skolem hull of the generators, including the diagram constants when present. The witness functions show directly that the hull is elementary: whenever an existential first-order formula with hull parameters is true in the ambient first-order model, its Skolem witness belongs to the hull. Induction on first-order formulas, or the Tarski-Vaught test, gives elementarity. Its reduct is therefore a first-order model of . In the version without diagram constants its cardinality is at most .
For an order automorphism , define
This is well defined. If two terms represent the same element, express their equality as a first-order formula on the increasing union of their generator indices. Indiscernibility and preservation of the index order carry that equality to the transported terms. The same argument for every relation shows preservation of the expanded structure; applying it to supplies the inverse. Every element is a term in the generators, so no other structure automorphism of the specified expansion can have the same action on them. Hence
For an application requiring the generators to lie in a definable infinite ordered class, impose that class predicate and its increasing-order first-order formulas too. The finite-fragment proof uses an increasing sequence in that class, so all these additional conditions are preserved. In particular the integer index order and its shift give the structure automorphism used in the NFU construction. The constants are order indiscernibles, not necessarily indiscernibles under arbitrary permutations of the index set.
In the game , where , the players alternately choose natural numbers and produce a sequence . Player I wins exactly when . A strategy in an infinite game assigns a move to every finite position where its player is to move; it is winning if every play following it is won by that player. A game is determined if one player has a winning strategy. Both cannot have winning strategies, since their joint play would have to be won by both. The axiom of determinacy asserts
Without assuming AD, one can prove determinacy for finite games by backward induction, and for games with open or closed payoffs by the following argument. Give its product topology of discrete move coordinates. If is open, let be the finite positions whose entire cylinder of extensions lies in . Form a winning-position attractor in an infinite game by transfinite recursion: add an I-position if some child has already been added, and add an II-position if all its children have already been added. Take unions at limits. The process stabilizes because there are only set-many positions and each genuine successor change adds a new one.
An added nonterminal position receives its least entry ordinal. At an I-position in the stable attractor, choose a child of smaller rank; at an II-position every child has smaller rank. Thus every play following I's rank-decreasing strategy must reach : an infinite strictly descending sequence of ordinals cannot exist. The resulting play is in , so I wins from any position in the attractor.
Outside the attractor, every child of an I-position remains outside, and an II-position has some child outside. Otherwise the ranks of all its children would have a set-sized supremum and the parent would have been added at a later stage. II chooses such a child and keeps the play outside forever. If its outcome were in the open set , some finite prefix would have its entire cylinder in , contrary to this avoidance. Therefore II wins from outside. With natural-number moves the least suitable child may be chosen at each position, so no choice axiom is needed for these strategies. This proves open determinacy. For a closed payoff, apply the same argument to its open complement with the players' winning roles interchanged. Clopen payoffs are included in both results.
Now assume AC and construct an undetermined game. The set of strategies for either player has cardinality , since a strategy is a function on a countably infinite set of positions. Each fixed strategy is compatible with plays: the other player's sequence of freely chosen moves determines distinct full plays. Use choice to enumerate I's strategies as and II's as , and well-order the space of plays.
Recursively choose following and following , with all selected plays distinct. At stage fewer than plays have been used, while each compatible-play set has size , so fresh choices exist; take the least ones in the fixed well-order. This does not require regularity of , since for every below its initial ordinal.
Put . Every I-strategy has the losing compatible play , and every II-strategy has the losing compatible play . Therefore neither player has a winning strategy. This choice diagonalization of an undetermined game proves
The elementary determinacy proofs above concern specified definable payoff classes; the diagonal construction explains why extending them to every arbitrary subset of the play space is incompatible with choice.

Articles by others on the same topic (0)

There are currently no matching articles.