path: root/lic_malinka.tex

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

\usepackage[utf8]{inputenc}
\usepackage[backend=biber]{biblatex}
\addbibresource{licmalinka.bib}

\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{amssymb}
\usepackage{amsthm} 
\usepackage{XCharter} 
\usepackage[charter, expert, greekuppercase=italicized, greekfamily=didot]{mathdesign}
\usepackage{mathtools} 
\usepackage{enumitem} 
\usepackage{tikz-cd} 
\usepackage{tikz}
\usetikzlibrary{arrows,arrows.meta}
\tikzcdset{arrow style=tikz, diagrams={>=latex}}

\usepackage{etoolbox}

\usepackage{xcolor} 
\definecolor{green}{RGB}{0,127,0}
\definecolor{redd}{RGB}{191,0,0} 

\definecolor{red}{RGB}{105,89,205}
\usepackage[colorlinks=true]{hyperref}

\usepackage[notref, notcite]{showkeys} 
\usepackage[cmtip,arrow]{xy}

\DeclareMathOperator{\Aut}{Aut} 
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Stab}{Stab} 
\DeclareMathOperator{\st}{st}
\DeclareMathOperator{\Flim}{Flim} 
\DeclareMathOperator{\Int}{{Int}}
\DeclareMathOperator{\rng}{{rng}}
\DeclareMathOperator{\dom}{{dom}}

\newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} 
\newcommand{\cC}{\mathcal C} 
\newcommand{\cV}{\mathcal{V}} 
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cG}{\mathcal{G}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\bN}{\mathbb N} 
\newcommand{\bR}{\mathbb R}
\newcommand{\bZ}{\mathbb Z} 
\newcommand{\bQ}{\mathbb Q}
\newcommand{\bK}{\mathcal K}

\newcommand{\FrAut}{\Pi}
\newcommand{\FrGr}{\Gamma}

\DeclareMathOperator{\im}{{Im}} 
\DeclareMathOperator{\id}{{id}} 
\DeclareMathOperator{\lin}{{Lin}}
\DeclareMathOperator{\Th}{{Th}}

\newtheorem{theorem}{Theorem} 
\numberwithin{theorem}{section}
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact} 
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{question}[theorem]{Question}
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem*{theorem2}{Theorem}
\newtheorem*{claim2}{Claim} 
\newtheorem*{corollary2}{Corollary}
\newtheorem*{question2}{Question} 
\newtheorem*{conjecture2}{Conjecture}


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


\theoremstyle{definition} 
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{definition2}{Definition} 
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark} 
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark2}{Remark}


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


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

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

  \section{Conjugacy classes in automorphism groups}

  TODO:
  \begin{itemize}
	\item w głównym dowodzie mogę użyć wprost AP, nie muszę tego uzasadniać
	  jeszcze raz.
  \end{itemize}

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

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

  % \begin{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{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}

    %   \begin{proposition} Generically, the set of fixed points of $f\in
  %   \Aut(M)$ is isomorphic to $M$ (as a graph).  \end{proposition}

  \begin{theorem}
	\label{theorem:generic_aut_graph}
	Let $\FrGr$ be the Fraïssé limit of the class of all finite graphs $\bK$.
	Then $\FrGr$ has a generic automorphism $\tau\in\Aut(\FrGr)$, i.e. the
	conjugacy class of $\tau$ is comeagre in $G = \Aut(\FrGr)$.
  \end{theorem}

  \begin{proof}
	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, this will also be a subset of the 
	conjugacy class of $\tau$. By the Banach-Mazur theorem 
	\ref{theorem:banach_mazur_thm} this will prove that the 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 \FrGr$ 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 $\FrGr$. 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 random graph
	such that $(\FrGr, g) = \Flim{\cH}$, i.e. the Fraïssé limit of finite
	graphs with automorphism. Precisely, $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$.
	By the Fraïssé theorem \ref{theorem:fraisse_thm}
	it will follow that $(\FrGr, g)\cong (\FrAut, \sigma)$. By the 
	proposition \ref{proposition:graph-aut-is-normal} we can assume without
	the loss of generality that $\FrAut = \FrGr$ as a plain graph. 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 $(\FrGr, g)$ is exactly $\cH$ and so that it is weakly ultrahomogeneous
	will produce expected result. First, let us enumerate all pairs of finite
	graphs with automorphism $\{\langle(A_n, \alpha_n), (B_n, \beta_n)\rangle\}_{n\in\bN}$
	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 graph. We enumerate the vertices of the random graph 
	$\FrGr = \{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 subgraph $\FrGr_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 graphs 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 graph 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}
			(A_{i,j}, \alpha_{i,j}) \arrow[d, "\subseteq"'] \arrow[r, "f_{i,j}"] & (\FrGr_{n-1}, g_{n-1}) \arrow[d, "\subseteq"] \\
			(B_{i,j}, \beta_{i,j}) \arrow[r, dashed, "\hat{f}_{i,j}"'] & (\FrGr_n, g_n)
		  \end{tikzcd}
		\end{center}
	\end{enumerate}

	First item makes sure that no infinite orbit will not be present in $g$. The 
	second item together with the first one are necessary for $g$ to be an 
	automorphism of $\FrGr$. 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 (iii) item. Namely, we will construct $\FrGr'_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 $(\FrGr'_n, g'_n)$. Without the loss of generality
	we may assume that $f_{i,j}$ is an inclusion and that $A_{i,j} = B_{i,j}\cap\FrGr_{n-1}$.
	Then let $\FrGr'_n = B_{i,j}\cup\FrGr_{n-1}$ and $g'_n = g_{n-1}\cup \beta_{i,j}$.
	Then $(B_{i,j}, \beta_{i,j})$ simply embeds by inclusion in $(\FrGr'_n, g'_n)$,
	i.e. this diagram commutes:

	\begin{center}
	  \begin{tikzcd}
		(A_{i,j}, \alpha_{i,j}) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & (\FrGr_{n-1}, g_{n-1}) \arrow[d, "\subseteq"] \\
		(B_{i,j}, \beta_{i,j}) \arrow[r, dashed, "\subseteq"'] & (\FrGr'_n, g'_n)
	  \end{tikzcd}
	\end{center}

	The argument that those are actually embeddings is almost the same as in
	proof of the amalgamation property of $\cH$.	

	It may be also assumed without the loss of generality that $\FrGr'_n\subseteq \FrGr$.
	Of course by the recursive assumption $\FrGr_{n-1}\subseteq\FrGr$. The 
	$\FrGr'_n \setminus\FrGr_{n-1} = B_{i,j}\setminus A_{i,j}$ can be found in
	$\FrGr$ by the random graph property -- we can find vertices of the remaining
	part of $B_{i,j}$ each at a time so that all edges are correct.

	Now, by the WHP of $\bK$ we can extend the graph $\FrGr'_n\cup\{v_n\}$ together
	with its partial isomorphism $g'_n$ to a graph $\FrGr_n$ together with its
	automorphism $g_n\supseteq g'_n$, where without the loss of generality we
	may assume that $\FrGr_n\subseteq\FrGr$. 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 $\FrGr$ such that $(\FrGr, g)$ has the age $\cH$ and has weak ultrahomogeneity.
	It is of course an automorphism of $\FrGr$ as it is defined for every $v\in\FrGr$
	and is a sum of increasing chain of finite automorphisms.

	Take any finite graph 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 $(\FrGr_n, g_n)$, hence it embeds
	into $(\FrGr, g)$. With a similar argument we can see that $(\FrGr, 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 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.
  \end{proof}

  \printbibliography
\end{document}