Definicje wkolo freissego

1 files changed, 460 insertions, 290 deletions

diff --git a/lic_malinka.tex b/lic_malinka.tex
index 62d1f7b..0dde9cd 100644
--- a/lic_malinka.tex
+++ b/lic_malinka.tex
@@ -1,96 +1,88 @@
-\documentclass[11pt, a4paper, final]{amsart}

-\setlength{\emergencystretch}{2em}

+\documentclass[11pt, a4paper, final]{amsart} \setlength{\emergencystretch}{2em}

 

+\usepackage[backend=biber]{biblatex}

+\addbibresource{licmalinka.bib}

 

-\usepackage[T1]{fontenc}

-\usepackage{mathtools}

+

+\usepackage[T1]{fontenc} \usepackage{mathtools}

 \usepackage[activate={true,nocompatibility},final,tracking=true,kerning=true,spacing=true,stretch=10,shrink=10]{microtype}

 \microtypecontext{spacing=nonfrench}

 % \usepackage[utf8]{inputenc}

 

-\usepackage{amsfonts}

-\usepackage{amsmath}

+\usepackage{amsfonts} 

+\usepackage{amsmath} 

 \usepackage{amssymb}

-\usepackage{amsthm}

-\usepackage{XCharter}

-\usepackage[charter,expert, greekuppercase=italicized, greekfamily=didot]{mathdesign}

-\usepackage{mathtools}

-\usepackage{enumitem}

+\usepackage{amsthm} 

+\usepackage{XCharter} 

+\usepackage[charter, expert, greekuppercase=italicized, greekfamily=didot]{mathdesign}

+\usepackage{mathtools} 

+\usepackage{enumitem} 

 \usepackage[utf8]{inputenc}

-\usepackage{tikz-cd}

+\usepackage{tikz-cd} 

 \usepackage{tikz}

+\usetikzlibrary{arrows,arrows.meta}

+\tikzcdset{arrow style=tikz, diagrams={>=latex}}

 

-\usepackage{etoolbox}

 

+\usepackage{etoolbox}

 

-\usepackage{xcolor}

+\usepackage{xcolor} 

 \definecolor{green}{RGB}{0,127,0}

-\definecolor{redd}{RGB}{191,0,0}

+\definecolor{redd}{RGB}{191,0,0} 

+

 \definecolor{red}{RGB}{105,89,205}

 \usepackage[colorlinks=true]{hyperref}

 

-\usepackage[notref, notcite]{showkeys}

+\usepackage[notref, notcite]{showkeys} 

 \usepackage[cmtip,arrow]{xy}

-%\usepackage[backend=biber,

-%url=false,

-%isbn=false,

-%backref=true,

-%citestyle=alphabetic,

-%bibstyle=alphabetic,

-%autocite=inline,

-%maxnames=99,

-%minalphanames=4,

-%maxalphanames=4,

-%sorting=nyt,]{biblatex}

-%\addbibresource{linear_strucures.bib}

-

-\DeclareMathOperator{\Aut}{Aut}

+

+\DeclareMathOperator{\Aut}{Aut} 

 \DeclareMathOperator{\Hom}{Hom}

-\DeclareMathOperator{\Stab}{Stab}

+\DeclareMathOperator{\Stab}{Stab} 

 \DeclareMathOperator{\st}{st}

-\DeclareMathOperator{\Flim}{FLim}

+\DeclareMathOperator{\Flim}{FLim} 

 \DeclareMathOperator{\Int}{{Int}}

 

-\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}}

-\newcommand{\cC}{\mathcal C}

-\newcommand{\cV}{\mathcal{V}}

+\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} 

+\newcommand{\cC}{\mathcal C} 

+\newcommand{\cV}{\mathcal{V}} 

 \newcommand{\cU}{\mathcal{U}}

-\newcommand{\bN}{\mathbb N}

+\newcommand{\bN}{\mathbb N} 

 \newcommand{\bR}{\mathbb R}

-\newcommand{\bZ}{\mathbb Z}

+\newcommand{\bZ}{\mathbb Z} 

 \newcommand{\bQ}{\mathbb Q}

+\newcommand{\bK}{\mathbb K}

 

-\DeclareMathOperator{\im}{{Im}}

+\DeclareMathOperator{\im}{{Im}} 

 \DeclareMathOperator{\lin}{{Lin}}

 \DeclareMathOperator{\Th}{{Th}}

 

-\newtheorem{theorem}{Theorem}

+\newtheorem{theorem}{Theorem} 

 \numberwithin{theorem}{section}

-\newtheorem{lemma}[theorem]{Lemma}

+\newtheorem{lemma}[theorem]{Lemma} 

 \newtheorem{claim}[theorem]{Claim}

-\newtheorem{fact}[theorem]{Fact}

+\newtheorem{fact}[theorem]{Fact} 

 \newtheorem{proposition}[theorem]{Proposition}

-\newtheorem{conjecture}[theorem]{Conjecture}

+\newtheorem{conjecture}[theorem]{Conjecture} 

 \newtheorem{axiom}[theorem]{Axiom}

 \newtheorem{question}[theorem]{Question}

-\newtheorem{corollary}[theorem]{Corollary}

+\newtheorem{corollary}[theorem]{Corollary} 

 \newtheorem*{theorem2}{Theorem}

-\newtheorem*{claim2}{Claim}

+\newtheorem*{claim2}{Claim} 

 \newtheorem*{corollary2}{Corollary}

-\newtheorem*{question2}{Question}

+\newtheorem*{question2}{Question} 

 \newtheorem*{conjecture2}{Conjecture}

 

 

-\newtheorem{clm}{Claim}

-\newtheorem*{clm*}{Claim}

+\newtheorem{clm}{Claim} \newtheorem*{clm*}{Claim}

 

 

-\theoremstyle{definition}

+\theoremstyle{definition} 

 \newtheorem{definition}[theorem]{Definition}

-\newtheorem*{definition2}{Definition}

+\newtheorem*{definition2}{Definition} 

 \newtheorem{example}[theorem]{Example}

 

-\theoremstyle{remark}

+\theoremstyle{remark} 

 \newtheorem{remark}[theorem]{Remark}

 \newtheorem*{remark2}{Remark}

 

@@ -98,248 +90,426 @@
 \AtEndEnvironment{proof}{\setcounter{clm}{0}}

 \newenvironment{clmproof}[1][\proofname]{\proof[#1]\renewcommand{\qedsymbol}{$\square$(claim)}}{\endproof}

 

-\newcommand{\xqed}[1]{%

-    \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill

-    \quad\hbox{\ensuremath{#1}}}

+\newcommand{\xqed}[1]{% \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill

+  \quad\hbox{\ensuremath{#1}}}

 

 

-\title{Tytuł}

+\title{Tytuł} 

 \author{Franciszek Malinka}

 

 \begin{document}

-

-    \begin{abstract}

-        Abstract

-    \end{abstract}

-    \section{Introduction}

-

-    \section{Preliminaries}

-    \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 iff 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$ (though being 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 in $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

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

-    

-    \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 $\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 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 $\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 auxilary 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 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 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}}$ suc h 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}[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}

-

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

-

-    \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 occurance 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{Fraïssé classes}

-    \begin{fact}[Fraïssé theorem]

-        \label{fact:fraisse_thm}

-        % Suppose $\cC$ is a class of finitely generated $L$-structures such that...

-

-        Then there exists a unique up to isomorphism countable $L$-structure $M$ such that...

-    \end{fact}

-

-    \begin{definition}

-        For $\cC$, $M$ as in Fact~\ref{fact:fraisse_thm}, we write $\Flim(\cC)\coloneqq M$.

-    \end{definition}

-

-    \begin{fact}

-        If $\cC$ is a uniformly locally finite Fraïssé class, then $\Flim(\cC)$ is $\aleph_0$-categorical and has quantifier elimination.

-    \end{fact}

-

-    \section{Conjugacy classes in automorphism groups}

-

-    \subsection{Prototype: pure set}

-    In this section, $M=(M,=)$ is an infinite countable set (with no structure beyond equality).

-    \begin{proposition}

-        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{proposition}

-        The conjugacy class of $f\in \Aut(M)$ is dense if and only if...

-    \end{proposition}

-    \begin{proposition}

-        If $f\in \Aut(M)$ has an infinite orbit, then the conjugacy class of $f$ is meagre.

-    \end{proposition}

-

-    \begin{proposition}

-        An automorphism $f$ of $M$ is generic if and only if...

-    \end{proposition}

-

-    \begin{proof}

-

-    \end{proof}

-

-    \subsection{More general structures}

-

-

-    \begin{proposition}

-        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)$.

-    \end{proposition}

-

-    \begin{definition}

-        We say that a Fraïssé class $\cC$ has \emph{weak Hrushovski property} (\emph{WHP}) if for every $A\in \cC$ and partial automorphism $p\colon A\to A$, there is some $B\in \cC$ 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,"\bar p"]&B\\

-                A\ar[u,"i"]\ar[r,"p"]&A\ar[u,"i"]

-            \end{tikzcd}

-        \end{center}

-    \end{definition}

-

-    \begin{proposition}

-        Suppose $\cC$ is a Fraïssé class in a relational language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$, all orbits of $f$ are finite.

-    \end{proposition}

-    \begin{proposition}

-        Suppose $\cC$ is a Fraïssé class in an arbitrary countable language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$ ...

-    \end{proposition}

-

-    \subsection{Random graph}

-    \begin{definition}

-        The \emph{random graph} is...

-    \end{definition}

-

-    \begin{fact}

-        The

-    \end{fact}

-

-    \begin{proposition}

-        Generically, the set of fixed points of $f\in \Aut(M)$ is isomorphic to $M$ (as a graph).

-    \end{proposition}

-

-\end{document}
\ No newline at end of file
+  \begin{abstract} 

+    Abstract 

+  \end{abstract} 

+  \section{Introduction}

+

+  \section{Preliminaries} 

+  \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 iff 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$ (though being 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 in $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

+  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}\}$.

+  \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 $\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 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 $\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 auxilary 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 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 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}}$ suc h 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.

+

+  \section{Fraïssé classes}

+

+  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 embedds 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$.

+  \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 $f\colon A\to B, g\colon A\to C$ there exists $D\in\bK$ together

+    with embeddings $h\colon B\to D$ and $j\colon C\to D$ such that 

+    $h\circ f = j\circ g$.

+    \begin{center}

+      \begin{tikzcd}

+                                  & D & \\

+        B \arrow[ur, dashed, "h"] &   & C \arrow[ul, dashed, "j"'] \\

+                                  & A \arrow[ur, "g"'] \arrow[ul, "f"]

+      \end{tikzcd}

+    \end{center}

+  \end{definition}

+

+  \begin{definition}

+    Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogenous} if every

+    isomorphism between finitely generated substrucutres 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, ultrahomogenous $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 ultrahomogenous} 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 ultrahomogenous if and only if it is weakly

+    ultrahomogenous.

+  \end{lemma}

+

+  This lemma will play a major role in the later parts of the paper. Weak

+  ultrahomogenity is an easier and more intuitive property and it will prove

+  useful when recursively constructing the generic automorphism of a Fraïssé 

+  limit.

+

+

+  % \begin{definition} For $\cC$, $M$ as in Fact~\ref{fact:fraisse_thm}, we

+  % write $\Flim(\cC)\coloneqq M$.  \end{definition}

+

+  % \begin{fact} If $\cC$ is a uniformly locally finite Fraïssé class, then

+  % $\Flim(\cC)$ is $\aleph_0$-categorical and has quantifier elimination.

+  % \end{fact}

+

+  % \section{Conjugacy classes in automorphism groups}

+

+  % \subsection{Prototype: pure set} In this section, $M=(M,=)$ is an

+  % infinite countable set (with no structure beyond equality).

+  % \begin{proposition} 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{proposition} The conjugacy class of $f\in \Aut(M)$ is dense if

+  %   and only if...  \end{proposition} \begin{proposition} If $f\in

+  % \Aut(M)$ has an infinite orbit, then the conjugacy class of $f$ is

+  % meagre.  

+  % \end{proposition}

+

+  % \begin{proposition} An automorphism $f$ of $M$ is generic if and only if...

+  % \end{proposition}

+

+  % \begin{proof}

+

+  % \end{proof}

+

+  % \subsection{More general structures}

+

+

+  % \begin{proposition} 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)$.  \end{proposition}

+

+  % \begin{definition} We say that a Fraïssé class $\cC$ has \emph{weak

+  %   Hrushovski property} (\emph{WHP}) if for every $A\in \cC$ and partial

+  %   automorphism $p\colon A\to A$, there is some $B\in \cC$ 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,"\bar p"]&B\\

+  %       A\ar[u,"i"]\ar[r,"p"]&A\ar[u,"i"] 

+  %     \end{tikzcd} 

+  %   \end{center}

+  % \end{definition}

+

+  % \begin{proposition} Suppose $\cC$ is a Fraïssé class in a relational

+  % language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$, all

+  % orbits of $f$ are finite.  \end{proposition} \begin{proposition} Suppose

+  %   $\cC$ is a Fraïssé class in an arbitrary countable language with WHP.

+  %   Then generically, for an $f\in \Aut(\Flim(\cC))$ ...  \end{proposition}

+

+  % \subsection{Random graph} \begin{definition} The \emph{random graph}

+  % is...  \end{definition}

+

+  % \begin{fact} The \end{fact}

+

+  %   \begin{proposition} Generically, the set of fixed points of $f\in

+  %   \Aut(M)$ is isomorphic to $M$ (as a graph).  \end{proposition}

+  \printbibliography

+\end{document}