\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{\.Istanbul Model Theory Seminar Notes, Fall 2012}
\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/}}

\uppertitleback{We are reading
\begin{quote}\centering
  Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald
  McPherson, and Sergei Starchenko, \emph{Vapnik--Chervonenkis Density in
  Some Theories Without the Independence Property, I},
  arXiv:1109.5438v1  [math.LO], \cite{2011arXiv1109.5438A}.
\end{quote}
These notes are based on:
\begin{compactenum}
\item
Ayhan G\"unayd\i n's talk on October 4, 2012, in which all theorems in
but Theorem~\ref{thm:IP-equiv} in the main text---\S\S\ref{sect:comb}
and \ref{sect:logic}---were stated; 
\item
my own preparations to speak on October 11;
\item
my experience in speaking then (I discussed \S\ref{sect:compact} first, and
then garbled the proof of Theorem~\ref{thm:SS} in
\S\ref{sect:comb}---the notes were OK, my use of them not);
\item
a discussion of the role of the Axiom of Choice in mathematics: \S\ref{sect:AD} is meant to suggest that paying attention to the use of this Axiom may be worthwhile.
\end{compactenum}}

\lowertitleback{\tableofcontents}

\maketitle

\section{Combinatorics}\label{sect:comb}

\begin{definition}
Let $\ess$ be a \textbf{set system,} that is, a set of sets.  Its
\textbf{Vapnik--Chervonenkis dimension,} denoted by
\begin{equation*}
\VC,
\end{equation*}
is the size of the largest finite set $A$ such that
\begin{equation*}
\{A\cap S\colon S\in\ess\}=\pow A.
\end{equation*}
Here $\ess$ is said to \textbf{shatter} the set $A$.  If there is no
bound on the size of $A$, then $\VC=\infty$. 
\end{definition}

There is no need to give a name to a set $X$ such that
$\ess\included\pow X$.  This set could just be $\bigcup\ess$.  Any set
that is shattered by $\ess$ is a subset of $\bigcup\ess$. 

\begin{examples}\mbox{}
\begin{asparaenum}
\item
Let $\ess$ be the set of half-lines $\{x\in\R\colon ax+b>0\}$.
  Then $\ess$ shatters $\{0,1\}$ (and every other pair of real numbers), but no set of size $3$.  Thus $\VC=2$.  One should note that the elements of $\ess$ are defined by two parameters.
\item
Let $\ess$ be the set of half-planes $\{(x,y)\in\R^2\colon
ax+by+c>0\}$ (defined by three parameters).  Then $\ess$ shatters
$\{(0,0),(0,1),(1,0)\}$ (and every other set of three non-collinear
points of $\R^2$), but no set of four points, so $\VC=3$. 
\item
The set of rectangles $[a,b]\times[c,d]$ shatters
$\{(\pm1,0),(0,\pm1)\}$, so it has dimension at least $4$. 
\end{asparaenum}
\end{examples}

\begin{definition}
Given the set-system $\ess$ and a set $A$, we define
\begin{equation*}
A\cap\ess=\{A\cap S\colon S\in\ess\}
\end{equation*}
If also $n\in\upomega$, we define
\begin{equation*}
\uppi_{\ess}(n)=\max\{\card{A\cap\ess}\colon\card A=n\}.
\end{equation*}
\end{definition}

Now we have that
\begin{align*}
\VC
&=\max\{\card A\colon\card{A\cap\ess}=2^{\card A}\}\\
&=\max\{n\in\upomega\colon\uppi_{\ess}(n)=2^n\}.
\end{align*}

The following is apparently due to Sauer and Shelah independently.
The proof is adapted from van den Dries \cite{MR1633348}. 

\begin{theorem}\label{thm:SS}
If $\VC=d$ and $d\leq n$, then
\begin{equation*}
\uppi_{\ess}(n)\leq\sum_{i=0}^d\binom ni.
\end{equation*}
\end{theorem}

\begin{proof}
We show that, if the last inequality fails, then $A$ itself has a subset larger than $d$ that is shattered by $\ess$, so $\VC>d$.  That is, under the hypotheses
\begin{align*}
\card A&=n,
&\card{A\cap\ess}&>\sum_{i=0}^d\binom ni
\end{align*} 
(which themselves entail $d<n$), the set $A$ has a subset $B$ such that
\begin{align*}
\card B&=d+1,& B\cap\ess=\pow B.
\end{align*}
This is easily true if $d=0$ or $d=n-1$.  Indeed, in case $d=0$, the set $A\cap\ess$ has an element $b$, so we can let $B=\{b\}$.  In case $d=n-1$, then
\begin{equation*}
\card{A\cap\ess}\geq\sum_{i=0}^{n-1}\binom ni+1=2^n,
\end{equation*}
so $A$ itself is the desired set $B$.

We continue by induction on $n$.  We have just treated the case where $n=d+1$.  Suppose the claim holds when $n=m$, but now
\begin{align*}
\card A&=m+1,
&\card{A\cap\ess}&>\sum_{i=0}^d\binom{m+1}i.
\end{align*}
We may assume $0<d<m$ (since we have taken care of the other cases).  Let $b\in A$.  If $(A\setminus\{b\})\cap\ess$ is so large that
\begin{equation*}
\card{(A\setminus\{b\})\cap\ess}>\sum_{i=0}^d\binom mi,
\end{equation*}
then by inductive hypothesis we are done.  So suppose $(A\setminus\{b\})\cap\ess$ is not so large.  We make the analysis
\begin{equation*}
(A\setminus\{b\})\cap\ess=\mathscr A_1\cup\mathscr A_2,
\end{equation*}
a disjoint union, where
\begin{equation*}
X\in\mathscr A_2\iff X\in A\cap\ess\And X\cup\{b\}\in A\cap\ess.
\end{equation*}
That is, $\mathscr A_2$ consists of the elements of $(A\setminus\{b\})\cap\ess$ that have two pre-images in $A\cap\ess$ under the map $Y\mapsto Y\setminus\{b\}$; but each element of $\mathscr A_1$ has one pre-image.
Then we compute
\begin{align*}
	\card{A\cap\ess}
	&=\card{\mathscr A_1}+2\cdot\card{\mathscr A_2}\\
	&=\card{\mathscr A_1}+\card{\mathscr A_2}+\card{\mathscr A_2}\\
	&=\card{(A\setminus\{b\})\cap\ess}+\card{\mathscr A_2},
	\end{align*}
	so that
\begin{align*}
\card{\mathscr A_2}
&=\card{A\cap\ess}-\card{(A\setminus\{b\})\cap\ess}\\
	&\geq\sum_{i=0}^d\left(\binom{m+1}i-\binom mi\right)\\
	&=\sum_{i=1}^d\binom m{i-1}\\
	&=\sum_{i=0}^{d-1}\binom mi.
	\end{align*}
Now, since
\begin{equation*}
\card{(A\setminus\{b\})\cap\ess}
\geq\card{\mathscr A_2},
\end{equation*}
we have by inductive hypothesis that $A\setminus\{b\}$ must have a subset $C$ such that
\begin{align*}
\card C&=d,&C\cap\ess=\pow C.
\end{align*}
But we need, and have, more than this.  We may assume
\begin{equation*}
C\cap\mathscr A_2=\pow C.
\end{equation*}
But each element of this set has two pre-images in $(C\cup\{b\})\cap\ess$ under $Y\mapsto Y\setminus\{b\}$.  That is, if $X\in C\cap\mathscr A_2$, then $(C\cup\{b\})\cap\ess$ contains both $X$ and $X\cup\{b\}$.
This ensures $(C\cup\{b\})\cap\ess=\pow{C\cup\{b\}}$, so we are done.
\end{proof}

We can compute
\begin{equation*}
\sum_{i=0}^d\binom ni=\frac1{d!}\cdot n^d+\text{lower terms}.
\end{equation*}
So if $\VC$ is finite, $\uppi_{\ess}(n)$ is eventually bounded by a polynomial in $n$ of degree no greater than $\VC$.

\begin{definition}
If $\VC$ is finite, then the \textbf{Vapnik--Chervonenkis density} of $\ess$ is
\begin{equation*}
\limsup_{n\to\infty}\frac{\log\uppi_{\ess}(n)}{\log n}.
\end{equation*}
This can be denoted by
\begin{equation*}
\vc.
\end{equation*}
\end{definition}
Then $\vc\leq\VC$.

\section{Logic}\label{sect:logic}

The examples above are of
the form where 
\begin{equation}\label{eqn:S}
\ess=\{\phi^{\str M}(x,b)\colon b\in M_y\}
\end{equation}
for some formula $\phi(x,y)$ in the signature of a structure $\str M$.
Here $x$ and $y$ are tuples of variables, and $M_y$ is the set of
tuples of elements of $M$ indexed by the entries in $y$, so
that\footnote{This notation readily allows $\str M$ to have several
  sorts.  If $x=(x_i\colon i<m)$, then elements of $M_x$ are of the
  form $(a_i\colon i<m)$, where $a_i$ belongs to the sort that $x_i$
  ranges over.  For the set $\phi^{\str M}(x,b)$, the paper writes
  $\phi^{\str M}(M_x,b)$, but this seems needless, unless one wants to
  be able to write $\phi^{\str M}(A,b)$ for $A\cap\phi^{\str
    M}(x,b)$.} 
\begin{equation*}
\phi^{\str M}(x,b)=\{a\in M_x\colon\str M\models\phi(a,b)\}.
\end{equation*}

\begin{definition}
When $\ess$ is as in \eqref{eqn:S}, we may write $\phi$ in place of $\ess$ in compound symbols; so $\VC[\phi]$ means $\VC$, and so on.
\end{definition}

The set-system $\ess$ as in \eqref{eqn:S} shatters a subset $A$ of $M_x$ if and only if, for all
subsets $C$ of $A$, there is an element $b_C$ of $M_y$ such that 
\begin{equation*}
C=A\cap\phi^{\str M}(x,b_C),
\end{equation*}
that is, for all $a$ in $A$,
\begin{equation*}
a\in C\iff\str M\models\phi(a,b_C).
\end{equation*}
If $\ess$ shatters all finite subsets of $M_x$, this is equivalent to
the model-theoretic property of $\phi$ called \emph{NIP,} defined as follows.

\begin{definition}
Let $T$ be a complete theory.  We say that $\phi(x,y)$ has the
\textbf{Independence Property} in $T$ if for all $n$ in $\upomega$, 
\begin{equation*}
T\entails\Exists{(x_i\colon i<n)}\Exists{(y_W\colon W\in\pow
  n)}\bigwedge_{i<n}\bigwedge_{W\included n}\phi^{i\in W}(x_i,y_W), 
\end{equation*}
where 
\begin{equation*}
\phi^{i\in W}\mathrel{\text{is}}\begin{cases}
	\phi,&\text{ if }i\in W,\\
	\lnot\phi,&\text{ if }i\notin W.
\end{cases}
\end{equation*}
If $\phi(x,y)$ does \emph{not} have the Independence Property, it has
\textbf{NIP.}
The theory $T$ itself has the Independence Property, if some formula has the Independence Property in $T$.  Otherwise $T$ is NIP.
\end{definition}

Some sources may reverse the roles of $x$ and $y$ in the definition.  This does not matter, as the definition is symmetric, by the next theorem below.

\begin{examples}
These are from Poizat \cite{MR1757487}.
\begin{asparaenum}
\item
If $T$ is the theory of $(\N,{}\divides{})$, then $x\divides y$ has the independence property in $T$.  For, if $(p_i\colon i\in\upomega)$ is the sequence of primes, and for all finite subsets $W$ of $\upomega$, if
\begin{equation*}
b_W=\prod_{i\in W}p_i,
\end{equation*}
then for all $i$ in $\upomega$, for all $W$ in $\powf{\upomega}$ (the set of finite subsets of $\upomega$),
\begin{equation*}
T\entails p_i\divides b_W\iff i\in W.
\end{equation*}
\item
If $T$ is the theory of an infinite Boolean algebra, then $x\leq y$ has the independence property in $T$.  For, in every model of $T$, there is a sequence $(a_i\colon i\in\upomega)$ of elements such that
\begin{equation*}
i\neq j\implies a_i\wedge a_j=0.
\end{equation*}
If $W\in\powf{\upomega}$, let
\begin{equation*}
b_W=\bigvee_{i\in W}a_i.
\end{equation*}
Then
\begin{equation*}
T\entails a_i\leq b_W\iff i\in W.
\end{equation*}
\end{asparaenum}
\end{examples}

\begin{theorem}
The definition of the Independence Property is symmetric in $x$ and $y$. 
\end{theorem}

\begin{proof}
Suppose $\phi(x,y)$ has the Independence Property in $T$.  Then for
all $n$ in $\upomega$,
\begin{equation*}
T\entails\Exists{(x_W\colon W\included n)}\Exists{(y_{\mathcal
    V}\colon\mathcal V\included\pow n)}\bigwedge_{W\subset
  n}\bigwedge_{\mathcal V\included\pow n}\phi^{W\in\mathcal
  V}(x_W,y_{\mathcal V}). 
\end{equation*}
Now we can take away all but $n$ of the $\mathcal V$.  In particular,
if $i<n$, we let 
\begin{equation*}
\mathcal V(i)=\{W\in\pow n\colon i\in W\}.
\end{equation*}
Now we take away all of the $\mathcal V$, except for the $\mathcal
V(i)$; and we can use $i$ in place of $\mathcal V(i)$ as an index.
This leaves us with 
\begin{equation*}
T\entails\Exists{(x_W\colon W\in\pow n)}\Exists{(y_i\colon
  i<n)}\bigwedge_{W\in\pow n}\bigwedge_{i<n}\phi^{i\in
  W}(x_W,y_i).\qedhere 
\end{equation*}
\end{proof}

The Independence Property is a special case of a more general property:

\begin{definition}
We say that $\phi(x,y)$ has the \textbf{Order Property} in $T$ if for all $n$ in $\upomega$,
\begin{equation*}
T\entails\Exists{(x_i\colon i<n)}\Exists{(y_j\colon j<n)}\bigwedge_{i<n}\bigwedge_{j<n}\phi^{i<j}(x_i,y_j).
\end{equation*}
\end{definition}

In the definition, by re-indexing, we can replace the condition $i<j$
with $i\leq j$ or $i\geq j$.  In particular, the definition is
symmetric in $x$ and $y$.  Also we have the following. 

\begin{theorem}
If $\phi(x,y)$ has the Independence Property in $T$, then it has the
Order Property in $T$. 
\end{theorem}

\begin{proof}
In the definition of the Independence Property, throw out all $W$ except those that are elements of $n$.
\end{proof}

\begin{example}
If $T$ is the theory of $(\Q,<)$, then $x<y$ has the Order Property in
$T$, but not the Independence Property.  (Moreover, no formula has the
Independence Property in $T$; but this would take work to prove.) 
\end{example}

Another way to define the Independence Property is given by the
following.  We shall use it to prove the theorem after this one.  (The
development is based on Poizat 
\cite{MR817208,MR1757487}.)  

\begin{theorem}\label{thm:IP-equiv}
The following are equivalent.
\begin{compactenum}
 \item\label{item:IP}
The formula $\phi(x,y)$ has the Independence Property in $T$.
\item\label{item:cof}
In some model $\str N$ of $T$, there is an indiscernible sequence
$(a_n\colon n\in\upomega)$ and an element $b$ such that both
$\{n\in\upomega\colon\str N\models\phi(a_n,b)\}$ and
$\{n\in\upomega\colon\str N\models\lnot\phi(a_n,b)\}$ are cofinal in
$\upomega$. 
\item\label{item:2}
In some model $\str N$ of $T$, there is an indiscernible
sequence $(a_n\colon n\in\upomega)$ and an element $b$ such that, for
all $n$ in $\upomega$, 
\begin{equation*}
\str N\models\phi^{2\divides n}(a_n,b).
\end{equation*}
\end{compactenum}
\end{theorem}

\begin{proof}
Condition \eqref{item:2} is a special case of \eqref{item:cof}, that is, \eqref{item:2}$\Rightarrow$\eqref{item:cof}; the converse follows by throwing out terms of the indiscernible sequence and re-indexing.

\eqref{item:2}$\Rightarrow$\eqref{item:IP}.  For every $n$ in $\upomega$, for every $W$ in
$\pow n$, there is $\sigma$ in ${}^n\upomega$ such that 
\begin{align*}
\sigma(0)&<\dots<\sigma(n-1),&2\divides\sigma(i)\iff i\in W.
\end{align*}
By \eqref{item:2} then, we have
\begin{equation*}
\str N\models\Exists y\bigwedge_{i<n}\phi^{i\in W}(a_{\sigma(i)},y),
\end{equation*}
so by indiscernibility
\begin{equation*}
\str N\models\Exists y\bigwedge_{i<n}\phi^{i\in W}(a_i,y).
\end{equation*}

\eqref{item:IP}$\Rightarrow$\eqref{item:2}.  Under the hypothesis, by Compactness, in some
model $\str M$ of $T$, there are collections $(a'_n\colon
n\in\upomega)$ and $(b_W\colon W\in\pow{\upomega})$ such that 
\begin{equation*}
\str M\models\phi(a'_n,b_W)\iff n\in W.
\end{equation*}
Let $\str N$ be an elementary extension of $\str M$, and let $\mathscr
U$ be an ultrafilter on $\upomega$.  For every subset $A$ of $N$, the
set of formulas $\psi(x)$ over $M\cup A$ such that 
\begin{equation*}
\{n\in\upomega\colon\str N\models\psi(a'_n)\}\in\mathscr U
\end{equation*}
is a complete type; for,
\begin{compactitem}
\item
it is closed under conjunction (since $\mathscr U$ is closed under intersection),
\item
it contains $\psi(x)$ or $\lnot\psi(x)$, for every $\psi(x)$ over $M\cup A$ (since $\mathscr U$ contains $W$ or $\upomega\setminus W$, for every $W$ in $\pow{\upomega}$),
\item
every element is satisfied in $\str N$.
\end{compactitem}
Assume further that $\mathscr U$ is nonprincipal, so it contains all cofinite subsets of $\upomega$.  Then the type just defined is not realized by any element of $M\cup A$.  (If it were realized by $c$ in this set, then it would contain the formula $x=c$, and then $c=a'_n$ for some $n$.  This $n$ would be unique, since all of the $a'_m$ are distinct; but then $\{n\}\in\mathscr U$.)

Assume further that $\str N$ is $\card M$-saturated.  We can now obtain a sequence $(a_n\colon n\in\upomega)$ from $\str N$ such that for all $n$ in $\upomega$, for all formulas $\psi(x)$ over $M\cup\{a_i\colon i<n\}$,
\begin{equation*}
\str N\models\psi(a_n)\iff\{k\in\upomega\colon\str N\models\psi(a'_k)\}\in\mathscr U.
\end{equation*}
Indeed, $a_n$ just realizes the appropriate complete type over $M\cup\{a_i\colon i<n\}$.  Also $a_n$ does not belong to this set.  Moreover, each $a_{n+i}$ realizes this type.
Therefore the sequence $(a_n\colon n\in\upomega)$ is indiscernible over $M$.

Suppose for some $\psi$ over $M$ we have
\begin{equation*}
\str N\models\lnot\psi(a_0,\dots,a_n).
\end{equation*}
Then by definition of $a_n$ we must have, for some $k$ in $\upomega$,
\begin{equation*}
\str N\models\lnot\psi(a_0,\dots,a_{n-1},a'_k).
\end{equation*}
Continuing in this matter, we obtain a sequence $\sigma$ on $n+1$ such that
\begin{equation*}
\str N\models\lnot\psi(a'_{\sigma(0)},\dots,a'_{\sigma(n)}).
\end{equation*}
Now consider the contrapositive of this result.  By hypothesis, for all $m$ in $\upomega$, for all sequences $\sigma$ on $2m$, we have
\begin{equation*}
\str N\models\Exists y\bigwedge_{i\divides2m}\phi^{2\divides i}(a'_{\sigma(i)},y).
\end{equation*}
Therefore
\begin{equation*}
\str N\models\Exists y\bigwedge_{i\divides2m}\phi^{2\divides i}(a_i,y).
\end{equation*}
By saturation, $b$ exists as desired.
\end{proof}

Condition \eqref{item:cof} in the theorem is that $\phi(x,b)$
\textbf{splits} the indiscernible sequence $(a_n\colon
n\in\upomega)$. 

\begin{theorem}
If a complete theory $T$ has the Independence Property, then a formula
$\phi(x,y)$, where $\card x=1$, has the Independence Property in $T$. 
\end{theorem}

\begin{proof}
Let $\card x=1$, and suppose $y$ is minimal such that some formula
$\phi((x,y),z)$ has the Independence Property in $T$.  By the symmetry
of this property, and the last theorem, there is a model $\str M$ of
$T$ and an indiscernible sequence $(a_n\colon n\in\upomega)$ and
$(b,c)$ from $\str M$ such that 
\begin{equation*}
\str M\models\phi^{2\divides n}(b,c,a_n).
\end{equation*}
We shall show that $(a_n\colon n\in\upomega)$ is indiscernible over
$c$.  In that case, by the last theorem, $\phi(x,(y,z))$ has the
Independence Property in $T$. 

We use induction.  Let $T_m$ be the theory that entails:
\begin{compactitem}
\item
$T$ itself;
\item
the indiscernibility of $(a_n\colon n\in\upomega)$;
\item
the sentences $\phi^{2\divides n}(b,c,a_n)$;
\item
the sentences
\begin{equation*}
\theta(c,a_{\sigma(0)},\dots,a_{\sigma(m-1)})\liff\theta(c,a_0,\dots,a_{m-1}),
\end{equation*}
where $\sigma(0)<\dots<\sigma(m-1)$ (and $\theta$ has no parameters). 
\end{compactitem}
So $T_0\included T_1\included\dots$
We want to show that $\bigcup_{m\in\upomega}T_m$ is consistent.

By hypothesis, $T_0$ is consistent.  

Suppose $T_m$ is consistent.
Supposing
$\sigma\in{}^m\upomega$, and $\sigma(0)<\dots<\sigma(m-1)$, we let
\begin{equation*}
a_{\sigma}=(a_{\sigma(0)},\dots,a_{\sigma(m-1)}).
\end{equation*}
Then
$\bigl((a_{\sigma},a_n)\colon\sigma(m-1)<n<\upomega\bigr)$ 
is an indiscernible sequence. 
Therefore, by the minimality of $y$, no formula
$\psi(c,a_{\sigma},y)$ splits the sequence $(a_n\colon n\in\upomega)$, but either all $a_n$ for $n$ sufficiently large satisfy the formula, or all such $a_n$ satisfy its negation.  

Therefore,
by throwing out some indices (always in adjacent pairs, to maintain parity), we
may assume that $\psi^{\str M}(c,a_{\sigma},y)$ includes the whole set
$\{a_n\colon\sigma(m-1)<n\}$, or else $\lnot\psi^{\str M}(c,a_{\sigma},y)$ does.  

By Compactness then, there is a
complete type $p_{\sigma}$ in $(z_0,\dots,z_m)$ over $c$ that is realized by each
$(a_{\sigma},a_n)$ such that $\sigma(m-1)<n$. 

Then again by Compactness, in some sufficiently saturated model of $T_m$, there must be some $a_{\upomega}$ such that
the sequence $(a_n\colon n<\upomega+1)$ is
indiscernible, and for each $\sigma$ as above,
$(a_{\sigma},a_{\upomega})$ realizes $p_{\sigma}$. 

Suppose $\sigma_k$ are chosen in ${}^m\upomega$ for each $k$ in
$\upomega$, so that 
\begin{equation*}
  \sigma_0(0)<\dots<\sigma_0(m-1)<\sigma_1(0)<\cdots
\end{equation*}
Then the sequence $\bigl((a_{\sigma_n},a_{\upomega})\colon
n\in\upomega)\bigr)$ is indiscernible.  Again by minimality of $y$, no formula
$\theta(c,z_0,\dots,z_m)$ can split the sequence.  Therefore, by
throwing out some indices again, we may assume that either
$\theta(c,z_0,\dots,z_m)$ or $\lnot\theta(c,z_0,\dots,z_m)$ is, for
all $\sigma$, contained in $p_{\sigma}$.

Then all of the $p_{\sigma}$ are the same type.
Thus $T_{m+1}$ is consistent.  This completes the induction and the proof.
\end{proof}

We can now conclude every weakly o-minimal theory (that is, the theory of a linearly ordered structure in which the definable singulary relations are finite unions of convex sets) is NIP.  In such a theory, we aim to show
\begin{equation*}
\vc[\phi(x,y)]\leq\card y.
\end{equation*}
If, instead, the theory is that of $\Q_p$, we aim to show
\begin{equation*}
\vc[\phi(x,y)]\leq2\cdot\card y-1.
\end{equation*}

\appendix

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

The recent model-theory text of Tent and Ziegler \cite{MR2908005} introduces the Compactness Theorem as follows:
\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.}\footnote{The quotation is taken from what is called an early second edition, distributed to the Seminar by email as a \url{pdf} file.}
\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 is 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 these notes, the Axiom of Choice has been tacitly 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 ${}^{\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_e$ assigns to each finite binary sequence an element of $2$; but $f_1$ need make no assignment to the empty 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, $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 the original ordinal is even or odd, according as $n$ is even or odd.
Now 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 can then 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,
\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
for all distinct $\alpha$ and $\beta$, $a^{\alpha}\neq a^{\beta}$, at least if $\alpha+\beta$ is odd.
\end{compactitem}
Indeed, we can proceed 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}$.
Therefore, if we now choose the partition of ${}^{\upomega}2$ so that
\begin{align*}
\{a^{\alpha}\colon\alpha+e\text{ even}\}\included A_{1-e},
\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{2011arXiv1109.5438A}
M.~{Aschenbrenner}, A.~{Dolich}, D.~{Haskell}, D.~{Macpherson}, and
  S.~{Starchenko}, \emph{{Vapnik--{C}hervonenkis density in some theories
  without the independence property, I}}, ArXiv e-prints (2011).

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

\bibitem{MR817208}
Bruno Poizat, \emph{Cours de th\'eorie des mod\`eles}, Bruno Poizat, Lyon,
  1985, Une introduction {\`a} la logique math{\'e}matique contemporaine. [An
  introduction to contemporary mathematical logic]. \MR{817208 (87f:03084)}

\bibitem{MR1757487}
\bysame, \emph{A course in model theory}, Universitext, Springer-Verlag, New
  York, 2000, An introduction to contemporary mathematical logic, Translated
  from the French by Moses Klein and revised by the author. \MR{1757487
  (2001a:03072)}

\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{MR1633348}
Lou van~den Dries, \emph{Tame topology and o-minimal structures}, London
  Mathematical Society Lecture Note Series, vol. 248, Cambridge University
  Press, Cambridge, 1998. \MR{1633348 (99j:03001)}

\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}