\documentclass[11pt, a4paper, final]{amsart} \setlength{\emergencystretch}{2em} \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[utf8]{inputenc} \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} \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 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{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 graphs, which form a Fraïssé class. \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 the disjoint parts). \end{proof} \begin{definition} The \emph{random graph} is the Fraïssé limit of the class of finite graphs $\cG$ denoted by $\Gamma = \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 verticies if they should be connected or not. It turns out that the graph constructed this way is exactly the random graph we described above. The random graph $\Gamma$ has one particular property that is unique to the random graph. \begin{fact}[random graph property] For each finite disjoint $X, Y\subseteq \Gamma$ there exists $v\in\Gamma$ 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\Gamma$. Let $G_{XY}$ be the subgraph of $\Gamma$ 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 verticies 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 $\Gamma$. Wihtout 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 ultrahomogenity of $\Gamma$ this isomoprhism extends to an automorphism $\sigma\in\Aut(\Gamma)$. 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 isomorhpic to the random graph $\Gamma$. \end{fact} \begin{proof} Enumerate verticies of both graphs: $\Gamma = \{a_1, a_2\ldots\}$ and $G = \{b_1, b_2\ldots\}$. We will construct a chain of partial isomorphisms $f_n\colon \Gamma\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 isomoprhism. Let $X = \{a\in\Gamma\mid aE_{\Gamma} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, i.e. $X$ are verticies of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\Gamma$ and $Y$ are those verticies that are not connected with $a_{n+1}$. Let $b$ be a vertex of $G$ that is connected to all verticies 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 isomoprhism. 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. $f = \bigcup^{\infty}_{n=0}f_n$ is an isomoprhism between $\Gamma$ and $G$. Take any $a, b\in \Gamma$. Then for some big enough $n$ we have that $aE_{\Gamma}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 $\Gamma$. \begin{proposition} 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 forms a Fraïssé class. \begin{proposition} Let $\cH$ be the class of all finite graphs with 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 obivous, JEP follows by the same argument as in plain graphs. We need to show that the class has the amalgamation property. Take any graphs $(A, \alpha), (B, \beta), (C,\gamma)$ such that $A$ embedds into $B$ and $C$. Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in the proof for the plain graphs. We will define the automorphis $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. (TODO: chyba nie tylko extends ale coś więcej: wiem o co chodzi, ale nie wiem jak to napisać) We let $\delta_{\upharpoonright X} = \id_X$ for $X\in \{A, B\setminus A, C\setminus B\}$. Let's check the definition is correct. In order to do that, we have to show that for any $u, v\in D (uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$. We have a few cases: \begin{itemize} \item \end{itemize} \end{proof} \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{fact} 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{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 substructures of $A$ $p\colon A\to 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} 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} \printbibliography \end{document}