\documentclass[11pt, a4paper, final]{amsart} \setlength{\emergencystretch}{2em} \usepackage[backend=biber]{biblatex} \addbibresource{licmalinka.bib} \usepackage[T1]{fontenc} \usepackage{mathtools} \usepackage[activate={true,nocompatibility},final,tracking=true,kerning=true,spacing=true,stretch=10,shrink=10]{microtype} \microtypecontext{spacing=nonfrench} % \usepackage[utf8]{inputenc} \usepackage{amsfonts} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsthm} \usepackage{XCharter} \usepackage[charter, expert, greekuppercase=italicized, greekfamily=didot]{mathdesign} \usepackage{mathtools} \usepackage{enumitem} \usepackage[utf8]{inputenc} \usepackage{tikz-cd} \usepackage{tikz} \usetikzlibrary{arrows,arrows.meta} \tikzcdset{arrow style=tikz, diagrams={>=latex}} \usepackage{etoolbox} \usepackage{xcolor} \definecolor{green}{RGB}{0,127,0} \definecolor{redd}{RGB}{191,0,0} \definecolor{red}{RGB}{105,89,205} \usepackage[colorlinks=true]{hyperref} \usepackage[notref, notcite]{showkeys} \usepackage[cmtip,arrow]{xy} \DeclareMathOperator{\Aut}{Aut} \DeclareMathOperator{\Hom}{Hom} \DeclareMathOperator{\Stab}{Stab} \DeclareMathOperator{\st}{st} \DeclareMathOperator{\Flim}{FLim} \DeclareMathOperator{\Int}{{Int}} \newcommand{\cupdot}{\mathbin{\mathaccent\cdot\cup}} \newcommand{\cC}{\mathcal C} \newcommand{\cV}{\mathcal{V}} \newcommand{\cU}{\mathcal{U}} \newcommand{\bN}{\mathbb N} \newcommand{\bR}{\mathbb R} \newcommand{\bZ}{\mathbb Z} \newcommand{\bQ}{\mathbb Q} \newcommand{\bK}{\mathbb K} \DeclareMathOperator{\im}{{Im}} \DeclareMathOperator{\lin}{{Lin}} \DeclareMathOperator{\Th}{{Th}} \newtheorem{theorem}{Theorem} \numberwithin{theorem}{section} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{fact}[theorem]{Fact} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{question}[theorem]{Question} \newtheorem{corollary}[theorem]{Corollary} \newtheorem*{theorem2}{Theorem} \newtheorem*{claim2}{Claim} \newtheorem*{corollary2}{Corollary} \newtheorem*{question2}{Question} \newtheorem*{conjecture2}{Conjecture} \newtheorem{clm}{Claim} \newtheorem*{clm*}{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem*{definition2}{Definition} \newtheorem{example}[theorem]{Example} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem*{remark2}{Remark} \AtEndEnvironment{proof}{\setcounter{clm}{0}} \newenvironment{clmproof}[1][\proofname]{\proof[#1]\renewcommand{\qedsymbol}{$\square$(claim)}}{\endproof} \newcommand{\xqed}[1]{% \leavevmode\unskip\penalty9999 \hbox{}\nobreak\hfill \quad\hbox{\ensuremath{#1}}} \title{Tytuł} \author{Franciszek Malinka} \begin{document} \begin{abstract} Abstract \end{abstract} \section{Introduction} \section{Preliminaries} \subsection{Descriptive set theory} \begin{definition} Suppose $X$ is a topological space and $A\subseteq X$. We say that $A$ is \emph{meagre} in $X$ if $A = \bigcup_{n\in\bN}A_n$, where $A_n$ are nowhere dense subsets of $X$ (i.e. $\Int(\bar{A_n}) = \emptyset$). \end{definition} \begin{definition} We say that $A$ is \emph{comeagre} in $X$ if it is a complement of a meagre set. Equivalently, a set is comeagre iff it contains a countable intersection of open dense sets. \end{definition} % \begin{example} Every countable set is meagre in any $T_1$ space, so, for example, $\bQ$ is meagre in $\bR$ (though being dense), which means that the set of irrationals is comeagre. Another example is... % \end{example} \begin{definition} We say that a topological space $X$ is a \emph{Baire space} if every comeagre subset of $X$ is dense in $X$ (equivalently, every meagre set has empty interior). \end{definition} \begin{definition} Suppose $X$ is a Baire space. We say that a property $P$ \emph{holds generically} for a point in $x\in X$ if $\{x\in X\mid P\textrm{ holds for }x\}$ is comeagre in $X$. \end{definition} \begin{definition} Let $X$ be a nonempty topological space and let $A\subseteq X$. The \emph{Banach-Mazur game of $A$}, denoted as $G^{\star\star}(A)$ is defined as follows: Players $I$ and $\textit{II}$ take turns in playing nonempty open sets $U_0, V_0, U_1, V_1,\ldots$ such that $U_0 \supseteq V_0 \supseteq U_1 \supseteq V_1 \supseteq\ldots$. We say that player $\textit{II}$ wins the game if $\bigcap_{n}V_n \subseteq A$. \end{definition} There is an important theorem on the Banach-Mazur game: $A$ is comeagre iff $\textit{II}$ can always choose sets $V_0, V_1, \ldots$ such that it wins. Before we prove it we need to define notions necessary to formalise and prove the theorem. \begin{definition} $T$ is \emph{the tree of all legal positions} in the Banach-Mazur game $G^{\star\star}(A)$ when $T$ consists of all finite sequences $(W_0, W_1,\ldots, W_n)$, where $W_i$ are nonempty open sets such that $W_0\supseteq W_1\supseteq\ldots\supseteq W_n$. In another words, $T$ is a pruned tree on $\{W\subseteq X\mid W \textrm{is open nonempty}\}$. \end{definition} \begin{definition} We say that $\sigma$ is \emph{a pruned subtree} of the tree of all legal positions $T$ if $\sigma\subseteq T$ and for any $(W_0, W_1, \ldots, W_n)\in\sigma, n\ge 0$ there is a $W$ such that $(W_0, W_1,\ldots, W_n, W)\in\sigma$ (it simply means that there's no finite branch in~$\sigma$). \end{definition} \begin{definition} Let $\sigma$ be a pruned subtree of the tree of all legal positions $T$. By $[\sigma]$ we denote \emph{the set of all infinite branches of $\sigma$}, i.e. infinite sequences $(W_0, W_1, \ldots)$ such that $(W_0, W_1, \ldots W_n)\in \sigma$ for any $n\in \bN$. \end{definition} \begin{definition} A \emph{strategy} for $\textit{II}$ in $G^{\star\star}(A)$ is a pruned subtree $\sigma\subseteq T$ such that \begin{enumerate}[label=(\roman*)] \item $\sigma$ is nonempty, \item if $(U_0, V_0, \ldots, U_n, V_n)\in\sigma$, then for all open nonempty $U_{n+1}\subseteq V_n$, $(U_0, V_0, \ldots, U_n, V_n, U_{n+1})\in\sigma$, \item if $(U_0, V_0, \ldots, U_{n})\in\sigma$, then for a unique $V_n$, $(U_0, V_0, \ldots, U_{n}, V_n)\in\sigma$. \end{enumerate} \end{definition} Intuitively, a strategy $\sigma$ works as follows: $I$ starts playing $U_0$ as any open subset of $X$, then $\textit{II}$ plays unique (by (iii)) $V_0$ such that $(U_0, V_0)\in\sigma$. Then $I$ responds by playing any $U_1\subseteq V_0$ and $\textit{II}$ plays uniqe $V_1$ such that $(U_0, V_0, U_1, V_1)\in\sigma$, etc. \begin{definition} A strategy $\sigma$ is a \emph{winning strategy for $\textit{II}$} if for any game $(U_0, V_0\ldots)\in [\sigma]$ player $\textit{II}$ wins, i.e. $\bigcap_{n}V_n \subseteq A$. \end{definition} Now we can state the key theorem. \begin{theorem}[Banach-Mazur, Oxtoby] \label{theorem:banach_mazur_thm} Let $X$ be a nonempty topological space and let $A\subseteq X$. Then A is comeagre $\Leftrightarrow$ $\textit{II}$ has a winning strategy in $G^{\star\star}(A)$. \end{theorem} In order to prove it we add an auxilary definition and lemma. \begin{definition} Let $S\subseteq\sigma$ be a pruned subtree of tree of all legal positions $T$ and let $p=(U_0, V_0,\ldots, V_n)\in S$. We say that S is \emph{comprehensive for p} if the family $\cV_p = \{V_{n+1}\mid (U_0, V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ (it may be that $n=-1$, which means $p=\emptyset$) is pairwise disjoint and $\bigcup\cV_p$ is dense in $V_n$ (where we think that $V_{-1} = X$). We say that $S$ is \emph{comprehensive} if it is comprehensive for each $p=(U_0, V_0,\ldots, V_n)\in S$. \end{definition} \begin{fact} If $\sigma$ is a winnig strategy for $\mathit{II}$ then there exists a nonempty comprehensive $S\subseteq\sigma$. \end{fact} \begin{proof} We construct $S$ recursively as follows: \begin{enumerate} \item $\emptyset\in S$, \item if $(U_0, V_0, \ldots, U_n)\in S$, then $(U_0, V_0, \ldots, U_n, V_n)\in S$ for the unique $V_n$ given by the strategy $\sigma$, \item let $p = (U_0, V_0, \ldots, V_n)\in S$. For a possible player $I$'s move $U_{n+1}\subseteq V_n$ let $U^\star_{n+1}$ be the unique set player $\mathit{II}$ would respond with by $\sigma$. Now, by Zorn's Lemma, let $\cU_p$ be a maximal collection of nonempty open subsets $U_{n+1}\subseteq V_n$ such that the set $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$ is pairwise disjoint. Then put in $S$ all $(U_0, V_0, \ldots, V_{n}, U_{n+1})$ such that $U_{n+1} \in \cU_p$. This way $S$ is comprehensive for $p$: the family $\cV_p = \{V_{n+1}\mid (U_0, V_0,\ldots, V_n, U_{n+1}, V_{n+1})\in S\}$ is exactly $\{U^\star_{n+1}\mid U_{n+1}\in\cU_p\}$, which is pairwise disjoint and $\bigcup\cV_p$ is obviously dense in $V_n$ by the maximality of $\cU_p$ -- if there was any open set $\tilde{U}_{n+1}\subseteq V_n$ disjoint from $\bigcup\cV_p$, then $\tilde{U}^{\star}_{n+1}\subseteq \tilde{U}_{n+1}$ would be also disjoint from $\bigcup\cV_p$, so the family $\cU_p\cup\{\tilde{U}_{n+1}\}$ would violate the maximality of $\cU_p$. \qedhere \end{enumerate} \end{proof} \begin{lemma} \label{lemma:comprehensive_lemma} Let $S$ be a nonempty comprehensive pruned subtree of a strategy $\sigma$. Then: \begin{enumerate}[label=(\roman*)] \item For any open $V_n\subseteq X$ there is at most one $p=(U_0, V_0, \ldots, U_n, V_n)\in S$. \item Let $S_n = \{V_n\mid (U_0, V_0, \ldots, V_n)\in S\}$ for $n\in\bN$ (i.e. $S_n$ is a family of all possible choices player $\textit{II}$ can make in its $n$-th move according to $S$). Then $\bigcup S_n$ is open and dense in $X$. \item $S_n$ is a family of pairwise disjoint sets. \end{enumerate} \end{lemma} \begin{proof} (i): Suppose that there are some $p = (U_0, V_0,\ldots, U_n, V_n)$, $p'=(U'_0, V'_0, \ldots, U'_n, V'_n)$ such that $V_n = V'_n$ and $p \neq p'$. Let $k$ be the smallest index such that those sequences differ. We have two possibilities: \begin{itemize} \item $U_k = U'_k$ and $V_k\neq V'_k$ -- this cannot be true simply by the fact that $S$ is a subset of a strategy (so $V_k$ is unique for $U_k$). \item $U_k\neq U'_k$: by the comprehensiveness of $S$ we know that for $q =(U_0, V_0, \ldots, U_{k-1}, V_{k-1})$ the set $\cV_q$ is pairwise disjoint. Thus $V_k\cap V'_k=\emptyset$, because $V_k, V'_k\in \cV_q$. But this leads to a contradiction -- $V_n$ cannot be a nonempty subset of both $V_k, V'_k$. \end{itemize} (ii): The lemma is proved by induction on $n$. For $n=0$ it follows trivially from the definition of comprehensiveness. Now suppose the lemma is true for $n$. Then the set $\bigcup_{V_n\in S_n}\bigcup\cV_{p_{V_n}}$ (where $p_{V_n}$ is given uniquely from (i)) is dense and open in $X$ by the induction hypothesis. But $\bigcup S_{n+1}$ is exactly this set, thus it is dense and open in $X$. (iii): We will prove it by induction on $n$. Once again, the case $n = 0$ follows from the comprehensiveness of $S$. Now suppose that the sets in $S_n$ are pairwise disjoint. Take some $x \in V_{n+1}\in S_{n+1}$. Of course $\bigcup S_n \supseteq \bigcup S_{n+1}$, thus by the inductive hypothesis $x\in V_{n}$ for the unique $V_n\in S_n$. It must be that $V_{n+1}\in \cV_{p_{V_n}}$, because $V_n$ is the only superset of $V_{n+1}$ in $S_n$. But $\cV_{p_{V_n}}$ is disjoint, so there is no other $V'_{n+1}\in \cV_{p_{V_n}}$ suc h that $x\in V'_{n+1}$. Moreover, there is no such set in $S_{n+1}\setminus\cV_{p_{V_n}}$, because those sets are disjoint from $V_{n}$. Hence there is no $V'_{n+1}\in S_{n+1}$ other than $V_n$ such that $x\in V'_{n+1}$. We've chosen $x$ and $V_{n+1}$ arbitrarily, so $S_{n+1}$ is pairwise disjoint. \end{proof} Now we can move to the proof of the Banach-Mazur theorem. \begin{proof}[Proof of theorem \ref{theorem:banach_mazur_thm}] $\Rightarrow$: Let $(A_n)$ be a sequence of dense open sets with $\bigcap_n A_n\subseteq A$. The simply $\textit{II}$ plays $V_n = U_n\cap A_n$, which is nonempty by the denseness of $A_n$. $\Leftarrow$: Suppose $\textit{II}$ has a winning strategy $\sigma$. We will show that $A$ is comeagre. Take a comprehensive $S\subseteq \sigma$. We claim that $\mathcal{S} = \bigcap_n\bigcup S_n \subseteq A$. By the lemma~\ref{lemma:comprehensive_lemma}, (ii) sets $\bigcup S_n$ are open and dense, thus $A$ must be comeagre. Now we prove the claim towards contradiction. Suppose there is $x\in \mathcal{S}\setminus A$. By the lemma \ref{lemma:comprehensive_lemma}, (iii) for any $n$ there is unique $x\in V_n\in S_n$. It follows that $p_{V_0}\subset p_{V_1}\subset\ldots$. Now the game $(U_0, V_0, U_1, V_1,\ldots) = \bigcup_n p_{V_n}\in [S]\subseteq [\sigma]$ is not winning for player $\textit{II}$, which contradicts the assumption that $\sigma$ is a winning strategy. \end{proof} \begin{corollary} \label{corollary:banach-mazur-basis} If we add a constraint to the Banach-Mazur game such that players can only choose basic open sets, then the theorem \ref{theorem:banach_mazur_thm} still suffices. \end{corollary} \begin{proof} If one adds the word \textit{basic} before each occurrence of word \textit{open} in previous proofs and theorems then they all will still be valid (except for $\Rightarrow$, but its an easy fix -- take $V_n$ a basic open subset of $U_n\cap A_n$). \end{proof} This corollary will be important in using the theorem in practice -- it's much easier to work with basic open sets rather than any open sets. \section{Fraïssé classes} In this section we will take a closer look at classes of finitely generated structures with some characteristic properties. More specifically, we will describe a concept developed by a French mathematician Roland Fraïssé called Fraïssé limit. \subsection{Definitions} \begin{definition} Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is the class $\bK$ of all finitely generated structures that embedds into $M$. The age of $M$ is also associated with class of all structures embeddable in $M$ \emph{up to isomorphism}. \end{definition} \begin{definition} We say that $M$ has \emph{countable age} when its age has countably many isomorphism types of finitely generated structures. \end{definition} \begin{definition} Let $\bK$ be a class of finitely generated structures. $\bK$ has \emph{hereditary property (HP)} if for any $A\in\bK$, any finitely generated substructure $B$ of $A$ it holds that $B\in\bK$. \end{definition} \begin{definition} Let $\bK$ be a class of finitely generated structures. We say that $\bK$ has \emph{joint embedding property (JEP)} if for any $A, B\in\bK$ there is a structure $C\in\bK$ such that both $A$ and $B$ embed in $C$. \end{definition} Fraïssé has shown fundamental theories regarding age of a structure, one of them being the following one: \begin{fact} \label{fact:age_is_hpjep} Suppose $L$ is a signature and $\bK$ is a nonempty finite or countable set of finitely generated $L$-structures. Then $\bK$ has the HP and JEP if and only if $\bK$ is the age of some finite or countable structure. \end{fact} Beside the HP and JEP Fraïssé has distinguished one more property of the class $\bK$, namely amalgamation property. \begin{definition} Let $\bK$ be a class of finitely generated $L$-structures. We say that $\bK$ has the \emph{amalgamation property (AP)} if for any $A, B, C\in\bK$ and embeddings $f\colon A\to B, g\colon A\to C$ there exists $D\in\bK$ together with embeddings $h\colon B\to D$ and $j\colon C\to D$ such that $h\circ f = j\circ g$. \begin{center} \begin{tikzcd} & D & \\ B \arrow[ur, dashed, "h"] & & C \arrow[ul, dashed, "j"'] \\ & A \arrow[ur, "g"'] \arrow[ul, "f"] \end{tikzcd} \end{center} \end{definition} \begin{definition} Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogenous} if every isomorphism between finitely generated substrucutres of $M$ extends to an automorphism of $M$. \end{definition} Having those definitions we can provide the main Fraïssé theorem. \begin{theorem}[Fraïssé theorem] \label{theorem:fraisse_thm} Let L be a countable language and let $\bK$ be a nonempty countable set of finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ is the age of a countable, ultrahomogenous $L$-structure $M$. Moreover, $M$ is unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\bK$ and denote this by $M = \Flim(\bK)$. \end{theorem} This is a well known theorem. One can read a proof of this theorem in Wilfrid Hodges' classical book \textit{Model Theory}~\cite{hodges_1993}. In the proof of this theorem appears another, equally important \ref{lemma:weak_ultrahom}. \begin{definition} We say that an $L$-structure $M$ is \emph{weakly ultrahomogenous} if for any $A, B$ finitely generated substructures of $M$ such that $A\subseteq B$ and an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which extends $f$. \begin{center} \begin{tikzcd} A \arrow[d, "\subseteq"'] \arrow[r, "f"] & D \\ B \arrow[ur, dashed, "g"'] \end{tikzcd} \end{center} \end{definition} \begin{lemma} \label{lemma:weak_ultrahom} A countable structure is ultrahomogenous if and only if it is weakly ultrahomogenous. \end{lemma} This lemma will play a major role in the later parts of the paper. Weak ultrahomogenity is an easier and more intuitive property and it will prove useful when recursively constructing the generic automorphism of a Fraïssé limit. % \begin{definition} For $\cC$, $M$ as in Fact~\ref{fact:fraisse_thm}, we % write $\Flim(\cC)\coloneqq M$. \end{definition} % \begin{fact} If $\cC$ is a uniformly locally finite Fraïssé class, then % $\Flim(\cC)$ is $\aleph_0$-categorical and has quantifier elimination. % \end{fact} % \section{Conjugacy classes in automorphism groups} % \subsection{Prototype: pure set} In this section, $M=(M,=)$ is an % infinite countable set (with no structure beyond equality). % \begin{proposition} If $f_1,f_2\in \Aut(M)$, then $f_1$ and $f_2$ are % conjugate if and only if for each $n\in \bN\cup \{\aleph_0\}$, $f_1$ % and $f_2$ have the same number of orbits of size $n$. % \end{proposition} % \begin{proposition} The conjugacy class of $f\in \Aut(M)$ is dense if % and only if... \end{proposition} \begin{proposition} If $f\in % \Aut(M)$ has an infinite orbit, then the conjugacy class of $f$ is % meagre. % \end{proposition} % \begin{proposition} An automorphism $f$ of $M$ is generic if and only if... % \end{proposition} % \begin{proof} % \end{proof} % \subsection{More general structures} % \begin{proposition} Suppose $M$ is an arbitrary structure and $f_1,f_2\in % \Aut(M)$. Then $f_1$ and $f_2$ are conjugate if and only if $(M,f_1)\cong % (M,f_2)$. \end{proposition} % \begin{definition} We say that a Fraïssé class $\cC$ has \emph{weak % Hrushovski property} (\emph{WHP}) if for every $A\in \cC$ and partial % automorphism $p\colon A\to A$, there is some $B\in \cC$ such that $p$ can % be extended to an automorphism of $B$, i.e.\ there is an embedding % $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following % diagram commutes: % \begin{center} % \begin{tikzcd} % B\ar[r,"\bar p"]&B\\ % A\ar[u,"i"]\ar[r,"p"]&A\ar[u,"i"] % \end{tikzcd} % \end{center} % \end{definition} % \begin{proposition} Suppose $\cC$ is a Fraïssé class in a relational % language with WHP. Then generically, for an $f\in \Aut(\Flim(\cC))$, all % orbits of $f$ are finite. \end{proposition} \begin{proposition} Suppose % $\cC$ is a Fraïssé class in an arbitrary countable language with WHP. % Then generically, for an $f\in \Aut(\Flim(\cC))$ ... \end{proposition} % \subsection{Random graph} \begin{definition} The \emph{random graph} % is... \end{definition} % \begin{fact} The \end{fact} % \begin{proposition} Generically, the set of fixed points of $f\in % \Aut(M)$ is isomorphic to $M$ (as a graph). \end{proposition} \printbibliography \end{document}