path: root/sections/preliminaries.tex

\documentclass[../lic_malinka.tex]{subfiles}

\begin{document}
  Before we get to the main work of the paper, we need to establish basic
  notions, known facts and theorems. This section provides a brief
  introduction to the theory of Baire spaces and category theory.
  Most of the notions are well known, interested reader may look at
  \cite{descriptive_set_theory}, \cite{maclane_1978}

  \subsection{Descriptive set theory}
  In this section we provide an important definition of a \emph{comeagre} set.
  It is purely topological notion, the intuition may come from the measure
  theory though. For example, in a standard Lebesuge measure on the 
  real interval $[0,1]$, the set of rationals is of measure $0$, although
  being a dense subset of the $[0,1]$. So, in a sense, the set of rationals
  is \emph{meagre} in the interval $[0,1]$. On the other hand, the set
  of irrational numbers is also dense, but have measure $1$, so it is
  \emph{comeagre}. 

  This is only a rough approximation of the topological 
  definition. The definitions are based on the Kechris' book \textit{Classical 
  Descriptive Set Theory} \cite{descriptive_set_theory}. One should look into
  it for more details and examples.

  \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}

  Every countable set is meagre in any $T_1$ space. So, $\bQ$
  is meagre in $\bR$ (although it is dense), which means that the set of
  irrationals is comeagre. The Cantor set is nowhere dense, hence meagre
  in the $[0,1]$ interval. 

  \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}

  Let $M$ be a structure. We define a topology on the automorphism group 
  $\Aut(M)$ by the basis of open sets: for a finite function
  $f\colon M\to M$ we have a basic open set 
  $[f]_{\Aut(M)} = \{g\in\Aut(M)\mid f\subseteq g\}$. This is a standard
  definition.

  \begin{fact}
	For a countable structure $M$, the topological space $\Aut(M)$ is a 
	Baire space.
  \end{fact}

  This is in fact a very weak statement, it is also true that $\Aut(M)$ is
  a Polish space (i.e. separable completely metrizable), and every Polish
  space is Baire. However, those additional properties are not important in
  this study.

  \begin{definition}
	\label{definition:generic_automorphism}
	Let $G = \Aut(M)$ be the automorphism group of structure $M$. We say
	that $f\in G$ is a \emph{generic automorphism}, if the conjugacy
	class of $f$ is comeagre in $G$.
  \end{definition}

  \begin{definition} 
	\label{definition:banach-mazur-game}
	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 \ref{theorem:banach_mazur_thm} 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$. 
  \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.

  We will often denote a sequence 
  $U_0 \supseteq V_0 \supseteq U_1 \supseteq V_1 \supseteq\ldots$ of open sets
  as \emph{an instance} of a Banach-Mazur game, or just simply by a \emph{game}.

  \begin{definition} 
    A strategy $\sigma$ is a \emph{winning strategy for $\textit{II}$} if for
    any instance $(U_0, V_0\ldots)\in [\sigma]$ of the Banach-Mazur game
	player $\textit{II}$ wins, i.e.
    $\bigcap_{n}V_n \subseteq A$.
  \end{definition}

  \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}
  
  The statement of the theorem is once again taken from Kechris 
  \cite{descriptive_set_theory} 8.33. However, the proof given in the book is 
  brief, thus we present a detailed version. In order to prove the 
  theorem 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 put $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
		move of player \textit{I} $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$.  
	  \end{enumerate}
	  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$).
	  \begin{enumerate}[resume, label=(\roman*)]
      \item  $\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 have 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$.  Then $\textit{II}$ simply 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 
	still will be valid (except for $\Rightarrow$, but its an easy fix --
    take for $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 arbitrary 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 a more 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 a collection of objects (denoted as
  $\Obj(\cC)$, but most often simply as $\cC$) and a collection of \emph{morphisms}
  $\Mor(A, B)$ between each pair of objects $A, B\in \cC$. We require that
  for each pair of morphisms $f\colon B\to C$, $g\colon A\to B$ there was a 
  morphism $f\circ g\colon A\to C$. If $f\colon A\to B$ then we say
  that $A$ is the domain of $f$ ($\dom{f}$) and that $B$ is the range of
  $f$ ($\rng{f}$).

  For every $A\in\cC$ there is an 
  \emph{identity morphism} $\id_A\colon A\to A$ 
  such that for any morphism $f\in \Mor(A, B)$
  we have that $f\circ id_A = \id_B \circ f$.

  We say that $f\colon A\to B$ is an \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 ``(homo)morphism`` 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)$ should hold.

  In category theory we distinguish \emph{covariant} and \emph{contravariant}
  functors. Here, we only consider 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}

  A 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}
	$\eta$ is function that assigns to each object $A$ of $\cC$ a morphism $\eta_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, "\eta_A"] \arrow[d, "F(f)"] & G(A) \arrow[d, "G(f)"] \\
		B & F(B) \arrow[r, "\eta_B"] & G(B) \\ 
      \end{tikzcd}
    \end{center}
  \end{definition}

  Natural transformation has, \textit{nomen omen}, natural properties. One
  particularly interesting to us is the following fact.

  \begin{fact}
	\label{fact:natural-automorphism}
	Let $\eta$ be a natural transformation of functors $F, G$ from category
	$\cC$ to $\cD$. Then $\eta$ is an isomorphism if and only if
	all of the component morphisms are isomorphisms.
  \end{fact}

  \begin{proof}
	Suppose that $\eta_{A}$ is an isomorphism for every $A\in\cC$, where 
	$\eta_{A}\colon F(A)\to G(A)$ is the morphism of the natural transformation
	corresponding to $A$. Then $\eta^{-1}$ is simply given by the morphisms
	$\eta^{-1}_A$.

	Now assume that $\eta$ is an isomorphism, i.e. $\eta^{-1}\circ\eta = \id_F$.
	\textit{Ad contrario} assume that there is $A\in\cC$ such that the component
	morphism $\eta_A\colon F(A)\to G(A)$ is not an isomorphism. It means
	that $\eta_A^{-1}\circ\eta_A \neq id_A$, hence 
	$F(A) = \dom(\eta^{-1}\circ\eta)(A) \neq \rng(\eta^{-1}\circ\eta)(A) = F(A)$,
	which is obviously a contradiction.
  \end{proof}

  \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[ul, "e"'] \arrow[ur, "f"] &
      \end{tikzcd}
    \end{center}
	
	is called a \emph{pushout diagram}.
  \end{definition}

  In both definitions of cospan and pushout diagrams we say that the object $C$
  is the \emph{base} of the diagram.

  \begin{definition}
	\label{definition:cospan_pushout}
	The \emph{cospan category} of category $\cC$, referred to as $\Cospan(\cC)$,
	is the category of cospan diagrams of $\cC$, where morphisms between
	two cospans are natural transformations of the underlying functors.

	We define \emph{pushout category} analogously and call it $\Pushout(\cC)$.
  \end{definition}

  From now on we work in subcategories of cospan diagrams and pushout diagrams
  where we fix the base structure. Formally, for a fixed
  $C\in\cC$, category $\Cospan_C(\cC)$ is the category of all cospans in 
  $\Cospan(\cC)$ such that the base of the diagram is $C$. 
  Natural transformation $\eta$ of two diagrams in $\Cospan_C(\cC)$ are 
  such that 
  the morphism $\eta_C\colon C\to C$ is an automorphism of $C$. 
  $\Pushout_C(\cC)$ is defined analogously. In most contexts we consider 
  only one base structure, 
  hence we will often write $\Pushout(\cC)$ instead of $\Pushout_C(\cC)$.
\end{document}