Zmiana struktury, teraz osobne pliki na każdą sekcję

4 files changed, 1054 insertions, 0 deletions

diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex
new file mode 100644
index 0000000..8beace0
--- /dev/null
+++ b/sections/conj_classes.tex
@@ -0,0 +1,251 @@
+\documentclass[../lic_malinka.tex]{subfiles}
+
+\begin{document}
+  Let $M$ be a countable $L$-structure. We define a topology on the $G=\Aut(M)$:
+  for any finite function $f\colon M\to M$ we have a basic open set 
+  $[f]_{G} = \{g\in G\mid f\subseteq g\}$.  
+
+  \subsection{Prototype: pure set} 
+
+  In this section, $M=(M,=)$ is an infinite countable set (with no structure
+  beyond equality).
+  
+  \begin{proposition} 
+	\label{proposition:cojugate-classes}
+	If $f_1,f_2\in \Aut(M)$, then $f_1$ and $f_2$ are conjugate if and only 
+    if for each $n\in \bN\cup \{\aleph_0\}$, $f_1$ and $f_2$ have the same 
+    number of orbits of size $n$.
+  \end{proposition}
+
+  \begin{theorem}
+	Let $\sigma\in \Aut(M)$ be an automorphism with no infinite orbit and with
+	infinitely many orbits of size $n$ for every $n>0$. Then the conjugacy
+	class of $\sigma$ is comeagre in $\Aut(M)$.
+  \end{theorem}
+
+  \begin{proof}
+	We will show that the conjugacy class of $\sigma$ is an intersection of countably
+	many comeagre sets. 
+
+	Let $A_n = \{\alpha\in Aut(M)\mid \alpha\text{ has infinitely many orbits of size }n\}$.
+	This set is comeagre for every $n>0$. Indeed, we can represent this set
+	as an intersection of countable family of open dense sets. Let $B_{n,k}$
+	be the set of all finite functions $\beta\colon M\to M$ that consists
+	of exactly $k$ distinct $n$-cycles. Then:
+	\begin{align*}
+	  A_n &= \{\alpha\in\ \Aut(M) \mid \alpha\text{ has infinitely many orbits of size }n\} \\
+		  &= \bigcap_{k=1}^{\infty} \{\alpha\in \Aut(M)\mid \alpha\text{ has at least }k\text{ orbits of size }n\} \\ 
+		  &= \bigcap_{k=1}^{\infty} \bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)},
+	\end{align*}
+	where indeed, $\bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)}$ is dense in
+	$\Aut(M)$: take any finite $\gamma\colon M\to M$ such that $[\gamma]_{\Aut(M)}$
+	is nonempty. Then also 
+	$\bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)}\cap[\gamma]_{\Aut(M)}\neq\emptyset$,
+	one can easily construct a permutation that extends $\gamma$ and have at least
+	$k$ many $n$-cycles.
+
+	Now we see that $A = \bigcap_{n=1}^{\infty} A_n$ is a comeagre set consisting
+	of all functions that have infinitely many $n$-cycles for each $n$. The only
+	thing left to show is that the set of functions with no infinite cycle is 
+	also comeagre. Indeed, for $m\in M$ let 
+	$B_m = \{\alpha\in\Aut(M)\mid m\text{ has finite orbit in }\alpha\}$. This 
+	is an open dense set. It is a sum over basic open sets generated by finite
+	permutations with $m$ in their domain. Denseness is also easy to see.
+
+	Finally, by the proposition \ref{proposition:cojugate-classes}, we can say that 
+	$$\sigma^{\Aut(M)}=\bigcap_{n=1}^\infty A_n \cap \bigcap_{m\in M} B_m,$$
+	which concludes the proof.
+  \end{proof}
+
+  \subsection{More general structures}
+
+  \begin{fact} 
+	\label{fact:conjugacy}
+    Suppose $M$ is an arbitrary structure and $f_1,f_2\in \Aut(M)$. 
+    Then $f_1$ and $f_2$ are conjugate if and only if $(M,f_1)\cong
+    (M,f_2)$ as structures with one additional unary relation that is
+    an automorphism.  
+  \end{fact}
+
+  \begin{proof}
+    Suppose that $f_1 = g^{-1}f_2g$ for some $g\in \Aut(M)$. 
+    Then $g$ is the automorphism we're looking for. On the other hand if 
+    $g\colon (M, f_1)\to (M, f_2)$ is an isomorphism, then 
+    $g\circ f_1 = f_2 \circ g$ which exactly means that $f_1, f_2$ conjugate.
+  \end{proof} 
+
+  \begin{theorem}
+	\label{theorem:generic_aut_general}
+	Let $\cC$ be a Fraïssé class of finite structures of a theory $T$ in a 
+	relational language $L$. Let $\cD$ be the class of the finite structures of
+	$T$ in the language $L$ with additional unary function symbol interpreted
+	as an automorphism of the structure. If $\cC$ has the weak Hrushovski property
+	and $\cD$ is a Fraïssé class, then there is a comeagre conjugacy class in the
+	automorphism group of the $\Flim(\cC)$.
+  \end{theorem}
+
+  \begin{proof}
+	Let $\Gamma = \Flim(\cC)$ and $(\Pi, \sigma) = \Flim(\cD)$. Let $G = \Aut(\Gamma)$,
+	i.e. $G$ is the automorphism group of $\Gamma$. First, by the theorem
+	\ref{theorem:isomorphic_fr_lims}, we may assume without the loss of generality
+	that $\Pi = \Gamma$.
+	We will construct a strategy for the second player in the Banach-Mazur game
+	on the topological space $G$. This strategy will give us a subset 
+	$A\subseteq G$ and as we will see a subset of a cojugacy class in $G$.
+	By the Banach-Mazur theorem \ref{theorem:banach_mazur_thm} this will prove 
+	that this class is comeagre.
+
+	Recall, $G$ has a basis consisting of open
+	sets $\{g\in G\mid g\upharpoonright_A = g_0\upharpoonright_A\}$ for some
+	finite set $A\subseteq \Gamma$ and some automorphism $g_0\in G$. In other
+	words, a basic open set is a set of all extensions of some finite partial
+	isomorphism $g_0$ of $\Gamma$. By $B_{g}\subseteq G$ we denote a basic 
+	open subset given by a finite partial isomorphism $g$. From now on we will
+	consider only finite partial isomorphism $g$ such that $B_g$ is nonempty.
+
+	With the use of corollary \ref{corollary:banach-mazur-basis} we can consider 
+	only games, where both players choose finite partial isomorphisms. Namely,
+	player \textit{I} picks functions $f_0, f_1,\ldots$ and player \textit{II}
+	chooses $g_0, g_1,\ldots$ such that
+	$f_0\subseteq g_0\subseteq f_1\subseteq g_1\subseteq\ldots$, which identify
+	the corresponding basic open subsets $B_{f_0}\supseteq B_{g_0}\supseteq\ldots$.
+
+	Our goal is to choose $g_i$ in such a manner that the resulting function
+	$g = \bigcap^{\infty}_{i=0}g_i$ will be an automorphism of the Fraïssé limit 
+	$\Gamma$ such that $(\Gamma, g) = \Flim{\cD}$. 
+	Precisely, $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$, 
+	by the Fraïssé theorem \ref{theorem:fraisse_thm}
+	it will follow that $(\Gamma, g)\cong (\Pi, \sigma)$. Hence,
+	by the fact	\ref{fact:conjugacy}, $g$ and $\sigma$ conjugate in $G$.
+
+	Once again, by the Fraïssé theorem \ref{theorem:fraisse_thm} and the
+	\ref{lemma:weak_ultrahom} lemma constructing $g_i$'s in a way such that
+	age of $(\Gamma, g)$ is exactly $\cD$ and so that it is weakly ultrahomogeneous
+	will produce expected result. First, let us enumerate all pairs of structures
+	$\{\langle(A_n, \alpha_n), (B_n, \beta_n)\rangle\}_{n\in\bN},\in\cD$
+	such that the first element of the pair embeds by inclusion in the second,
+	i.e. $(A_n, \alpha_n)\subseteq (B_n, \beta_n)$. Also, it may be that 
+	$A_n$ is an empty. We enumerate the elements of the Fraïssé limit 
+	$\Gamma = \{v_0, v_1, \ldots\}$.
+
+	Fix a bijection $\gamma\colon\bN\times\bN\to\bN$ such that for any
+	$n, m\in\bN$ we have $\gamma(n, m) \ge n$. This bijection naturally induces
+	a well ordering on $\bN\times\bN$. This will prove useful later, as the
+	main argument of the proof will be constructed as a bookkeeping argument.
+
+	Just for sake of fixing a technical problem, let $g_{-1} = \emptyset$ and
+	$X_{-1} = \emptyset$. 
+	Suppose that player \textit{I} in the $n$-th move chooses a finite partial
+	isomorphism $f_n$. We will construct $g_n\supseteq f_n$ and a set $X_n\subseteq\bN^2$
+	such that following properties hold:
+
+	\begin{enumerate}[label=(\roman*)]
+	  \item $g_n$ is an automorphism of the induced substructure $\Gamma_n$,
+	  \item $g_n(v_n)$ and $g_n^{-1}(v_n)$ are defined,
+	  \item let 
+		$\{\langle (A_{n,k}, \alpha_{n, k}), (B_{n,k}, \beta_{n,k}), f_{n, k}\rangle\}_{k\in\bN}$
+		be the enumeration of all pairs of finite structures of $T$ with automorphism 
+		such that the first is a substructure of the second, i.e. 
+		$(A_{n,k}, \alpha_{n,k})\subseteq (B_{n,k}, \beta_{n,k})$, and $f_{n,k}$
+		is an embedding	of $(A_{n,k}, \alpha_{n,k})$ in the $\FrGr_{n-1}$ (which
+		is the substructure induced by $g_{n-1}$). Let 
+		$(i, j) = \min\{(\{0, 1, \ldots\} \times \bN) \setminus X_{n-1}\}$ (with the
+		order induced by $\gamma$). Then $X_n = X_{n-1}\cup\{(i,j)\}$ and
+		$(B_{n,k}, \beta_{n,k})$ embeds in $(\FrGr_n, g_n)$ so that this diagram
+		commutes:
+
+		\begin{center}
+		  \begin{tikzcd}
+									  & (\Gamma_n, g_n) & \\
+			(B_{i,j}, \beta_{i,j}) \arrow[ur, dashed, "\hat{f}_{i,j}"] &   & (\FrGr_{n-1}, g_{n-1}) \arrow[ul, dashed, "\subseteq"'] \\
+									  & (A_{i,j}, \alpha_{i,j}) \arrow[ur, "f_{i,j}"'] \arrow[ul, "\subseteq"]
+		  \end{tikzcd}
+		\end{center}
+	\end{enumerate}
+
+	First item makes sure that no infinite orbit will be present in $g$. The 
+	second item together with the first one are necessary for $g$ to be an 
+	automorphism of $\Gamma$. The third item is the one that gives weak
+	ultrahomogeneity. Now we will show that indeed such $g_n$ may be constructed.
+	
+	First, we will suffice the item (iii). Namely, we will construct $\Gamma'_n, g'_n$
+	such that $g_{n-1}\subseteq g'_n$ and $f_{i,j}$ extends to an embedding of
+	$(B_{i,j}, \beta_{i,j})$ to $(\Gamma'_n, g'_n)$. But this can be easily
+	done by the fact, that $\cD$ has the amalgamation property. Moreover, without
+	the loss of generality we can assume that all embeddings are inclusions.
+
+    \begin{center}
+      \begin{tikzcd}
+                                  & (\Gamma'_n, g'_n) & \\
+        (B_{i,j}, \beta_{i,j}) \arrow[ur, dashed, "\subseteq"] &   & (\Gamma_{n-1}, g_{n-1}) \arrow[ul, dashed, "\subseteq"'] \\
+								  & (A_{i,j}, \alpha_{i,j}) \arrow[ur, "\subseteq"'] \arrow[ul, "\subseteq"]
+      \end{tikzcd}
+    \end{center}
+
+	By the weak ultrahomogeneity we may assume that $\Gamma'_n\subseteq \Gamma$:
+
+	\begin{center}
+	  \begin{tikzcd}
+		(B_{i,j}\cup\Gamma_{n-1}, \beta_{i,j}\cup g_{n-1}) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Gamma \\
+		(\Gamma'_{n}, g'_n)\arrow[ur, dashed, "f"'] 
+	  \end{tikzcd}
+	\end{center}
+
+	Now, by the WHP of $\bK$ we can extend the graph $\Gamma'_n\cup\{v_n\}$ together
+	with its partial isomorphism $g'_n$ to a graph $\Gamma_n$ together with its
+	automorphism $g_n\supseteq g'_n$ and without the loss of generality we
+	may assume that $\Gamma_n\subseteq\Gamma$. This way we've constructed $g_n$
+	that has all desired properties.
+
+	Now we need to see that $g = \bigcap^{\infty}_{n=0}g_n$ is indeed an automorphism
+	of $\Gamma$ such that $(\Gamma, g)$ has the age $\cH$ and is weakly ultrahomogeneous.
+	It is of course an automorphism of $\Gamma$ as it is defined for every $v\in\Gamma$
+	and is a sum of increasing chain of finite automorphisms.
+
+	Take any finite structure of $T$ with automorphism $(B, \beta)$. Then, there are
+	$i, j$ such that $(B, \beta) = (B_{i, j}, \beta_{i,j})$ and $A_{i,j}=\emptyset$.
+	By the bookkeeping there was $n$ such that 
+	$(i, j) = \min\{\{0,1,\ldots\}\times\bN\setminus X_{n-1}\}$.
+	This means that $(B, \beta)$ embeds into $(\Gamma_n, g_n)$, hence it embeds
+	into $(\Gamma, g)$, thus it has age $\cH$. 
+	With a similar argument we can see that $(\Gamma, g)$ is weakly ultrahomogeneous.
+
+	By this we know that $g$ and $\sigma$ conjugate in $G$. As we stated in the
+	beginning of the proof, the set $A$ of possible outcomes of the game (i.e.
+	possible $g$'s we end up with) is comeagre in $G$, thus $\sigma^G$ is also
+	comeagre and $\sigma$ is a generic automorphism, as it contains a comeagre
+	set $A$.
+  \end{proof}
+
+  \subsection{Properties of the generic automorphism}
+
+  Let $\cC$ be a Fraïssé class in a finite relational language $L$ with
+  weak Hrushovski property. Let $\cH$ be the Fraïssé class of the $L$-structures
+  with additional automorphism symbol. Let $\Gamma = \Flim(\cC)$.
+
+ %  \begin{proposition}
+	% Let $\sigma$ be the generic automorphism of the random graph $\FrGr$. Then
+	% the graph induced by the set of the fixed points of $\sigma$ is isomorphic
+	% to $\FrGr$.
+ %  \end{proposition}
+	%
+ %  \begin{proof}
+	% Let $F = \{v\in\FrGr\mid \sigma(v) = v\}$. It suffices to show that $F$ is
+	% infinite and has the random graph property.
+ %  \end{proof}
+  \begin{proposition}
+	Let $\sigma$ be the generic automorphism of $\Gamma$. Then the set
+	of fixed points of $\sigma$ is isomorphic to $\Gamma$.
+  \end{proposition}
+
+  \begin{proof}
+	Let $S = \{x\in \Gamma\mid \sigma(x) = x\}$.
+	First we need to show that it is an infinite. By the theorem \ref{theorem:generic_aut_general}
+	we know that $(\Gamma, \sigma)$ is the Fraïssé limit of $\cH$, thus we
+	can embedd finite $L$-structures of any size with identity as an 
+	automorphism of the	structure into $(\Gamma, \sigma)$. Thus $S$ has to be
+	infinite. Also, the same argument shows that the age of the structure is
+	exactly $\cC$. It is weakly ultrahomogeneous, also by the fact that
+	$(\Gamma, \sigma)$ is in $\cH$.
+  \end{proof}
+\end{document}
diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex
new file mode 100644
index 0000000..ca2247e
--- /dev/null
+++ b/sections/fraisse_classes.tex
@@ -0,0 +1,451 @@
+\documentclass[../lic_malinka.tex]{subfiles}
+
+\begin{document}
+  In this section we will take a closer look at classes of finitely
+  generated structures with some characteristic properties. More
+  specifically, we will describe a concept developed by a French
+  mathematician Roland Fraïssé called Fraïssé limit.
+
+  \subsection{Definitions} 
+  \begin{definition}
+    Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is
+    the class $\bK$ of all finitely generated structures that embeds into $M$.
+    The age of $M$ is also associated with class of all structures embeddable in
+    $M$ \emph{up to isomorphism}.
+  \end{definition}
+
+  \begin{definition}
+    We say that $M$ has \emph{countable age} when its age has countably many 
+    isomorphism types of finitely generated structures. 
+  \end{definition}
+
+  \begin{definition}
+    Let $\bK$ be a class of finitely generated structures. $\bK$ has 
+    \emph{hereditary property (HP)} if for any $A\in\bK$, any finitely generated
+    substructure $B$ of $A$ it holds that $B\in\bK$. 
+  \end{definition}
+
+  \begin{definition}
+    Let $\bK$ be a class of finitely generated structures. We say that $\bK$ has
+    \emph{joint embedding property (JEP)} if for any $A, B\in\bK$ there is a
+    structure $C\in\bK$ such that both $A$ and $B$ embed in $C$.
+
+    \begin{center}
+      \begin{tikzcd}
+                                  & C & \\
+        A \arrow[ur, dashed, "f"] &   & B \arrow[ul, dashed, "g"'] 
+	  \end{tikzcd}
+    \end{center}
+
+	In terms of category theory, this is a \emph{span} in category $\bK$.
+  \end{definition}
+
+  Fraïssé has shown fundamental theories regarding age of a structure, one of 
+  them being the following one:
+  
+  \begin{fact}
+    \label{fact:age_is_hpjep}
+    Suppose $L$ is a signature and $\bK$ is a nonempty finite or countable set 
+    of finitely generated $L$-structures. Then $\bK$ has the HP and JEP if
+    and only if $\bK$ is the age of some finite or countable structure. 
+  \end{fact}
+
+  Beside the HP and JEP Fraïssé has distinguished one more property of the 
+  class $\bK$, namely amalgamation property.
+
+  \begin{definition}
+    Let $\bK$ be a class of finitely generated $L$-structures. We say that $\bK$
+    has the \emph{amalgamation property (AP)} if for any $A, B, C\in\bK$ and
+    embeddings $e\colon C\to A, f\colon C\to B$ there exists $D\in\bK$ together
+    with embeddings $g\colon A\to D$ and $h\colon A\to D$ such that 
+    $g\circ e = h\circ f$.
+    \begin{center}
+      \begin{tikzcd}
+                                  & D & \\
+        A \arrow[ur, dashed, "g"] &   & B \arrow[ul, dashed, "h"'] \\
+                                  & C \arrow[ur, "f"'] \arrow[ul, "e"]
+      \end{tikzcd}
+    \end{center}
+  \end{definition}
+
+  In terms of category theory, amalgamation over some structure $C$ is a
+  pushout diagram.
+
+  \begin{definition}
+    Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogeneous} if every
+    isomorphism between finitely generated substructures of $M$ extends to an
+    automorphism of $M$.
+  \end{definition}
+
+  Having those definitions we can provide the main Fraïssé theorem.
+
+  \begin{theorem}[Fraïssé theorem]
+    \label{theorem:fraisse_thm}
+    Let L be a countable language and let $\bK$ be a nonempty countable set of
+    finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ is 
+    the age of a countable, ultrahomogeneous $L$-structure $M$. Moreover, $M$ is
+    unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\bK$
+    and denote this by $M = \Flim(\bK)$.
+  \end{theorem}
+
+  This is a well known theorem. One can read a proof of this theorem in Wilfrid
+  Hodges' classical book \textit{Model Theory}~\cite{hodges_1993}. In the proof
+  of this theorem appears another, equally important \ref{lemma:weak_ultrahom}.
+
+  \begin{definition}
+    We say that an $L$-structure $M$ is \emph{weakly ultrahomogeneous} if for any
+    $A, B$ finitely generated substructures of $M$ such that $A\subseteq B$ and
+    an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which
+    extends $f$.
+    \begin{center}
+      \begin{tikzcd}
+        A \arrow[d, "\subseteq"'] \arrow[r, "f"] & D \\
+        B \arrow[ur, dashed, "g"']
+      \end{tikzcd}
+    \end{center}
+  \end{definition}
+
+  \begin{lemma}
+    \label{lemma:weak_ultrahom}
+    A countable structure is ultrahomogeneous if and only if it is weakly
+    ultrahomogeneous.
+  \end{lemma}
+
+  This lemma will play a major role in the later parts of the paper. Weak
+  ultrahomogeneity is an easier and more intuitive property and it will prove
+  useful when recursively constructing the generic automorphism of a Fraïssé 
+  limit.
+
+  % \begin{fact} If $\bK$ is a uniformly locally finite Fraïssé class, then
+  % $\Flim(\bK)$ is $\aleph_0$-categorical and has quantifier elimination.
+  % \end{fact}
+
+  \subsection{Random graph} 
+  
+  In this section we'll take a closer look on a class of finite unordered graphs, 
+  which is a Fraïssé class. 
+
+  The language of unordered graphs $L$ consists of a single binary
+  relational symbol $E$. If $G$ is an $L$-structure then we call it a
+  \emph{graph}, and its elements $\emph{vertices}$. If for some vertices 
+  $u, v\in G$ we have $G\models uEv$ then we say that there is an $\emph{edge}$ 
+  connecting $u$ and $v$. If $G\models \forall x\forall y (xEy\leftrightarrow yEx)$
+  then we say that $G$ is an \emph{unordered graph}. From now on we omit the word
+  \textit{unordered} and  graphs as unordered.
+
+  \begin{proposition}
+    Let $\cG$ be the class of all finite graphs. $\cG$ is a Fraïssé class.
+  \end{proposition}
+  \begin{proof}
+    $\cG$ is of course countable (up to isomorphism) and has the HP 
+    (graph substructure is also a graph). It has JEP: having two finite graphs 
+    $G_1,G_2$ take their disjoint union $G_1\sqcup G_2$ as the extension of them
+    both. $\cG$ has the AP. Having graphs $A, B, C$, where $B$ and $C$ are
+    supergraphs of $A$, we can assume without loss of generality, that 
+    $(B\setminus A) \cap (C\setminus A) = \emptyset$. Then 
+    $A\sqcup (B\setminus A)\sqcup (C\setminus A)$ is the graph we're looking
+    for (with edges as in B and C and without any edges between $B\setminus A$
+	and $C\setminus A$).
+  \end{proof}
+
+  \begin{definition}
+    The \emph{random graph} is the Fraïssé limit of the class of finite graphs
+    $\cG$ denoted by $\FrGr = \Flim(\cG)$.
+  \end{definition}
+
+  The concept of the random graph emerges independently in many fields of
+  mathematics. For example, one can construct the graph by choosing at random
+  for each pair of vertices if they should be connected or not. It turns out
+  that the graph constructed this way is isomorphic to the random graph with
+  probability 1.
+
+  The random graph $\FrGr$ has one particular property that is unique to the
+  random graph.
+
+  \begin{fact}[random graph property]
+	For each finite disjoint $X, Y\subseteq \FrGr$ there exists $v\in\FrGr\setminus (X\cup Y)$
+    such that $\forall u\in X (vEu)$ and $\forall u\in Y (\neg vEu)$.
+  \end{fact}
+  \begin{proof}
+    Take any finite disjoint $X, Y\subseteq\FrGr$. Let $G_{XY}$ be the
+    subgraph of $\FrGr$ induced by the $X\cup Y$. Let $H = G_{XY}\cup \{w\}$,
+    where $w$ is a new vertex that does not appear in $G_{XY}$. Also, $w$ is connected to 
+    all vertices of $G_{XY}$ that come from $X$ and to none of those that come
+    from $Y$. This graph is of course finite, so it is embeddable in $\FrGr$.
+    Without loss of generality assume that this embedding is simply inclusion. 
+    Let $f$ be the partial isomorphism from $X\sqcup Y$ to $H$, with $X$ and
+    $Y$ projected to the part of $H$ that come from $X$ and $Y$ respectively. 
+    By the ultrahomogeneity of $\FrGr$ this isomorphism extends to an automorphism
+    $\sigma\in\Aut(\FrGr)$. Then $v = \sigma^{-1}(w)$ is the vertex we sought. 
+  \end{proof}
+
+  \begin{fact}
+    If a countable graph $G$ has the random graph property, then it is
+    isomorphic to the random graph $\FrGr$.
+  \end{fact}
+  \begin{proof}
+    Enumerate vertices of both graphs: $\FrGr = \{a_1, a_2\ldots\}$ and $G
+    = \{b_1, b_2\ldots\}$.
+    We will construct a chain of partial isomorphisms $f_n\colon \FrGr\to G$
+    such that $\emptyset = f_0\subseteq f_1\subseteq f_2\subseteq\ldots$ and $a_n \in
+    \dom(f_n)$ and $b_n\in\rng(f_n)$.
+
+	Suppose we have $f_n$. We seek $b\in G$ such that $f_n\cup \{\langle
+    a_{n+1}, b\rangle\}$ is a partial isomorphism. 
+    If $a_{n+1}\in\dom{f_n}$, then simply $b = f_n(a_{n+1})$. Otherwise,
+	let $X = \{a\in\FrGr\mid
+    aE_{\FrGr} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, i.e. $X$ are
+    vertices of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and
+    $Y$ are those vertices that are not connected with $a_{n+1}$. Let $b$ be
+    a vertex of $G$ that is connected to all vertices of $f_n[X]$ and to none
+    $f_n[Y]$ (it exists by the random graph property). Then $f_n\cup \{\langle
+    a_{n+1}, b\rangle\}$ is a partial isomorphism. We find $a$ for the
+    $b_{n+1}$ in the similar manner, so that $f_{n+1} = f_n\cup \{\langle
+    a_{n+1}, b\rangle, \langle a, b_{n+1}\rangle\}$ is a partial isomorphism.
+
+    Finally, $f = \bigcup^{\infty}_{n=0}f_n$ is an isomorphism between $\FrGr$
+    and $G$. Take any $a, b\in \FrGr$. Then for some big enough $n$ we have
+    that $aE_{\FrGr}b\Leftrightarrow f_n(a)E_{G}f_n(b) \Leftrightarrow f(a)E_{G}f(b)$.
+  \end{proof}
+
+  Using this fact one can show that the graph constructed in the probabilistic
+  manner is in fact isomorphic to the random graph $\FrGr$.
+
+  \begin{definition} We say that a Fraïssé class $\bK$ has \emph{weak
+    Hrushovski property} (\emph{WHP}) if for every $A\in \bK$ and an isomorphism
+	of its substructures $p\colon A\to A$ (also called a partial automorphism of $A$),
+	there is some $B\in \bK$ such 
+    that $p$ can be extended to an automorphism of $B$, i.e.\ there is an 
+    embedding $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following
+    diagram commutes: 
+    \begin{center} 
+      \begin{tikzcd} 
+        B\ar[r,dashed,"\bar p"]&B\\
+        A\ar[u,dashed,"i"]\ar[r,"p"]&A\ar[u,dashed,"i"] 
+      \end{tikzcd} 
+    \end{center}
+  \end{definition}
+
+  \begin{proposition}
+    \label{proposition:finite-graphs-whp}
+    The class of finite graphs $\cG$ has the weak Hrushovski property. 
+  \end{proposition}
+
+  \begin{proof}
+    It may be there some day, but it may not!
+  \end{proof}
+
+  \subsection{Canonical amalgamation}
+
+  \begin{definition}
+	Let $\bK$ be a class finitely generated $L$-structures. We say that
+	$\bK$ has \emph{canonical amalgamation} if for every $C\in\bK$ there
+	is a functor $\otimes_C\colon\Cospan(\bK)\to\Pushout(\bK)$ such that
+	it has the following properties:
+	\begin{itemize}
+	  \item Let $A\leftarrow C\rightarrow B$ be a cospan. Then $\otimes_C$ sends
+		it to a pushout that preserves ``the bottom`` structures and embeddings, i.e.:
+		\begin{center}
+		  \begin{tikzcd}
+			& & 	 							& 		 & A\otimes_C B & \\
+			A & & B  \arrow[r, dashed, "A\otimes_C B"] & A \arrow[ur, dashed] & & B \arrow[ul, dashed] \\
+			& C \arrow[ul] \arrow[ur]  & & & C \arrow[ul] \arrow[ur] &
+		  \end{tikzcd}
+		\end{center}
+
+	  We have deliberately omited names for embeddings of $C$. Of course, 
+	  the functor has to take them into account, but this abuse of notation
+	  is convenient and should not lead into confusion.
+	  \item Let $A\leftarrow C\rightarrow B$, $A'\leftarrow C\rightarrow B'$ be cospans
+		with a natural transformation given by $\alpha\colon A\to A', \beta\colon B\to B',
+		\gamma\colon C\to C$. Then $\otimes_C$ preserves the morphisms of
+		when sending the natural transformation of those cospans to natural
+		transformation of pushouts by adding the 
+		$\delta\colon A\otimes_C B\to A'\otimes_C B'$ morphism:
+
+		\begin{center}
+		  \begin{tikzcd}
+			& A'\otimes_C B' & \\
+			A' \arrow[ur] & & B' \arrow[ul] \\
+			& A\otimes_C B  \ar[uu, dashed, "\delta"] & \\
+			& C \arrow[uul, bend left] \arrow[uur, bend right] & \\
+			A \arrow[uuu, dashed, "\alpha"] \arrow[uur, bend left, crossing over] & & B \arrow[uuu, dashed, "\beta"'] \arrow[uul, bend right, crossing over] \\
+			& C \arrow[ur] \arrow[ul] \arrow[uu, dashed, "\gamma"] & \\ 
+		  \end{tikzcd}
+		\end{center}
+		% \begin{center}
+		%   \begin{tikzcd}
+			% & A \ar[rrr, dashed, "\alpha"] \ar[drr, bend left=20, crossing over] & & & A' \ar[dr] & \\
+			% C \ar[rr, dashed, "\gamma"] \ar[ur] \ar[dr] & & C \ar[rrd, bend right=20] \ar[rru, bend left=20] & A\otimes_C B \ar[rr, dashed, "\delta"] & & A' \otimes_C B' \\
+			% & B \ar[rrr, dashed, "\beta"] \ar[urr, bend right=20, crossing over] & & & B' \ar[ur] & \\
+		%   \end{tikzcd}
+		% \end{center}
+	\end{itemize}
+  \end{definition}
+
+  \begin{theorem}
+	\label{theorem:canonical_amalgamation_thm}
+	Let $\bK$ be a Fraïssé class of $L$-structures with canonical amalgamation. 
+	Then the class $\cH$ of $L$-structures with automorphism is a Fraïssé class.
+  \end{theorem}
+
+  \begin{proof}
+	$\cH$ is obviously countable and has HP. It suffices to show that it
+	has AP (JEP follows by taking $C$ to be the empty structure). Take any
+	$(A,\alpha), (B,\beta), (C,\gamma)\in \cH$ such that $(C,\gamma)$ embeds
+	into $(A,\alpha)$ and $(B,\beta)$. Then $\alpha, \beta, \gamma$ yield
+	an automorphism $\eta$ (as a natural transformation) of a cospan:
+	\begin{center}
+	  \begin{tikzcd}
+		A & & B \\
+		% & C \ar[ur] \ar[ul] & \\
+		A \ar[u, dashed, "\alpha"] & C \ar[ur] \ar[ul] & B \ar[u, dashed, "\beta"'] \\
+		& C \ar[ur] \ar[ul] \ar[u, dashed, "\gamma"] &
+		% (A, \alpha) & & (B, \beta) \\
+		% & (C, \gamma) \ar[ur] \ar[ul] &
+	  \end{tikzcd}
+	\end{center}
+	
+	Then, by the fact \ref{fact:functor_iso}, $\otimes_C(\eta)$ is an automorphism
+	of the pushout diagram:
+	
+	\begin{center}
+	  \begin{tikzcd}
+		& A\otimes_C B \ar[loop above, "\delta"] & \\
+		A \ar[ur] \ar[loop left, "\alpha"]& & B \ar[ul] \ar[loop right, "\beta"]\\
+		& C \ar[ur] \ar[ul] \ar[loop below, "\gamma"] & 
+	  \end{tikzcd}
+	\end{center}
+	
+	TODO: ten diagram nie jest do końca taki jak trzeba, trzeba w zasadzie skopiować
+	ten z definicji kanonicznej amalgamcji. Czy to nie będzie wyglądać źle?
+
+	This means that the morphism $\delta\colon A\otimes_C B\to A\otimes_C B$
+	has to be automorphism. Thus, by the fact that the diagram commutes, 
+	we have the amalgamation of $(A, \alpha)$ and $(B, \beta)$ over $(C,\gamma)$ 
+	in $\cH$.
+  \end{proof}
+
+  \subsection{Graphs with automorphism}
+  The language and theory of unordered graphs is fairly simple. We extend the
+  language by one unary symbol $\sigma$ and interpret it as an arbitrary
+  automorphism on the graph structure. It turns out that the class of such
+  structures is a Fraïssé class.
+
+  \begin{proposition}
+    Let $\cH$ be the class of all finite graphs with an automorphism, i.e.
+    structures in the language $(E, \sigma)$ such that $E$ is a symmetric
+    relation and $\sigma$ is an automorphism on the structure. $\cH$ is
+    a Fraïssé class.
+  \end{proposition}
+  \begin{proof}
+    Countability and HP are obvious, JEP follows by the same argument as in
+    plain graphs. We need to show that the class has the amalgamation property.
+
+    Take any $(A, \alpha), (B, \beta), (C,\gamma)\in\cH$ such that $A$ embeds
+    into $B$ and $C$. Without the loss of generality we may assume that 
+	$B\cap C = A$ and $\alpha\subseteq\beta,\gamma$. 
+	Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in
+    the proof for the plain graphs. We will define the automorphism
+    $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. 
+	We let $\delta\upharpoonright_B = \beta, \delta\upharpoonright_C = \gamma$.
+	Let's check the definition is correct. We have to show that 
+	$(uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$ holds for any $u, v\in
+	D$. We have two cases:
+    \begin{itemize}
+      \item $u, v\in X$, where $X$ is either $B$ or $C$. This case is trivial.
+      \item $u\in B\setminus A, v\in C\setminus A$. Then
+        $\delta(u)=\beta(u)\in B\setminus A$, similarly $\delta(v)=\gamma(v)\in
+        C\setminus A$. This follows from the fact, that $\beta\upharpoonright_A
+        = \alpha$, so for any $w\in A\quad\beta^{-1}(w)=\alpha^{-1}(w)\in A$,
+        similarly for $\gamma$. Thus, from the construction of $D$, $\neg uE_Dv$
+        and $\neg \delta(u)E_D\delta(v)$.
+    \end{itemize}
+  \end{proof}
+
+  The proposition says that there is a Fraïssé for the class $\cH$ of finite
+  graphs with automorphisms. We shall call it $(\FrAut, \sigma)$. Not
+  surprisingly, $\FrAut$ is in fact a random graph.
+
+  \begin{proposition}
+	\label{proposition:graph-aut-is-normal}
+	The Fraïssé limit of $\cH$ interpreted as a plain graph (i.e. as a reduct
+	to the language of graphs) is isomorphic to the random graph $\FrGr$. 
+  \end{proposition}
+
+  \begin{proof}
+    It is enough to show that $\FrAut = \Flim(\cH)$ has the random graph
+    property. Take any finite disjoint $X, Y\subseteq \FrAut$. Without the loss
+    of generality assume that $X\cup Y$ is $\sigma$-invariant, i.e.
+    $\sigma(v)\in X\cup Y$ for $v\in X\cup Y$. This assumption can be made 
+    because there are no infinite orbits in $\sigma$, which in turn is due to
+    the fact that $\cH$ is the age of $\FrAut$. 
+
+    Let $G_{XY}$ be the graph induced by $X\cup Y$. Take $H=G_{XY}\sqcup {v}$ 
+    as a supergraph of $G_{XY}$ with one new vertex $v$ connected to all 
+    vertices of $X$ and to none of $Y$. By the proposition
+    \ref{proposition:finite-graphs-whp} we can extend $H$ together with its
+    partial isomorphism $\sigma\upharpoonright_{X\cup Y}$ to a graph $R$ with
+    automorphism $\tau$. Once again, without the loss of generality we can
+    assume that $R\subseteq\FrAut$, because $\cH$ is the age of $\FrAut$. But
+    $R\upharpoonright_{G_{XY}}$ together with $\tau\upharpoonright_{G_{XY}}$
+    are isomorphic to the $G_{XY}$ with $\sigma\upharpoonright_{G_{XY}}$.
+
+    Thus, by ultrahomogeneity of $\FrAut$ this isomorphism extends to an 
+    automorphism $\theta$ of $(\FrAut, \sigma)$. Then $\theta(v)$ is the vertex
+    that is connected to all vertices of $X$ and none of $Y$, because
+    $\theta[R\upharpoonright_X] = X, \theta[R\upharpoonright_Y] = Y$.
+  \end{proof}
+
+
+  \begin{theorem}
+	\label{theorem:isomorphic_fr_lims}
+	Let $\cC$ be a Fraïssé class of finite structures in a relational language
+	$L$ of some theory $T$. Let $\cD$ be a class of finite structures of the
+	theory $T$ in a relational language $L$ with additional unary function 
+	symbol interpreted as an automorphism of the structure. If $\cC$ has the
+	weak Hrushovski property and $\cD$ is a Fraïssé class then the Fraïssé
+	limit of $\cC$ is isomorphic to the Fraïssé limit of $\cD$ reduced
+	to the language $L$.
+  \end{theorem}
+
+  \begin{proof}
+	Let $\Gamma=\Flim(\cC)$ and $(\Pi, \sigma) =\Flim(\cD)$. By the Fraïssé 
+	theorem \ref{theorem:fraisse_thm} it suffices to show that the age of $\Pi$
+	is $\cC$ and that it has the weak ultrahomogeneity in the class $\cC$. The
+	former comes easily, as for every structure $A\in \cC$ we have the structure
+	$(A, \id_A)\in \cD$, which means that the structure $A$ embedds into $\Pi$.
+	Also, if a structure $(B, \beta)\in\cD$ embedds into $\cD$, then $B\in\cC$.
+	Hence, $\cC$ is indeed the age of $\Pi$.
+
+	Now, take any structure $A, B\in\cC$ such that $A\subseteq B$. Without the
+	loss of generality assume that $A = B\cap \Pi$. Let $\bar{A}$ be the
+	smallest structure closed on the automorphism $\sigma$ and containg $A$.
+	It is finite, as $\cC$ is the age of $\Pi$. By the weak Hrushovski property,
+	of $\cC$ let $(\bar{B}, \beta)$ be a structure extending 
+	$(B\cup \bar{A}, \sigma\upharpoonright_{\bar{A}})$. Again, we may assume 
+	that $B\cup \bar{A}\subseteq \bar{B}$. Then, by the fact that $\Pi$ is a 
+	Fraïssé limit of $\cD$ there is an embedding 
+	$f\colon(\bar{B}, \beta)\to(\Pi, \sigma)$
+	such that the following diagram commutes:
+
+    \begin{center}
+      \begin{tikzcd}
+		(A, \emptyset) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & (\bar{A}, \sigma\upharpoonright_A) \arrow[d, "\subseteq"] \arrow[r, "\subseteq"] & (\Pi, \sigma) \\
+		(B, \sigma\upharpoonright_B) \arrow[r, dashed, "\subseteq"'] & (\bar{B}, \beta) \arrow[ur, dashed, "f"]
+      \end{tikzcd}
+    \end{center}
+
+	Then we simply get the following diagram:
+
+	\begin{center}
+	  \begin{tikzcd}
+		A \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Pi \\
+		B \arrow[ur, dashed, "f\upharpoonright_B"'] 
+	  \end{tikzcd}
+	\end{center}
+
+	which proves that $\Pi$ is indeed a weakly ultrahomogeneous structure in $\cC$.
+	Hence, it is isomorphic to $\Gamma$.
+  \end{proof}
+\end{document}
diff --git a/sections/introduction.tex b/sections/introduction.tex
new file mode 100644
index 0000000..89004c7
--- /dev/null
+++ b/sections/introduction.tex
@@ -0,0 +1,5 @@
+\documentclass[../lic_malinka.tex]{subfiles}
+
+\begin{document}
+  There will be something!
+\end{document}
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}