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

1 files changed, 6 insertions, 1039 deletions

diff --git a/lic_malinka.tex b/lic_malinka.tex
index 4ce39e0..96f97a3 100644
--- a/lic_malinka.tex
+++ b/lic_malinka.tex
@@ -37,6 +37,8 @@
 \usepackage[notref, notcite]{showkeys} 

 \usepackage[cmtip,arrow]{xy}

 

+\usepackage{subfiles}

+

 \DeclareMathOperator{\Aut}{Aut} 

 \DeclareMathOperator{\Hom}{Hom}

 \DeclareMathOperator{\Stab}{Stab} 

@@ -107,7 +109,6 @@
 \newcommand{\xqed}[1]{% \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill

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

 

-

 \title{Tytuł} 

 \author{Franciszek Malinka}

 

@@ -116,1050 +117,16 @@
     Abstract 

   \end{abstract} 

   \section{Introduction}

+  \subfile{sections/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 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?

+  \subfile{sections/preliminaries}

 

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

+  \subfile{sections/fraisse_classes}

 

   \section{Conjugacy classes in automorphism groups}

+  \subfile{sections/conj_classes}

 

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

   \printbibliography

 \end{document}