From 14de439d475ec315ae40c85f813036e5568a019f Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Wed, 29 Jun 2022 16:03:50 +0200 Subject: =?UTF-8?q?Zmiana=20struktury,=20teraz=20osobne=20pliki=20na=20ka?= =?UTF-8?q?=C5=BCd=C4=85=20sekcj=C4=99?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- lic_malinka.pdf | Bin 419889 -> 419937 bytes lic_malinka.tex | 1045 +----------------------------------------- sections/conj_classes.tex | 251 ++++++++++ sections/fraisse_classes.tex | 451 ++++++++++++++++++ sections/introduction.tex | 5 + sections/preliminaries.tex | 347 ++++++++++++++ 6 files changed, 1060 insertions(+), 1039 deletions(-) create mode 100644 sections/conj_classes.tex create mode 100644 sections/fraisse_classes.tex create mode 100644 sections/introduction.tex create mode 100644 sections/preliminaries.tex diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 4d7d77d..dc875f1 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ 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} diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex new file mode 100644 index 0000000..8beace0 --- /dev/null +++ b/sections/conj_classes.tex @@ -0,0 +1,251 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + Let $M$ be a countable $L$-structure. We define a topology on the $G=\Aut(M)$: + for any finite function $f\colon M\to M$ we have a basic open set + $[f]_{G} = \{g\in G\mid f\subseteq g\}$. + + \subsection{Prototype: pure set} + + In this section, $M=(M,=)$ is an infinite countable set (with no structure + beyond equality). + + \begin{proposition} + \label{proposition:cojugate-classes} + If $f_1,f_2\in \Aut(M)$, then $f_1$ and $f_2$ are conjugate if and only + if for each $n\in \bN\cup \{\aleph_0\}$, $f_1$ and $f_2$ have the same + number of orbits of size $n$. + \end{proposition} + + \begin{theorem} + Let $\sigma\in \Aut(M)$ be an automorphism with no infinite orbit and with + infinitely many orbits of size $n$ for every $n>0$. Then the conjugacy + class of $\sigma$ is comeagre in $\Aut(M)$. + \end{theorem} + + \begin{proof} + We will show that the conjugacy class of $\sigma$ is an intersection of countably + many comeagre sets. + + Let $A_n = \{\alpha\in Aut(M)\mid \alpha\text{ has infinitely many orbits of size }n\}$. + This set is comeagre for every $n>0$. Indeed, we can represent this set + as an intersection of countable family of open dense sets. Let $B_{n,k}$ + be the set of all finite functions $\beta\colon M\to M$ that consists + of exactly $k$ distinct $n$-cycles. Then: + \begin{align*} + A_n &= \{\alpha\in\ \Aut(M) \mid \alpha\text{ has infinitely many orbits of size }n\} \\ + &= \bigcap_{k=1}^{\infty} \{\alpha\in \Aut(M)\mid \alpha\text{ has at least }k\text{ orbits of size }n\} \\ + &= \bigcap_{k=1}^{\infty} \bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)}, + \end{align*} + where indeed, $\bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)}$ is dense in + $\Aut(M)$: take any finite $\gamma\colon M\to M$ such that $[\gamma]_{\Aut(M)}$ + is nonempty. Then also + $\bigcup_{\beta\in B_{n,k}} [\beta]_{\Aut(M)}\cap[\gamma]_{\Aut(M)}\neq\emptyset$, + one can easily construct a permutation that extends $\gamma$ and have at least + $k$ many $n$-cycles. + + Now we see that $A = \bigcap_{n=1}^{\infty} A_n$ is a comeagre set consisting + of all functions that have infinitely many $n$-cycles for each $n$. The only + thing left to show is that the set of functions with no infinite cycle is + also comeagre. Indeed, for $m\in M$ let + $B_m = \{\alpha\in\Aut(M)\mid m\text{ has finite orbit in }\alpha\}$. This + is an open dense set. It is a sum over basic open sets generated by finite + permutations with $m$ in their domain. Denseness is also easy to see. + + Finally, by the proposition \ref{proposition:cojugate-classes}, we can say that + $$\sigma^{\Aut(M)}=\bigcap_{n=1}^\infty A_n \cap \bigcap_{m\in M} B_m,$$ + which concludes the proof. + \end{proof} + + \subsection{More general structures} + + \begin{fact} + \label{fact:conjugacy} + Suppose $M$ is an arbitrary structure and $f_1,f_2\in \Aut(M)$. + Then $f_1$ and $f_2$ are conjugate if and only if $(M,f_1)\cong + (M,f_2)$ as structures with one additional unary relation that is + an automorphism. + \end{fact} + + \begin{proof} + Suppose that $f_1 = g^{-1}f_2g$ for some $g\in \Aut(M)$. + Then $g$ is the automorphism we're looking for. On the other hand if + $g\colon (M, f_1)\to (M, f_2)$ is an isomorphism, then + $g\circ f_1 = f_2 \circ g$ which exactly means that $f_1, f_2$ conjugate. + \end{proof} + + \begin{theorem} + \label{theorem:generic_aut_general} + Let $\cC$ be a Fraïssé class of finite structures of a theory $T$ in a + relational language $L$. Let $\cD$ be the class of the finite structures of + $T$ in the language $L$ with additional unary function symbol interpreted + as an automorphism of the structure. If $\cC$ has the weak Hrushovski property + and $\cD$ is a Fraïssé class, then there is a comeagre conjugacy class in the + automorphism group of the $\Flim(\cC)$. + \end{theorem} + + \begin{proof} + Let $\Gamma = \Flim(\cC)$ and $(\Pi, \sigma) = \Flim(\cD)$. Let $G = \Aut(\Gamma)$, + i.e. $G$ is the automorphism group of $\Gamma$. First, by the theorem + \ref{theorem:isomorphic_fr_lims}, we may assume without the loss of generality + that $\Pi = \Gamma$. + We will construct a strategy for the second player in the Banach-Mazur game + on the topological space $G$. This strategy will give us a subset + $A\subseteq G$ and as we will see a subset of a cojugacy class in $G$. + By the Banach-Mazur theorem \ref{theorem:banach_mazur_thm} this will prove + that this class is comeagre. + + Recall, $G$ has a basis consisting of open + sets $\{g\in G\mid g\upharpoonright_A = g_0\upharpoonright_A\}$ for some + finite set $A\subseteq \Gamma$ and some automorphism $g_0\in G$. In other + words, a basic open set is a set of all extensions of some finite partial + isomorphism $g_0$ of $\Gamma$. By $B_{g}\subseteq G$ we denote a basic + open subset given by a finite partial isomorphism $g$. From now on we will + consider only finite partial isomorphism $g$ such that $B_g$ is nonempty. + + With the use of corollary \ref{corollary:banach-mazur-basis} we can consider + only games, where both players choose finite partial isomorphisms. Namely, + player \textit{I} picks functions $f_0, f_1,\ldots$ and player \textit{II} + chooses $g_0, g_1,\ldots$ such that + $f_0\subseteq g_0\subseteq f_1\subseteq g_1\subseteq\ldots$, which identify + the corresponding basic open subsets $B_{f_0}\supseteq B_{g_0}\supseteq\ldots$. + + Our goal is to choose $g_i$ in such a manner that the resulting function + $g = \bigcap^{\infty}_{i=0}g_i$ will be an automorphism of the Fraïssé limit + $\Gamma$ such that $(\Gamma, g) = \Flim{\cD}$. + Precisely, $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$, + by the Fraïssé theorem \ref{theorem:fraisse_thm} + it will follow that $(\Gamma, g)\cong (\Pi, \sigma)$. Hence, + by the fact \ref{fact:conjugacy}, $g$ and $\sigma$ conjugate in $G$. + + Once again, by the Fraïssé theorem \ref{theorem:fraisse_thm} and the + \ref{lemma:weak_ultrahom} lemma constructing $g_i$'s in a way such that + age of $(\Gamma, g)$ is exactly $\cD$ and so that it is weakly ultrahomogeneous + will produce expected result. First, let us enumerate all pairs of structures + $\{\langle(A_n, \alpha_n), (B_n, \beta_n)\rangle\}_{n\in\bN},\in\cD$ + such that the first element of the pair embeds by inclusion in the second, + i.e. $(A_n, \alpha_n)\subseteq (B_n, \beta_n)$. Also, it may be that + $A_n$ is an empty. We enumerate the elements of the Fraïssé limit + $\Gamma = \{v_0, v_1, \ldots\}$. + + Fix a bijection $\gamma\colon\bN\times\bN\to\bN$ such that for any + $n, m\in\bN$ we have $\gamma(n, m) \ge n$. This bijection naturally induces + a well ordering on $\bN\times\bN$. This will prove useful later, as the + main argument of the proof will be constructed as a bookkeeping argument. + + Just for sake of fixing a technical problem, let $g_{-1} = \emptyset$ and + $X_{-1} = \emptyset$. + Suppose that player \textit{I} in the $n$-th move chooses a finite partial + isomorphism $f_n$. We will construct $g_n\supseteq f_n$ and a set $X_n\subseteq\bN^2$ + such that following properties hold: + + \begin{enumerate}[label=(\roman*)] + \item $g_n$ is an automorphism of the induced substructure $\Gamma_n$, + \item $g_n(v_n)$ and $g_n^{-1}(v_n)$ are defined, + \item let + $\{\langle (A_{n,k}, \alpha_{n, k}), (B_{n,k}, \beta_{n,k}), f_{n, k}\rangle\}_{k\in\bN}$ + be the enumeration of all pairs of finite structures of $T$ with automorphism + such that the first is a substructure of the second, i.e. + $(A_{n,k}, \alpha_{n,k})\subseteq (B_{n,k}, \beta_{n,k})$, and $f_{n,k}$ + is an embedding of $(A_{n,k}, \alpha_{n,k})$ in the $\FrGr_{n-1}$ (which + is the substructure induced by $g_{n-1}$). Let + $(i, j) = \min\{(\{0, 1, \ldots\} \times \bN) \setminus X_{n-1}\}$ (with the + order induced by $\gamma$). Then $X_n = X_{n-1}\cup\{(i,j)\}$ and + $(B_{n,k}, \beta_{n,k})$ embeds in $(\FrGr_n, g_n)$ so that this diagram + commutes: + + \begin{center} + \begin{tikzcd} + & (\Gamma_n, g_n) & \\ + (B_{i,j}, \beta_{i,j}) \arrow[ur, dashed, "\hat{f}_{i,j}"] & & (\FrGr_{n-1}, g_{n-1}) \arrow[ul, dashed, "\subseteq"'] \\ + & (A_{i,j}, \alpha_{i,j}) \arrow[ur, "f_{i,j}"'] \arrow[ul, "\subseteq"] + \end{tikzcd} + \end{center} + \end{enumerate} + + First item makes sure that no infinite orbit will be present in $g$. The + second item together with the first one are necessary for $g$ to be an + automorphism of $\Gamma$. The third item is the one that gives weak + ultrahomogeneity. Now we will show that indeed such $g_n$ may be constructed. + + First, we will suffice the item (iii). Namely, we will construct $\Gamma'_n, g'_n$ + such that $g_{n-1}\subseteq g'_n$ and $f_{i,j}$ extends to an embedding of + $(B_{i,j}, \beta_{i,j})$ to $(\Gamma'_n, g'_n)$. But this can be easily + done by the fact, that $\cD$ has the amalgamation property. Moreover, without + the loss of generality we can assume that all embeddings are inclusions. + + \begin{center} + \begin{tikzcd} + & (\Gamma'_n, g'_n) & \\ + (B_{i,j}, \beta_{i,j}) \arrow[ur, dashed, "\subseteq"] & & (\Gamma_{n-1}, g_{n-1}) \arrow[ul, dashed, "\subseteq"'] \\ + & (A_{i,j}, \alpha_{i,j}) \arrow[ur, "\subseteq"'] \arrow[ul, "\subseteq"] + \end{tikzcd} + \end{center} + + By the weak ultrahomogeneity we may assume that $\Gamma'_n\subseteq \Gamma$: + + \begin{center} + \begin{tikzcd} + (B_{i,j}\cup\Gamma_{n-1}, \beta_{i,j}\cup g_{n-1}) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Gamma \\ + (\Gamma'_{n}, g'_n)\arrow[ur, dashed, "f"'] + \end{tikzcd} + \end{center} + + Now, by the WHP of $\bK$ we can extend the graph $\Gamma'_n\cup\{v_n\}$ together + with its partial isomorphism $g'_n$ to a graph $\Gamma_n$ together with its + automorphism $g_n\supseteq g'_n$ and without the loss of generality we + may assume that $\Gamma_n\subseteq\Gamma$. This way we've constructed $g_n$ + that has all desired properties. + + Now we need to see that $g = \bigcap^{\infty}_{n=0}g_n$ is indeed an automorphism + of $\Gamma$ such that $(\Gamma, g)$ has the age $\cH$ and is weakly ultrahomogeneous. + It is of course an automorphism of $\Gamma$ as it is defined for every $v\in\Gamma$ + and is a sum of increasing chain of finite automorphisms. + + Take any finite structure of $T$ with automorphism $(B, \beta)$. Then, there are + $i, j$ such that $(B, \beta) = (B_{i, j}, \beta_{i,j})$ and $A_{i,j}=\emptyset$. + By the bookkeeping there was $n$ such that + $(i, j) = \min\{\{0,1,\ldots\}\times\bN\setminus X_{n-1}\}$. + This means that $(B, \beta)$ embeds into $(\Gamma_n, g_n)$, hence it embeds + into $(\Gamma, g)$, thus it has age $\cH$. + With a similar argument we can see that $(\Gamma, g)$ is weakly ultrahomogeneous. + + By this we know that $g$ and $\sigma$ conjugate in $G$. As we stated in the + beginning of the proof, the set $A$ of possible outcomes of the game (i.e. + possible $g$'s we end up with) is comeagre in $G$, thus $\sigma^G$ is also + comeagre and $\sigma$ is a generic automorphism, as it contains a comeagre + set $A$. + \end{proof} + + \subsection{Properties of the generic automorphism} + + Let $\cC$ be a Fraïssé class in a finite relational language $L$ with + weak Hrushovski property. Let $\cH$ be the Fraïssé class of the $L$-structures + with additional automorphism symbol. Let $\Gamma = \Flim(\cC)$. + + % \begin{proposition} + % Let $\sigma$ be the generic automorphism of the random graph $\FrGr$. Then + % the graph induced by the set of the fixed points of $\sigma$ is isomorphic + % to $\FrGr$. + % \end{proposition} + % + % \begin{proof} + % Let $F = \{v\in\FrGr\mid \sigma(v) = v\}$. It suffices to show that $F$ is + % infinite and has the random graph property. + % \end{proof} + \begin{proposition} + Let $\sigma$ be the generic automorphism of $\Gamma$. Then the set + of fixed points of $\sigma$ is isomorphic to $\Gamma$. + \end{proposition} + + \begin{proof} + Let $S = \{x\in \Gamma\mid \sigma(x) = x\}$. + First we need to show that it is an infinite. By the theorem \ref{theorem:generic_aut_general} + we know that $(\Gamma, \sigma)$ is the Fraïssé limit of $\cH$, thus we + can embedd finite $L$-structures of any size with identity as an + automorphism of the structure into $(\Gamma, \sigma)$. Thus $S$ has to be + infinite. Also, the same argument shows that the age of the structure is + exactly $\cC$. It is weakly ultrahomogeneous, also by the fact that + $(\Gamma, \sigma)$ is in $\cH$. + \end{proof} +\end{document} diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex new file mode 100644 index 0000000..ca2247e --- /dev/null +++ b/sections/fraisse_classes.tex @@ -0,0 +1,451 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + In this section we will take a closer look at classes of finitely + generated structures with some characteristic properties. More + specifically, we will describe a concept developed by a French + mathematician Roland Fraïssé called Fraïssé limit. + + \subsection{Definitions} + \begin{definition} + Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is + the class $\bK$ of all finitely generated structures that embeds into $M$. + The age of $M$ is also associated with class of all structures embeddable in + $M$ \emph{up to isomorphism}. + \end{definition} + + \begin{definition} + We say that $M$ has \emph{countable age} when its age has countably many + isomorphism types of finitely generated structures. + \end{definition} + + \begin{definition} + Let $\bK$ be a class of finitely generated structures. $\bK$ has + \emph{hereditary property (HP)} if for any $A\in\bK$, any finitely generated + substructure $B$ of $A$ it holds that $B\in\bK$. + \end{definition} + + \begin{definition} + Let $\bK$ be a class of finitely generated structures. We say that $\bK$ has + \emph{joint embedding property (JEP)} if for any $A, B\in\bK$ there is a + structure $C\in\bK$ such that both $A$ and $B$ embed in $C$. + + \begin{center} + \begin{tikzcd} + & C & \\ + A \arrow[ur, dashed, "f"] & & B \arrow[ul, dashed, "g"'] + \end{tikzcd} + \end{center} + + In terms of category theory, this is a \emph{span} in category $\bK$. + \end{definition} + + Fraïssé has shown fundamental theories regarding age of a structure, one of + them being the following one: + + \begin{fact} + \label{fact:age_is_hpjep} + Suppose $L$ is a signature and $\bK$ is a nonempty finite or countable set + of finitely generated $L$-structures. Then $\bK$ has the HP and JEP if + and only if $\bK$ is the age of some finite or countable structure. + \end{fact} + + Beside the HP and JEP Fraïssé has distinguished one more property of the + class $\bK$, namely amalgamation property. + + \begin{definition} + Let $\bK$ be a class of finitely generated $L$-structures. We say that $\bK$ + has the \emph{amalgamation property (AP)} if for any $A, B, C\in\bK$ and + embeddings $e\colon C\to A, f\colon C\to B$ there exists $D\in\bK$ together + with embeddings $g\colon A\to D$ and $h\colon A\to D$ such that + $g\circ e = h\circ f$. + \begin{center} + \begin{tikzcd} + & D & \\ + A \arrow[ur, dashed, "g"] & & B \arrow[ul, dashed, "h"'] \\ + & C \arrow[ur, "f"'] \arrow[ul, "e"] + \end{tikzcd} + \end{center} + \end{definition} + + In terms of category theory, amalgamation over some structure $C$ is a + pushout diagram. + + \begin{definition} + Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogeneous} if every + isomorphism between finitely generated substructures of $M$ extends to an + automorphism of $M$. + \end{definition} + + Having those definitions we can provide the main Fraïssé theorem. + + \begin{theorem}[Fraïssé theorem] + \label{theorem:fraisse_thm} + Let L be a countable language and let $\bK$ be a nonempty countable set of + finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ is + the age of a countable, ultrahomogeneous $L$-structure $M$. Moreover, $M$ is + unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\bK$ + and denote this by $M = \Flim(\bK)$. + \end{theorem} + + This is a well known theorem. One can read a proof of this theorem in Wilfrid + Hodges' classical book \textit{Model Theory}~\cite{hodges_1993}. In the proof + of this theorem appears another, equally important \ref{lemma:weak_ultrahom}. + + \begin{definition} + We say that an $L$-structure $M$ is \emph{weakly ultrahomogeneous} if for any + $A, B$ finitely generated substructures of $M$ such that $A\subseteq B$ and + an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which + extends $f$. + \begin{center} + \begin{tikzcd} + A \arrow[d, "\subseteq"'] \arrow[r, "f"] & D \\ + B \arrow[ur, dashed, "g"'] + \end{tikzcd} + \end{center} + \end{definition} + + \begin{lemma} + \label{lemma:weak_ultrahom} + A countable structure is ultrahomogeneous if and only if it is weakly + ultrahomogeneous. + \end{lemma} + + This lemma will play a major role in the later parts of the paper. Weak + ultrahomogeneity is an easier and more intuitive property and it will prove + useful when recursively constructing the generic automorphism of a Fraïssé + limit. + + % \begin{fact} If $\bK$ is a uniformly locally finite Fraïssé class, then + % $\Flim(\bK)$ is $\aleph_0$-categorical and has quantifier elimination. + % \end{fact} + + \subsection{Random graph} + + In this section we'll take a closer look on a class of finite unordered graphs, + which is a Fraïssé class. + + The language of unordered graphs $L$ consists of a single binary + relational symbol $E$. If $G$ is an $L$-structure then we call it a + \emph{graph}, and its elements $\emph{vertices}$. If for some vertices + $u, v\in G$ we have $G\models uEv$ then we say that there is an $\emph{edge}$ + connecting $u$ and $v$. If $G\models \forall x\forall y (xEy\leftrightarrow yEx)$ + then we say that $G$ is an \emph{unordered graph}. From now on we omit the word + \textit{unordered} and graphs as unordered. + + \begin{proposition} + Let $\cG$ be the class of all finite graphs. $\cG$ is a Fraïssé class. + \end{proposition} + \begin{proof} + $\cG$ is of course countable (up to isomorphism) and has the HP + (graph substructure is also a graph). It has JEP: having two finite graphs + $G_1,G_2$ take their disjoint union $G_1\sqcup G_2$ as the extension of them + both. $\cG$ has the AP. Having graphs $A, B, C$, where $B$ and $C$ are + supergraphs of $A$, we can assume without loss of generality, that + $(B\setminus A) \cap (C\setminus A) = \emptyset$. Then + $A\sqcup (B\setminus A)\sqcup (C\setminus A)$ is the graph we're looking + for (with edges as in B and C and without any edges between $B\setminus A$ + and $C\setminus A$). + \end{proof} + + \begin{definition} + The \emph{random graph} is the Fraïssé limit of the class of finite graphs + $\cG$ denoted by $\FrGr = \Flim(\cG)$. + \end{definition} + + The concept of the random graph emerges independently in many fields of + mathematics. For example, one can construct the graph by choosing at random + for each pair of vertices if they should be connected or not. It turns out + that the graph constructed this way is isomorphic to the random graph with + probability 1. + + The random graph $\FrGr$ has one particular property that is unique to the + random graph. + + \begin{fact}[random graph property] + For each finite disjoint $X, Y\subseteq \FrGr$ there exists $v\in\FrGr\setminus (X\cup Y)$ + such that $\forall u\in X (vEu)$ and $\forall u\in Y (\neg vEu)$. + \end{fact} + \begin{proof} + Take any finite disjoint $X, Y\subseteq\FrGr$. Let $G_{XY}$ be the + subgraph of $\FrGr$ induced by the $X\cup Y$. Let $H = G_{XY}\cup \{w\}$, + where $w$ is a new vertex that does not appear in $G_{XY}$. Also, $w$ is connected to + all vertices of $G_{XY}$ that come from $X$ and to none of those that come + from $Y$. This graph is of course finite, so it is embeddable in $\FrGr$. + Without loss of generality assume that this embedding is simply inclusion. + Let $f$ be the partial isomorphism from $X\sqcup Y$ to $H$, with $X$ and + $Y$ projected to the part of $H$ that come from $X$ and $Y$ respectively. + By the ultrahomogeneity of $\FrGr$ this isomorphism extends to an automorphism + $\sigma\in\Aut(\FrGr)$. Then $v = \sigma^{-1}(w)$ is the vertex we sought. + \end{proof} + + \begin{fact} + If a countable graph $G$ has the random graph property, then it is + isomorphic to the random graph $\FrGr$. + \end{fact} + \begin{proof} + Enumerate vertices of both graphs: $\FrGr = \{a_1, a_2\ldots\}$ and $G + = \{b_1, b_2\ldots\}$. + We will construct a chain of partial isomorphisms $f_n\colon \FrGr\to G$ + such that $\emptyset = f_0\subseteq f_1\subseteq f_2\subseteq\ldots$ and $a_n \in + \dom(f_n)$ and $b_n\in\rng(f_n)$. + + Suppose we have $f_n$. We seek $b\in G$ such that $f_n\cup \{\langle + a_{n+1}, b\rangle\}$ is a partial isomorphism. + If $a_{n+1}\in\dom{f_n}$, then simply $b = f_n(a_{n+1})$. Otherwise, + let $X = \{a\in\FrGr\mid + aE_{\FrGr} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, i.e. $X$ are + vertices of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and + $Y$ are those vertices that are not connected with $a_{n+1}$. Let $b$ be + a vertex of $G$ that is connected to all vertices of $f_n[X]$ and to none + $f_n[Y]$ (it exists by the random graph property). Then $f_n\cup \{\langle + a_{n+1}, b\rangle\}$ is a partial isomorphism. We find $a$ for the + $b_{n+1}$ in the similar manner, so that $f_{n+1} = f_n\cup \{\langle + a_{n+1}, b\rangle, \langle a, b_{n+1}\rangle\}$ is a partial isomorphism. + + Finally, $f = \bigcup^{\infty}_{n=0}f_n$ is an isomorphism between $\FrGr$ + and $G$. Take any $a, b\in \FrGr$. Then for some big enough $n$ we have + that $aE_{\FrGr}b\Leftrightarrow f_n(a)E_{G}f_n(b) \Leftrightarrow f(a)E_{G}f(b)$. + \end{proof} + + Using this fact one can show that the graph constructed in the probabilistic + manner is in fact isomorphic to the random graph $\FrGr$. + + \begin{definition} We say that a Fraïssé class $\bK$ has \emph{weak + Hrushovski property} (\emph{WHP}) if for every $A\in \bK$ and an isomorphism + of its substructures $p\colon A\to A$ (also called a partial automorphism of $A$), + there is some $B\in \bK$ such + that $p$ can be extended to an automorphism of $B$, i.e.\ there is an + embedding $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following + diagram commutes: + \begin{center} + \begin{tikzcd} + B\ar[r,dashed,"\bar p"]&B\\ + A\ar[u,dashed,"i"]\ar[r,"p"]&A\ar[u,dashed,"i"] + \end{tikzcd} + \end{center} + \end{definition} + + \begin{proposition} + \label{proposition:finite-graphs-whp} + The class of finite graphs $\cG$ has the weak Hrushovski property. + \end{proposition} + + \begin{proof} + It may be there some day, but it may not! + \end{proof} + + \subsection{Canonical amalgamation} + + \begin{definition} + Let $\bK$ be a class finitely generated $L$-structures. We say that + $\bK$ has \emph{canonical amalgamation} if for every $C\in\bK$ there + is a functor $\otimes_C\colon\Cospan(\bK)\to\Pushout(\bK)$ such that + it has the following properties: + \begin{itemize} + \item Let $A\leftarrow C\rightarrow B$ be a cospan. Then $\otimes_C$ sends + it to a pushout that preserves ``the bottom`` structures and embeddings, i.e.: + \begin{center} + \begin{tikzcd} + & & & & A\otimes_C B & \\ + A & & B \arrow[r, dashed, "A\otimes_C B"] & A \arrow[ur, dashed] & & B \arrow[ul, dashed] \\ + & C \arrow[ul] \arrow[ur] & & & C \arrow[ul] \arrow[ur] & + \end{tikzcd} + \end{center} + + We have deliberately omited names for embeddings of $C$. Of course, + the functor has to take them into account, but this abuse of notation + is convenient and should not lead into confusion. + \item Let $A\leftarrow C\rightarrow B$, $A'\leftarrow C\rightarrow B'$ be cospans + with a natural transformation given by $\alpha\colon A\to A', \beta\colon B\to B', + \gamma\colon C\to C$. Then $\otimes_C$ preserves the morphisms of + when sending the natural transformation of those cospans to natural + transformation of pushouts by adding the + $\delta\colon A\otimes_C B\to A'\otimes_C B'$ morphism: + + \begin{center} + \begin{tikzcd} + & A'\otimes_C B' & \\ + A' \arrow[ur] & & B' \arrow[ul] \\ + & A\otimes_C B \ar[uu, dashed, "\delta"] & \\ + & C \arrow[uul, bend left] \arrow[uur, bend right] & \\ + A \arrow[uuu, dashed, "\alpha"] \arrow[uur, bend left, crossing over] & & B \arrow[uuu, dashed, "\beta"'] \arrow[uul, bend right, crossing over] \\ + & C \arrow[ur] \arrow[ul] \arrow[uu, dashed, "\gamma"] & \\ + \end{tikzcd} + \end{center} + % \begin{center} + % \begin{tikzcd} + % & A \ar[rrr, dashed, "\alpha"] \ar[drr, bend left=20, crossing over] & & & A' \ar[dr] & \\ + % C \ar[rr, dashed, "\gamma"] \ar[ur] \ar[dr] & & C \ar[rrd, bend right=20] \ar[rru, bend left=20] & A\otimes_C B \ar[rr, dashed, "\delta"] & & A' \otimes_C B' \\ + % & B \ar[rrr, dashed, "\beta"] \ar[urr, bend right=20, crossing over] & & & B' \ar[ur] & \\ + % \end{tikzcd} + % \end{center} + \end{itemize} + \end{definition} + + \begin{theorem} + \label{theorem:canonical_amalgamation_thm} + Let $\bK$ be a Fraïssé class of $L$-structures with canonical amalgamation. + Then the class $\cH$ of $L$-structures with automorphism is a Fraïssé class. + \end{theorem} + + \begin{proof} + $\cH$ is obviously countable and has HP. It suffices to show that it + has AP (JEP follows by taking $C$ to be the empty structure). Take any + $(A,\alpha), (B,\beta), (C,\gamma)\in \cH$ such that $(C,\gamma)$ embeds + into $(A,\alpha)$ and $(B,\beta)$. Then $\alpha, \beta, \gamma$ yield + an automorphism $\eta$ (as a natural transformation) of a cospan: + \begin{center} + \begin{tikzcd} + A & & B \\ + % & C \ar[ur] \ar[ul] & \\ + A \ar[u, dashed, "\alpha"] & C \ar[ur] \ar[ul] & B \ar[u, dashed, "\beta"'] \\ + & C \ar[ur] \ar[ul] \ar[u, dashed, "\gamma"] & + % (A, \alpha) & & (B, \beta) \\ + % & (C, \gamma) \ar[ur] \ar[ul] & + \end{tikzcd} + \end{center} + + Then, by the fact \ref{fact:functor_iso}, $\otimes_C(\eta)$ is an automorphism + of the pushout diagram: + + \begin{center} + \begin{tikzcd} + & A\otimes_C B \ar[loop above, "\delta"] & \\ + A \ar[ur] \ar[loop left, "\alpha"]& & B \ar[ul] \ar[loop right, "\beta"]\\ + & C \ar[ur] \ar[ul] \ar[loop below, "\gamma"] & + \end{tikzcd} + \end{center} + + TODO: ten diagram nie jest do końca taki jak trzeba, trzeba w zasadzie skopiować + ten z definicji kanonicznej amalgamcji. Czy to nie będzie wyglądać źle? + + This means that the morphism $\delta\colon A\otimes_C B\to A\otimes_C B$ + has to be automorphism. Thus, by the fact that the diagram commutes, + we have the amalgamation of $(A, \alpha)$ and $(B, \beta)$ over $(C,\gamma)$ + in $\cH$. + \end{proof} + + \subsection{Graphs with automorphism} + The language and theory of unordered graphs is fairly simple. We extend the + language by one unary symbol $\sigma$ and interpret it as an arbitrary + automorphism on the graph structure. It turns out that the class of such + structures is a Fraïssé class. + + \begin{proposition} + Let $\cH$ be the class of all finite graphs with an automorphism, i.e. + structures in the language $(E, \sigma)$ such that $E$ is a symmetric + relation and $\sigma$ is an automorphism on the structure. $\cH$ is + a Fraïssé class. + \end{proposition} + \begin{proof} + Countability and HP are obvious, JEP follows by the same argument as in + plain graphs. We need to show that the class has the amalgamation property. + + Take any $(A, \alpha), (B, \beta), (C,\gamma)\in\cH$ such that $A$ embeds + into $B$ and $C$. Without the loss of generality we may assume that + $B\cap C = A$ and $\alpha\subseteq\beta,\gamma$. + Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in + the proof for the plain graphs. We will define the automorphism + $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. + We let $\delta\upharpoonright_B = \beta, \delta\upharpoonright_C = \gamma$. + Let's check the definition is correct. We have to show that + $(uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$ holds for any $u, v\in + D$. We have two cases: + \begin{itemize} + \item $u, v\in X$, where $X$ is either $B$ or $C$. This case is trivial. + \item $u\in B\setminus A, v\in C\setminus A$. Then + $\delta(u)=\beta(u)\in B\setminus A$, similarly $\delta(v)=\gamma(v)\in + C\setminus A$. This follows from the fact, that $\beta\upharpoonright_A + = \alpha$, so for any $w\in A\quad\beta^{-1}(w)=\alpha^{-1}(w)\in A$, + similarly for $\gamma$. Thus, from the construction of $D$, $\neg uE_Dv$ + and $\neg \delta(u)E_D\delta(v)$. + \end{itemize} + \end{proof} + + The proposition says that there is a Fraïssé for the class $\cH$ of finite + graphs with automorphisms. We shall call it $(\FrAut, \sigma)$. Not + surprisingly, $\FrAut$ is in fact a random graph. + + \begin{proposition} + \label{proposition:graph-aut-is-normal} + The Fraïssé limit of $\cH$ interpreted as a plain graph (i.e. as a reduct + to the language of graphs) is isomorphic to the random graph $\FrGr$. + \end{proposition} + + \begin{proof} + It is enough to show that $\FrAut = \Flim(\cH)$ has the random graph + property. Take any finite disjoint $X, Y\subseteq \FrAut$. Without the loss + of generality assume that $X\cup Y$ is $\sigma$-invariant, i.e. + $\sigma(v)\in X\cup Y$ for $v\in X\cup Y$. This assumption can be made + because there are no infinite orbits in $\sigma$, which in turn is due to + the fact that $\cH$ is the age of $\FrAut$. + + Let $G_{XY}$ be the graph induced by $X\cup Y$. Take $H=G_{XY}\sqcup {v}$ + as a supergraph of $G_{XY}$ with one new vertex $v$ connected to all + vertices of $X$ and to none of $Y$. By the proposition + \ref{proposition:finite-graphs-whp} we can extend $H$ together with its + partial isomorphism $\sigma\upharpoonright_{X\cup Y}$ to a graph $R$ with + automorphism $\tau$. Once again, without the loss of generality we can + assume that $R\subseteq\FrAut$, because $\cH$ is the age of $\FrAut$. But + $R\upharpoonright_{G_{XY}}$ together with $\tau\upharpoonright_{G_{XY}}$ + are isomorphic to the $G_{XY}$ with $\sigma\upharpoonright_{G_{XY}}$. + + Thus, by ultrahomogeneity of $\FrAut$ this isomorphism extends to an + automorphism $\theta$ of $(\FrAut, \sigma)$. Then $\theta(v)$ is the vertex + that is connected to all vertices of $X$ and none of $Y$, because + $\theta[R\upharpoonright_X] = X, \theta[R\upharpoonright_Y] = Y$. + \end{proof} + + + \begin{theorem} + \label{theorem:isomorphic_fr_lims} + Let $\cC$ be a Fraïssé class of finite structures in a relational language + $L$ of some theory $T$. Let $\cD$ be a class of finite structures of the + theory $T$ in a relational language $L$ with additional unary function + symbol interpreted as an automorphism of the structure. If $\cC$ has the + weak Hrushovski property and $\cD$ is a Fraïssé class then the Fraïssé + limit of $\cC$ is isomorphic to the Fraïssé limit of $\cD$ reduced + to the language $L$. + \end{theorem} + + \begin{proof} + Let $\Gamma=\Flim(\cC)$ and $(\Pi, \sigma) =\Flim(\cD)$. By the Fraïssé + theorem \ref{theorem:fraisse_thm} it suffices to show that the age of $\Pi$ + is $\cC$ and that it has the weak ultrahomogeneity in the class $\cC$. The + former comes easily, as for every structure $A\in \cC$ we have the structure + $(A, \id_A)\in \cD$, which means that the structure $A$ embedds into $\Pi$. + Also, if a structure $(B, \beta)\in\cD$ embedds into $\cD$, then $B\in\cC$. + Hence, $\cC$ is indeed the age of $\Pi$. + + Now, take any structure $A, B\in\cC$ such that $A\subseteq B$. Without the + loss of generality assume that $A = B\cap \Pi$. Let $\bar{A}$ be the + smallest structure closed on the automorphism $\sigma$ and containg $A$. + It is finite, as $\cC$ is the age of $\Pi$. By the weak Hrushovski property, + of $\cC$ let $(\bar{B}, \beta)$ be a structure extending + $(B\cup \bar{A}, \sigma\upharpoonright_{\bar{A}})$. Again, we may assume + that $B\cup \bar{A}\subseteq \bar{B}$. Then, by the fact that $\Pi$ is a + Fraïssé limit of $\cD$ there is an embedding + $f\colon(\bar{B}, \beta)\to(\Pi, \sigma)$ + such that the following diagram commutes: + + \begin{center} + \begin{tikzcd} + (A, \emptyset) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & (\bar{A}, \sigma\upharpoonright_A) \arrow[d, "\subseteq"] \arrow[r, "\subseteq"] & (\Pi, \sigma) \\ + (B, \sigma\upharpoonright_B) \arrow[r, dashed, "\subseteq"'] & (\bar{B}, \beta) \arrow[ur, dashed, "f"] + \end{tikzcd} + \end{center} + + Then we simply get the following diagram: + + \begin{center} + \begin{tikzcd} + A \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Pi \\ + B \arrow[ur, dashed, "f\upharpoonright_B"'] + \end{tikzcd} + \end{center} + + which proves that $\Pi$ is indeed a weakly ultrahomogeneous structure in $\cC$. + Hence, it is isomorphic to $\Gamma$. + \end{proof} +\end{document} diff --git a/sections/introduction.tex b/sections/introduction.tex new file mode 100644 index 0000000..89004c7 --- /dev/null +++ b/sections/introduction.tex @@ -0,0 +1,5 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + There will be something! +\end{document} diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex new file mode 100644 index 0000000..832beae --- /dev/null +++ b/sections/preliminaries.tex @@ -0,0 +1,347 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + \subsection{Descriptive set theory} + \begin{definition} + Suppose $X$ is a topological space and $A\subseteq X$. + We say that $A$ is \emph{meagre} in $X$ if $A = \bigcup_{n\in\bN}A_n$, + where $A_n$ are nowhere dense subsets of $X$ (i.e. $\Int(\bar{A_n}) + = \emptyset$). + \end{definition} + + \begin{definition} + We say that $A$ is \emph{comeagre} in $X$ if it is + a complement of a meagre set. Equivalently, a set is comeagre if and only if it + contains a countable intersection of open dense sets. + \end{definition} + + % \begin{example} + Every countable set is meagre in any $T_1$ space, so, for example, $\bQ$ + is meagre in $\bR$ (although it is dense), which means that the set of + irrationals is comeagre. Another example is... + % \end{example} + + \begin{definition} + We say that a topological space $X$ is a \emph{Baire space} if every + comeagre subset of $X$ is dense in $X$ (equivalently, every meagre set has + empty interior). + \end{definition} + + \begin{definition} + Suppose $X$ is a Baire space. We say that a property $P$ \emph{holds + generically} for a point $x\in X$ if $\{x\in X\mid P\textrm{ holds for + }x\}$ is comeagre in $X$. + \end{definition} + + \begin{definition} + Let $X$ be a nonempty topological space and let + $A\subseteq X$. The \emph{Banach-Mazur game of $A$}, denoted as + $G^{\star\star}(A)$ is defined as follows: Players $I$ and + $\textit{II}$ take turns in playing nonempty open sets $U_0, V_0, + U_1, V_1,\ldots$ such that $U_0 \supseteq V_0 \supseteq U_1 \supseteq + V_1 \supseteq\ldots$. We say that player $\textit{II}$ wins the game if + $\bigcap_{n}V_n \subseteq A$. + \end{definition} + + There is an important theorem on the Banach-Mazur game: $A$ is comeagre + if and only if $\textit{II}$ can always choose sets $V_0, V_1, \ldots$ such that + it wins. Before we prove it we need to define notions necessary to + formalise and prove the theorem. + + \begin{definition} + $T$ is \emph{the tree of all legal positions} in the Banach-Mazur game + $G^{\star\star}(A)$ when $T$ consists of all finite sequences $(W_0, + W_1,\ldots, W_n)$, where $W_i$ are nonempty open sets such that + $W_0\supseteq W_1\supseteq\ldots\supseteq W_n$. In other words, $T$ is + a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$. + \end{definition} + + \begin{definition} + We say that $\sigma$ is \emph{a pruned subtree} of the tree of all legal + positions $T$ if $\sigma\subseteq T$, for any $(W_0, W_1, \ldots, + W_n)\in\sigma, n\ge 0$ there is a $W$ such that $(W_0, W_1,\ldots, W_n, + W)\in\sigma$ (it simply means that there's no finite branch in~$\sigma$) and + $(W_0, W_1,\ldots W_{n-1})\in\sigma$ (every node on a branch is in $\sigma$). + \end{definition} + + \begin{definition} + Let $\sigma$ be a pruned subtree of the tree of all legal positions $T$. By + $[\sigma]$ we denote \emph{the set of all infinite branches of $\sigma$}, + i.e. infinite sequences $(W_0, W_1, \ldots)$ such that $(W_0, W_1, \ldots + W_n)\in \sigma$ for any $n\in \bN$. + \end{definition} + + \begin{definition} + A \emph{strategy} for $\textit{II}$ in + $G^{\star\star}(A)$ is a pruned subtree $\sigma\subseteq T$ such that + \begin{enumerate}[label=(\roman*)] + \item $\sigma$ is nonempty, + \item if $(U_0, V_0, \ldots, U_n, V_n)\in\sigma$, then for all open + nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, U_n, V_n, + U_{n+1})\in\sigma$, + \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for a unique $V_n$, + $(U_0, V_0, \ldots, U_{n}, V_n)\in\sigma$. + \end{enumerate} + \end{definition} + + Intuitively, a strategy $\sigma$ works as follows: $I$ starts playing + $U_0$ as any open subset of $X$, then $\textit{II}$ plays unique (by + (iii)) $V_0$ such that $(U_0, V_0)\in\sigma$. Then $I$ responds by + playing any $U_1\subseteq V_0$ and $\textit{II}$ plays unique $V_1$ + such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc. + + \begin{definition} + A strategy $\sigma$ is a \emph{winning strategy for $\textit{II}$} if for + any game $(U_0, V_0\ldots)\in [\sigma]$ player $\textit{II}$ wins, i.e. + $\bigcap_{n}V_n \subseteq A$. + \end{definition} + + Now we can state the key theorem. + + \begin{theorem}[Banach-Mazur, Oxtoby] + \label{theorem:banach_mazur_thm} + Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is + comeagre $\Leftrightarrow$ $\textit{II}$ has a winning strategy in + $G^{\star\star}(A)$. + \end{theorem} + + In order to prove it we add an auxiliary definition and lemma. + \begin{definition} + Let $S\subseteq\sigma$ be a pruned subtree of tree of all legal positions + $T$ and let $p=(U_0, V_0,\ldots, V_n)\in S$. We say that S is + \emph{comprehensive for p} if the family $\cV_p = \{V_{n+1}\mid (U_0, + V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ (it may be that $n=-1$, which + means $p=\emptyset$) is pairwise disjoint and $\bigcup\cV_p$ is dense in + $V_n$ (where we think that $V_{-1} = X$). + We say that $S$ is \emph{comprehensive} if it is comprehensive for + each $p=(U_0, V_0,\ldots, V_n)\in S$. + \end{definition} + + \begin{fact} + If $\sigma$ is a winning strategy for $\mathit{II}$ then + there exists a nonempty comprehensive $S\subseteq\sigma$. + \end{fact} + + \begin{proof} + We construct $S$ recursively as follows: + \begin{enumerate} + \item $\emptyset\in S$, + \item if $(U_0, V_0, \ldots, U_n)\in S$, then $(U_0, V_0, \ldots, U_n, + V_n)\in S$ for the unique $V_n$ given by the strategy $\sigma$, + \item let $p = (U_0, V_0, \ldots, V_n)\in S$. For a possible player $I$'s + move $U_{n+1}\subseteq V_n$ let $U^\star_{n+1}$ be the unique set + player $\mathit{II}$ would respond with by $\sigma$. Now, by Zorn's + Lemma, let $\cU_p$ be a maximal collection of nonempty open subsets + $U_{n+1}\subseteq V_n$ such that the set $\{U^\star_{n+1}\mid + U_{n+1}\in\cU_p\}$ is pairwise disjoint. Then put in $S$ all $(U_0, + V_0, \ldots, V_{n}, U_{n+1})$ such that $U_{n+1} \in \cU_p$. This way + $S$ is comprehensive for $p$: the family $\cV_p = \{V_{n+1}\mid (U_0, + V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ is exactly + $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$, which is pairwise disjoint and + $\bigcup\cV_p$ is obviously dense in $V_n$ by the maximality of $\cU_p$ + -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint + from $\bigcup\cV_p$, then $\tilde{U}^{\star}_{n+1}\subseteq + \tilde{U}_{n+1}$ would be also disjoint from $\bigcup\cV_p$, so the + family $\cU_p\cup\{\tilde{U}_{n+1}\}$ would violate the maximality of + $\cU_p$. + \qedhere + \end{enumerate} + \end{proof} + + \begin{lemma} + \label{lemma:comprehensive_lemma} + Let $S$ be a nonempty comprehensive pruned subtree of a strategy $\sigma$. + Then: + \begin{enumerate}[label=(\roman*)] + \item For any open $V_n\subseteq X$ there is at most one $p=(U_0, V_0, + \ldots, U_n, V_n)\in S$. + \item Let $S_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$ for $n\in\bN$ + (i.e. $S_n$ is a family of all possible choices player $\textit{II}$ + can make in its $n$-th move according to $S$). Then $\bigcup S_n$ is + open and dense in $X$. + \item $S_n$ is a family of pairwise disjoint sets. + \end{enumerate} + \end{lemma} + + \begin{proof} + (i): Suppose that there are some $p = (U_0, V_0,\ldots, + U_n, V_n)$, $p'=(U'_0, V'_0, \ldots, U'_n, V'_n)$ such that $V_n + = V'_n$ and $p \neq p'$. Let $k$ be the smallest index such that those + sequences differ. We have two possibilities: + \begin{itemize} + \item $U_k = U'_k$ and $V_k\neq V'_k$ -- this cannot be true simply by + the fact that $S$ is a subset of a strategy (so $V_k$ is unique for + $U_k$). \item $U_k\neq U'_k$: by the comprehensiveness of $S$ we know + that for $q =(U_0, V_0, \ldots, U_{k-1}, V_{k-1})$ the set $\cV_q$ is + pairwise disjoint. Thus $V_k\cap V'_k=\emptyset$, because $V_k, V'_k\in + \cV_q$. But this leads to a contradiction -- $V_n$ cannot be a nonempty + subset of both $V_k, V'_k$. + \end{itemize} + + (ii): The lemma is proved by induction on $n$. For $n=0$ it follows + trivially from the definition of comprehensiveness. Now suppose the + lemma is true for $n$. Then the set $\bigcup_{V_n\in + S_n}\bigcup\cV_{p_{V_n}}$ (where $p_{V_n}$ is given uniquely from + (i)) is dense and open in $X$ by the induction hypothesis. But + $\bigcup S_{n+1}$ is exactly this set, thus it is dense and open in + $X$. + + (iii): We will prove it by induction on $n$. Once again, the case $n + = 0$ follows from the comprehensiveness of $S$. Now suppose that the + sets in $S_n$ are pairwise disjoint. Take some $x \in V_{n+1}\in + S_{n+1}$. Of course $\bigcup S_n \supseteq \bigcup S_{n+1}$, thus by + the inductive hypothesis $x\in V_{n}$ for the unique $V_n\in S_n$. It + must be that $V_{n+1}\in \cV_{p_{V_n}}$, because $V_n$ is the only + superset of $V_{n+1}$ in $S_n$. But $\cV_{p_{V_n}}$ is disjoint, so + there is no other $V'_{n+1}\in \cV_{p_{V_n}}$ such that $x\in + V'_{n+1}$. Moreover, there is no such set in + $S_{n+1}\setminus\cV_{p_{V_n}}$, because those sets are disjoint from + $V_{n}$. Hence there is no $V'_{n+1}\in S_{n+1}$ other than $V_n$ + such that $x\in V'_{n+1}$. We've chosen $x$ and $V_{n+1}$ arbitrarily, + so $S_{n+1}$ is pairwise disjoint. + \end{proof} + + Now we can move to the proof of the Banach-Mazur theorem. + + \begin{proof}[Proof of theorem \ref{theorem:banach_mazur_thm}] + $\Rightarrow$: Let $(A_n)$ be a sequence of dense open sets with + $\bigcap_n A_n\subseteq A$. The simply $\textit{II}$ plays $V_n + = U_n\cap A_n$, which is nonempty by the denseness of $A_n$. + + $\Leftarrow$: Suppose $\textit{II}$ has a winning strategy $\sigma$. + We will show that $A$ is comeagre. Take a comprehensive $S\subseteq + \sigma$. We claim that $\mathcal{S} = \bigcap_n\bigcup S_n \subseteq + A$. By the lemma~\ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup + S_n$ are open and dense, thus $A$ must be comeagre. Now we prove the + claim towards contradiction. + + Suppose there is $x\in \mathcal{S}\setminus A$. By the lemma + \ref{lemma:comprehensive_lemma}, (iii) for any $n$ there is unique + $x\in V_n\in S_n$. It follows that $p_{V_0}\subset + p_{V_1}\subset\ldots$. Now the game $(U_0, V_0, U_1, V_1,\ldots) + = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ is not winning for + player $\textit{II}$, which contradicts the assumption that $\sigma$ is + a winning strategy. \end{proof} + + \begin{corollary} + \label{corollary:banach-mazur-basis} + If we add a constraint to the Banach-Mazur game such that players can only + choose basic open sets, then the theorem \ref{theorem:banach_mazur_thm} + still suffices. + \end{corollary} + + \begin{proof} + If one adds the word \textit{basic} before each occurrence + of word \textit{open} in previous proofs and theorems then they all + will still be valid (except for $\Rightarrow$, but its an easy fix -- + take $V_n$ a basic open subset of $U_n\cap A_n$). + \end{proof} + + This corollary will be important in using the theorem in practice -- + it's much easier to work with basic open sets rather than any open + sets. + + \subsection{Category theory} + + In this section we will give a short introduction to the notions of + category theory that will be necessary to generalize the key result of the + paper. + + We will use a standard notation. If the reader is interested in detailed + introduction to the category theory, then it's recommended to take a look + at \cite{maclane_1978}. Here we will shortly describe the standard notation. + + A \emph{category} $\cC$ consists of the collection of objects (denoted as + $\Obj(\cC)$, but most often simply as $\cC$) and collection of \emph{morphisms} + $\Mor(A, B)$ between each pair of objects $A, B\in \cC$. We require that + for each morphisms $f\colon B\to C$, $g\colon A\to B$ there is a morphism + $f\circ g\colon A\to C$. For every $A\in\cC$ there is an + \emph{identity morphism} $\id_A$ such that for any morphism $f\in \Mor(A, B)$ + it follows that $f\circ id_A = \id_B \circ f$. + + We say that $f\colon A\to B$ is \emph{isomorphism} if there is (necessarily + unique) morphism $g\colon B\to A$ such that $g\circ f = id_A$ and $f\circ g = id_B$. + Automorphism is an isomorphism where $A = B$. + + A \emph{functor} is a ``homeomorphism`` of categories. We say that + $F\colon\cC\to\cD$ is a functor + from category $\cC$ to category $\cD$ if it associates each object $A\in\cC$ + with an object $F(A)\in\cD$, associates each morphism $f\colon A\to B$ in + $\cC$ with a morphism $F(f)\colon F(A)\to F(B)$. We also require that + $F(\id_A) = \id_{F(A)}$ and that for any (compatible) morphisms $f, g$ in $\cC$ + $F(f\circ g) = F(f) \circ F(g)$. + + In category theory we distinguish \emph{covariant} and \emph{contravariant} + functors. Here, we only consider \emph{covariant functors}, so we will simply + say \emph{functor}. + + \begin{fact} + \label{fact:functor_iso} + Functor $F\colon\cC\to\cD$ maps isomorphism $f\colon A\to B$ in $\cC$ + to the isomorphism $F(f)\colon F(A)\to F(B)$ in $\cD$. + \end{fact} + + Notion that will be very important for us is a ``morphism of functors`` + which is called \emph{natural transformation}. + \begin{definition} + Let $F, G$ be functors between the categories $\cC, \cD$. A \emph{natural + transformation} + $\tau$ is function that assigns to each object $A$ of $\cC$ a morphism $\tau_A$ + in $\Mor(F(A), G(A))$ such that for every morphism $f\colon A\to B$ in $\cC$ + the following diagram commutes: + + \begin{center} + \begin{tikzcd} + A \arrow[d, "f"] & F(A) \arrow[r, "\tau_A"] \arrow[d, "F(f)"] & G(A) \arrow[d, "G(f)"] \\ + B & F(B) \arrow[r, "\tau_B"] & G(B) \\ + \end{tikzcd} + \end{center} + \end{definition} + + \begin{definition} + In category theory, a \emph{diagram} of type $\mathcal{J}$ in category $\cC$ + is a functor $D\colon \mathcal{J}\to\cC$. $\mathcal{J}$ is called the + \emph{index category} of $D$. In other words, $D$ is of \emph{shape} $\mathcal{J}$. + + For example, $\mathcal{J} = \{-1\leftarrow 0 \rightarrow 1\}$, then a diagram + $D\colon\mathcal{J}\to \cC$ is called a \emph{cospan}. For example, + if $A, B, C$ are objects of $\cC$ and $f\in\Mor(C, A), g\in\Mor(C, B)$, then + the following diagram is a cospan: + + \begin{center} + \begin{tikzcd} + A & & B \\ + & C \arrow[ur, "g"'] \arrow[ul, "f"] & + \end{tikzcd} + \end{center} + \end{definition} + + From now we omit explicit definition of the index category, as it is easily + referable from a picture. + + \begin{definition} + Let $A, B, C, D$ be objects in the category $\cC$ with morphisms + $e\colon C\to A, f\colon C\to B, g\colon A\to D, h\colon B\to D$ such + that $g\circ e = h\circ f$. + Then the following diagram: + \begin{center} + \begin{tikzcd} + & D & \\ + A \arrow[ur, "g"] & & B \arrow[ul, "h"'] \\ + & C \arrow[ur, "e"'] \arrow[ul, "f"] & + \end{tikzcd} + \end{center} + + is called a \emph{pushout} diagram + \end{definition} + + \begin{definition} + The \emph{cospan category} of category $\cC$, refered to as $\Cospan(\cC)$, + is the category of cospan diagrams of $\cC$, where morphisms between + two cospans are normal transformations of the underlying functors. + + We define \emph{pushout category} analogously and call it $\Pushout(\cC)$. + \end{definition} + + TODO: dodać tu przykład? +\end{document} -- cgit v1.2.3