diff options
Diffstat (limited to 'sections')
| -rw-r--r-- | sections/conj_classes.tex | 83 | ||||
| -rw-r--r-- | sections/fraisse_classes.tex | 11 | ||||
| -rw-r--r-- | sections/introduction-pl.tex | 43 | ||||
| -rw-r--r-- | sections/preliminaries.tex | 16 |
4 files changed, 115 insertions, 38 deletions
diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex index d380df6..b122058 100644 --- a/sections/conj_classes.tex +++ b/sections/conj_classes.tex @@ -1,7 +1,8 @@ \documentclass[../lic_malinka.tex]{subfiles} \begin{document} - Let $M$ be a countable $L$-structure. We define a topology on the $G=\Aut(M)$: + Let $M$ be a countable $L$-structure. Recall, 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\}$. @@ -10,12 +11,16 @@ In this section, $M=(M,=)$ is an infinite countable set (with no structure beyond equality). - \begin{proposition} - \label{proposition:cojugate-classes} + \begin{remark} + \label{remark: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} + \end{remark} + + \begin{proof} + It is easy to see. + \end{proof} \begin{theorem} Let $\sigma\in \Aut(M)$ be an automorphism with no infinite orbit and with @@ -30,7 +35,7 @@ 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 + be the set of all finite functions $\beta\colon M\to M$ that consist 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\} \\ @@ -49,10 +54,10 @@ 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 + is an open dense set. It is a union 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 + Finally, by the remark \ref{remark: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} @@ -63,22 +68,23 @@ \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 + (M,f_2)$ as structures with one additional unary function 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 + Then $g$ is the isomorphism between $(M,f_1)$ and $(M,f_2)$. + 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 + Let $\cC$ be a Fraïssé class of finite $L$-structures. + Let $\cD$ be the class of structures from $\cC$ 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)$. @@ -86,13 +92,13 @@ \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 + 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 conjugacy class in $G$. - By the Banach-Mazur theorem \ref{theorem:banach_mazur_thm} this will prove + $A\subseteq G$ and as we will see a subset of the $\sigma$'s conjugacy class. + By the Banach-Mazur theorem (see \ref{theorem:banach_mazur_thm}) this will prove that this class is comeagre. Recall, $G$ has a basis consisting of open @@ -100,28 +106,36 @@ 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. + open subset given by a finite partial isomorphism $g$. Note that $B_g$ + is nonemty because of ultrahomogeneity of $\Gamma$. - With the use of corollary \ref{corollary:banach-mazur-basis} we can consider - only games, where both players choose finite partial isomorphisms. Namely, + 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 + % 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, we will find $g_i$'s such that + % $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$ and 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$. + + Our goal is to choose $g_i$ in such a manner that + $\bigcap^{\infty}_{i=0}B_{g_i} = \{g\}$ and $(\Gamma, g)$ is ultrahomogeneous + with age $\cD$. By the Fraïssé theorem (see \ref{theorem:fraisse_thm}) it will follow + that $(\Gamma, \sigma)\cong (\Gamma, g)$, thus by the Fact \ref{fact:conjugacy} + we have that $\sigma$ and $g$ conjugate. + + % Once again, by the Fraïssé theorem and by Lemma + % \ref{lemma:weak_ultrahom} 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 @@ -131,12 +145,13 @@ 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. + main ingredient of the proof will be a bookkeeping argument. - Just for sake of fixing a technical problem, let $g_{-1} = \emptyset$ and + For technical reasons, 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$ + isomorphism $f_n$. We will construct a finite partial isomorphism $g_n\supseteq f_n$ + and a set $X_n\subseteq\bN^2$ such that following properties hold: \begin{enumerate}[label=(\roman*)] diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex index 5e45400..5f3d833 100644 --- a/sections/fraisse_classes.tex +++ b/sections/fraisse_classes.tex @@ -483,17 +483,20 @@ $(\Pi, \sigma)$, then obviously $B\in\cC$ by the definition of $\cD$. Hence, $\cC$ is indeed the age of $\Pi$. - Now, take any structures $A, B\in\cC$ such that $A\subseteq B$. Without the + Now, take any structures $A, B\in\cC$ such that $A\subseteq B$. We will + find an embedding of $B$ into $\Pi$ to show that $\Pi$ is indeed weakly + homogeneous. + Without the loss of generality assume that $A = B\cap \Pi$. Let $\bar{A}\subseteq\Pi$ be the smallest substructure closed under the automorphism - $\sigma$ and containing $A$. It is finitely generated, as $\cC$ is the age - of $\Pi$. + $\sigma$ and containing $A$. It is finitely generated as an $L$-structure, + as $\cC$ is the age of $\Pi$. Let $C$ be a finitely generated structure such that $\bar{A}\rightarrow C \leftarrow B$. Such structure exists by the JEP of $\cC$. Again, we may assume without the loss of generality that $\bar{A}\subseteq C$. Then $\sigma\upharpoonright_{\bar{A}}$ is a - partial isomorphism of $C$, hence by the WHP it can be extended to + partial automorphism of $C$, hence by the WHP it can be extended to a structure $(\bar{C}, \gamma)\in\cD$ such that $\gamma\upharpoonright_{\bar{A}} = \sigma\upharpoonright_{\bar{A}}$. diff --git a/sections/introduction-pl.tex b/sections/introduction-pl.tex new file mode 100644 index 0000000..5c5ce35 --- /dev/null +++ b/sections/introduction-pl.tex @@ -0,0 +1,43 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + Teoria modeli jest działem matematyki zajmującym się klasyfikacją i + konstrukcją struktur z określonymi cechami (szczególnie takimi, które + da się wyrazić logiką pierwszego rzędu). Opisuje klasyczne matematyczne + obiekty w szerszym kontekście, abstrahuje ich własności i opisuje + połączenia między pozornie niepowiązanymi strukturami. Niniejsza praca + bada granicę klas Fraïsségo z dodatkowymi kombinatorycznymi i kategoryjnymi + własnościami. Klasy Fraïsségo są powszechnie znanym i używanym konceptem + w teorii modeli, zarówno jako narzędzie opisujące ``generyczne'' struktury, + jak i źródło przykładów. + + Klasy Fraïsségo i ich granice zostały opisane po raz pierwszy przez + francuskiego logika Rolanda Fraïsségo. Zawdzięczamy my również argument + ``back-and-forth'', fundamentalną teoriomodelową metodę konstrukcji + elementarnie równoważnych struktur, na podstawie której bazują gry + Ehrenfeuchta-Fraïsségo. + + Graf losowy \ref{definition:random_graph}, + zwany również grafem Rado, jest prototypową strukturą tej + prac. Graf losowy można skonstruować jako granicę Fraïsségo klasy skończonych + grafów nieskierowanych. Służy on jako użyteczny przykład, daje intuicję + stojącą za konstrukcją granicy Fraïsségo, słabej własności Hrushovskiego + oraz wolnej amalgamacji. Ponadto, co najważniejsze dla niniejszej pracy, + graf losowy ma takzwany \emph{generyczny automorfizm} + \ref{definition:generic_automorphism}, co zostało po raz pierwsze zdefiniowane + i udowodnione przez Trussa w \cite{truss_gen_aut}. + + Kluczowe twierdzenie \ref{theorem:generic_aut_general} mówi, że klasa + Fraïsségo z kanoniczną amalgamacją i słabą własnością Hrushovskiego + ma generyczny automorfizm. Istnienie takiego automorfizmu w tym przypadku + wynika z wcześniejszych klasycznych wyników Ivanova \cite{ivanov_1999} + oraz Kechrisa-Rosendala \cite{https://doi.org/10.1112/plms/pdl007}. + W tej pracy pokazujemy nowy sposób konstrukcji generczynego automorfizmu + poprzez rozszerzenie struktur klasy o (totalny) automorfizm oraz + analizę granicy Fraïsségo nowo powstałej klasy. Posługujemy się przy tym + grami Banacha-Mazura, które są dobrze znanym narzędziem w deskryptywnej + teorii mnogości. + + Opisana konstrukcja generycznego automorfizmu okazuje się pomocna w dowodzeniu + niektórych własności tego automorfizmu (patrz \ref{proposition:fixed_points}). +\end{document} diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex index 729ef1d..266845c 100644 --- a/sections/preliminaries.tex +++ b/sections/preliminaries.tex @@ -52,6 +52,22 @@ }x\}$ is comeagre in $X$. \end{definition} + Let $M$ be a structure. We define a topology on the automorphism group + $\Aut(M)$ of $M$ by the basis of open sets: for a finite function + $f\colon M\to M$ we have a basic open set + $[f]_{\Aut(M)} = \{g\in\Aut(M)\mid f\subseteq g\}$. This is a standard + definition. + + \begin{fact} + For a countable structure $M$, the topological space $\Aut(M)$ is a + Baire space. + \end{fact} + + This is in fact a very weak statement, it is also true that $\Aut(M)$ is + a Polish space (i.e. separable completely metrizable), and every Polish + space is Baire. However, those additional properties are not important in + this study. + \begin{definition} \label{definition:generic_automorphism} Let $G = \Aut(M)$ be the automorphism group of structure $M$. We say |