diff options
| -rw-r--r-- | lic_malinka.pdf | bin | 302220 -> 317498 bytes | |||
| -rw-r--r-- | lic_malinka.tex | 82 |
2 files changed, 76 insertions, 6 deletions
diff --git a/lic_malinka.pdf b/lic_malinka.pdf Binary files differindex 286d1e2..e25f4b6 100644 --- a/lic_malinka.pdf +++ b/lic_malinka.pdf diff --git a/lic_malinka.tex b/lic_malinka.tex index adaaf91..0f916db 100644 --- a/lic_malinka.tex +++ b/lic_malinka.tex @@ -49,9 +49,12 @@ \DeclareMathOperator{\Stab}{Stab}
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\Flim}{FLim}
+\DeclareMathOperator{\Int}{{Int}}
\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}
\newcommand{\cC}{\mathcal C}
+\newcommand{\cV}{\mathcal{V}}
+\newcommand{\cU}{\mathcal{U}}
\newcommand{\bN}{\mathbb N}
\newcommand{\bR}{\mathbb R}
\newcommand{\bZ}{\mathbb Z}
@@ -60,7 +63,6 @@ \DeclareMathOperator{\im}{{Im}}
\DeclareMathOperator{\lin}{{Lin}}
\DeclareMathOperator{\Th}{{Th}}
-\DeclareMathOperator{\Int}{{Int}}
\newtheorem{theorem}{Theorem}
\numberwithin{theorem}{section}
@@ -118,11 +120,11 @@ \end{definition}
\begin{definition}
- We say that $A$ is \emph{comeagre} in $X$ if it is a complement of a meager set. Equivalently, a set is comeagre iff it contains a countable intersection of open dense sets.
+ We say that $A$ is \emph{comeagre} in $X$ if it is a complement of a meagre set. Equivalently, a set is comeagre iff it contains a countable intersection of open dense sets.
\end{definition}
% \begin{example}
- Every countable set is nowhere dense in any $T_1$ space, so, for example, $\bQ$ is meager in $\bR$ (though being dense), which means that the set of irrationals is comeagre. Another example is...
+ Every countable set is nowhere dense in any $T_1$ space, so, for example, $\bQ$ is meagre in $\bR$ (though being dense), which means that the set of irrationals is comeagre. Another example is...
% \end{example}
\begin{definition}
@@ -138,7 +140,7 @@ \end{definition}
There is an important theorem on the Banach-Mazur game: $A$ is comeagre
- iff $II$ can always choose sets $V_0, V_1, \ldots$ such that it wins. Before we prove it we need to define notions necessary to formalize this theorem.
+ iff $II$ can always choose sets $V_0, V_1, \ldots$ such that it wins. Before we prove it we need to define notions necessary to formalise and prove the theorem.
\begin{definition}
$T$ is \emph{the tree of all legal positions} in the Banach-Mazur game $G^{\star\star}(A)$ when $T$ consists of all finite sequences $(W_0, W_1,\ldots, W_n)$, where $W_i$ are nonempty open sets such that $W_0\supseteq W_1\supseteq\ldots\supseteq W_n$. In another words, $T$ is a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$.
@@ -146,7 +148,6 @@ By $[T]$ we denote the set of all "infinite branches" of $T$, i.e. infinite sequences $(U_0, V_0, \ldots)$ such that $(U_0, V_0, \ldots U_n, V_n)\in T$ for any $n\in \bN$.
\end{definition}
-
\begin{definition}
A \emph{strategy} for $II$ in $G^{\star\star}(A)$ is a subtree $\sigma\subseteq T$ such that
\begin{enumerate}[label=(\roman*)]
@@ -156,7 +157,76 @@ \end{enumerate}
\end{definition}
- Intuitively, the strategy $\sigma$ works as follows: $I$ starts playing $U_0$ as any open subset of $X$, then $II$ plays unique (by (iii)) $V_0$ such that $(U_0, V_0)\in\sigma$. Then $I$ responds by playing any $U_1\subseteq V_0$ and $II$ plays uniqe $V_1$ such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc.
+ Intuitively, a strategy $\sigma$ works as follows: $I$ starts playing $U_0$ as any open subset of $X$, then $II$ plays unique (by (iii)) $V_0$ such that $(U_0, V_0)\in\sigma$. Then $I$ responds by playing any $U_1\subseteq V_0$ and $II$ plays uniqe $V_1$ such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc.
+
+ \begin{definition}
+ A strategy $\sigma$ is a \emph{winning strategy for $II$} if for any game $(U_0, V_0\ldots)\in [\sigma]$ (where $[\sigma]$ is defined analogically to $[T]$) player $II$ wins, i.e. $\bigcap_{n}V_n \subseteq A$.
+ \end{definition}
+
+ Now we can state the key theorem.
+
+ \begin{theorem}
+ \label{theorem:banach_mazur_thm}
+ Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is comeagre $\Leftrightarrow$ $II$ has a winning strategy in $G^{\star\star}(A)$.
+ \end{theorem}
+
+ In order to prove it we add an auxilary definition and lemma.
+ \begin{definition}
+ Let $S$ be a pruned subtree of a strategy $\sigma$ and let $p=(U_0, V_0,\ldots, V_n)\in S$. We say that S is \emph{comprehensive for p} if the family $\cV_p = \{V_{n+1}\mid (U_0, V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ (it may be that $n=-1$) is pairwise disjoint and $\bigcup\cV_p$ is dense in $V_n$.
+
+ We say that $S$ is \emph{comprehensive} if it is comprehensive for any $p=(U_0, V_0,\ldots, V_n)\in S$.
+ \end{definition}
+
+ \begin{lemma}
+ \label{lemma:comprehensive_lemma}
+ Let $S$ be a comprehensive pruned subtree of a strategy $\sigma$. Then:
+ \begin{enumerate}[label=(\roman*)]
+ \item For any $V_n$ such that there is $p=(U_0, V_0, \ldots, V_n)\in S$, this $p$ is unique.
+ \item Let $W_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$, i.e. $W_n$ is a family of all possible choices player $II$ can make in its $n$-th move. Then $\bigcup W_n$ is open and dense in $X$.
+ \item There exists such comprehensive $S\subseteq \sigma$.
+ \end{enumerate}
+ \end{lemma}
+
+ \begin{proof}
+ (i): Suppose that there are some $p = (U_0, V_0,\ldots, U_n, V_n)$, $p'=(U'_0, V'_0, \ldots, U'_n, V'_n)$ such that $V_n = V'_n$ and $p \neq p'$. Let $k$ be the smallest index such that those sequences differ. We have two possibilities:
+ \begin{itemize}
+ \item $U_k = U'_k$ and $V_k\neq V'_k$ -- this cannot be true simply by the fact that $S$ is a subset of a strategy.
+ \item $U_k\neq U'_k$: by the comprehensiveness of $S$ we know that for $q =(U_0, V_0, \ldots, U_{k-1}, V_{k-1})$ the set $\cV_q$ is pairwise disjoint. Thus $V_k\cap V'_k=\emptyset$, because $V_k, V'_k\in \cV_q$. But this leads to a contradiction -- $V_n$ cannot be a nonempty subset of both $V_k, V'_k$.
+ \end{itemize}
+
+ (ii): The lemma is proved by induction on $n$. For $n=0$ it follows trivially from the definition of comprehensiveness. Now suppose the lemma is true for $n$. Then the set $\bigcup_{V_n\in W_n}\bigcup\cV_{p_{V_n}}$ ($p_{V_n}$ is given uniquely from (i)) is dense and open in $X$ by the induction hypothesis. But $\bigcup W_{n+1}$ is its superset, thus $\bigcup W_{n+1}$ is dense and open in $X$.
+
+ (iii): We construct $S$ recursively as follows:
+ \begin{enumerate}
+ \item $\emptyset\in S$,
+ \item if $(U_0, V_0, \ldots, U_n)\in S$, then $(U_0, V_0, \ldots, U_n, V_n)\in S$ for the unique $V_n$ given by the strategy $\sigma$,
+ \item let $p = (U_0, V_0, \ldots, V_n)\in S$, let $U^\star_{n+1}$ be the unique set player $II$ whould play by $\sigma$ given that player $I$ played $U_{n+1}\subseteq V_n$. Now, by Zorn's Lemma, let $\cU_p$ be a maximal collection of nonempty open subsets $U_{n+1}\subseteq V_n$ such that the set $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$ is pairwise disjoint. Then put in $S$ all $(U_0, V_0, \ldots, V_{n}, U_{n+1}, U^\star_{n+1})$ such that $U_{n+1} \in \cU_p$. This way $S$ is comprehensive for $p$: the family $\cV_p = \{V_{n+1}\mid (U_0, V_0,\ldots, V_n, U_{n+1}, V_{n+1})\ S\}$ is exactly $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$, which is pairwise disjoint and $\bigcup\cV_p$ is obviously dense in $V_n$ by it's maximality -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint from $\bigcup\cU_p$, then the family $\cU_p\cup\{\tilde{U}_{n+1}\}$ violates the maximality of $\cU_p$.
+ \end{enumerate}
+ \end{proof}
+
+ Now we can move to the proof of the Banach-Mazur theorem.
+
+ \begin{proof}
+ $\Rightarrow$: Let $(A_n)$ be a sequence of dense open sets with $\bigcap_n A_n\subseteq A$. The simply $II$ plays $V_n = U_n\cap A_n$, which is nonempty by the denseness of $A_n$.
+
+ $\Leftarrow$: Suppose $II$ has a winning strategy $\sigma$. We will show that $A$ is comeagre. Suppose we have a comprehensive $S\subseteq \sigma$. We claim that $\mathcal{W} = \bigcap_n\bigcup W_n \subseteq A$. By \ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup W_n$ are open and dense, thus $A$ must be comeagre. Now we prove the claim.
+
+ (A.a.) Suppose there is $x\in \mathcal{W}$ that is not in $A$. We will prove by induction that for any $n$ there is exactly one $V_n\in W_n$ such that $x\in V_n$. For $n = 0$ this follows trivially by the comprehensiveness of $S$. Now suppose that there is exactly one $V_n\in W_n$ such that $x\in V_n$. By our assumption there is a $V'_{n+1}\in W_{n+1}$ such that $x\in V'_{n+1}$. By \ref{lemma:comprehensive_lemma} we have unique $p_{V'_{n+1}}=(U'_0, V'_0, \ldots, V'_{n+1})\in S$. It must be that $x\in V'_n$, so by the induction hypothesis $V'_n = V_n$, thus $V'_{n+1}\in \cV_{p_{V_{n}}}$. But the family $\cV_{p_{V_{n}}}$ is disjoint, hence $V_{n+1} = V'_{n+1}$ is unique.
+
+ Now the game $(U_0, V_0, U_1, V_1,\ldots) = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ where $x\in V_0, V_1,\ldots$ is not winning for player $II$, which contradicts the assumption that $\sigma$ is a winning strategy.
+ \end{proof}
+
+ Pytania:
+ \begin{itemize}
+ \item Czy da się coś zrobić, żeby $\mathcal{V}$ nie było takie brzydkie?
+ \item Jak to napisać, że się zrzyna z książki?
+ \item Dodatkowy przykład pod def 2.2
+ \item $G^{\star\star}(A)$ czy $G^{**}(A)$? Czy może $G^{**}(X, A)?$ Jakiś skrót na to?
+ \item w \ref{lemma:comprehensive_lemma} (i), jak to ładniej sformułować?
+ \item w \ref{lemma:comprehensive_lemma} (iii), może to wyodrębnić? Może to dać jako pierwsze, a pierwsze dwa później?
+ \item dodać tytuł do \ref{theorem:banach_mazur_thm}
+ \item czy w dowodzie twierdzenia napisać jeszcze raz co to jest $W_n$?
+ \end{itemize}
\subsection{Fraïssé classes}
\begin{fact}[Fraïssé theorem]
|