84
ANUJ DAWAR AND YURI GUREVICH
ꢀ
ꢀ
for all ꢁ-length strings b
b
c ≺ b such that a ∈ R , and therefore, a ∈ R
c
ꢀ
such that c ≺ b .
ꢂ
We also have, from Gale and Stewart [10], a set W of ꢁ-length strings
such that if W is the set of winning strings for P-I in an ꢁ-length string
construction game, then the game is indeterminate. We next see that this
yields a structure (albeit an uncountable one), where the game we have
defined is indeterminate.
Let A be a structure whose universe A is the union of three disjoint sets,
ꢁ
O = {0} × ꢁ, P = {1} × 2, and a singleton {a}. A interprets two binary
relations: ꢃ= {((0, m), (0, n)) | m < n}, the standard ordering on O; and
E = {((0, m), (1, s)) | s(m) = 1}. A also interprets a unary relation symbol
S as the subset of P encoding the undetermined winning set W of Gale and
Stewart.
Now, it is easy to construct the desired first order definable operators Φ0
and Φ . It is easiest to think of them as defining, simultaneously, a pair of
1
unary relations R and S (as in the proof of Theorem 5). If there is an element
of O that is not in S, let x be the least such element (according to the order ꢃ)
and let Φ (R, S) = (R, S ∪ {x}) and Φ (R, S) = (R ∪ {x}, S ∪ {x}); if
0
1
O ⊆ S and W (p ), where p ∈ P is the element (1, {m | (0, m) ∈ R}), then
R
R
Φ (R, S) = Φ (R, S) = (R ∪ {a}, S); otherwise Φ (R, S) = Φ (R, S) =
0
1
0
1
(
R, S).
It can be easily checked that the induction of Φ and Φ on A closes at
0
1
ꢁ
+ 1, and neither P-I nor P-II has a winning strategy on a.
This leaves open the question of whether the game is determined on every
countable structure. What we can show is that there is a pair of formulas
even first order formulas) for which determinacy of the string construction
(
game is independent of ZFC. We establish this below.
Theorem 8. There are two first order definable operators Φ and Φ such
0
1
that the determinacy of the game they define on (ꢁ, <) is independent of ZFC.
Proof. We first define a pair of operators which have the required property
on the structure of arithmetic (ꢁ, <, +, ×), and then note at the end how
they can be modified to obtain operators that work on the order (ꢁ, <).
1
ꢁ
We use the fact that there is a Σ subset W of 2 such that the question
1
whether P-I has a winning strategy to construct an ꢁ-length string in W is
independent of ZFC (see [17, 6A.12 and 6G.7]).
1
Since W is Σ , there is a first order formula ꢅ(X, R), where X and R are
1
unary relation symbols, such that (ꢁ, <, +, ×, R) |= ∃Xꢅ if, and only if,
b ∈ W , where b : ꢁ → {0, 1} is the string given by b (n) = 1 if, and only
R
R
R
if, n ∈ R.
We define the operators Φ and Φ so that they construct three relations X,
0
1
R and T, where T is only changed at the last stage, and 0 is included in
T if, and only if, (ꢁ, <, +, ×) satisfies ꢅ(X, R). R is constructed in the
first ꢁ moves of the game, using an auxiliary relation S. In the next ꢁ