From 6423bfc8e832c6925074bee71d69b54b862ecf1b Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 15 Feb 2022 21:08:55 +0100 Subject: Poprawki banacha mazura --- lic_malinka.pdf | Bin 317761 -> 316808 bytes lic_malinka.tex | 110 ++++++++++++++++++++++++++++++++++---------------------- 2 files changed, 68 insertions(+), 42 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index a83d3d3..bc6add8 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ diff --git a/lic_malinka.tex b/lic_malinka.tex index b1906c8..24e3008 100644 --- a/lic_malinka.tex +++ b/lic_malinka.tex @@ -124,7 +124,7 @@ \end{definition} % \begin{example} - 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... + Every countable set is meagre 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} @@ -136,54 +136,75 @@ \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 $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 $II$ wins the game if $\bigcap_{n}V_n \subseteq A$. + 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 - 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. + iff $\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 another words, $T$ is a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$. - 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} + We say that $\sigma$ is \emph{a pruned subtree} of the tree of all legal positions $T$ if $\sigma\subseteq T$ and 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$). + \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 $II$ in $G^{\star\star}(A)$ is a subtree $\sigma\subseteq T$ such that + 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, V_n)\in\sigma$, then for all open nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, V_n, U_{n+1})\in\sigma$, - \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for unique $V_n$, $(U_0, V_0, \ldots, U_{n}, V_n)\in\sigma$. + \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 $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 $\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 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$. + 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} + \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$ $II$ has a winning strategy in $G^{\star\star}(A)$. + 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 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$, which means $p=\emptyset$) is pairwise disjoint and $\bigcup\cV_p$ is dense in $V_n$ (where we think that $V_{-1} = X$). + 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 any $p=(U_0, V_0,\ldots, V_n)\in S$. + 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 winnig 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 its 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}\}$ would violate the maximality of $\cU_p$. + \qedhere + \end{enumerate} + \end{proof} + \begin{lemma} \label{lemma:comprehensive_lemma} - Let $S$ be a comprehensive pruned subtree of a strategy $\sigma$. Then: + Let $S$ be a nonempty 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 $S$. + \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} @@ -194,40 +215,45 @@ \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$. + (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 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$ would 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})$ 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 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} + (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 chosed $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} - $\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$. + \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 $II$ has a winning strategy $\sigma$. We will show that $A$ is comeagre. Take 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. + $\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. - (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. + 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} - 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$? - \item ostatni akapit dowodu twierdzenia, czy taka suma tych $p_{V_n}$ to jest sensowny napis? Jak to inaczej napisać? - \end{itemize} + % 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 DONE W/E $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 DONE dodać tytuł do \ref{theorem:banach_mazur_thm} + % \item czy w dowodzie twierdzenia napisać jeszcze raz co to jest $W_n$? + % \item DONE TAK ostatni akapit dowodu twierdzenia, czy taka suma tych $p_{V_n}$ to jest sensowny napis? Jak to inaczej napisać? + % \end{itemize} + + % Odpowiedzi: + % \begin{itemize} + % % \item dodać osobną definicję na $[\sigma]$ (tzn dla dowolnego poddrzewa). + % \item $II$ -> $\mathit{II}$ + % \item w ogóle dodać def poddrzewa (co to znaczy pruned?) + % \item w \ref{lemma:comprehensive_lemma} (i) zmienić na "dla każdego otwartego podzbioru X jest co najwyżej jedno takie p" + % \item powiedzieć że S musi być niepuste + % \item w \ref{lemma:comprehensive_lemma} zamienić kolejność w pierwszym zdaniu gwiazdki z nie-gwiazdką + % \item zmienić $W_n -> S_n$ + % \item rozwinąć \ref{lemma:comprehensive_lemma} (ii), poza tym $W_{n+1}$ jest dokładnie równy, a nie tylko superset, dodać kwantyfikator na n, a może wplecić jeszcze to że te rodziny $W_n$ też są rozłączne? + % \end{itemize} \subsection{Fraïssé classes} \begin{fact}[Fraïssé theorem] -- cgit v1.2.3