% LaTeX2e
% Lecture notes on set theory without choice
% A. Miller   Jan 08 

\documentclass[12pt]{article}
\usepackage{amssymb}

%\def\header{A.Miller\hfill Set Theory without Choice \hfill}
\def\header{\today} 
\pagestyle{myheadings}
\markboth\header\header


\def\Si{\Sigma}
\def\al{\alpha}
\def\anal{{\bf\Sigma^1_1}}
\def\bor{{\rm Borel}}
\def\bs{\par\bigskip\par}
\def\catx#1{\hat{\phantom{a}}\la #1\ra}
\def\cat{\hat{\phantom{a}}}
\def\cc{{\mathcal C}}
\def\cl{{\rm cl}}
\def\dd{{\mathcal D}}
\def\de{\delta}
\def\emp{\emptyset}
\def\eps{\epsilon}
\def\ka{\kappa}
\def\last#1{last(\vec{#1})}
\def\la{\langle}
\def\om{\omega}
\def\poset{{\mathbb P}}
\def\pow(#1){{\mathcal P}(#1)}
\def\proj{{proj}}
\def\proof{\par\noindent Proof\par\noindent}
\def\qed{\par\noindent QED\par\bigskip}
\def\ra{\rangle}
\def\reals{{\mathbb R}}
\def\res{\upharpoonright}
\def\rmand{\mbox{ and }}
\def\rmiff{{\mbox{ iff }}}
\def\rmor{\mbox{ or }}
\def\si{\sigma}
\def\sm{\setminus}
\def\sous{{\mathcal A}}
\def\sp{\phantom{AA}}
\def\st{\;:\;} % such that
\def\su{\subseteq}
\def\symdiff{\triangle}
\def\xxx{xxxxxxxxxxxxxxx}
\def\yyy{yyyyyy}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{define}[theorem]{Definition}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}

\begin{document}

\begin{center}
{\large Lecture notes on set theory without choice}
\end{center}

\begin{flushright}
Arnold W. Miller
\footnote{
\par Mathematics Subject Classification 2000: 03E99
\par Keywords: Axiom of Choice}
\end{flushright}

\def\address{\begin{flushleft}
Arnold W. Miller \\
miller@math.wisc.edu \\
http://www.math.wisc.edu/$\sim$miller\\
University of Wisconsin-Madison \\
Department of Mathematics, Van Vleck Hall \\
480 Lincoln Drive \\
Madison, Wisconsin 53706-1388 \\
\end{flushleft}}

\begin{center}  Abstract  \end{center}
\begin{quote}
The first part of the course will discuss various consequences of
AD, the Axiom of Determinacy.  AD is inconsistent with AC. On
the other hand, it implies many good properties hold for sets o
real numbers. For example, AD implies LM (every set of reals is
Lebesgue measurable), BP (every set of reals has the property of
Baire), and P (every uncountable set of reals contains a
homeomorphic copy of the Cantor set).  In addition, it is
connected with the theory of large cardinals, e.g., AD implies
that the first uncountable cardinal, omega-one, is a measurable
cardinal.  For the second part of the course, we will cover
Solovay's model of LM+BP+P.  For the last part, we will present some
models of set theory in which the axiom of choice fails as badly
as we can conceive possible. For example, the Feferman-Levy model
in which the real line is the countable union of countable sets.
\end{quote}

\bigskip

\tableofcontents

\bigskip

\section{Open determinacy}

For $X$ a set define
$$X^\om=\{x\st x:\om\to X\}$$
where $\om=\{0,1,2,\ldots,\}$. Let
$$X^{<\om}=\bigcup_{n<\om}X^n$$ 
be the finite sequences in $X$.
$X$ is given the discrete topology,
i.e., every subset of $X$ is open and $X^\om$ the product topology.
A clopen basis for this topology consists of the sets: 
$$[s]=\{x\in X^\om\st s\su x\}\mbox{ where } s\in X^{<\om}.$$
Open sets are arbitrary unions of basic clopen sets.
Equivalently,  $A\su X^\om$ is open iff for any
$x\in A$ there is an $n<\om$ such that $[x\res n]\su A$.

The most popular choices for $X$ are $X=\om$ or $X=2=\{0,1\}$.

Given $A\su X^\om$ define the following infinite two person game
$G(A)$.  There are two players I and II which alternate writing
down an element of $X^\om$:

\begin{tabbing}
xxx \= xxx    \= xxx     \=  xxx      \= xxx       \kill
I   \> $x(0)$ \>        \> $x(2)$        \\ 
II  \>        \> $x(1)$  \>          \> $\ldots$      \\
\end{tabbing}

Player I wins the play of the game $x$ iff $x\in A$.

A strategy for a game such as this is a map $\si:X^{<\om}\to X$.
Given two strategies $\si$ and $\tau$ then we can define
$$\si*\tau=x\in X^\om$$
as the result of playing the strategy $\si$ for player I against
the strategy $\tau$ for player II as follows:
$$x(0)=\si(\la\ra),$$ 
$$x(2n)=\si(\la x(1),x(3),\ldots,x(2n-1)\ra)$$
and
$$x(2n+1)=\tau(\la x(0),x(2),\ldots,x(2n)\ra).$$

We say that the game $G(A)$ is determined iff either Player I 
has a winning strategy or
Player II has a winning strategy:
$$(\exists \si \forall \tau \;\;\; \si *\tau \in A) \rmor 
(\exists \tau \forall \si \;\;\; \si *\tau \in X^\om\sm{A}).$$ 

\begin{theorem}\label{gale}
(Gale, Stewart \cite{gale}) If $A\su X^\om$ is open, then
$G(A)$ is determined.
\end{theorem}
\proof
Suppose the open player (Player I) has no winning strategy.
Then the closed player plays so as to never reach
a position in the game in which the open player has a
winning strategy.
\qed

\begin{cor}
Closed games are determined.
\end{cor}




\bs
Remark. Theorem \ref{gale} implies the axiom of choice.  To see this,
suppose we are given
a family of nonempty sets $Q$. Let $X$ be transitive set containing
$Q$. Consider the game on
$X^\om$ in which Player II
wins iff ($x(1)\in x(0)$ or $x(0)\notin Q$).  This game is clopen,
Player I cannot have a winning strategy, and a strategy for Player II
gives a choice function for $Q$.




\begin{define}
For $T\su X^{<\om}$ a tree, i.e, $s\su t\in T\to s\in T$,
and $$A\su [T]=^{def}\{x\in X^\om\st \forall
n<\om\;\; x\res n\in T\}$$ define the game $G(A,T)$ to be the game
in which the players are required to stay on the tree $T$.
\end{define}

\begin{lemma}
Suppose $T\su X^{<\om}$ is a tree and $U\su [T]$ is relatively open.
Then the game $G(T,U)$ is determined.\footnote{
A good way to visualize this Lemma is to draw the tree $T$.  Color a node of
$T$ green if it has the property that all infinite branches thru
it are in $U$.  Color the other nodes red.  The object of the open
set player is go thru a green node.  The desire of his opponent is
stay on the red nodes. \par I really enjoy using colored chalk in a
lecture. If I had to write one of those ``Statement of Teaching
Philosophies'' that all our job candidates seem to have, I would
definitely devote several paragraphs to how using colored chalk has
enhanced my enjoyment of giving a lecture.
}
\end{lemma}

\begin{define}
A $G_\de$ set is a set which can be written as
a countable intersection of open sets.
\end{define}

\begin{theorem}
(P.Wolfe \cite{wolfe}) If $A\su X^\om$ is a $G_\de$ set, then $G(A)$ is
determined.
\end{theorem}
\proof
Suppose Player II has no winning strategy.
Let $T$ be the set of all $s\in X^{<\om}$ such that every 
$r\su s$ is not lost for Player I, i.e., Player II has no winning
strategy in the game $G(A)$ starting from the position r.

Let $A=\bigcap_n U_n$ where the $U_n$ are open.

\bs
Claim. For any $s\in T$ and $n<\om$ Player I has a winning strategy
in the game $G(U_n,T)$ starting at $s$.
\bs
Otherwise by the Lemma Player II has a winning strategy $\tau$ for
$G(U_n,T)$ starting at $s$.  But then Player II has a winning strategy
starting at $s$ in the game $G(A)$.   He\footnote{
The politically correct thing is to refer to the
players as ``she''.  For example, see the last problem in
Komj\'ath and Totik
\cite{komjath}. Perhaps even more
distracting is to sometimes call a random player ``he''
and other times call him ``she''. This will guarantee
to cause any reader to stop thinking about the math and
start contemplating the oppressed role of women in our
society. \par Perhaps to confirm more closely to reality, we
should adopt the rule that the player with a winning strategy
is refered to as `he' and the player that he beats is
refered to as `she'.
} 
just plays $\tau$
unless Player I leaves the tree $T$, but leaving $T$ means
that Player II has a winning strategy from the position.
\bs

The winning strategy for Player I in $G(A)$ is to first play his winning
strategy for $G(T,U_0)$ starting at $s_0=\la\ra$ until a position $s_1$
is reached with $[s_1]\su U_0$.  Then he plays his winning
strategy for $G(T,U_1)$ starting at $s_1$ until he reaches a position
$s_2$ with $[s_2)\su U_1$, etc.  Note that $T$ has the property that
Player II cannot be the first to leave $T$.

\qed

\section{The perfect set game}

\begin{define}
Given $A\su 2^\om$ define the game $G_p(A)$ as follows:
\begin{tabbing}
xxx \= \xxx    \= \xxx    \=  \xxx      \= \xxx       \kill
I   \> $s_0\in 2^{<\om}$ \>  $s_1\in 2^{<\om}$ \> $s_2\in 2^{<\om}$ 
 \> \ldots  \\ 
II  \> \sp $i_0\in\{0,1\}$  \> \sp $i_1\in\{0,1\}$  \> \sp $i_2\in\{0,1\}$
 \> \sp \ldots   \\
\end{tabbing}
Player I wins iff $x\in A$ where $x=s_0\catx{i_0}\cat{s_1}\catx{i_0}\cdots$
\end{define}

\begin{define}
A tree $T\su 2^{<\om}$ is perfect iff for any $s\in T$ there exists
$t\supseteq s$ such that both $t\catx{0}$ and $t\catx{1}$ are in $T$.
A set $P\su 2^\om$ is perfect iff there exists a perfect tree $T$ such
that $P=[T]$.
\end{define}

Note that perfect sets are those sets 
which are homeomorphic to $2^\om$.

\begin{theorem}
(M.Davis \cite{davis}) For any $A\su 2^\om$:
\begin{enumerate}
\item Player I has a winning strategy in $G_p(A)$ iff $A$ contains
a perfect set.
\item Player II has a winning strategy in $G_p(A)$ iff $A$ is countable.
\end{enumerate}
\end{theorem}

\proof

\bs
$(1) (\leftarrow)$

\noindent Player I's strategy is to play along the perfect tree to
nodes $t$ with both $t\catx{0}$ and $t\catx{1}$ in $T$.

\bs
$(1) (\rightarrow)$

\noindent Let $\si$ be a winning strategy for Player I.
Take the tree generated by positions consistent with $\si$.

\bs
$(2) (\leftarrow)$

\noindent On his $n^{th}$ move of the game
Player II avoids the $n^{th}$ element of $A$.

\bs
$(2) (\rightarrow)$

\noindent Let $\tau$ be a winning strategy for Player II.  Let
$p=\la s_0,i_i,s_1,\ldots,s_n,i_n\ra$ be any position in
the game consistent with playing $\tau$ ( this means that
$i_k=\tau(s_0,\ldots,s_k)$ for every $k\leq n$ ).

We think of $x_p\in 2^\om$ as the element of $2^\om$ which 
$\tau$ is trying to avoid.  It is defined as follows. Let 
$$\hat{p}=s_0\catx{i_0}\cat{s_1}\catx{i_1}\cdots s_n\catx{i_n}$$
and let $l=|\hat{p}|$ be the length of $\hat{p}$ and put
\begin{enumerate}
\item $x_p\res l=\hat{p}$,
\item $x_p(l)=1-\tau(s_0,\ldots,s_n,\la\ra)$, and
\item $x_p(k)=1-\tau(s_0,\ldots,s_n,t)$ where $t=x_p\res [l,k)$.
\end{enumerate}
That is, $x_p$ goes in the opposite direction to what the strategy says.

\bs
Claim. $A\su B=\{x_p\st p$ is a position consistent with $\tau\}$.
\bs

It is enough to prove that if $x\notin B$ then there exists
$s_0,i_0,s_1,i_1,\ldots $ consistent with $\tau$ such that
$x=s_0\catx{i_0}\cat{s_1}\catx{i_1}\cdots$.  Since $\tau$ is
a winning strategy for Player II we have that $x\notin A$.

Suppose we have already constructed $p=\la s_0,i_i,s_1,\ldots,s_n,i_n\ra$ 
consistent with $\tau$ and $\hat{p}\su x$.  Then since
$x_p\neq x$ there must be some $k\geq l=|\hat{p}|$ such that
$x_p\res k=x\res k$ and $x_p(k)\neq x(k)$.  Take $s_{n+1}=x\res [l,k)$.
By construction of $x_p$ we have that $x(k)=\tau(s_0,\ldots,s_{n+1})$.

This proves the Claim and since $B$ is countable, $A$ is countable.
\qed

\section{Axiom of determinacy}

\begin{define}
AD, axiom of determinacy, is the statement that for
every $A\su\om^\om$ the game $G(A)$ is determined.
\end{define}

This axiom was first proposed by Mycielski and Steinhaus \cite{myciel-stein}
in 1962.

\begin{cor}
$AD\to P$ where $P$ stands for the perfect set property: for all
$A\su 2^\om$ either $A$ is countable or $A$ contains a perfect subset.
\end{cor}

\begin{cor}
$P\to \neg AC$, i.e., the axiom of choice fails.  In fact $AD$, implies
we cannot have an $\om_1$ sequence $\la x_\al\in 2^\om\st\al<\om_1\ra$
of distinct elements.  Hence $AD$ is inconsistent with the axiom of
choice.
\end{cor}

\begin{prop}
(Mycielski \cite{myciel64}) $AD\to WCC$, the weak countable choice axiom,
i.e., any countable family of nonempty subsets of $\om^\om$ has a
choice function.
\end{prop}

\begin{prop}
(Levy \cite{levy}) $P+WCC$ implies that $\om_1$ is a strongly inaccessible
cardinal of $L$.
\end{prop}
\proof
$WCC$ implies that $\om_1$ is regular.  It must be a limit cardinal in
$L$, otherwise we would have for some cardinal $\ka$ of $L$ that
$(\ka^+)^L=\om_1$. But then there exists $x\in 2^\om$ such 
that $\om_1=(\om_1)^{L[x]}$ and since $L[x]$ is a model of choice
there would be an $\om_1$ sequence in $2^\om$.
\qed

\begin{prop}
(Mycielski \cite{myciel64}) The
axiom of determinacy is inconsistent
for games on $\om_1^\om$.  It is also inconsistent for games
of length $\om_1$, i.e., payoff sets which are subsets of
$2^{\om_1}$.
\end{prop}
\proof
Cook up games which if they are determined give an $\om_1$ distinct
sequence in $2^\om$.
\qed

Since (even clopen) determinacy for games on $(\pow(2^\om))^\om$
would give a choice function which would well-order $2^\om$, we
see that $AD$ for games on $(\pow(2^\om))^\om$ is inconsistent.

\begin{define}
$AD_\reals$ is the statement that all games on $X^\om$ are determined
for any set $X$ with $|X|\leq |\reals|$.
\end{define}

\begin{prop}
(Mycielski \cite{myciel64}) The axiom of determinacy for games
on $2^\om$ is equivalent to the  axiom of determinacy for games
on $\om^\om$
\end{prop}

\section{The Banach-Mazur Game}


\begin{define}
Given $A\su\om^\om$ define the Banach-Mazur Game, $G_{BM}(A)$ as follows:
\begin{tabbing}
xxx \= \xxx    \= \xxx    \=  \xxx      \= \xxx       \kill
I   \> $s_0\in \om^{<\om}$ \>  $s_2\in 2^{<\om}$ \> $s_4\in 2^{<\om}$ 
 \> \ldots  \\ 
II  \> \sp $s_1\in \om^{<\om}$  \> \sp $s_3\in \om^{<\om}$  \> 
\sp $s_5\in \om^{<\om}$ \> \sp \ldots   \\
\end{tabbing}
With the rule that $s_n\su s_{n+1}$ be proper extension, i.e., 
$s_n\neq s_{n+1}$.
Player II wins iff $x\in A$ where $x=s_0\cat{s_1}\cat{s_2}\cat{s_3}\cdots$.
\end{define}

This game was invented by Mazur in 1935.  He asked when is it determined
(see Mauldin \cite{mauldin} problem 43).



\begin{define}
A set $N\su \om^\om$ is nowhere dense iff its closure has no interior.
Equivalently, $\forall s\in \om^{<\om}\;\;\exists t\in \om^{<\om} \;\;( s\su t$
and $[t]\cap N=\emp$).
\end{define}

Since $[t]\cap N=\emp$ implies $[t]\cap cl(N)=\emp$, it follows that
the closure of nowhere dense set (nwd) is closed nowhere dense (cnwd).
The complement of a cnwd set is an open dense set.

\begin{define}
A set $M\su \om^\om$ is meager iff it is the countable union of nowhere
dense sets, equivalently $M$ is contained in the countable union 
of closed nowhere
dense sets.
\end{define}

\begin{define}
A set is comeager iff it is the complement of a meager set, equivalently
it contains the countable intersection of open dense sets.
\end{define}



\begin{theorem}(Banach, see Oxtoby \cite{oxtoby}) For any $A\su\om^\om$
\begin{enumerate}
\item Player II has a winning strategy in $G_{BM}(A)$ iff $A$ is comeager.
\item Player I has a winning strategy in $G_{BM}(A)$ iff $A\cap [s]$ is meager
for some $s\in \om^{<\om}$.
\end{enumerate}
\end{theorem}
\proof

\bs
$(1) \rightarrow$

If $A$ is comeager, then there exists $\la U_n\st n<\om\ra$ open dense
sets with $\bigcap_{n<\om}U_n\su A$.  Player II just plays so that
$[s_{2n+1}]\su U_n$.

\bs
$(1) \leftarrow$

Let $\tau$ be a winning strategy for Player II.  Inductively construct
sets $\Si_n$ such that


\begin{enumerate}

\item If $\vec{s}\in\Si_n$, then $\vec{s}=\la s_0,s_1,\ldots,s_{2n+1}\ra$
is a position in the game consistent with $\tau$.

For $\vec{s}\in\Si_n$, let $\last{s}=s_{2n+1}$.
\item 
$\{\last{s}\st \vec{s}\in \Si_n\}$ is a maximal antichain in $\om^{<\om}$.

\item The map $\vec{s}\mapsto \last{s}$ is one-to-one on $\Si_n$.

\item $\Si_n=\{\vec{s}\res 2n+1\st \vec{s}\in \Si_{n+1}\}$.

\end{enumerate}

To construct these sets, suppose that 
$\vec{s}=\la s_0,s_1,\ldots,s_{2n+1}\ra\in\Si_n$.  Then note that
$$D=\{t\st \exists r\; \tau(s_0,s_2,\ldots,s_{2n+1},r)=t\}$$
is dense below $s_{2n+1}$.  Hence it contains an antichain maximal
beneath $s_{2n+1}$.  Union up all the sets you obtain and
you get $\Si_{n+1}$ as required.

\bs
Now define
$$U_n=\bigcup\{\;[\;\last{s}\;]\st \vec{s}\in\Si_n\}$$
and note that it is a dense open set.  
But note that for any 
$x\in \bigcap_{n<\om}U_n$ there is a unique sequence
$\la s_n:n<\om\ra$ such that 
$$x=\bigcup_{n<\om}s_n \;\;\rmand\;\;(
\la s_0,s_1,\ldots,s_{2n+1}\ra\in \Si_n
\mbox{ for every }n).$$  It
follows that $x$ is an outcome of the game consistent with the
winning strategy $\tau$ and hence in the payoff set $A$.
It follows that $A$ contains $\bigcap_{n<\om}U_n$ and is therefore 
comeager.

\bs
The proof for $(2)$ is completely analogous.

\qed

\begin{cor}
$AD$ implies that 

$\forall A\su\om^\om$ the game $G_{BM}(A)$ is determined

\noindent and this is equivalent to

$\forall A\su\om^\om$ either $A$ is comeager or $\exists s\in \om^{<\om}$
such that $A\cap [s]$ is meager
\end{cor}



\begin{define}
A set $B$ in a topological space $X$ has the property of Baire iff there
exists an open set $U$ such that $B\symdiff U$ is meager.
The symbol $\symdiff$ stands for the symmetric difference:
$P\symdiff  Q=(P\sm Q)\cup (Q\sm P)$.  Sets with the Baire property
are also refered to as `almost open'.
\end{define}

\begin{cor}
$AD\to BP$ where $BP$ is the statement that every subset of
$\om^\om$ has the property of Baire.
\end{cor}

\section{Dependent Choice DC}

\begin{define}
The axiom of dependent choice ($DC$) stands for the proposition that
for every set $X$ and $R\su X^2$ a binary relation on $X$:
$$(\forall a\in X \;\exists b\in X \;\; aRb)\to(\exists
\la a_n:n<\om\ra\in X^\om\;\;\forall n<\om\;\; a_nRa_{n+1}).$$
\end{define}


\begin{define}
The axiom of countable choice ($CC$) stands for the statement
that every countable family of nonempty sets has a choice function.
\end{define}

\begin{prop}
$DC\to CC$ 
\end{prop}
\proof
Given $(A_n:n<\om)$ nonempty sets let $X$ and $R$ be:
$$X=\bigcup_{n<\om}\prod_{k\leq n}A_k \rmand
R=\{\la s,t\ra\in X^2\st s\subsetneq t\}
$$
\qed



\begin{prop}
(Blair \cite{blair})  The following are equivalent (in ZF):
\begin{enumerate}
\item DC
\item The Baire category theorem for complete metric
spaces, i.e., comeager sets are dense.
\item A partial order $\poset$ is well-founded iff there does
not exists a descending sequence, $\la p_n:n<\om\ra\in\poset^\om$
such that $p_{n+1}<p_n$ for every $n$.
\end{enumerate}
\end{prop}
\proof

\bs
\noindent $(1)\to (2)$

Given $U_n$ for $n<\om$ open dense sets
and an arbitrary nonempty open set $V_0$, construct nonempty open sets
$V_{n+1}$ such that
\begin{enumerate}
\item $V_{n+1}\su \cl(V_{n+1})\su U_n\cap V_{n}$ and 
\item the diameter of $V_{n+1}$ is less than $1\over n+1$.
\end{enumerate}
Then choose $p_n\in V_n$.  The sequence is Cauchy, hence converges
to some $p\in X$.  Since tails of the sequence are in
the closed set $\cl(V_n)$ we have that $p\in\bigcap_nU_n$.

\bs
\noindent $(1)\to (3)$

Given poset $\poset$ and nonempty subset $X\su\poset$ with no minimal
element define $R\su X^2$ by $aRb$ iff $b<a$.


\bs
\noindent $(3)\to (1)$

Let $\poset=X^{<\om}$ ordered by $p\leq q$ iff $q\su p$.  Then
the subset $A\su\poset$ defined by:
$$A=\{(a_i:i<n)\st n<\om, \rmand \forall i<n-1\;\; a_iRa_{i+1}\}$$
has no minimal element.

\bs
\noindent $(2)\to (1)$

Given $X$ and $R$ the space $X^\om$ where $X$ has the discrete
topology has the complete metric $d$ defined by:
$$d(x,y)=\left\{
\begin{array}{ll}
0 & \mbox{ if } x=y \\
{1\over n+1}  & \mbox{ if } x\res n=y\res n \rmand x(n)\neq y(n)\\
\end{array}\right.$$
Let 
$$U_n=\{x\in X^\om\st \exists m\;\; x(n)\; R\; x(m)\}.$$
Then $U_n$ is open dense.  If $x\in\bigcap_{n<\om}U_n$, 
then $\forall n\;\exists m \;\;x(n)\; R\; x(m)$.  Since the
range of $x$ is well-ordered we can construct a sequence as
required without using choice.

\qed


Kechris \cite{kechris-dc} has shown that $Con(ZF+AD)\to Con(ZF+AD+DC)$.
Hence if we could derive a contradiction by using $AD+DC$ we could
already get one from $AD$ alone.


\section{Superperfect sets}

\begin{define}
A tree $T\su\om^{<\om}$ is superperfect iff for every $s\in T$ there
exists $t\supseteq s$ such $\exists^{\infty} n \;\; t\catx{n}\in T$.
A set $P\su\om^\om$ is superperfect iff there exists a superperfect
tree $T$ such that $P=[T]$.
\end{define}

\begin{prop}
A set $P\su \om^\om$ is superperfect iff it is closed and
homeomorphic to $\om^\om$.
\end{prop}

\begin{define}
For $f,g\in\om^\om$ $$f\leq^* g \rmiff 
\forall^\infty n\in\om\;\; f(n)\leq g(n).$$
\end{define}

\begin{prop}
For any $f\in \om^\om$ the set
$$\{g\in\om^\om\st g\leq^* f\}$$
is $\si$-compact, ie. the countable union of compact sets.
Also if $F\su\om^\om$ is $\si$-compact, then there exists
$f$ such that $g\leq^*f$ for all $g\in F$.
\end{prop}

\begin{define}
Given $A\su\om^\om$ the superperfect game $G_{sup}(A)$ is defined
as follows:
\begin{tabbing}
xxx \= \xxx    \= \xxx    \=  \xxx      \= \xxx       \kill
I   \> $s_0\in \om^{<\om}$ \>  $s_1\in \om^{<\om}$
                           \> $s_2\in \om^{<\om}$
 \> \ldots  \\ 

    \>                     \>  $s_1(0)>n_0$  
                           \>  $s_2(0)>n_1$ \\
\\
II  \> \sp $n_0\in\om$  \> \sp $n_1\in\om$  \> \sp $n_2\in\om$
 \> \sp \ldots   \\
\end{tabbing}
Player I wins iff $x\in A$ where $x=s_0\cat{s_1}\cat{s_2}\cdots$.
\end{define}

\begin{theorem}
(Kechris \cite{kechris-super}) Suppose $A\su\om^\om$ then
\begin{enumerate}
\item Player I has a winning strategy in $G_{sup}(A)$ iff $A$ contains
a superperfect set.
\item Player II has a winning strategy in $G_{sup}(A)$ iff
there exists $f\in\om^\om$ such that $g\leq^*f$ for every
$g\in A$.
\end{enumerate}
\end{theorem}
\proof
The proof of $(1)$ and $(2)\leftarrow$ are left to the reader.

\bs
\noindent $(2)\rightarrow$

Let $\tau$ be a winning strategy for Player II.  Let 
$p=\la s_0,s_1,\ldots,s_n\ra$ be a position
in the game consistent with $\tau$. (This simply means
that $s_{k+1}(0)>\tau(s_0,\ldots,s_{k})$ for every $k<n$.)

Define a map 
$f_p:\om^{<\om}\to \om$ as follows:
$$f_p(t)= \tau(s_0,s_1,\ldots,s_n,s)$$  
if  $(s_0,s_1,\ldots,s_n,s)$
is consistent with $\tau$ and
$t=s_0 \cat s_1\ldots\cat s_n\cat s$.  
Otherwise $f_p(t)=0$.

Since there are only countably many $p$ there exists a 
$h:\om^{<\om}\to\om$ such that 
$$\forall^\infty s\in\om^{<\om}\;\; f_p(s)<h(s)$$
for every position $p$ consistent with $\tau$.

\bs
{\bf Claim}. 
$A\su\{g\in\om^\om\st \forall^\infty n\;\; g(n)\leq h(g\res n)\}$.

\bs

\noindent Suppose  
$$\exists^\infty n\;\; g(n)> h(g\res n).$$  
Then we will
construct an infinite sequence $s_0,s_1,\ldots$ which is
consistent with $\tau$ such that
$g=s_0\cat{s_1}\cat{s_2}\cdots$.   But since $\tau$ is a winning
strategy this implies $g\notin A$.  

Suppose we
have already constructed 
$p=(s_0,s_1,\ldots,s_n)$ consistent with $\tau$ so that
\begin{enumerate}
\item $s_0\cat{s_1}\cat{s_2}\cdots\cat s_n\su g$ and
\item $g(l)>\tau(s_0,s_1,\ldots,s_n)$ where $l$ is the
lenght of $s_0\cat{s_1}\cat{s_2}\cdots\cat s_n$.
\end{enumerate}
Then 
$$(\forall^\infty m \;\; h(g\res m)>f_p(g\res m))\rmand
(\exists^\infty m \;\;g(m)>h(g\res m)).$$ 
Hence we can find $m>l$ with $g(m)>f_p(g\res m)$ and take
$s_{n+1}=g\res [l,m)$ as required.

\qed

\section{Measurability and AD}

Lebesgue measure $\mu$ is a countably additive measure on 
the Borel subsets of the real line.  It satisfies
\begin{itemize}
\item $\mu:\bor(\reals)\to [0,\infty]$,  
\item $\mu([a,b])=b-a$
for every interval $[a,b]$, and 
\item it is countably additive, meaning
if $(B_n:n<\om)$ are pairwise disjoint Borel sets, then
$$\mu(\bigcup_{n<\om}B_n)=\sum_{n<\om}\mu(B_n).$$ 
\end{itemize}
The outer measure $\mu^*$ is
defined by
$$\mu^*(X)=\inf\{\sum_{n=0}^\infty \mu(I_n)\st
I_n \mbox{ are intervals such that } X\su\bigcup_{n<\om}I_n\}.$$
For Borel sets $\mu$ and $\mu^*$ agree.
A set $X$ has measure zero iff $\mu^*(X)=0$.
A set $X$ is measurable iff there is a Borel set $B$ such
that $B\symdiff X$ has measure zero.

\begin{prop}
If $X\su\reals$ is not measurable, then there exists a Borel
set $B\su X$ such that if $Y=X\sm B$, then $Y$ has inner meaure
zero, i.e, any measurable $Z\su Y$ has measure zero but
the outer measure of $Y$ is positive,  $\mu^*(Y)>0$.
\end{prop}

\begin{theorem}
(Mycielski-\'Swierczkowski \cite{myciel-swier})
Let $LM$ stands for the proposition that
every set of reals is Lebesgue measurable.
Then $AD\to LM$.
\end{theorem}

Before proving this theorem we will need two technical lemmas.



\begin{lemma}
Suppose $X\su \reals$ has measure zero and we are given
$(\eps_n>0:n<\om)$.  Then there exists 
$(C_n:n<\om)$ such that
\begin{enumerate}
 \item  each $C_n$ is a finite union of closed intervals,
 \item $\mu(C_n)\leq \eps_n$ for each $n$, and
 \item $X\su\bigcup_{n<\om}C_n$.
\end{enumerate}
\end{lemma}
\proof
Without loss we may assume that $\sum_{n<\om}\eps_n<\infty$.
Since $X$ has measure zero we may find closed intervals
$I_n$ such that 
$$X\su\bigcup_{n<\om}I_n \rmand \sum_{n<\om}\mu(I_n)=\sum_{n<\om}\eps_n.$$
Actually we might first get $\leq$ above but we could always expand $I_0$ to
make it an equality.  Now define $\delta_n=\mu(I_n)$. 
We can break up the $I_n$ using the following algorithm:
Find $n$ so that 
$$\de_0+\cdots+\de_{n-1}<\eps_0\leq \de_0+\cdots+\de_{n-1}+\de_n.$$
Break up $\de_n=\de_n^0+\de_n^1$ into nonnegative reals so that
$$\de_0+\cdots+\de_{n-1}+\de_n^0=\eps_0.$$
Break $I_n$ into the overlapping closed intervals $I_n^0$ and
$I_n^1$ where $I_n^0$ is lefthand piece of $I_n$ of length $\de_n^0$ and
$I_n^1$ is righthand piece of $I_n$ of length $\de_n^1$.
Set 
$$C_0=I_0\cup I_1\cup I_2\cup\ldots I_{n-1}\cup I_n^0.$$
Then proceed with the intervals $I_n^1,I_{n+1},\ldots$ and
the equal sums
$$\de^1_n+\de_{n+1}+\de_{n+2}+\cdots=\eps_1+\eps_2 +\cdots$$
and use the same procedure to find $C_1$, etc.
\qed


\begin{lemma} \label{lemlm1}
Suppose $X\su \reals$ has measure zero and we are given
$(\eps_n>0:n<\om)$.  Then there exists 
$(C_n:n<\om)$ such that
\begin{enumerate}
 \item  each $C_n$ is a finite union of open intervals
 with rational endpoints,
 \item $\mu(C_n)< \eps_n$ for each $n$, and
 \item $X\su\bigcup_{n<\om}C_n$.
\end{enumerate}
\end{lemma}
\proof
This is an immediate corollary of the preceeding lemma. Apply it
to the sequence $({\eps_n\over 2}:n<\om)$.  Then fattening up
each closed interval by just a little bit.
\qed

\begin{lemma}\label{lemlm2}
If $f:\om^\om\to A\su\reals$ is onto and continuous, then 
$A$ is measurable.
\end{lemma}
\proof
This will be proved latter.  It follows from the fact that
analytic sets are measurable.
\qed



Now we are ready to prove the Theorem.  By the proposition if
$LM$ is false then we can find a set of reals $X$ such that
the inner measure of $X$ is zero, but the outer measure of
$X$ is positive. Without loss of generality we may
assume that $X\su [0,1]$.  Choose $(\eps_n>0 : n<\om)$ so that
$$\sum_{n<\om}2^n\eps_n<{1\over 2}\mu^*(X).$$
And define $\cc_n$ to be the set of
$C$ such that $C$ is a finite union of open intervals
with rational endpoints and
$\mu(C)< \eps_n$.

Consider the following game $G_{meas}$:
\begin{tabbing}
yyy \= \yyy    \= \yyy    \=  \yyy      \= \yyy       \kill
I   \> $I_0$ \>  $I_1$ \> $I_2$  \> \ldots \\
II  \> \sp $C_0$  \> \sp $C_1$  \> \sp $C_2$ \> \sp  \ldots   \\
\end{tabbing}
We require that $C_n\in\cc_n$ and 
$I_n=[{{k}\over {2^n}},{{k+1}\over {2^n}}]$ for some
integer $k$,
\par Player II wins iff 
$$(X\cap\bigcap_{n<\om}I_n)\su \bigcup_{n<\om}C_n.$$

Claim. Player I cannot have a winning strategy in $G_{meas}$.

\proof
Suppose $\si$ were such a winning strategy.  Clearly
the intervals played by $\si$ must be nested.  Then $\si$ determines
a continuous mapping
$$f:\prod_{n<\om}\cc_n\to [0,1]$$
by the rule that $f(C_n:n<\om)=x$ iff $\{x\}=\bigcap_{n<\om} I_n$ 
where $\si(C_n:n<m)=I_m$.  But the image $A$ of $f$ is measurable by
Lemma \ref{lemlm2} and since we are assuming $\si$ is a winning strategy
$A\su X$.  Since $X$ has inner measure zero, $A$ has measure zero.  But
by Lemma \ref{lemlm1}, $A$ can be covered 
by $(C_n:n<\om)\in \prod_{n<\om}\cc_n$.  But if Player II
plays this sequence then 
$\si$ losses this play of the game. 
\qed



Hence, if the game $G_{meas}$ is determined, then Player II has a winning
strategy $\tau$.  But note that there are only $2^n$ possible plays of
$I_n$ for Player I.  This means that we can find $\dd_n\su\cc_n$
of size $2^n$ which includes all possible $n^{th}$ plays of
$\tau$.  Since Player I can squeeze
down on any $x\in X$ it follows that
$$X\su\bigcup_{n<\om}\cup\dd_n\rmand\mu(\bigcup_{n<\om}\cup\dd_n)\leq
\sum_{n<\om}2^n\eps_n\leq ({1\over 2})\mu^*(X)$$
which is a contradiction.
\qed




\section{Souslin Operation}




\begin{define}
The Souslin operation is defined as follows:  Given
a family of sets $(A_s:s\in\om^{<\om})$ define the set $A$ as
$$A=\bigcup_{f\in\om^\om}\bigcap_{n<\om}A_{f\res n}.$$
This operation is also known as ``Operation $\mathcal A$''.
\end{define}

\begin{define}
Given a topological space $X$ define $\sous(X)$ to be all
sets of the form 
$\bigcup_{f\in\om^\om}\bigcap_{n<\om}C_{f\res n}$
for $C_s$'s closed
in $X$.
\end{define}

\begin{prop}
The family $\sous(X)$ is closed under countable unions and 
countable intersections.
\end{prop}
\proof
Given $$A_m=\bigcup_{f\in\om^\om}\bigcap_{n<\om}C_{f\res n}^m$$
then
$$\bigcup_{m<\om}A_m=\bigcup_{g\in\om^\om}\bigcap_{n<\om}D_{g\res n}$$
where 
$$D_{g\res n}=C^{g(0)}_{g\res (0,n)}.$$
For intersection note that
$$\forall n<\om\;\exists f\in\om^\om\;\; P(n,f)\rmiff
\exists (f_n\in\om^\om : n<\om)\;\forall n<\om\;\;P(n,f_n)$$
by weak countable choice, WCC.
Hence
$$\bigcap_{m<\om}A_m=\bigcup_{g\in\om^{\om\times\om}}
\bigcap_{n<\om}D_{g\res (n\times n)}$$
where 
$$D_{g\res (n\times n)}=\bigcap\{ C_{g_k\res n}^k\st k<n\}$$
where $g_k\in\om^\om$ is defined by $g_k(i)=g(k,i)$.
To make this look more like the Souslin operation, let
$\{p_n:n<\om\}$ be a listing of $\om\times\om$ which satisfies
the property \footnote{ We pause to here to let the reader
verify that it is possible to have such a listing of the pairs 
$\cdots \cdots \cdots$ 
This morning I had biscuits and gravy for
breakfast. The  Saw-Mill gravy was made by browning flour in the
drippings of Jimmy Dean's hot sausage and  then adding milk.  It
was poured over hot freshly baked Pillsbury Grande biscuits.
Manna from Heaven!
$\cdots \cdots \cdots$  OK lets go on.}
that for every $n<\om$:
$$\{p_i:i<n^2\}=n\times n.$$
Then 
$$\bigcap_{m<\om}A_m=\bigcup_{g\in\om^{\om\times\om}}
\bigcap_{n<\om}D_{g\res \{p_i: i<n\}}$$
where we put $D_{g\res \{p_i: i<k\}}=X$ for any $k$ with 
$n^2<k<(n+1)^2$.
\qed

\begin{cor}
If $X$ is a metric space, then $\sous(X)$ contains all Borel
subsets of $X$.
\end{cor}
\proof
Clearly all closed sets are in $\sous(X)$ and since in a metric
space open sets are the countable union of closed sets, the result
follows.
\qed

Examples of spaces in which not every open set is in $\sous(X)$ would
be $X=\om_1$ or $X=\om_1+1$ with the order topology.



\begin{prop}
For any topological space $X$ and $A\su X$ the following are equivalent:
\begin{enumerate}
\item $A\in\sous(X)$
\item there exist a closed set $C\su \om^\om\times X$
such that
$$A=\proj_X(C)=^{def}\{x\in X\st\exists f\in\om^\om \;(f,x)\in C\}.$$
\end{enumerate}
\end{prop}
\proof

\noindent $(1)\to (2)$
\bs

Suppose
$$A=\bigcup_{f\in\om^\om}\bigcap_{n<\om}C_{f\res n}$$
where the $C_s$'s are closed.  Define
$$C=\bigcap_{n<\om}\bigcup_{s\in\om^n}([s]\times C_s).$$
Then $C$ is closed in $\om^\om\times X$. 

Suppose $x\in\proj_X(C)$. Then for some $f$ we have $(f,x)\in C$.
But then it is easy to check that $x\in\bigcap_{n<\om}C_{f\res n}$.
Suppose $x\in A$.  Then there exists $f\in\om^\om$ such that
$x\in C_{f\res n}$ for every $n$.  But then
$(f,x)\in [f\res n]\times C_{f\res n}$ so $(f,x)\in C$ and 
$x\in\proj_X(C)$.

\bs
\noindent $(2)\to (1)$
\bs

Suppose $A=\proj_X(C)$ for $C\su \om^\om\times X$ closed.
For $s\in\om^{<\om}$ define
$$Q_s=\{x\in X\st ([s]\times\{x\})\cap C\neq\emp\}\rmand C_s=\cl(Q_s).$$

Suppose $x\in \proj_X(C)$. Then there exist $f\in\om^\om$ such that
$(x,f)\in C$.  But then it follows that $x\in Q_{f\res n}\su C_{f\res n}$
for
every $n$.  For the opposite inclusion suppose that
$$x\in \bigcup_{f\in\om^\om}\bigcap_{n<\om}C_{f\res n}$$
and choose $f$ so that
$x\in C_{f\res n}$ for every $n$.  
Suppose for contradiction that $(f,x)\notin C$. Since $C$ is
closed there exists an open $U$ and an $n<\om$ with
$x\in U$ and $U\times [f\res n]$ disjoint from $C$.  But
this means that $U$ is disjoint from $Q_{f\res n}$ and hence
$x\notin C_{f\res n}$.  Hence $x\in\proj_X(C)$.

\qed

Another proof that the family of sets
$\sous(X)$ is closed under countable intersections:

Given $A_m=\proj_X(C_m)$ for $m<\om$ let
$$C=\{(f,x)\in \om^{\om\times\om}\times X\st 
\forall m<\om\;\;(f_m,x)\in C_m\}.$$
Then 
$$\bigcap_{m<\om}A_m=\proj_X(C).$$


\begin{cor}
For $X$ a metric space, if $B\su\om^\om\times X$ is Borel, then
$A=\proj_X(B)$ is in $\sous(X)$.
\end{cor}
\proof
Since $B$ is in $\sous(\om^\om\times X)$ there exists a closed set
$C\su \om^\om\times(\om^\om\times X)$ with
$B=\proj_{\om^\om\times X}(C)$.  But then
$A=\proj_X(C)$.
\qed



\begin{define}
The class of $\anal$ sets are those sets $A$ which are in
$\sous(X)$ for some Polish space $X$, i.e., $X$ is a separable
completely metrizable space.  These sets are also known as analytic
sets.
\end{define}

\begin{cor}
A set $A\su \om^\om$ is $\anal$ iff there exists a tree 
$T\su\om^{<\om}\times\om^{<\om}$ such that
$$A=p[T]=^{def}\{x\st\exists y\in\om^\om\;\;
\forall n \;\;(x\res n,y\res n)\in T\}.$$
\end{cor}
\proof
Given a closed set $C\su\om^\om\times\om^\om$ whose projection
onto the first coordinate gives $A$  define $T$ by
$$T=\{(s,t)\st ([s]\times [t])\cap C\neq\emp\}.$$
\qed

\section{Analytic sets and the perfect set property}

\begin{theorem}\label{thmsous}
(Souslin 1917) Suppose $A\su 2^\om$ is $\anal$.  Then either
$A$ is countable or $A$ contains a perfect subset.
\end{theorem}
\proof
Suppose $T\su 2^{<\om}\times \om^{<\om}$ is a tree such that
$A=p[T]$.  Suppose that $A$ is uncountable and define
$$\hat{T}=\{(s,t)\in T\st p[T_{(s,t)}]\mbox{ is uncountable }\}$$
where $T_{(s,t)}$ is the subtree of $T$ of nodes comparable to
$(s,t)$.

\begin{lemma}\label{lemsous1}
For any $(s,t)\in \hat{T}$ there exists $n<\om$ such that
$(s,t\catx{n})\in \hat{T}$.
\end{lemma}
\proof
Note that
$$p[T_{(s,t)}]=\{x\in [s]\st\exists y\in [t]\;\; (x,y)\in [T]\}=
\bigcup_{n<\om} p[T_{(s,t\catx n)}].$$
\qed

\begin{lemma}\label{lemsous2}
For any $(s,t)\in \hat{T}$ there exists $r$ with $s\su r\in 2^{<\om}$ such
that both $(r\catx 0,t)$ and $(r\catx 1,t)$ are in $\hat{T}$.
\end{lemma}
\proof
Let 
$$Q=\{r\in 2^{<\om}\st s\su r\rmand (r,t)\in \hat{T}\}.$$
If the lemma is false then all of the elements of $Q$ would have to
lie along a single branch $x\in 2^\om$.  But then 
$$p[T_{(s,t)}]\su \{x\}\cup \bigcup \{p[T_{(r,t)}]
\st s\su r \rmand r\notin Q\}$$
and this is a countable union of countable sets.
\qed

Using the two lemmas we can now construct our perfect set and
prove Theorem \ref{thmsous}.
Inductively choose $(s_\si,t_\si)$ for $\si\in 2^{<\om}$ so that:
\begin{enumerate}
\item $(s_\si,t_\si)\in\hat{T}$,
\item $|s_\si|= |t_\si|$,
\item $s_{\si\catx 0}$ and $s_{\si\catx 1}$ are incomparble, and
\item $s_\si\su s_{\si\catx i}$ and 
$t_\si\su t_{\si\catx i}$ for $i=0,1$.
\end{enumerate}
This is easy to do since given $(s_\si,t_\si)$ we first apply 
Lemma \ref{lemsous2} to find $s_{\si\catx 0}$ and $s_{\si\catx 1}$
and then use Lemma \ref{lemsous1} repeatedly to find
$t_{\si\catx i}$ of the same length as $s_{\si\catx i}$.
The maps $f:2^\om\to 2^\om$ and $g:2^\om\to \om^\om$ defined by
$$f(x)=\bigcup_{n<\om}s_{x\res n} \rmand g(x)=\bigcup_{n<\om}t_{x\res n}$$
are continuous and $f$ is one-to-one.  Since $(f(x),g(x))\in [T]$
for every $x$ it follows that the range of $f$ is a perfect subset of $A$.

\qed

Souslin's Theorem is true for every $\anal$ set, i.e., it holds
for any Polish space in place of $2^\om$.
% This is particularly easy to see for $\om^\om$ or $\reals$.

\begin{theorem}
(Kechris) Suppose $A\su\om^\om$ is $\anal$.  Then either $A$ contains
a superperfect set or $\exists g\in\om^\om\;\; \forall f\in A\;\;
f\leq^* g$.
\end{theorem}
\proof


\section{ Miscellania }

Does a game with a computable payoff set always have a computable
winning strategy?

\begin{example}(Galvin)
There exists a computable set $A\su\om^3$ such that the 
three move game below has no computable winning strategy:
\begin{tabbing}
xxxxxxx \= xxxxxxx    \= xxxxxxx     \=  xxxxxxxx      \= xxx       \kill
I   \> $x\in\om$ \>        \> $s\in\om$        \\ 
II  \>        \> $y\in\om$  \>             \\
\end{tabbing}
Player I wins iff $(x,y,s)\in A$.
\end{example}
\proof
Let $B$ be a simple set with computable enumeration $\bigcup_s B_s$.
Put 
$$(x,y,s)\in A \rmiff y\leq x \rmor y\in A_s.$$  Player II has a winning
strategy, he just plays an element of the complement of $A$ bigger than
$x$.  But he cannot have a computable winning strategy since $A$ is
simple.
\qed

\begin{example}
(Kleene) There is a computable closed set $C\su\om^\om$ for which
there is no hyperarithmetic winning strategy.
\end{example}
\proof
By computable closed set we mean $\Pi^0_1$ class, equivalently
there exists a computable tree $T\su\om^{<\om}$ such that
$C=[T]$.  Kleene has shown that there exists a nonempty $\Pi^0_1$
class $B$ which contains no hyperarithmetic reals.  If
$C=B\times\om^\om$, then clearly Player I has a winning strategy, just
play an element of $B$ and ignore Player II.  But he cannot have an
hyperarithmetic winning strategy, since the play against the constant
zero function would give an hyperarithmetic element of $B$.
\qed

For an interesting paradoxical game, see Zwicker \cite{zwicker}. Zwicker
calls a game $G$ almost finite iff it always eventually ends. In the
Hypergame Player I plays an almost finite game $G$, then Player II plays the
first move in $G$ and then they continue in $G$ until it ends.
Is the Hypergame itself an almost finite game?

\begin{prop}
The Hypergame is almost finite.
\end{prop}
\proof
After the play of the almost finite game $G$ the players play the game $G$ 
which since it is almost finite, must end after finitely many more plays.
\qed



\begin{prop}
The Hypergame is not almost finite.
\end{prop}
\proof
If the Hypergame $H$ is almost finite, then player I can play it on the first
move.  Since they are now playing the Hypergame, Player II can play it
as his first move, etc. Hence the following infinite play is legal:
\begin{tabbing}
yyy \= \yyy    \= \yyy    \=  \yyy      \= \yyy       \kill
I   \> $H$ \> $H$ \> $H$  \> \ldots  \\ 
II  \> \sp $H$ \> \sp $H$ \> \sp $H$  \> \ldots  \\ 
\end{tabbing}
\qed


\begin{thebibliography}{99}

\bibitem{blair} Blair, Charles E.; The Baire category theorem implies the
principle of dependent choices.  Bull. Acad. Polon. Sci. Sér. Sci. Math.
Astronom. Phys.  25  (1977), no. 10, 933--934.

\bibitem{cabal76} {\bf Cabal Seminar 76--77.} Proceedings of the Caltech-UCLA
Logic Seminar 1976--77. Edited by Alexander S. Kechris and Yiannis N.
Moschovakis. Lecture Notes in Mathematics, 689. Springer, Berlin, 1978. iii+282
pp. ISBN: 3-540-09086-* 03-06

\bibitem{cabal77} {\bf Cabal Seminar 77--79.} Proceedings of the Caltech-UCLA
Logic Seminar, 1977--79. Edited by Alexander S. Kechris, Donald A. Martin and
Yiannis N. Moschovakis. Lecture Notes in Mathematics, 839. Springer, Berlin,
1981. ii+274 pp. ISBN: 3-540-10288-4 03-06 (03E15)

\bibitem{cabal79} {\bf Cabal seminar 79--81.} Proceedings of the Caltech-UCLA
logic seminar held during the academic years 1979/1981. Edited by A. S. Kechris,
D. A. Martin and Y. N. Moschovakis. Lecture Notes in Mathematics, 1019.
Springer-Verlag, Berlin, 1983. ii+284 pp. ISBN: 3-540-12688-0 (Reviewer: Ryszard
Frankiewicz) 03-06 (03E15 03E55 03E60)

\bibitem{cabal81} {\bf Cabal Seminar 81--85.} Proceedings of the Caltech-UCLA
Logic Seminar held during 1981--85. Edited by A. S. Kechris, D. A. Martin and J.
R. Steel. Lecture Notes in Mathematics, 1333. Springer-Verlag, Berlin, 1988.
vi+224 pp. ISBN: 3-540-50020-0 03-06 (03E15)

\bibitem{davis} Davis, Morton; Infinite games of perfect information. 1964 {\bf
Advances in game theory} 85--101 Princeton Univ. Press, Princeton, N.J.

\bibitem{gale} Gale, David; Stewart, F. M.; Infinite games with perfect
information. {\bf Contributions to the theory of games}, vol. 2, pp. 245--266.
Annals of Mathematics Studies, no. 28 Princeton University Press, Princeton, N.
J., 1953. 

\bibitem{goldblatt} Goldblatt, Robert; On the role of the Baire category theorem
and dependent choice in the foundations of logic. J. Symbolic Logic 50 (1985),
no. 2, 412--422.

\bibitem{kechris-super} Kechris, Alexander S.; On a notion of smallness for
subsets of the Baire space. Trans. Amer. Math. Soc. 229 (1977), 191--207.

\bibitem{kechris-dc} Kechris, Alexander S.; The axiom of determinacy implies
dependent choices in $L( R)$. J. Symbolic Logic 49 (1984), no. 1, 161--173.

\bibitem{komjath} Komjath, Totik, Ultrafilters, Math Monthly Jan 08.

\bibitem{levy} L\'evy, Azriel; Definability in axiomatic set theory. II. 1970
{\bf Mathematical Logic and Foundations of Set Theory (Proc. Internat. Colloq.,
Jerusalem, 1968)}  pp. 129--145 North-Holland, Amsterdam

\bibitem{mauldin} {\bf The Scottish Book}. Mathematics from the Scottish Caf\'e.
Including selected papers presented at the Scottish Book Conference held at
North Texas State University, Denton, Tex., May 1979. Edited by R. Daniel
Mauldin. Birkh\"auser, Boston, Mass., 1981. xiii+268 pp. (2 plates). ISBN:
3-7643-3045-7

\bibitem{myciel-stein} Mycielski, Jan; Steinhaus, H.; A mathematical axiom
contradicting the axiom of choice. Bull. Acad. Polon. Sci. S\'er. Sci. Math.
Astronom. Phys. 10 1962 1--3. 

\bibitem{myciel64} Mycielski, Jan; On the axiom of determinateness. Fund. Math.
53 1963/1964 205--224. 

\bibitem{myciel-swier}
Mycielski, Jan; \'Swierczkowski, S.;
On the Lebesgue measurability and the axiom of determinateness.
Fund. Math. 54 1964 67--71.

\bibitem{myciel66} Mycielski, Jan; On the axiom of determinateness. II. Fund.
Math. 59 1966 203--212. 

\bibitem{oxtoby} Oxtoby, John C.; {\bf Measure and category. A survey of the
analogies between topological and measure spaces.} Graduate Texts in
Mathematics, Vol. 2. Springer-Verlag, New York-Berlin, 1971. viii+95 pp.

\bibitem{wolfe} Wolfe, Philip; The strict determinateness of certain infinite
games. Pacific J. Math. 5 (1955), 841--847.

\bibitem{tel} Telg\'arsky, Rastislav; Topological games: on the 50th 
anniversary of the Banach-Mazur game. Rocky Mountain J. Math. 17 (1987), no. 2,
227--276.

\bibitem{zwicker} Zwicker, William S.; Playing games with games: the hypergame
paradox. Amer. Math. Monthly 94 (1987), no. 6, 507--514. 

\end{thebibliography}

\address

\end{document}





