diff options
Diffstat (limited to 'sections/preliminaries.tex')
| -rw-r--r-- | sections/preliminaries.tex | 347 |
1 files changed, 347 insertions, 0 deletions
diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex new file mode 100644 index 0000000..832beae --- /dev/null +++ b/sections/preliminaries.tex @@ -0,0 +1,347 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + \subsection{Descriptive set theory} + \begin{definition} + Suppose $X$ is a topological space and $A\subseteq X$. + We say that $A$ is \emph{meagre} in $X$ if $A = \bigcup_{n\in\bN}A_n$, + where $A_n$ are nowhere dense subsets of $X$ (i.e. $\Int(\bar{A_n}) + = \emptyset$). + \end{definition} + + \begin{definition} + We say that $A$ is \emph{comeagre} in $X$ if it is + a complement of a meagre set. Equivalently, a set is comeagre if and only if it + contains a countable intersection of open dense sets. + \end{definition} + + % \begin{example} + Every countable set is meagre in any $T_1$ space, so, for example, $\bQ$ + is meagre in $\bR$ (although it is dense), which means that the set of + irrationals is comeagre. Another example is... + % \end{example} + + \begin{definition} + We say that a topological space $X$ is a \emph{Baire space} if every + comeagre subset of $X$ is dense in $X$ (equivalently, every meagre set has + empty interior). + \end{definition} + + \begin{definition} + Suppose $X$ is a Baire space. We say that a property $P$ \emph{holds + generically} for a point $x\in X$ if $\{x\in X\mid P\textrm{ holds for + }x\}$ is comeagre in $X$. + \end{definition} + + \begin{definition} + Let $X$ be a nonempty topological space and let + $A\subseteq X$. The \emph{Banach-Mazur game of $A$}, denoted as + $G^{\star\star}(A)$ is defined as follows: Players $I$ and + $\textit{II}$ take turns in playing nonempty open sets $U_0, V_0, + U_1, V_1,\ldots$ such that $U_0 \supseteq V_0 \supseteq U_1 \supseteq + V_1 \supseteq\ldots$. We say that player $\textit{II}$ wins the game if + $\bigcap_{n}V_n \subseteq A$. + \end{definition} + + There is an important theorem on the Banach-Mazur game: $A$ is comeagre + if and only if $\textit{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 other words, $T$ is + a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$. + \end{definition} + + \begin{definition} + We say that $\sigma$ is \emph{a pruned subtree} of the tree of all legal + positions $T$ if $\sigma\subseteq T$, for any $(W_0, W_1, \ldots, + W_n)\in\sigma, n\ge 0$ there is a $W$ such that $(W_0, W_1,\ldots, W_n, + W)\in\sigma$ (it simply means that there's no finite branch in~$\sigma$) and + $(W_0, W_1,\ldots W_{n-1})\in\sigma$ (every node on a branch is in $\sigma$). + \end{definition} + + \begin{definition} + Let $\sigma$ be a pruned subtree of the tree of all legal positions $T$. By + $[\sigma]$ we denote \emph{the set of all infinite branches of $\sigma$}, + i.e. infinite sequences $(W_0, W_1, \ldots)$ such that $(W_0, W_1, \ldots + W_n)\in \sigma$ for any $n\in \bN$. + \end{definition} + + \begin{definition} + A \emph{strategy} for $\textit{II}$ in + $G^{\star\star}(A)$ is a pruned subtree $\sigma\subseteq T$ such that + \begin{enumerate}[label=(\roman*)] + \item $\sigma$ is nonempty, + \item if $(U_0, V_0, \ldots, U_n, V_n)\in\sigma$, then for all open + nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, U_n, V_n, + U_{n+1})\in\sigma$, + \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for a unique $V_n$, + $(U_0, V_0, \ldots, U_{n}, V_n)\in\sigma$. + \end{enumerate} + \end{definition} + + Intuitively, a strategy $\sigma$ works as follows: $I$ starts playing + $U_0$ as any open subset of $X$, then $\textit{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 $\textit{II}$ plays unique $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 $\textit{II}$} if for + any game $(U_0, V_0\ldots)\in [\sigma]$ player $\textit{II}$ wins, i.e. + $\bigcap_{n}V_n \subseteq A$. + \end{definition} + + Now we can state the key theorem. + + \begin{theorem}[Banach-Mazur, Oxtoby] + \label{theorem:banach_mazur_thm} + Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is + comeagre $\Leftrightarrow$ $\textit{II}$ has a winning strategy in + $G^{\star\star}(A)$. + \end{theorem} + + In order to prove it we add an auxiliary definition and lemma. + \begin{definition} + Let $S\subseteq\sigma$ be a pruned subtree of tree of all legal positions + $T$ 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$, which + means $p=\emptyset$) is pairwise disjoint and $\bigcup\cV_p$ is dense in + $V_n$ (where we think that $V_{-1} = X$). + We say that $S$ is \emph{comprehensive} if it is comprehensive for + each $p=(U_0, V_0,\ldots, V_n)\in S$. + \end{definition} + + \begin{fact} + If $\sigma$ is a winning strategy for $\mathit{II}$ then + there exists a nonempty comprehensive $S\subseteq\sigma$. + \end{fact} + + \begin{proof} + 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$. For a possible player $I$'s + move $U_{n+1}\subseteq V_n$ let $U^\star_{n+1}$ be the unique set + player $\mathit{II}$ would respond with by $\sigma$. 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})$ 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})\in 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 the maximality of $\cU_p$ + -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint + from $\bigcup\cV_p$, then $\tilde{U}^{\star}_{n+1}\subseteq + \tilde{U}_{n+1}$ would be also disjoint from $\bigcup\cV_p$, so the + family $\cU_p\cup\{\tilde{U}_{n+1}\}$ would violate the maximality of + $\cU_p$. + \qedhere + \end{enumerate} + \end{proof} + + \begin{lemma} + \label{lemma:comprehensive_lemma} + Let $S$ be a nonempty comprehensive pruned subtree of a strategy $\sigma$. + Then: + \begin{enumerate}[label=(\roman*)] + \item For any open $V_n\subseteq X$ there is at most one $p=(U_0, V_0, + \ldots, U_n, V_n)\in S$. + \item Let $S_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$ for $n\in\bN$ + (i.e. $S_n$ is a family of all possible choices player $\textit{II}$ + can make in its $n$-th move according to $S$). Then $\bigcup S_n$ is + open and dense in $X$. + \item $S_n$ is a family of pairwise disjoint sets. + \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 (so $V_k$ is unique for + $U_k$). \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 + S_n}\bigcup\cV_{p_{V_n}}$ (where $p_{V_n}$ is given uniquely from + (i)) is dense and open in $X$ by the induction hypothesis. But + $\bigcup S_{n+1}$ is exactly this set, thus it is dense and open in + $X$. + + (iii): We will prove it by induction on $n$. Once again, the case $n + = 0$ follows from the comprehensiveness of $S$. Now suppose that the + sets in $S_n$ are pairwise disjoint. Take some $x \in V_{n+1}\in + S_{n+1}$. Of course $\bigcup S_n \supseteq \bigcup S_{n+1}$, thus by + the inductive hypothesis $x\in V_{n}$ for the unique $V_n\in S_n$. It + must be that $V_{n+1}\in \cV_{p_{V_n}}$, because $V_n$ is the only + superset of $V_{n+1}$ in $S_n$. But $\cV_{p_{V_n}}$ is disjoint, so + there is no other $V'_{n+1}\in \cV_{p_{V_n}}$ such that $x\in + V'_{n+1}$. Moreover, there is no such set in + $S_{n+1}\setminus\cV_{p_{V_n}}$, because those sets are disjoint from + $V_{n}$. Hence there is no $V'_{n+1}\in S_{n+1}$ other than $V_n$ + such that $x\in V'_{n+1}$. We've chosen $x$ and $V_{n+1}$ arbitrarily, + so $S_{n+1}$ is pairwise disjoint. + \end{proof} + + Now we can move to the proof of the Banach-Mazur theorem. + + \begin{proof}[Proof of theorem \ref{theorem:banach_mazur_thm}] + $\Rightarrow$: Let $(A_n)$ be a sequence of dense open sets with + $\bigcap_n A_n\subseteq A$. The simply $\textit{II}$ plays $V_n + = U_n\cap A_n$, which is nonempty by the denseness of $A_n$. + + $\Leftarrow$: Suppose $\textit{II}$ has a winning strategy $\sigma$. + We will show that $A$ is comeagre. Take a comprehensive $S\subseteq + \sigma$. We claim that $\mathcal{S} = \bigcap_n\bigcup S_n \subseteq + A$. By the lemma~\ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup + S_n$ are open and dense, thus $A$ must be comeagre. Now we prove the + claim towards contradiction. + + Suppose there is $x\in \mathcal{S}\setminus A$. By the lemma + \ref{lemma:comprehensive_lemma}, (iii) for any $n$ there is unique + $x\in V_n\in S_n$. It follows that $p_{V_0}\subset + p_{V_1}\subset\ldots$. Now the game $(U_0, V_0, U_1, V_1,\ldots) + = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ is not winning for + player $\textit{II}$, which contradicts the assumption that $\sigma$ is + a winning strategy. \end{proof} + + \begin{corollary} + \label{corollary:banach-mazur-basis} + If we add a constraint to the Banach-Mazur game such that players can only + choose basic open sets, then the theorem \ref{theorem:banach_mazur_thm} + still suffices. + \end{corollary} + + \begin{proof} + If one adds the word \textit{basic} before each occurrence + of word \textit{open} in previous proofs and theorems then they all + will still be valid (except for $\Rightarrow$, but its an easy fix -- + take $V_n$ a basic open subset of $U_n\cap A_n$). + \end{proof} + + This corollary will be important in using the theorem in practice -- + it's much easier to work with basic open sets rather than any open + sets. + + \subsection{Category theory} + + In this section we will give a short introduction to the notions of + category theory that will be necessary to generalize the key result of the + paper. + + We will use a standard notation. If the reader is interested in detailed + introduction to the category theory, then it's recommended to take a look + at \cite{maclane_1978}. Here we will shortly describe the standard notation. + + A \emph{category} $\cC$ consists of the collection of objects (denoted as + $\Obj(\cC)$, but most often simply as $\cC$) and collection of \emph{morphisms} + $\Mor(A, B)$ between each pair of objects $A, B\in \cC$. We require that + for each morphisms $f\colon B\to C$, $g\colon A\to B$ there is a morphism + $f\circ g\colon A\to C$. For every $A\in\cC$ there is an + \emph{identity morphism} $\id_A$ such that for any morphism $f\in \Mor(A, B)$ + it follows that $f\circ id_A = \id_B \circ f$. + + We say that $f\colon A\to B$ is \emph{isomorphism} if there is (necessarily + unique) morphism $g\colon B\to A$ such that $g\circ f = id_A$ and $f\circ g = id_B$. + Automorphism is an isomorphism where $A = B$. + + A \emph{functor} is a ``homeomorphism`` of categories. We say that + $F\colon\cC\to\cD$ is a functor + from category $\cC$ to category $\cD$ if it associates each object $A\in\cC$ + with an object $F(A)\in\cD$, associates each morphism $f\colon A\to B$ in + $\cC$ with a morphism $F(f)\colon F(A)\to F(B)$. We also require that + $F(\id_A) = \id_{F(A)}$ and that for any (compatible) morphisms $f, g$ in $\cC$ + $F(f\circ g) = F(f) \circ F(g)$. + + In category theory we distinguish \emph{covariant} and \emph{contravariant} + functors. Here, we only consider \emph{covariant functors}, so we will simply + say \emph{functor}. + + \begin{fact} + \label{fact:functor_iso} + Functor $F\colon\cC\to\cD$ maps isomorphism $f\colon A\to B$ in $\cC$ + to the isomorphism $F(f)\colon F(A)\to F(B)$ in $\cD$. + \end{fact} + + Notion that will be very important for us is a ``morphism of functors`` + which is called \emph{natural transformation}. + \begin{definition} + Let $F, G$ be functors between the categories $\cC, \cD$. A \emph{natural + transformation} + $\tau$ is function that assigns to each object $A$ of $\cC$ a morphism $\tau_A$ + in $\Mor(F(A), G(A))$ such that for every morphism $f\colon A\to B$ in $\cC$ + the following diagram commutes: + + \begin{center} + \begin{tikzcd} + A \arrow[d, "f"] & F(A) \arrow[r, "\tau_A"] \arrow[d, "F(f)"] & G(A) \arrow[d, "G(f)"] \\ + B & F(B) \arrow[r, "\tau_B"] & G(B) \\ + \end{tikzcd} + \end{center} + \end{definition} + + \begin{definition} + In category theory, a \emph{diagram} of type $\mathcal{J}$ in category $\cC$ + is a functor $D\colon \mathcal{J}\to\cC$. $\mathcal{J}$ is called the + \emph{index category} of $D$. In other words, $D$ is of \emph{shape} $\mathcal{J}$. + + For example, $\mathcal{J} = \{-1\leftarrow 0 \rightarrow 1\}$, then a diagram + $D\colon\mathcal{J}\to \cC$ is called a \emph{cospan}. For example, + if $A, B, C$ are objects of $\cC$ and $f\in\Mor(C, A), g\in\Mor(C, B)$, then + the following diagram is a cospan: + + \begin{center} + \begin{tikzcd} + A & & B \\ + & C \arrow[ur, "g"'] \arrow[ul, "f"] & + \end{tikzcd} + \end{center} + \end{definition} + + From now we omit explicit definition of the index category, as it is easily + referable from a picture. + + \begin{definition} + Let $A, B, C, D$ be objects in the category $\cC$ with morphisms + $e\colon C\to A, f\colon C\to B, g\colon A\to D, h\colon B\to D$ such + that $g\circ e = h\circ f$. + Then the following diagram: + \begin{center} + \begin{tikzcd} + & D & \\ + A \arrow[ur, "g"] & & B \arrow[ul, "h"'] \\ + & C \arrow[ur, "e"'] \arrow[ul, "f"] & + \end{tikzcd} + \end{center} + + is called a \emph{pushout} diagram + \end{definition} + + \begin{definition} + The \emph{cospan category} of category $\cC$, refered to as $\Cospan(\cC)$, + is the category of cospan diagrams of $\cC$, where morphisms between + two cospans are normal transformations of the underlying functors. + + We define \emph{pushout category} analogously and call it $\Pushout(\cC)$. + \end{definition} + + TODO: dodać tu przykład? +\end{document} |