Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 21 / 6

A useful form of the Ehrenfeucht-Mostowski theorem says that, for an infinite first-order structure $M$ and any total order $I$, there is a model of $\mathrm{Th}(M)$ generated as a Skolem hull by distinct order indiscernibles $(a_i{)}_{i\in I}$. Every order automorphism of $I$ extends uniquely to an automorphism of the specified Skolem expansion of that hull. The model can be obtained inside an elementary extension of a Skolem expansion of $M$; the generated hull itself need not contain $M$.

Choose a Skolem expansion $M^{\ast }$ by iteratively adjoining witness functions: for each existential formula in the current language choose a function returning a witness whenever one exists, with an arbitrary value otherwise. Repeat for countably many rounds. Every formula in the final language uses finitely many symbols, so has a witness function from a later round. Thus the expansion is Skolemized for its own formulas, as required for elementarity of its hull. Add constants $a_i$ for $i\in I$ to the complete theory of $M^{\ast }$, require them to be distinct, and impose the schemefor every formula in the Skolem language. If an elementary extension of $M^{\ast }$ is desired, also add its elementary diagram with separate names for its elements.

Every finite part of this theory is satisfiable. Choose infinitely many distinct elements $b_0,b_1,\dots$ of $M$. For each of the finitely many arities in that fragment, color increasing index tuples by the finite vector of truth values of the formulas occurring. Repeated applications of the infinite Ramsey theorem give an infinite subset on which all these vectors are constant. Interpret the finitely many $a_i$ in increasing-index order from that subset. This satisfies the finite indiscernibility requirements and distinctness, while the elementary diagram is satisfied by the named original structure. The compactness theorem gives a structure $N^{\ast }$ satisfying the whole theory.

Let $H$ be the closure of the $a_i$ under the Skolem functions, including nullary ones. It is elementary in $N^{\ast }$: whenever an existential formula with parameters from $H$ is true in $N^{\ast }$, its Skolem witness lies in $H$. This is the Tarski-Vaught test, whose proof is induction on formulas, using precisely this witness property for the existential step. Hence the reduct of $H$ is a model of $\mathrm{Th}(M)$.

For an order automorphism $\sigma :I\to I$, defineThis is well-defined. If two terms denote the same element, write their equality as a formula on the combined increasing tuple of their indices; indiscernibility preserves that formula after transport by $\sigma$. The same argument preserves every relation and function. Applying ${\sigma }^{-1}$ gives the inverse, so $\hat{\sigma }$ is an automorphism. Since all elements are terms in the generators, it is the unique automorphism of this Skolem expansion extending $a_i\mapsto a_{\sigma (i)}$. This proves the theorem.

One may require the indiscernibles to lie in any specified infinite sequence of the starting structure, or to satisfy additional finite-tuple properties holding along that sequence: the same finite satisfiability proof chooses its homogeneous subsequence there. This strengthened form is what the rank-domain construction of NFU uses. Uniqueness is asserted in the Skolem expansion, not for all automorphisms of its reduct.

For $A\subseteq {\omega }^{\omega }$, let the players alternately choose natural numbers, producing $x\in {\omega }^{\omega }$; I wins exactly when $x\in A$. A strategy assigns a move to each finite position at which its player moves. It is winning if every compatible completed play is won by that player. A game is determined when one player has a winning strategy. The axiom of determinacy is

We can prove determinacy for open and closed payoffs, including clopen payoffs; finite games are covered by backward induction. Here is the full open-payoff argument. For an open $A$, let $W_0$ consist of finite positions whose entire cylinder of continuations is contained in $A$. Recursively putand take unions at limits. Since positions form a set, this process reaches a fixed point $W$. More explicitly, a strict increase at each stage would assign a distinct position to each stage beyond the Hartogs bound of the position set, which is impossible; for natural-number moves the least newly added position in a fixed enumeration makes that assignment explicit.

If the initial position belongs to $W$, I can win. At an I-position first added at a successor stage, choose the least move to a position of smaller first-entry rank. At an II-position first added at a successor stage, every successor already has smaller rank. A play following this strategy cannot have an infinite strictly descending sequence of ordinal ranks, so reaches $W_0$ in finitely many steps; all its further continuations lie in $A$. If the initial position is outside $W$, II keeps the play outside $W$: at an I-position no successor is in $W$, and at an II-position at least one successor is outside $W$, so II chooses the least such move. The play never reaches a winning prefix. Since $A$ is open, membership in $A$ would have been certified by some finite prefix, so the resulting play is outside $A$. Thus every open game is determined. Applying this argument to the open complement of a closed payoff, with the players' objectives interchanged, proves closed determinacy too. The argument needs no choice of moves beyond taking the least available natural number.

To refute AD under AC, first use binary moves. There are $\mathfrak{c}=2^{{\aleph }_0}$ strategies for each player, since its positions form a countable set. Enumerate them as $({\sigma }_{\alpha }{)}_{\alpha <\mathfrak{c}}$ and $({\tau }_{\alpha }{)}_{\alpha <\mathfrak{c}}$. Each fixed strategy admits exactly $\mathfrak{c}$ compatible plays: the other player's arbitrary binary sequence determines the completed play injectively. Recursively choose a play $u_{\alpha }$ following ${\sigma }_{\alpha }$ and a play $v_{\alpha }$ following ${\tau }_{\alpha }$, each different from all earlier reservations and from each other. This is possible because at stage $\alpha$ fewer than $\mathfrak{c}$ plays have been reserved. No regularity assumption on $\mathfrak{c}$ is used: every ordinal $\alpha <\mathfrak{c}$ has cardinality below $\mathfrak{c}$, and doubling an infinite smaller cardinal does not reach $\mathfrak{c}$.

Set $B=\{v_{\alpha }:\alpha <\mathfrak{c}\}\subseteq 2^{\omega }$. Strategy ${\sigma }_{\alpha }$ loses on $u_{\alpha }\notin B$, while ${\tau }_{\alpha }$ loses on $v_{\alpha }\in B$. Thus this binary game is undetermined. Turn it into a natural-number game by declaring that the first player to play a number outside $\{0,1\}$ loses. Formally its I-payoff isA winning strategy in this game could not prescribe an illegal move after a compatible legal history, since the opponent could thereby win. Its restriction to legal histories would therefore give a winning binary strategy, contradicting the construction. Hence the choice diagonalization of an undetermined game provesThis does not contradict open or closed determinacy: the diagonal payoff has no such regularity requirement.