\documentclass[%
version=last,%
a5paper,
10pt,%
%headings=small,%
bibliography=totoc,%
twoside,%
reqno,%
parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
%titlepage=true,%
pagesize]
{scrartcl}

\usepackage{hfoldsty,url}
\usepackage[neverdecrease]{paralist}

\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item[]}
{\end{list}}

\usepackage{amsmath,amsthm,amssymb,mathrsfs,bm}
\usepackage[all]{xy}

\newcommand{\stnd}[1]{\mathbb{#1}}
\newcommand{\R}{\stnd R}
\newcommand{\C}{\stnd C}
\newcommand{\Q}{\stnd Q}
%\newcommand{\U}{\stnd U}
%\newcommand{\Ham}{\stnd H}
%\newcommand{\mi}{\mathrm i}
%\newcommand{\End}[1]{\operatorname{End}(#1)}
%\newcommand{\Der}[1]{\operatorname{Der}(#1)}
%\newcommand{\gn}[1]{\ulcorner#1\urcorner}

%\newcommand{\pos}[1]{#1^+}
%\newcommand{\Rp}{\pos{\R}}
\newcommand{\Z}{\stnd Z}
%\newcommand{\Qp}{\pos{\Q}}
\newcommand{\N}{\stnd N}
%\newcommand{\inv}{^{-1}}
%\newcommand{\cmpl}[1]{\overline{#1}}

\newcommand{\str}[1]{\mathfrak{#1}}
%\newcommand{\df}{\mathrm{DF}}
%\newcommand{\acf}{\mathrm{ACF}}
%\newcommand{\rcf}{\mathrm{RCF}}

\usepackage{upgreek}
%\newcommand{\vnn}{\upomega}

\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
%\newcommand{\Qq}[2][\alpha]{\mathsf Q_{#1}#2\;}
%\newcommand{\dee}[1][x]{\operatorname d_{#1}}

%\newcommand{\cof}[1]{\operatorname{cof}(#1)}
%\newcommand{\stp}[1]{\operatorname{st}(#1)}
%\newcommand{\pred}[1]{\operatorname{pred}(#1)}
\newcommand{\included}{\subseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\pincluded}{\subset}

%\newcommand{\Aut}[2]{\operatorname{Aut}(#1/#2)}
\newcommand{\Aut}[1][K]{\operatorname{Aut}(#1)}
%\newcommand{\Lin}[2]{\operatorname L_{#1}(#2)}
%\newcommand{\Def}[2]{\operatorname{Def}_{#2}(#1)}
%\newcommand{\St}[2]{\operatorname{St}_{#1}(#2)}
\newcommand{\St}[1][\Sn]{\operatorname S(#1)}
%\newcommand{\tp}[2]{\operatorname{tp}(#1/#2)}
%\newcommand{\symdiff}{\triangle}
\newcommand{\lto}{\rightarrow}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\powf}[1]{\mathscr P_{\upomega}(#1)}
\newcommand{\card}[1]{\lvert#1\rvert}
%\newcommand{\Sone}{\mathrm S_1}
%\newcommand{\Stwo}{\mathrm S_2}
%\newcommand{\RM}{\operatorname{RM}}
%\newcommand{\dM}{\operatorname{dM}}
%\newcommand{\st}{\operatorname{st}}

\let\oldleq\leq
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\setminus}{\smallsetminus}

\newtheorem{theorem}{Theorem}
\newtheorem*{corollary}{Corollary}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}
\newtheorem*{examples}{Examples}

\renewcommand{\theequation}{\fnsymbol{equation}}

\newcommand{\ess}{\mathscr S}
\newcommand{\VC}[1][\ess]{\operatorname{VC}(#1)}
\newcommand{\vc}[1][\ess]{\operatorname{vc}(#1)}

\newcommand{\entails}{\vdash}
\newcommand{\divides}{\mid}
\newcommand{\sig}{\mathscr S}
\newcommand{\Mod}{\mathbf{Mod}}
\newcommand{\mts}{\mathbf{Mod}/\mathord{\equiv}}
\newcommand{\Sn}{\operatorname{Sn}}
\newcommand{\Th}[1][\mathcal K]{\operatorname{Th}(#1)}
\newcommand{\I}[1]{\operatorname I(#1)}
\newcommand{\V}[1]{\operatorname V(#1)}

\begin{document}
\title{Compactness and choice}
\author{David Pierce}
\date{\today}
\publishers{Mathematics Department\\
Mimar Sinan Fine Arts University\\
Istanbul\\
\url{dpierce@msgsu.edu.tr}\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\maketitle

\begin{quote}
  These notes were originally prepared for the Istanbul Model Theory
  Seminar, October 11, 2012.
\end{quote}

\tableofcontents

\section{Compactness}\label{sect:compact}


The recent model-theory text of Tent and Ziegler \cite{MR2908005} introduces the Compactness Theorem as follows:\footnote{The
  quotation is taken from what is called an early second edition of
  the text.} 
\begin{quote}
Its name is motivated by the results in Section 4.2
which associate to each theory a certain compact topological space.

We call a theory $T$ \emph{finitely satisfiable} if every finite
subset of $T$ is consistent. 

\textbf{Theorem 2.2.1 \textnormal{(Compactness Theorem)}.}
\emph{Finitely satisfiable theories are consistent.}
\end{quote}
The section referred to begins:
\begin{quote}
  We now endow the set of types of a given theory with a topology. The
  Compactness Theorem 2.2.1 then translates into the statement that
  this topology is compact, whence its name.

Fix a theory $T$. An $n$-type is a maximal set of formulas
$p(x_1,\dots,x_n)$ consistent with $T$. We denote by $\mathrm S_n(T)$
the set of all $n$-types of $T$. We also write $\mathrm S(T)$ for
$\mathrm S_1(T)$.\footnote{$\mathrm S_0(T)$ can be considered as
the set of all complete extensions of $T$, up to equivalence.  [Footnote in source.]}
[\dots]

\textbf{Remark.} The Stone duality theorem asserts that the map
\begin{equation*}
X\mapsto \{C\mid C \text{ clopen subset of }X\}
\end{equation*}
yields an equivalence between the category of $0$-dimensional compact
spaces and the category of Boolean algebras. The inverse map assigns
to every Boolean algebra $\mathcal B$ its Stone space $\mathrm
S(\mathcal B)$, the set of all ultrafilters (see Exercise 1.2.4) of
$\mathcal B$. For more on Boolean 
algebras see [Givant and Halmos, \emph{Introduction to Boolean algebras}]. 
\end{quote}
Nothing is incorrect here.  But one might be led to believe that the
type spaces are \emph{by definition} Stone spaces of Boolean algebras
of logically equivalent formulas.  Since Stone spaces are always
compact, the type spaces are compact, and one might then conclude that
the Compactness Theorem follows.  But this would be a wrong
conclusion, since this theorem fails in second-order logic, and yet
Stone spaces of algebras of second-order formulas are still compact.

By the definition above, the type spaces are \emph{dense subspaces} of certain
Stone spaces.  The Compactness Theorem is that these subspaces are
compact.  Since Stone spaces are
Hausdorff, the type spaces must then be closed; therefore they are the
whole Stone spaces.  The point of this section to spell out the
details of these observations. 

Fix some logic $L$ that extends ordinary propositional logic: it could be a first-order logic, a second-order logic, or something else.  There is a class $\Mod$ of
structures interpreting $L$, and a set $\Sn$ of sentences of $L$.  If
$\sigma\in\Sn$, we can define
\begin{equation*}
  \Mod(\sigma)=\{\str A\in\Mod\colon\str A\models\sigma\}.
\end{equation*}
If $\str A\in\Mod$, we can define
\begin{equation*}
  \Th[\str A]=\{\sigma\in\Sn\colon\str A\models\sigma\}.
\end{equation*}
If $\Gamma\included\Sn$ and $\mathcal K\included\Mod$, we define
\begin{align*}
  \Mod(\Gamma)&=\bigcap_{\sigma\in\Gamma}\Mod[\sigma],&
\Th&=\bigcap_{\str A\in\mathcal K}\Th[\str A].
\end{align*}
The classes $\Mod(\Gamma)$ are \textbf{elementary classes} (though usually this term assumes a first-order logic); the classes $\Th$ are \textbf{theories.}
The functions $\Gamma\mapsto\Mod(\Gamma)$ and $\mathcal K\mapsto\Th$ determine a \emph{Galois correspondence} between the theories and the elementary classes.\footnote{Evry relation $R$ between sets or classes $A$ and $B$ induces a Galois correspondence between certain subsets of $A$ and of $B$.  In one direction this one-to-one, order-reversing correspondence is $X\mapsto\bigcap_{x\in X}\{y\in B\colon x\mathrel Ry\}$.  The original Galois correspondence is induced by the relation $\{(a,\sigma)\in K\times\Aut\colon\sigma(a)=a\}$, where $K$ is a field.}

Moreover, since
\begin{equation*}
  \Mod(\sigma\lor\tau)=\Mod(\sigma)\cup\Mod(\tau),
\end{equation*}
the elementary classes are the closed \emph{classes} of a \emph{topology} on $\Mod$
with basis consisting of the closed classes $\Mod(\sigma)$.

To say that the logic $L$ has a \textbf{compactness theorem} is to say that if $\Gamma\included\Sn$ and every finite subset of $\Gamma$ has a model, then $\Gamma$ itself has a model.  But this just means that if $\{\Mod(\sigma)\colon\sigma\in\Gamma\}$ has the Finite Intersection Property, then $\bigcap_{\sigma\in\Gamma}\Mod(\sigma)\neq\emptyset$: that is, $\Mod$ is compact as a topological space.

A similar Galois correspondence arises in algebraic geometry.  Suppose $L/K$
is a field-extension, and $X$ is an $n$-tuple of variables.  
If $f\in K[X]$, define
\begin{equation*}
  \V f=\{a\in L^n\colon f(a)=0\}.
\end{equation*}
If $a\in L^n$, define
\begin{equation*}
  \I a=\{f\in K[X]\colon f(a)=0\}.
\end{equation*}
If $A\included K[X]$ and $B\included L^n$, define
\begin{align*}
  \V A&=\bigcap_{f\in A}\V f,&
\I B&=\bigcap_{a\in B}\I a.
\end{align*}
The sets $\V A$ are \textbf{algebraic sets} over $K$.  The sets $\I B$ are radical ideals, but perhaps not every radical ideal of $K[X]$ is of this form, unless $L$ is algebraically closed.
In any case, there is a Galois correspondence between the algebraic sets and the radical ideals of the form $\I B$.
Moreover, since
\begin{equation*}
  \V{fg}=\V f\cup\V g,
\end{equation*}
the sets $\V f$ compose a basis of closed sets for a topology on
$L^n$, the \textbf{Zariski topology,} in which the closed sets are just the algebraic sets.  (Strictly, there is a Zariski topology for every subfield $K$ of $L$.)

The radical ideals $\I a$ are prime ideals; but not necessarily every prime ideal is of
this form, unless we have both that $L$ is algebraically closed, \emph{and} that the
transcendence-degree of $L/K$ is at least $n$.

Let us suppose this is so.  If we identify points $a$ and $b$ of $L^n$
if $\I a=\I b$, then the space becomes the \textbf{spectrum} of $K[X]$: the corresponding topological space whose underlying set consists of the prime ideals of $K[X]$.  The spectrum need not be
Hausdorff, since it is possible to have $\I a\pincluded\I b$, so that every closed set that contains $\I a$ contains $\I b$, but not conversely.\footnote{Of course the symbol $\pincluded$ here is to $\included$ as $<$ is to $\leq$.  Two errors of \TeX\ are that \texttt{$\backslash$subset} gives $\pincluded$ and not $\included$, and \texttt{$\backslash$leq} and \texttt{$\backslash$le} give $\oldleq$ and not $\leq$.}  The spectrum is however compact, since $L^n$ itself is compact.  Indeed, suppose a collection $\{\V f\colon
f\in A\}$ of basic closed subsets of $L^n$ has the Finite Intersection Property.  Since
\begin{equation*}
\V f\cap\V g=\V{f,g},
\end{equation*}
the set $A$ must generate a proper ideal of $K[X]$.  This ideal then is included in a prime
ideal $\I a$, so $a\in\bigcap_{f\in A}\V f$.

In the logical situation, we identify $\sigma$ and $\tau$ if
$\Mod(\sigma)=\Mod(\tau)$.  Then $\Sn$ becomes a Boolean algebra in
the usual way.  Every subset $\Th$ of $\Sn$ can now be understood as a \emph{filter} of this
algebra; and every subset $\Th[\str A]$, as an \emph{ultrafilter.}  (Note that $\Th[\emptyset]$ is the improper filter $\Sn$.)

However, not every ultrafilter of $\Sn$ need be the theory of some
structure.  For, such an ultrafilter is just a subset $\mathscr U$ with two properties:
\begin{compactenum}
  \item
Every finite subset of $\mathscr U$ has a model.
\item
If $\sigma\notin\mathscr U$, then $\lnot\sigma\in\mathscr U$.
\end{compactenum}
In the second-order logic for $(\N,1,x\mapsto x+1)$ with an additional constant-symbol $c$, the Peano axioms, together with the sentences $c\neq1$, $c\neq2$, and so on, are
included in a proper filter, and therefore an ultrafilter; but they
have no model.

In general, if two structures have the same theory, we may say the structures are \textbf{elementarily equivalent,} though again this term is usually reserved for first-order logic.  We may denote the relation by $\equiv$.  As in algebraic geometry, we may now consider $\mts$ instead of $\Mod$ itself.  The points of $\mts$ can be considered as the theories of structures; that is, we assume
\begin{equation*}
(\mts)=\{\Th[\str A]\colon\str A\in\Mod\}.
\end{equation*}
  Then $\mts$ is a subspace of the Stone space $\St$ of ultrafilters of $\Sn$.  We have seen that it may be a proper subspace.

However, it is a \emph{dense} subspace.  For, the basic closed subsets of $\St$ are the subsets $[\sigma]$, where $\sigma\in\Sn$ and
\begin{equation*}
[\sigma]=\{U\in\St\colon\sigma\in U\}.
\end{equation*}
(Here $U$ stands for ultrafilter.  Again, it is not necessarily the complete theory of some structure.  Therefore $\sigma\in U$ should not be written as $U\vdash\sigma$.)  Since
\begin{equation*}
[\lnot\sigma]=\St\setminus[\sigma],
\end{equation*}
the basic closed sets are also basic open sets.  If $U\in[\sigma]$, then $\sigma\neq\bot$, so $\sigma$ has a model $\str A$, and then $\Th[\str A]\in[\sigma]$.  Thus $\mts$ is dense in $\St$.

The Stone space of a Boolean algebra can be identified with the spectrum of the corresponding Boolean ring.  This is because prime ideals of a Boolean ring are maximal and are the duals of ultrafilters:  If $\mathfrak p$ is a prime ideal, then $\{\lnot x\colon x\in\mathfrak p\}$ is an ultrafilter.  This ultrafilter is also the complement of $\mathfrak p$.

In particular, Stone spaces are compact.  They are also Hausdorff, so that compact subspaces are closed.  Therefore the following are equivalent:
\begin{compactenum}
\item
$L$ has a compactness theorem,
\item\label{item:compact}
$\mts$ is compact,
\item\label{item:closed}
$\mts$ is a closed subspace of $\St$,
\item
$\mts$ is all of $\St$.
\end{compactenum}
In case $L$ is a first-order logic, we can give direct proofs of \eqref{item:compact} and \eqref{item:closed}.  (Poizat gives them both.)  We use \textbf{ultraproducts} in each case, and \textbf{\L o\'s's Theorem.}  Specifically, for every indexed family $(\str A_i\colon i\in\Omega)$ of structures in $\Mod$, for every ultrafilter $\mathscr U$ on $\Omega$, there is a structure $\str A$ such that, for all $\sigma$ in $\Sn$,
\begin{equation}\label{eqn:Los}
\str A\models\sigma\iff\{i\in\Omega\colon \str A_i\models\sigma\}\in\mathscr U.
\end{equation}
In fact, $\str A$ can be taken as the ultraproduct denoted by
\begin{equation*}
\prod_{i\in\Omega}\str A_i/\mathscr U;
\end{equation*}
and when one proves \eqref{eqn:Los}, one will allow $\sigma$ to have constants $(a_i\colon i\in\Omega)$ from $\prod_{i\in\Omega}A_i$, interpreted in each $\str A_i$ as $a_i$.  This does not really give a more general result, since we can now go back and assume those constants were part of the language from the beginning.


\begin{proof}[Proof of compactness.]
Write $[\sigma]$ for $\{T\in\mts\colon\sigma\in T\}$.
Suppose the collection $\{[\sigma]\colon\sigma\in B\}$ has the Finite Intersection Property.  Then it generates a proper filter of subsets of $\mts$, so it is included in an ultrafilter $\mathscr U$ on $\mts$.  If $T\in\mts$, then $T$ has a model $\str A_T$.
Let $\str A$ be the ultraproduct
\begin{equation*}
\prod_{T\in\mts}\str A_T/\mathscr U.
\end{equation*}
Suppose $\sigma\in B$, so that $[\sigma]\in\mathscr U$.  We have
\begin{equation*}
\{T\in\mts\colon\str A_T\models\sigma\}=\{T\in\mts\colon\sigma\in T\}=[\sigma].
\end{equation*}
By \L o\'s's Theorem, $\str A\models\sigma$, so $\Th[\str A]\in[\sigma]$.  So $\mts$ is compact.
\end{proof}

We can streamline the proof by using that an arbitrary topological
space is compact if and only if every ultrafilter on the underlying
set includes the filter of neighborhoods of a point.\footnote{The
  topological reference that I happen to have on hand is Willard \cite{MR0264581}.}  Then we can just
start the proof with $\mathscr U$.  

Moreover, using this criterion for compactness, we have a neat proof that the Stone space $\St[B]$ of an arbitrary Boolean algebra $B$ is compact:  For, if $\mathscr U$ is an ultrafilter on $\St[B]$, then it converges to the point
\begin{equation*}
\{x\in B\colon[x]\in\mathscr U\},
\end{equation*}
where $[x]=\{F\in\St[B]\colon x\in F\}$.  To see this, first note that the given `point' is indeed a filter $F$ on $B$, because the map $x\mapsto[x]$ from $B$ to $\pow{\St[B]}$ is a Boolean algebra homomorphism; $F$ is then an ultrafilter on $B$, because the homomorphism is injective.  Finally, if $F\in[x]$, this just means $x\in F$, so $[x]\in\mathscr U$.

In this last proof, we can replace $\St[B]$ with an arbitrary subset $\Omega$ of it.  We obtain that an ultrafilter $\mathscr U$ on $\Omega$ converges to the point
\begin{equation*}
\{x\in B\colon[x]\cap\Omega\in\mathscr U\}
\end{equation*}
of $\St[B]$.  The proof goes through as before, except that one needs to note also
\begin{equation*}
[x]\cap\Omega\notin\mathscr U\iff[\lnot x]\cap\Omega\in\mathscr U.
\end{equation*}
Now consider the case where $B$ is $\Sn$, and $\Omega$ is $\mts$.  The limit of $\mathscr U$ is precisely the theory of the ultraproduct $\str A$ that we found above.

Indeed, \L o\'s's Theorem can be understood as being the statement that the limit of $\mathscr U$ is indeed the theory of this structure.  In the original statement of the theorem, the indices are arbitrary; but we could treat the index of $\str A_i$ as $\Th[\str A_i]$ itself.  We may have wanted $\str A_i$ and $\str A_j$ to be the same structure, or just to have the same theory, even though $i\neq j$; but we can deal with this by expanding the language.

In short, seen in the right light, the Compactness Theorem of first-order logic and \L o\'s's Theorem are the same, except that the latter theorem actually gives you the desired model.

As noted, we can also show directly that $\mts$ is closed:

\begin{proof}[Proof of closedness.]
Let $U\in\St$.  Every element $\sigma$ of $U$ has a model $\str A_{\sigma}$.  Also, the subsets $\{\tau\colon\tau\leq\sigma\}$ of $U$ generate a proper filter, since
\begin{equation*}
\{\tau\colon\tau\leq\sigma\}\cap\{\rho\colon\rho\leq\sigma\}=\{\tau\colon\tau\leq\sigma\land\rho\}.
\end{equation*}
(Remember that $\tau\leq\sigma$ means every model of $\tau$ is a model of $\sigma$; we can write this also as $\tau\vdash\sigma$.)
Let $\mathscr U$ be an ultrafilter on $U$ that includes this filter.  Then the ultraproduct $\prod_{\sigma\in U}\str A_{\sigma}/\mathscr U$ is a model of $U$, since
\begin{equation*}
\{\tau\colon\str A_{\tau}\models\sigma\}\includes\{\tau\colon\tau\leq\sigma\}.\qedhere
\end{equation*}
\end{proof}


\section{Choice and Determinacy}\label{sect:AD}

In the first section, the Axiom of Choice was assumed.
The purpose of this section is to suggest that this Axiom is not
`obviously' or `intuitively' correct, since it contradicts another
set-theoretic axiom that might be considered `obviously' or
`intuitively' correct.  That axiom is the Axiom of Determinacy,
according to which, in certain \emph{games} of infinite length, one of
the players always has a winning strategy. 

We consider games with two players.  Hodges \cite{Hodges-Building}
calls these players $\forall$ and $\exists$, after Abelard and Eloise;
but I propose to call them simply $0$ and $1$, for notational
purposes.  A \textbf{game} that $0$ and $1$ can play is determined by
a partition $A_0\amalg A_1$ of the set ${}^{\upomega}2$ of binary
sequences on $\upomega$.  A particular \textbf{play} of the game can
be analyzed as a sequence of \textbf{rounds,} indexed by $\upomega$.
In round $m$, player $0$ chooses an element $a_{2m}$ of $2$; this is
the \textbf{move} of $0$ in this round.  Then player $1$ moves by
choosing an element $a_{2m+1}$ of $2$.  The play itself is then the
sequence $(a_n\colon n\in\upomega)$ or $a$, which is an element of
${}^{\upomega}2$.  The play is \textbf{won} by that player $e$ such
that $a\in A_e$; and then player $1-e$ has \textbf{lost.} 

Each player $e$ may use a \textbf{strategy,} namely a function $f_e$
from $\bigcup_{m\in\upomega}{}^{m+e}2$ to $2$.  (So $f_0$ assigns an
element of $2$ to each finite binary sequence; $f_1$ does this to
every \emph{nonempty} finite binary sequence.)  If both $f_0$ and $f_1$ are
chosen, then a play is determined, namely the sequence $(a_n\colon
n\in\upomega)$ given by 
\begin{align*}
a_{2m}&=f_0(a_1,a_3,\dots,a_{2m-1}),&
a_{2m+1}&=f_1(a_0,a_2,\dots,a_{2m}),
\end{align*}
or simply by
\begin{equation*}
a_{2m+e}=f_e(a_{1-e},a_{3-e},\dots,a_{2m-1+e}).
\end{equation*}
That is, $f_e$ determines the move of player $e$ from the previous
moves by the \emph{other} player.  The player's own previous moves
need not be formally considered, since they themselves were already
determined by the player's strategy and the other player's previous
moves. 

Suppose player $1-e$ has chosen strategy $f_{1-e}$.  For every $b$ in
${}^{\upomega}2$, player $e$ might choose a strategy $f_e$ that is
constant on each set ${}^{m+e}2$, having the value $b_m$ there.  The
resulting play will be $a$, where 
\begin{align*}
a_{2m+1-e}&=f_{1-e}(b_0,b_1,\dots,b_{m-e}),&a_{2m+e}=b_m.
\end{align*}
This shows that, for every choice of $f_{1-e}$, there are continuum-many plays that can result if player $1-e$ uses this strategy.

If, using a strategy $f_e$, player $e$ wins all plays of a game, then $f_e$ is a \textbf{winning} strategy for that game.  The game is \textbf{determined} if one of the players has a winning strategy.  The \textbf{Axiom of Determinacy} is that in every game, one of the players has a winning strategy: in other words, for every choice of the $A_e$, one of the following sentences of infinitary logic is true:
\begin{gather*}
	\Exists{x_0}\Forall{x_1}\Exists{x_2}\cdots\;(x_0,x_1,x_2,\dots)\in A_0,\\
	\Forall{x_0}\Exists{x_1}\Forall{x_2}\cdots\;(x_0,x_1,x_2,\dots)\in A_1.	
\end{gather*}
However, this Axiom is false under the assumption of the Axiom of
Choice, or more precisely under the assumption that the Continuum can
be well-ordered, so that there is a least ordinal, called
$2^{\upomega}$, whose cardinality is that of ${}^{\upomega}2$. 

Indeed, every ordinal is $\alpha+n$ for some unique limit ordinal
$\alpha$ and finite ordinal $n$.  Then $\alpha+n$ is even or odd,
according as $n$ is even or odd.  Assuming the Axiom of Choice, we can
list all possible strategies as
$(f^{\alpha}\colon\alpha<2^{\upomega})$, where $f^{\alpha}$ will be a
strategy for $e$ if and only if $\alpha+e$ is even.   

We shall now define a list $(a^{\alpha}\colon\alpha<2^{\upomega})$ of
possible plays (that is, elements of ${}^{\upomega}2$) so that,  
\begin{compactitem}
\item
for all $\alpha$, if $\alpha+e$ is even, then $e$ can use strategy
$f^{\alpha}$ for the play $a^{\alpha}$; that is, for all $m$ in $\upomega$,
\begin{equation*}
a^{\alpha}_{2m+e}=f^{\alpha}(a^{\alpha}_{1-e},a^{\alpha}_{3-e},\dots,a^{\alpha}_{2m-1+e});
\end{equation*}
\item
 $a^{\alpha}\neq a^{\beta}$ for all distinct $\alpha$ and $\beta$ such
  that $\alpha+\beta$ is odd.
\end{compactitem}
We do this recursively.  If $(a^{\beta}\colon\beta<\alpha)$ has
been defined, and $\alpha<2^{\upomega}$, then since there are
continuum-many plays in which the strategy $f^{\alpha}$ is used, one
of them, to be called $a^{\alpha}$, is not among those $a^{\beta}$
such that $\beta<\alpha$ and $\beta+\alpha$ is odd. 

Since, if $\alpha+e$ is even, player $e$ can use strategy $f^{\alpha}$
for the play $a^{\alpha}$, this means player $1-e$ has \emph{some}
strategy that, with $f^{\alpha}$, determines $a^{\alpha}$.    That is,
player $1-e$ can win against strategy $f^{\alpha}$, provided
$a^{\alpha}\in A_{1-e}$.  We now choose the partition of
${}^{\upomega}2$ so that  
\begin{align*}
\{a^{\alpha}\colon\alpha\text{ even}\}&\included A_1,&
\{a^{\alpha}\colon\alpha\text{ odd}\}&\included A_0.
\end{align*}
Then neither player has a winning strategy for the game: the game is
not determined. 


%\bibliographystyle{amsplain}
%\bibliography{../../../Dropbox/Public/references}
%\bibliography{../references}

\def\rasp{\leavevmode\raise.45ex\hbox{$\rhook$}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{1}

\bibitem{Hodges-Building}
Wilfrid Hodges, \emph{Building models by games}, Dover Publications, Mineola,
  New York, 2006, original publication, 1985. \MR{MR812274 (87h:03045)}

\bibitem{MR2908005}
Katrin Tent and Martin Ziegler, \emph{A course in model theory}, Lecture Notes
  in Logic, vol.~40, Association for Symbolic Logic, La Jolla, CA, 2012.
  \MR{2908005}

\bibitem{MR0264581}
Stephen Willard, \emph{General topology}, Addison-Wesley Publishing Co.,
  Reading, Mass.-London-Don Mills, Ont., 1970. \MR{MR0264581 (41 \#9173)}

\end{thebibliography}


\end{document}