% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\def\goth{\mathfrak}
\def\concat{\;\hat{ }\;}
\def\UU{{\cal U}}
\def\VV{{\cal V}}
\def\uu{{\cal U}}
\def\vv{{\cal V}}
\def\mm{{\cal M}}
\def\ss{{\cal S}}
\def\ii{{\cal I}}
\def\qq{{\cal Q}}
\def\bor{{\rm Borel}}
\def\al{{\alpha}}
\def\emp{\emptyset}
\def\sm{\setminus}
\def\sub{\subseteq}
\def\be{\beta}
\def\closure{{\rm closure}}
\def\aa{{\cal A}}
\def\comp{\sim}
\def\seq{{\omega^{<\omega}}}
\def\bsp{\omega^\omega}
\def\rmiff{\mbox{ iff }}
\def\rmand{\mbox{ and }}
\def\rmor{\mbox{ or }}
\def\cross{\times}
\def\proj{{\rm proj}}
\def\cl{{\rm cl}}
\def\cc{{\cal C}}
\def\bb{{\cal B}}
\def\om{\omega}
\def\la{\langle}
\def\ra{\rangle}
\def\infsets{{[\omega]^\omega}}
\def\infsub#1{[#1]^{\omega}}
\def\conj{\mathop{\bigwedge\kern -6pt\bigwedge}}
\def\proof{\par\noindent proof:\par}
\def\res{\upharpoonright}
\def\qed{\nopagebreak\par\noindent\nopagebreak$\blacksquare$\par}
\def\moda{{\goth A}}
\def\modb{{\goth B}}
\def\finsets{[\omega]^{<\omega}}
\def\subend{{\subseteq_{end}}}
\def\finsub#1{[#1]^{<\omega}}
\def\claim{{\bigskip\par\noindent{\bf Claim.  }}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}

\begin{document}
\begin{center}
  Infinite Ramsey Theory\\
  Math 873\\
  Fall 1996\\
  A.Miller
\end{center}


\section{Ramsey's Theorem}

\def\note{\footnote{One of my colleagues told me about
the pidgeon head principal.  If you get into an elevator
and there are more buttons pressed than there are people
in the elevator, then there must be a pidgeon head.}}


Let $\om=\{0,1,2,\ldots\}$ and for any set $A$ and
$n\leq\om$ let
$$[A]^n=\{B\subseteq A: |B|=n\}$$
where $|B|$ is the cardinality of the set $B$.  So, for
example, $\infsets$, is the set of all infinite subsets of
$\om$.
\begin{theorem}
  (Pidgeon Hole Principal\note) Suppose $f:\om\to k$.  Then
  there exists $H\in\infsets$ such that $f\res H$ is
  constant.
\end{theorem}


\begin{theorem}
  Ramsey's Theorem (\cite{ramsey}) for any $m,k<\om$ and
  $f:[\om]^k\to m$ there exists $H\in\infsets$ such
  that $f\res [H]^k$ is constant.
\end{theorem}
\proof

The set $H$ is said to be homogeneous for the function $f$.

We begin with the standard proof for $k=2$.
Construct $a_0<a_1<...<a_{n-1}$ and $X_n\in\infsets$ as follows:

Let $a_n=\min\{X_{n-1}\}$ and find $X_n\in\infsub{X_{n-1}\setminus\{a_n\}}$
so that for every $a\leq a_n$ and $u,v\in X_n$
$$f(a,u)=f(a,v).$$

We can construct such a set
by iteratively applying the pidgeon hole principal as follows.
Note given any $a\in\om$ and $Y\in\infsets$ there is a $Z\in\infsub{Y}$
and $i<m$ such that for every $z\in Z$ we have $f(\{a,z\})=i$.
Now we just iterate this
$$X_{n-1}=Z_0\supseteq Z_1\supseteq Z_2 \ldots \supseteq Z_m=X_n$$
taking care of all $a\leq a_n$ (so $m=a_n+1$).

Finally consider the set $K=\{a_n:n\in\om\}$.  It is ``tail homogeneous'',
i.e., for any $u,v,w$ distinct elements of $K$ if
$u<v$ and $u<w$, then $f(u,v)=f(u,w)$.  Thus we can define
$g:K \to m$ by $g(u)=f(u,v)$ for any $v>u$ in $K$.
By the pidgeon hole principle there exists $H\in\infsub{K}$ such
that $g\res H$ is constant and therefore $f\res [H]^2$ is constant.

Instead of giving the standard proof for $k>2$ for novelty we give
a proof\footnote{This proof was found by my fellow graduate
student Charlie Gray (circa 1975) and is based on the idea of Simpson's
model theoretic proof of the Erdos-Rado Theorem.}
using model theory.  Let $f:[\om]^{k+1}\to m$ be any function.
Consider the model
$$\moda=(\om,<,f,\underline{n})_{n\in\om}.$$
By applying the compactness theorem we can find a model $\modb$
which is a proper elementary extension of $\moda$.  This means
it contains a ``hyperfinite'' integer $H$, i.e., an element of
the model $\modb$ satisfying $n<H$ for every $n\in\om$.
We construct a sequence $a_0<a_1<\ldots<a_n$ in $\om$ with the
following property:

For any $u_1<u_2<\ldots u_k\leq a_{n-1}$ we have that
$$f(u_1,\ldots,u_k,a_n)=f^{\modb}(u_1,\ldots,u_k,H).$$
This can be done, because if we define $i_{u_1,\ldots,u_k}<m$
by
$$f^\modb(u_1,\ldots,u_k,H)=i_{u_1,\ldots,u_k}$$
then
$$\modb\models \exists x > a_n \; \conj_{u_1<\ldots<u_k\leq a_{n-1}}
f(u_1,\ldots,u_k,x)= i_{u_1,\ldots,u_k}$$
(namely $x=H$) so by elementarity
$$\moda\models \exists x > a_n \; \conj_{u_1<\ldots<u_k\leq a_{n-1}}
f(u_1,\ldots,u_k,x)= i_{u_1,\ldots,u_k}$$
so now choose $a_n$ to be any such $x\in\om$.

Now our set $K=\{a_n:n\in\om\}$ is tail-homogeneous, i.e.,
given any $u_1<u_2<\ldots<u_k$ and $v,w >u_k$ in $K$
we have
$$f(u_1,\ldots,u_k,u)=f(u_1,\ldots,u_k,v)$$
(since both are equal to $f^{\modb}(u_1,\ldots,u_k,H)$).
As before, we define
$$g:[K]^{k+1}\to m \mbox{ by }
g(u_1,\ldots,u_k)=f^{\modb}(u_1,\ldots,u_k,H)$$ and apply
induction to $g$ to get $H\in\infsub{K}$ on which $g$ is
constant and then $f\res [H]^{k+1}$ is constant.
\qed

\begin{cor}
  Finite Ramsey Theorem. For any $m,k,h<\om$ there exists
  $N<\om$ such that for every  $f:[N]^k\to m$ there exists
  $H\in [N]^h$ such that $f\res [H]^k$ is constant.
\end{cor}
\proof
Suppose there is no such $N$ and let $f_N:[N]^k\to m$ be a
counterexample for each $N$.  Define
$$g:[\om]^{k+1}\to m \mbox{ by }
g(a_1,a_2,\dots,a_k,b)=f_b( a_1,a_2,\dots,a_k)$$
where $a_1<a_2<\ldots<a_k<b$.  By Ramsey's Theorem,
there exists $H\in\infsets$ such that
$g\res [H]^{k+1}$ is constant.  But if
$a_1<a_2<...<a_h<b$ are any $h+1$ elements of $H$
then $\{a_1,\ldots,a_h\}$ is a homogeneous set for
$f_b$, a contradiction.

There is another proof which works by invoking the compactness
theorem.
\qed

Ramsey's theorem is not a corollary of it's finite version.
This follows from the fact that there is a
recursive partition with no recursive homogeneous set,
a result due to Specker.  See, for example, Simpson
\cite{simprev},and Jockusch \cite{joc}.


\section{Galvin-Prikry Theorem}

Let $\uu\subset\infsets$ be arbitrary but fixed.  In what
follows lower case $s,t,\ldots$ letters will refer to
finite subsets of $\om$ and upper case letters $X,Y,\ldots$
to infinite subsets of $\om$.

Given $s\in\finsets$ and $Y\in\infsets$ define
\begin{itemize}
  \item $s\subend Y$ iff $s\subseteq Y$ and $\max(s)<\min(Y\setminus s)$,
  \item $[s,Y]=\{X\in\infsets: s\subend X\subseteq Y\cup s\}$,
  \item $Y$ accepts $s$ iff $[s,Y]\subseteq \uu$,
  \item $Y$ rejects $s$ iff $\neg\exists X\in\infsub{Y}\;\; X$ accepts $s$.
\end{itemize}

\begin{prop}
  If $Y$ accepts (rejects) $s$ and $X\in\infsub{Y}$, then
  $X$ accepts (rejects) $s$.
\end{prop}

\begin{prop}
  Given any $Y$ and $s$ there exists $X\in\infsub{Y}$ such that
  either $X$ accepts $s$ or $X$ rejects $s$.
\end{prop}

\begin{prop}
  Given any $Y$ and $s_1,s_2,\ldots,s_n$ there exists
  $X\in\infsub{Y}$ such that for each
  $i=1,\ldots,n$ either $X$ accepts $s_i$ or $X$ rejects $s_i$.
\end{prop}
\proof
Iterate, i.e., construct
$$Y=Y_0\supseteq Y_1\supseteq Y_2\ldots\supseteq Y_n=X$$
so that $Y_i$ either accepts $s_i$ or rejects $s_i$.
\qed


\begin{prop} \label{decisive}
  Given any $Y\in\infsets$ there exists $Z\in\infsub{Y}$ such
  that for every $s\in\finsub{Z}$ either
  $Z$ rejects $s$ or $Z$ accepts $s$.
\end{prop}
\proof
Construct $a_0<a_1<\ldots <a_n=\min(Y_n)$ with
$$Y=Y_0\supseteq Y_1\supseteq Y_2\supseteq \ldots$$
so that for every $n$ and $s\subseteq\{a_0,\ldots,a_n\}$
we have that $Y_{n+1}$ either rejects or accepts $s$.
Let $Z=\{a_n:n<\om\}$.  If $s\in\finsub{Z}$, then
let $a_n=\max(s)$.  By construction
$Y_{n+1}$ accepts or rejects $s$.  But
$[s,Z]=[s,Y_{n+1}]$ since $a_m\in Y_{n+1}$ for
all $m\geq n+1$.  It follows that
if $Y_{n+1}$ accepts $s$, then $Z$ accepts $s$; and
if $Y_{n+1}$ rejects $s$, then $Z$ rejects $s$.
\qed


Call such a $Z$ as in Proposition \ref{decisive} decisive.

\begin{prop} \label{reject}
  Suppose $Z$ is decisive and $Z$ rejects the empty set.
  Then there exists $Y\in\infsub{Z}$ such that $Y$
  rejects $s$ for every $s\in\finsub{Y}$.
\end{prop}

In order to prove this proposition we have the following claim.
\claim
  Suppose $Z$ is decisive and $Z$ rejects $t$ for every
  $t\subseteq s$.   Then for all but finitely many
  $n\in Z$, for every $t\subseteq s\cup\{n\}$ $Z$ rejects $t$.
\proof
Suppose not.  Then there are infinitely many $n\in Z$ such
that for some $s_n\subset s\cup\{n\}$  we have that
$Z$ accepts $s_n$.  Since $Z$ rejects all subsets of $s$ it
must be that $s_n=t_n\cup\{n\}$ for some  $t_n\subseteq s$.
Since $s$ is a finite set there must be
$Y\in\infsub{Z}$ and $t\subseteq s$ such that for
every $n\in Y$ we have that $Z$ accepts $t\cup\{n\}$
and hence $[t\cup\{n\},Z]\subseteq\uu$.
Without loss we may assume $\max(s)<\min(Y)$.
But
$$[t,Y]=\bigcup\{[t\cup\{n\},Y]: n\in Y\}$$
and
$$[t\cup\{n\},Y]\subseteq [t\cup\{n\},Z]\subseteq \uu.$$
This means that $Y$ accepts $t$.  But $Z$ rejects $t$.
Contradiction.
\qed

To prove the proposition construct
$$\{a_0,a_1,\ldots,a_{n-1}\}\subseteq Z$$
inductively so that $Z$ rejects every $t\subseteq \{a_0,a_1,\ldots,a_{n-1}\}$.
We can get started because $Z$ rejects the empty set.
Let $Y=\{a_0,a_1,\ldots\}$.
\qed

Define
\begin{itemize}
 \item $\uu\subseteq\infsets$ is Ramsey iff for every $X\in\infsets$ there
 exists $Y\in\infsub{X}$ such that either $\infsub{Y}\subseteq\uu$
 or $\infsub{Y}\cap\uu=\emptyset$,
 \item $\uu\subseteq\infsets$ is Completely Ramsey iff
 for every $X\in\infsets$ and $s\in\finsets$ there
 exists $Y\in\infsub{X}$ such that either $[s,Y]\subseteq\uu$
 or $[s,Y]\cap\uu=\emptyset$.
\end{itemize}

Since $\infsub{Y}=[\emptyset,Y]$ it is clear that Completely Ramsey
implies Ramsey. The usual topology on $\infsets$ is the topology
it inherits by being considered as follows:
$$\infsets\subseteq P(\om)\equiv 2^\om$$
A basic open set in the usual or product topology has the form,
$[s,\om]$.  The Ellentuck Topology has as its
basic open sets those of the form $[s,X]$ where
$s\in\finsets$ and $X\in\infsets$.  To be a basis (as opposed to
subbasis) it is neccessary that the intersection of any
two basic open sets is a union of basic open sets.

\begin{prop}
  Suppose $[s,X]$ and $[t,Y]$ are two basic open sets.  Then
  either they are disjoint or
  $$[s,X]\cap[t,Y]=[s\cup t,X\cap Y].$$
\end{prop}
\proof
If neither $s\subend t$ or $t\subend s$, then they are disjoint,
since then there are no $Z$ with $s\subend Z$ and $t\subend Z$.
So suppose $s\subend t$. Now if it is not true that
$(t\setminus s)\subseteq X$, then again they are disjoint, since
$t\subseteq Z$ for every $Z\in [t,Y]$.  Finally if
$X\cap Y$ is finite, then they are disjoint.  If none
of these things happen, then $s\cup t=t$, $t\setminus s\subseteq X$,
and both sides can described as the set of infinite $Z$ such that
$t\subend Z$ and $(Z\setminus t)\subseteq (X\cap Y)$.
\qed

\begin{lemma} \label{ramsey}
If $\uu$ is open in the Ellentuck Topology, then $\uu$ is Ramsey.
\end{lemma}
\proof
Given $X\in\infsets$ apply the Proposition \ref{decisive}
and find $Z\in\infsub{X}$ such $Z$ is decisive.  Now if
$Z$ accepts the empty set, then $\infsub{Z}=[\emptyset,Z]\subseteq\uu$ and
we are done. If $Z$ rejects the empty set, then apply
Proposition \ref{reject} and obtain $Y\in\infsub{Z}$ such
that $Y$ rejects all of its finite subsets. To finish
the proof it is enough to prove the following
\claim  $\infsub{Y}\cap \uu=\emp$.
\proof
If not, there is some $Z\in\infsub{Y}\cap\uu$.
In the Ellentuck topology the sets of the form
$[Z\cap n, Z]$ form a neighborhood basis for $Z$.
Since $\uu$ is open, it must be that for some $n$
$$Z\in [Z\cap n, Z]\subseteq\uu.$$
But this means that $Z$ accepts $Z\cap n$ contradicting the
fact that $Y$ rejects $Z\cap n$. \qed

\begin{lemma}
If $\uu$ is open in the Ellentuck Topology, then $\uu$ is Completely
Ramsey.
\end{lemma}
\proof
We can either say - just do the whole proof over again but
start with $[s,Y]$ instead of $[\emptyset,Y]$ or we can use
the following argument.

Fix $s$ and $Y$ with $\max(s)<\min(Y)$.
Let $h:\infsets\to[s,Y]$ be defined as follows.
Let $Y=\{y_n:n<\om\}$ be written in increasing order.
For each $X\in\infsets$ let $h(X)=s\cup\{y_n:n\in X\}$.
It is easy to check that $h$ is a homeomorphism in the
Ellentuck topology, in fact, it takes basic open sets
to basic open sets.  Let $\vv=h^{-1}(\uu)$.  Then
$\vv$ is open and hence by Lemma \ref{ramsey}
it is Ramsey, and so there exists $H\in\infsets$ such
that either $\infsub{H}\subseteq\vv$ or
$\infsub{H}\cap\vv=\emptyset$.  Let $Z=\{y_n:n\in H\}$.
Then either $[s,Z]\subseteq\uu$ or
$[x,Z]\cap\uu=\emptyset$. \qed

\begin{lemma}
  The Completely Ramsey sets form a $\sigma$-algebra, i.e.,
  a family of sets closed under taking compliments and taking
  countable unions.
\end{lemma}
\proof
It is easy to see that the compliment of a Completely Ramsey
set is Completely Ramsey.  It also easy to see that the union
of two Completely Ramsey sets is Completely Ramsey.  So
it suffices to prove that the countable union of an increasing
union of Completely Ramsey sets is Completely Ramsey.
Let $\uu=\cup_{n<\om}\uu_n$ be an increasing union of
Completely Ramsey sets. We begin by showing that $\uu$ is Ramsey.
The acceptance-rejection terminology is with respect to a
fixed background set $\vv$ so we write ``modulo $\vv$'' to indicate
which one.
For any $X\in\infsets$ there exists $Y\in\infsub{X}$ such that
either
\begin{itemize}
 \item $Y$ accepts the empty set modulo $\uu$, and so $\infsub{Y}\sub\uu$,
  or
 \item $Y$ rejects all of its finite subsets modulo $\uu$.
\end{itemize}
In the first case, we are done, so we must analize the second case.
If $Y$ rejects $s$ modulo $\uu$, then since $\uu_n$ is smaller
it must also reject $s$ modulo $\uu_n$.  But $\uu_n$ is
Completely Ramsey, so there must be $Z\in\infsub{Y}$ such
that
$$[s,Z]\cap \uu_n=\emptyset.$$
\begin{lemma}
  Suppose for every finite $s\in\infsub{Y}$, and $Z\in\infsub{Y}$,
  there exists $W\in\infsub{Z}$ such that $[s,Z]\cap \uu_n=\emptyset.$
  Then there exists $Z\in\infsub{Y}$ such that
  $$\infsub{Z}\cap(\cup_{n<\om}\uu_n)=\emptyset.$$
\end{lemma}
\proof
Construct $a_0<a_1<\ldots<a_{n-1}<a_n=\min{Y_n}$ with
$$Y=Y_0\supseteq Y_1\supseteq\ldots$$
Apply the hypothesis to obtain
$Y_{n+1}\in\infsub{Y_n}$ with the property that
$a_n<\min(Y_{n+1})$ and so that for every
$s\subseteq\{a_0,a_1,\ldots, a_{n}\}$
$$[s,Y_{n+1}]\cap \uu_n=\emptyset.$$
Now let $Z=\{a_n:n\in\om\}$.  We claim that:
$\infsub{Z}\cap(\cup_{n<\om}\uu_n)=\emptyset$. If not,
there exists $W\in\infsub{Z}\cap \uu_n$ for some $n$.
Since the $\uu_n$ are increasing, we may (by choosing $n$ larger,
$\uu_n$ is an increasing sequence)
assume that $a_n\in W$.  But then letting $s=W\cap (a_n+1)$
$$W\in [s,W]\subseteq [s,Y_{n+1}]$$
contradicting the fact that
$$[s,Y_{n+1}]\cap \uu_n=\emp.$$
\qed
This proves that the countable union of Completely Ramsey sets
is Ramsey.  The proof that it is Completely Ramsey is the same
but done by relativizing the entire argument to a
fixed $[s,Y]$.
\qed

\begin{cor} (Galvin-Prikry \cite{gp})  The Borel subsets \label{gpthm}
of $\infsets$ are Ramsey, i.e., for any
Borel set $B\subseteq \infsets$ there exists an
$H\in\infsets$ such that either $\infsub{H}\subseteq B$ or
$\infsub{H}\cap B=\emptyset$ .  In fact, the Borel subsets of
$\infsets$ in the Ellentuck topology are Completely Ramsey.
\end{cor}

Ramsey's Theorem is also a corollary of the Galvin-Prikry
Theorem.  Given $f:[\om]^n\to 2$ define
$B\subseteq \infsets$ by
$$B=\{X\in\infsets: f(\{x_1,\ldots,x_n\})=0\}$$
where $\{x_1,\ldots,x_n\}$ is the first $n$ elements $X$.
Then $B$ is Borel (in fact clopen) and a homogeneous set
for it, is homogeneous for $f$.


\section{Rosenthal's Theorem}

A sequence of subsets of a set $X$ $\langle A_n:n\in\om\rangle$
converges iff for any $x\in X$ we have that $x\in A_n$ for
all but finitely many $n$ or $x\notin A_n$ for all but
finitely many $n$.  This is the same as saying that the
characteristic functions are pointwise convergent.

A sequence of sets, $\langle A_n:n\in\om\rangle$,
is independent iff given any two disjoint finite
subsets of $\om$, $s$ and $t$ the set
$$(\bigcap_{n\in s} A_n)\cap (\bigcap_{n\in t} \comp{A_n})$$
is nonempty.  ($\comp{A_n}$ is the compliment of $A_n$ in
the set $X$.)

\begin{theorem}
(Rosenthal \cite{rosen})
Given $\la A_n:n\in\om\ra$, sequence of subsets of a set $X$,
there exists a $C\in\infsets$ such that either
$\langle A_n:n\in C\rangle$ is convergent or
$\langle A_n:n\in C\rangle$ is independent.
\end{theorem}

\proof
This proof was found by Farahat (see also Lindenstrauss
and Tzafriri \cite{lind} page 100.)
Define $\qq\subseteq \infsets$ by
$Y\in \qq$ iff
$Y=\{y_0<y_1<\ldots\}$ and for every $n\in\om$
$$A_0\cap \comp{A_1}\cap A_2\cap \comp{A_3}\cap\cdots
\cap \comp{A_{2n-1}}\cap A_{2n}\not=\emptyset.$$
That is, we take the compliment of every other one.
Then $\qq$ is a closed set.  Therefore, by the Galvin-Prikry Theorem,
there exists an infinite $H\subseteq \om$
such that either
\begin{enumerate}
  \item $\infsub{H}\subseteq \qq$ or
  \item $\infsub{H}\cap \qq=\emptyset$.
\end{enumerate}
In the second case take $C=H$.  Then it must be that
$\langle A_n:n\in H\rangle$ is convergent, otherwise we
could find $x\in X$ and an infinite subsequence
of $H$, say $K=\{k_0<k_1<\ldots\}$,
with $x\in A_{k_{2n}}$ and $x\notin A_{k_{2n+1}}$ for
each $n$, but then $K\in\qq$, contradiction.

In the first case, $\infsub{H}\subseteq \qq$,
let $H=\{h_n:n<\om\}$ and take
$$C=\{h_{2n+1}:n<\om\}.$$
Then $\langle A_n:n\in C\rangle$ is independent.
This is because, given any disjoint $s$ and $t$ in $\finsub{C}$,
we can find $K\in\infsub{H}$ (by filling in on
the even ones as needed) so that
$$s\subseteq\{h_{2n}:n<\om\} \rmand t\subseteq\{h_{2n+1}:n<\om\}.$$
But since $K\in\qq$ this implies
$$(\bigcap_{n\in s} A_n)\cap (\bigcap_{n\in t} \comp{A_n})\not=\emptyset.$$
\qed





\section{Ellentuck's Theorem}

Silver \cite{silver} generalized the Galvin-Prikry Theorem (Thm \ref{gpthm})
by showing the $\Sigma^1_1$ sets are Ramsey (in fact Completely Ramsey).
His proof was metamathematical.   Ellentuck \cite{ellen} gave
a more general and simplier proof of Silver's Theorem.

In order to state Ellentuck's result we begin by reviewing the
notion of Property of Baire or Baire Property. Let $X$ be any
topological space.
Define
\begin{itemize}
 \item $N\subseteq X$ is nowhere dense iff its closure has no interior.
    Or equivalently for any nonempty basic open set $U$ there exists a
    nonempty basic open set $V\subseteq U$ such that $V\cap N=\emptyset$.
 \item $M\subseteq X$ is meager iff $M$ is the countable union of
    nowhere dense subsets of $X$.  Meager is also refer to as
   ``first category'' in $X$.
 \item $G\subseteq X$ is comeager iff $X\setminus G$ is meager.
 \item $B\subseteq X$ has the Property of Baire iff there exists
    an open set $U$ and a meager set $M$ such that
    $$B=U\triangle M$$
    where $U\triangle M= (U\setminus M)\cup (M\setminus U)$ is
    the symmetric difference.  It equivalent to say
    $B\triangle U=M$.
\end{itemize}

Note that a set is nowhere dense iff its closure is nowhere dense.
Thus any meager set can be covered by a meager $F_\sigma$, i.e.,
a countable union of closed nowhere dense sets.  Also any
subset of a nowhere dense set is nowhere dense, and hence
the meager subsets of $X$ form a $\sigma$-ideal.  One terminology
for ``sets with the Baire Property'' is to refer to them as ``sets
which are almost open''.   Another equivalent definition is the
following: a set $B\subseteq X$ has the Baire property iff
there exists a comeager set $G$ and an open set $U$ such
that $B\cap G=U\cap G$.  Thus when we restrict $B$ to a comeager
subset, it is open.

\begin{theorem} (Baire)
 The sets with Property of Baire in $X$ form a $\sigma$-algebra,
 i.e., if $B$ has the Property of Baire then so does $X\setminus B$; and
 if $\langle B_n:n\in\om\rangle$ each have the Baire property,
 then so does $\cup_{n<\om}B_n$.
\end{theorem}
\proof

If $U$ is any open set let $V$ be the interior of $X\setminus U$ and note
that $X\setminus (U\cup V)$ is nowhere dense.  This is true because
for any nonempty open $W$ either $W$ meets $U$ (and so
$W\cap U\subseteq W$ is a nonempty open set missing $X\setminus (U\cup V)$)
or $W$ is disjoint from $U$ and hence contained in $V$, the
interior of the closed set $X\setminus U$, (and so
$W$ already misses $X\setminus (U\cup V)$).

Suppose $B\cap G=U\cap G$ where $U$ is open and $G$ is comeager.
Then
$$(X\setminus B)\cap G^\prime = V\cap G^\prime$$
where $V$ is the interior of $X\setminus U$ and
$G^\prime=G\cap (U\cup V)$ is comeager.

If $B_n\cap G_n=U_n\cap G_n$ where each $G_n$ is comeager and $U_n$ open,
then
$$(\cup_{n<\om}{B_n})\cap (\cap_{n<\om}G_n)=
(\cup_{n<\om}{U_n})\cap (\cap_{n<\om}G_n).$$
\qed

\begin{theorem} (Ellentuck \cite{ellen}) \label{ellenthm}
 A set $B\subseteq \infsets$ is Completely Ramsey iff
 it has the Baire Property in the Ellentuck topology.
\end{theorem}
\proof

This will follow easily from the following lemma:
\begin{lemma} \label{ellenlem}
 Any meager set in the Ellentuck topology is nowhere dense.
\end{lemma}

Before proving the Lemma let us deduce from it, Theorem \ref{ellenthm}.
Suppose that $\bb\subseteq \infsets$ is Completely Ramsey.  Let
$$\uu=\cup\{[s,X]: [s,X]\subseteq \bb\},$$
i.e., $\uu$ is the interior
of $\bb$ in the Ellentuck topology.  To see, that $\bb$ has the
property of Baire, it is enough to show that $\bb\setminus \uu$ is
nowhere dense.  Since $\uu$ is open it is Completely Ramsey, hence
$\bb\setminus \uu$ is Completely Ramsey.  Given any $[s,A]$ there
exists $B\in\infsub{A}$ such that either
$$[s,B]\subseteq (\bb\setminus \uu) \rmor [s,B]\cap
(\bb\setminus \uu)=\emptyset.$$
But the first cannot happen by the definition of $\uu$, so the second,
$[s,B]\cap (\bb\setminus \uu)=\emptyset$, must happen.  And since
$[s,A]$ is an arbitrary basic open set, it follows that
$\bb\setminus \uu$ is nowhere dense.

Conversely, suppose $\bb$ has the property of Baire in the Ellentuck
topology.  Then there exists an open set $\uu$ and meager set $\mm$
such that $\bb\triangle \uu\subseteq M$.  By Lemma \ref{ellenlem}
There is a closed nowhere dense $\cc$ with $\mm\subseteq \cc$.  Now
since open sets are Completely Ramsey, for
any $[s,X]$ there exists $Y\in\infsub{X}$ such that
$[s,Y]\subseteq \uu$ or $[s,Y]\cap \uu=\emptyset$.  Since closed
sets are Completely Ramsey, there exists $Z\in\infsub{Y}$
such that either
$[s,Z]\subseteq \cc$ or $[s,Z]\cap \cc=\emptyset$.  But
the first doesn't
happen, because $\cc$ is nowhere dense.  It follows
that $[s,Z]\subseteq \bb$ or $[s,Z]\cap \bb=\emptyset$ (according
to what was true for $\uu$).  And so $\bb$ is Completely Ramsey.

{\bf Proof of Lemma \ref{ellenlem}.  }  This proof is somewhat
analogous to the proof that the countable union of Completely
Ramsey sets is Completely Ramsey.  Suppose that
$\qq_n$ for $n\in\om$ are nowhere dense in the Ellentuck
topology.  Since their closures are also nowhere dense,
and the finite union of nowhere dense set is nowhere dense,
we may assume without loss that they are closed and increasing.
Since they are closed each $\qq_n$ is completely Ramsey.
Now given any $A\in\infsets$ we can construct a sequence
$$a_0<a_1<\ldots<a_{n-1}<\min(A_n)$$
as follows.  Let $A_0=A$.  Given
$$a_0<a_1<\ldots<a_n=\min(A_n)$$
find $A_{n+1}\subseteq A_n$ with
the property that for every $s\subseteq\{a_0,\ldots,a_n\}$
$$[s,A_{n+1}]\cap \qq_n=\emptyset.$$
Now consider $B=\{a_n:n<\om\}$.  We claim that
$$\infsub{B}\cap \cup_{n<\om}\qq_n.$$
If not, there exists $C$ and $n$ with $a_n\in C$
and $C\in\qq_n$.  But if
$$s=C\cap\{a_0,\ldots,a_n\}$$
then $C\in [s,A_{n+1}]$ contradicting the fact
that
$$[s,A_{n+1}]\cap \qq_n=\emptyset.$$
By relativizing this argument to any $[s,A]$ it
follows that $\cup_{n<\om}\qq_n$ is nowhere dense
and the lemma is proved.
\qed












\section{Souslin Operation}

The Souslin operation is the following.
Given $\{A_s:s\in\seq\}$ define
$$S\la A_s:s\in\seq\ra=
   \bigcup_{f\in\bsp}\cap_{n<\om}A_{f\res n}.$$
This is the Souslin operation also called operation A.
Given a family of sets $\aa$ define
$$\ss(\aa)=\{S\la A_s:s\in\seq\ra: \{ A_s:s\in\seq\}\sub\aa\}.$$
Typically $\aa$ is the family of all closed subsets of a topological
space $X$ and then $\ss(\aa)$ is known as the family of Souslin sets.

\begin{theorem} Let $\aa$ be an arbitrary family of sets. Then:
 \begin{enumerate}
    \item $\aa\sub\ss(\aa)$,
    \item $\ss(\aa)$ is closed under countable unions, i.e.,
    $X_n\in\ss(\aa)$ for each $n$ implies $\bigcup_{n<\om}X_n\in\ss(\aa)$,
    \item $\ss(\aa)$ is closed under countable intersections, and
    \item $\ss(\ss(\aa))=\ss(\aa).$
 \end{enumerate}
\end{theorem}
\proof
The first item is obvious, since if $A_s=A$ for all $s$ then
$$A=S\la A_s:s\in\seq\ra.$$
For countable unions,
note that
if $X_k=\bigcup_{f\in\bsp}\cap_{n<\om}A_{f\res n}^k$, then
$$\bigcup_{k<\om}X_k=\bigcup_{f\in\bsp}\cap_{n<\om}B_{f\res n}$$
where $B_s=A^{s(0)}_{\la s(1),\ldots,s(n)\ra}$ for each
$s\in \om^{n+1}$.

For countable intersections, a coding argument is required.
Let $\la n,m\ra\in\om$ be a bijective map between
$\om^2$ and $\om$ satisfying, $i<j$ implies
$\la k,i\ra < \la k,j\ra$.
Given $X_k=\bigcup_{f\in\bsp}\cap_{n<\om}A_{f\res n}^k$
then
$$\bigcap_{k<\om}X_k=\bigcup_{f\in\bsp}\cap_{n<\om}B_{f\res n}$$
where
$$B_s=A_t^k$$
where $t$ and $k$ are determined by $s$ as
follows.   Let $s=(s(0),\ldots,s(n))$, then $n=\la k,m\ra$
and $t=(t(0),\ldots,t(m))$
where $t(i)=s(\la k,i\ra)$
for each $i\leq m$.  This encoding is based on the
idea
$$\forall k\in\om\;\exists f\in\bsp \;\theta(f,k) \rmiff
\exists f\in\bsp \;\forall k\in\om \;\theta(f_k,k)$$
where $f_k(n)=f(\la k,n\ra)$.

The fact that $\ss(\ss(\aa))=\ss(\aa)$ is left to the reader,
see \cite{rodjay} for example.
\qed

Another way to define the Souslin sets is in terms of
the projection operation.

For $B\sub U\cross X$ let
$$\proj_X(B)=\{x\in X:\exists u\in U\;\; (u,x)\in B\}$$
For $\bb$ a family
of subsets of $U\cross X$ let
$$\proj_X(\bb)=\{\proj_X(B):B\in\bb\}.$$

For $X$ a topological space let $\cl(X)$ be the family
of closed subsets of $X$.

\begin{theorem} \label{proj}
  For any topological space $X$
  $$\proj_X(\cl(\bsp \cross X))=\ss(\cl(X))$$
\end{theorem}
\proof
If $B=\bigcup_{f\in\bsp}\cap_{n<\om}C_{f\res n}$ where
each $C_s$ is closed in $X$, then let
$$C=\{(f,x):\forall n<\om\;\; x\in C_{f\res n}\}\sub \bsp\cross X.$$
Then $C$ is closed and $B=\proj_X(C)$.

Suppose $B=\proj_X(C)$ where $C\sub \bsp\cross X$ is
closed.  For each $s\in\seq$ define
$$A_s=\closure(\{x\in X:\exists f\supseteq s \;(f,x)\in C\}).$$
We claim that
$$B=\bigcup_{f\in\bsp}\cap_{n<\om}A_{f\res n}.$$
If $x\in B=\proj_X(C)$, then for some $f\in\bsp$ we have
that $(f,x)\in C$ and therefore $x\in A_{f\res n}$ for each
$n\in\om$. Contrarywise, if $x\in S\la A_s:s\in\seq\ra$ then
for some $g\in\bsp$ for each $m<\om$
$$x\in \closure(\{x\in X:\exists f\supseteq g\res m \;\;(f,x)\in C\}).$$
But this implies that $(g,x)\in C$ since $C$ is closed and
therefore $(g,x)\notin C$ would imply that there exists
an $m$ and open $U\sub X$ with
$$(g,x)\in [g\res m]\cross U$$
and $[g\res m]\cross U$ disjoint from $C$, contradiction.
\qed

The Borel subsets of $X$, $\bor(X)$, is the smallest
$\sigma$-algebra containing the open subsets of $X$.

\begin{theorem}
  Suppose $X$ is a topological space and every closed subset
  of $X$ is a countable intersection of open sets.   (More
  generally, assume every open set is in $\ss(\cl(X))$).
  Then the following classes are all the same:
  \begin{enumerate}
    \item $\ss(\cl(X))$
    \item $\ss(\bor(X))$
    \item $\proj_X(\cl(\bsp \cross X))$
    \item $\proj_X(\bor(\bsp \cross X))$
  \end{enumerate}
\end{theorem}
\proof
Obviously (1) implies (2), (3) implies (4), and we already know (1) and
(3) are equivalent.  The fact that (2) implies (4) is proved similarly
to Theorem \ref{proj}.

So we only need to see that (4) implies (3):
Let $Y=\bsp\cross X$.  Then $\bor(Y)\sub \ss(\cl(Y))$.
This is true because $\ss(\cl(Y))$ is closed under countable
union and countable intersections and contains the closed
sets.   So it is enough to see that every open subset
of $Y$ is in $\ss(\cl(Y))$.  But (because $\bsp$ has countable
base) every open subset of $Y$ is a countable union of
open rectangles, i.e., set of the form $U\cross V$ where
$U\sub\bsp$ is open and $V\sub X$ is open.
It follows that
$$\proj_X(\bor(\bsp \cross X))\sub
  \proj_X(\proj_{\bsp\cross X}(\cl(\bsp\cross\bsp\cross X))
$$
$$ =
  \proj_X(\cl(\bsp\cross\bsp\cross X))=
  \proj_X(\cl(\bsp\cross X)).$$
\qed

This class of sets also includes
$\proj_X(\bor(Z\cross X))$ for all sufficiently nice $Z$.
For more on projective sets see Miller \cite{proj}.


Marczewski proved a general theorem which gives
a sufficient condition under which a $\sigma$-field is closed
under the Souslin operation.  A $\sigma$-field
$\bb$ of subsets of a set $X$ is a family of sets
closed under complimentation and countable unions

A $\sigma$-ideal $\ii$ in $\bb$ is a subfamily of
$\bb$ which is closed under countable unions and taking
subsets, i.e., if $Z\in \ii$ and $W\sub Z$ then $W\in \ii$.

\begin{theorem} \label{marcz}
  (Marczewski, See Kuratowski \cite{kur}) Suppose the $\sigma$-field
  $\bb$ on the set $X$ and a $\sigma$-ideal $\ii$ in $\bb$ satisfy
  the following minimal covering property:
\begin{quote}
  For every $Y\sub X$ there exists $B\in\bb$ such that
  $Y\sub B$ and for every $C\in \bb$ if
  $Y\sub C\sub B$, then $B\sm C\in \ii$.
\end{quote}
  Then $\ss(\bb)=\bb$, i.e., $\bb$ is closed under the
  Souslin operation.
\end{theorem}
\proof
Suppose $A_s\in \bb$ and
$$A=\bigcup_{f\in\bsp}\cap_{n<\om}A_{f\res n}.$$
For each $s\in\seq$ define
$$A^s=\bigcup_{s\sub f\in\bsp}\cap_{n<\om}A_{f\res n}.$$
Note
\begin{enumerate}
  \item $A=A^{\la\ra}$ where $\la\ra$ is the empty sequence,
  \item $A^s\sub A_s$,
  \item $A^s=\cup_{n<\om}A^{s\concat n}$
\end{enumerate}
Apply the minimal cover assumption to all $A^s$, to get $B_s\supseteq A^s$
with $B_s\in\bb$ a minimal cover.  Using (2) we may as well
assume $B_s\sub A_s$.  By using (3) we may replace
$B_{s\concat n}$ with $B_{s\concat n}\cap B_s$, so without
loss, we may assume $B_{s\concat n}\sub B_s$ for each
$s$ and $n$.  Now note that since
$$A^s=\cup_{n<\om}A^{s\concat n}\sub
\cup_{n<\om}B_{s\concat n}\sub B_s$$
we have that by the minimal cover property that
$$(B_s\sm \cup_{n<\om}B_{s\concat n})\in\ii.$$
To finish the proof, since $A=A^{\la\ra}$,
$A^{\la\ra}\sub B_{\la\ra}$ and $B_{\la\ra}\in\bb$, it
is enough to show $B_{\la\ra}\sm A^{\la\ra}\in \ii$.
$$B_{\la\ra}\sm A^{\la\ra}
 =
 B_{\la\ra}\sm (\bigcup_{f\in\bsp}\cap_{n<\om}A_{f\res n})
 \sub
 B_{\la\ra}\sm (\bigcup_{f\in\bsp}\cap_{n<\om}B_{f\res n})$$
This follows from the assumption
that $B_s\sub A_s$ so we are subtracking off a smaller
set.
$$
B_{\la\ra}\sm (\bigcup_{f\in\bsp}\cap_{n<\om}B_{f\res n})
\sub
\bigcup_{s\in\seq}(B_s \sm \cap_{n<\om}B_{s\concat n}).$$
Since the last set is in $\ii$ we are done.
This inclusion is true because if
$x$ not in
$\bigcup_{s\in\seq}(B_s \sm \cap_{n<\om}B_{s\concat n})$
then whenever $x\in B_s$ there is an $n<\om$ such
that $x\in B_{x\concat n}$.  Hence if $x\in B_{\la\ra}$
but not in $\bigcup_{s\in\seq}(B_s \sm \cap_{n<\om}B_{s\concat n})$
we can construct $f\in\bsp$ such that
$x$ is in $\cap_{n<\om}B_{f\res n}$. \qed

The two main examples for which Marczewski's result holds are
\begin{enumerate}
  \item $\bb$ is the family of sets with the property of
  Baire in some topological space $X$ and $\ii$ is the
  ideal of meager sets, and
  \item $\ii$ is a ccc ideal in $\bb$, i.e., there does not
  an uncountable disjoint family of sets in $\bb\sm\ii$.
\end{enumerate}
The second property holds, for example, when $\bb$ is the
family of  measurable sets and $\ii$ is the $\sigma$-ideal
of measure zero sets where $\mu$ is some finite countably
additive measure on $X$.

\begin{theorem}
  If $\ii$ is a ccc ideal in $\bb$, then
  they satisfy minimal cover property (see hypothesis of Theorem \ref{marcz}).
\end{theorem}
\proof
Given $Y\sub X$ arbitrary, try to construct disjoint
$B_\al$ as follows.  Given $B_\al:\al<\be$, consider if
there exists $B\in(\bb\sm \ii)$ such that
\begin{enumerate}
\item $B\cap A=\emp$ and
\item $B\cap B_\al=\emp$ for all $\al<\be$.
\end{enumerate}
If there is such a $B$ let $B_\be$ be any such.
If there is no such $B$ stop the construction.
Since $\ii$ is ccc the construction must eventually stop
at some countable stage $\be_0<\om_1$.  Let
$$B=X\sm (\cup_{\al<\be_0}B_\al).$$
Then $B$ is a minimal cover of $A$, because if
$A\sub C\sub B$ and $C\in\bb$, then if
$B\sm C\notin \ii$ it would be a candidate for
$B_{\be_0}$ which however never got defined.\qed

The obvious generalization of the above proof is
to $\kappa$-fields and $\kappa$-ideals and the
$\kappa^+$ chain condition.

\begin{theorem}
  If $\bb$ is the family of sets with the property of Baire in some
  topological space $X$ and $\ii$ the meager ideal, then
  they satisfy minimal cover property (as in Theorem \ref{marcz}).
\end{theorem}
\proof

\claim Suppose $\uu$ is family of open sets and for every
$U\in\uu$ we have that $Y\cap U$ is meager.  Then
$(\cup\uu)\cap Y$ is meager.
\proof
First assume the family $\uu$ is pairwise disjoint.  Then
for each $U\in\uu$ there would exists $N_n^U$ nowhere dense
so that
$$Y\cap U=\cup_{n<\om}N_n^U.$$
But because the $U\in\uu$ are disjoint it is easy to check
that each
$$N_n=\cup_{U\in\uu}N_n^U$$
is nowhere dense.

Given an arbitrary family of open sets $\uu$ let
$\vv$ be a maximal family of pairwise disjoint open sets
which refines $\uu$, i.e., for every $V\in \vv$ there
exists $U\in \uu$ with $V\sub U$.  So we know
by the first case that
$(\cup\vv)\cap Y$ is meager.  But the maximality assumtion
implies that
$\cup\uu\sm \cup\vv$ is nowhere dense, hence
$$(\cup\uu)\cap Y\sub(\cup\uu\sm \cup\vv)\;\;\cup\;\;
((\cup\vv)\cap Y)$$
is meager. This proves the Claim. \qed

Now to prove the theorem, let $Y\sub X$ be arbitrary and
put
$$\uu=\{U : U \mbox{ open  and } U\cap Y \mbox{ meager }\}.$$
Let
$$B=(X\sm (\cup\uu))\;\;\cup\;\; ((\cup\uu)\cap Y).$$
Then $B$ has the property of Baire since it is the union
of a closed set and a meager set.  Also $Y\sub B$.
If $Y\sub C\sub B$ and $C$ has the Baire property,
then so does $B\sm C$.  So let
$$B\sm C=(U\sm M_1)\cup M_2$$
where $U$ is open and $M_1,M_2$ are meager.  Since
$B\sm C$ is disjoint from $Y$, $U\cap Y\sub M_1$.
Hence $U\in\uu$.  It follows that
$$U\cap B \sub (\cup\uu)\cap Y$$
and therefore that $U$ is meager and so $B\sm C$
is meager.\qed

This result would follow trivially from the ccc case if $X$ had a countable
base, but in the case we are interested in, the Ellentuck topology,
the space is not second countable.

\begin{cor}
  (Silver \cite{silver}) Every $\Sigma_1^1$ set is Ramsey.
\end{cor}

\begin{thebibliography}{99}

\bibitem{ellen}
E.Ellentuck,
A new proof that analytic sets are Ramsey, J. Symbolic
Logic, 39(1974),163-165.

\bibitem{gp}
F.Galvin and K.Prikry,
Borel sets and Ramsey's theorem, J. Symbolic Logic, (1973)38, 193-198.

\bibitem{joc}
C.Jockusch, Ramsey's theorem and recursion theory, Journal
of Symbolic Logic, 37(1972), 268-280.


\bibitem{kur}
K.Kuratowski, {\bf Topology}, vol 1, Academic Press, (1966).

\bibitem{lind}
J.Lindenstrauss and L. Tzafriri, {\bf Classical Banach Spaces I, Sequence
Spaces}, Springer-Verlag, 1977.

\bibitem{proj}
A.Miller, Projective subsets of separable metric space,
Annals of Pure and Appliced Logic, 50(1990), 53-69.

\bibitem{ramsey}
F.P.Ramsey,
On a Problem of Formal Logic, Proceedings of the London Mathematical
Society, 30(1930), 264-286.

\bibitem{rodjay}
C.A.Rogers, J.E.Jayne, K-analytic sets, in {\bf Analytic Sets},
edited by C.A.Rogers, Academic Press 1980, 1-181.

\bibitem{rosen}
H.Rosenthal, A characterization of Banach spaces containing
$l_1$, Proceedings of the National Academy of Sciences (USA),
71(1974), 2411-2413.

\bibitem{silver}
J.Silver, Every analytic set is Ramsey, Journal of Symbolic Logic,
35(1970), 60-64.

\bibitem{simprev}
S.Simpson, Reverse Mathematics, in {\bf Recursion Theory,
Proceedings of Symposia in Pure Mathematics}, edited
by A.Nerode and R.Shore, American Mathematical Society,
42(1982), 461-472.



\end{thebibliography}

\end{document}