From 006c57fdeb81d97b1ee222d14346e3844df343f5 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Wed, 13 Jul 2022 23:06:05 +0200 Subject: Chyba poprawiony dowod 4.4 --- lic_malinka.pdf | Bin 483340 -> 483862 bytes sections/conj_classes.tex | 122 +++++++++++++++++++++++++++++-------------- sections/fraisse_classes.tex | 21 ++------ sections/preliminaries.tex | 2 +- uwagi_29_06_22.txt | 4 +- 5 files changed, 90 insertions(+), 59 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 03b45e9..671b753 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex index 96522f5..9620220 100644 --- a/sections/conj_classes.tex +++ b/sections/conj_classes.tex @@ -82,7 +82,7 @@ \begin{theorem} \label{theorem:generic_aut_general} - Let $\cC$ be a Fraïssé class of finite $L$-structures. + Let $\cC$ be a Fraïssé class of finitely generated $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 @@ -90,11 +90,25 @@ automorphism group of the $\Flim(\cC)$. \end{theorem} + Before we get to the proof, let us establish some notions. If + $g\colon\Gamma\to\Gamma$ is a finite injective function, then we say that + $g$ is \emph{good} if it gives (in a natural way) an isomorphism between + $\langle \dom(g)\rangle$ and $\langle\rng(g)\rangle$, i.e. substructures + generated by $\dom(g)$ and $\rng(g)$ respectively. Of course, in our + case, $g$ is good + if and only if $[g]_{\Aut(\Gamma)} \neq\emptyset$ (becuase of ultrahomogeneity + of $\Gamma$. + + Also it is important to mention that an isomorphism between two finitely + generated structures is uniquely given by a map from generators of one structure + to the other. This allow us to treat a finite function as an isomorphism + of finitely generated structure. + \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 + Let $\Gamma = \Flim(\cC)$ and $(\Pi, \sigma) = \Flim(\cD)$. First, by the Theorem \ref{theorem:isomorphic_fr_lims}, we may assume without the loss of generality - that $\Pi = \Gamma$. + that $\Pi = \Gamma$. Let $G = \Aut(\Gamma)$, + i.e. $G$ is the automorphism group of $\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 the $\sigma$'s conjugacy class. @@ -105,8 +119,8 @@ 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$. Note that $B_g$ + automorphism $g_0$ of $\Gamma$. By $B_{g}\subseteq G$ we denote a basic + open subset given by a finite partial isomorphism $g$. Again, Note that $B_g$ is nonemty because of ultrahomogeneity of $\Gamma$. With the use of Corollary \ref{corollary:banach-mazur-basis} we can consider @@ -150,20 +164,32 @@ 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 a finite partial isomorphism $g_n\supseteq f_n$ - and a set $X_n\subseteq\bN^2$ - such that following properties hold: + automorphism $f_n$. We will construct a finite partial automorphism + $g_n\supseteq f_n$ together with a finitely generated substrucutre + $\Gamma_n \subseteq \Gamma$ and a set $X_n\subseteq\bN^2$ + such that the following properties hold: \begin{enumerate}[label=(\roman*)] - \item $g_n$ is an automorphism of the induced substructure $\Gamma_n$, + \item $g_n$ is good and + $\dom(g_n)\cup\rng(g_n)\subseteq\langle\dom(g_n)\rangle = \Gamma_n$, + i.e. $g_n$ gives an automorphism of a finitely generated + 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 + + \end{enumerate} + Before we give the third point, suppose recursively that $g_{n-1}$ already + satisfy all those properties. Let us enumerate + $\{\langle (A_{n,k}, \alpha_{n, k}), (B_{n,k}, \beta_{n,k}), f_{n, k}\rangle\}_{k\in\bN}$ + all pairs of finitely generated structures with automorphisms such + that the first substructure embed into the second by inclusion, 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}, g_{n-1})$. + We allow $A_{n,k}$ to be empty. Although $g_{n-1}$ is a finite function, + we may treat it as an automorphism as we have said before. + + \begin{enumerate}[resume, label=(\roman*)] + \item + 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 @@ -178,13 +204,15 @@ \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 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 + First, we will satisfy the item (iii). Namely, we will construct $\Gamma'_n, g'_n$ + such that $g_{n-1}\subseteq g'_n$, $\Gamma_{n-1}\subseteq\Gamma'_n$, + $g'_n$ gives an automorphism of $\Gamma'_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. @@ -197,34 +225,48 @@ \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 $\cK$ 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 + It is important to note that $g'_n$ should be a finite function and once + again, as it is an automorphism of a finitely generated structure, we may + think it is simply a map from one generators of $\Gamma'_n$ to the + others. By the weak ultrahomogeneity of $\Gamma$, we may assume that + $\Gamma'_n\subseteq \Gamma$. + + % \begin{center} + % \begin{tikzcd} + % B_{i,j}\cup\Gamma_{n-1} \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Gamma \\ + % \Gamma'_{n}\arrow[ur, dashed, "f"'] + % \end{tikzcd} + % \end{center} + + Now, by the WHP of $\cK$ we can extend $\langle\Gamma'_n\cup\{v_n\}\rangle$ together + with its partial isomorphism $g'_n$ to a finitely generated structure $\Gamma_n$ + together with its + automorphism $g_n\supseteq g'_n$ and (again by weak ultrahomogeneity) + 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. + and is an union of an increasing chain of automorphisms of finitely generated + substructures. - Take any finite structure of $T$ with automorphism $(B, \beta)$. Then, there are + Take any $(B, \beta)\in\cD$. 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}\}$. + $(i, j) = \min\{\{0,1,\ldots n-1\}\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. + into $(\Gamma, g)$. Hence, the age of $(\Gamma, g)$ is $\cH$. + + It is also weakly ultrahomogeneous. Having $(A,\alpha)\subseteq(B,\beta)$, + and an embedding $f\colon(A,\alpha)\to(\Gamma,g)$, we may find $n\in\bN$ + such that $(i,j) = \min\{\{0,1,\ldots n-1\}\times X_{n-1}\}$ and + $(A,\alpha) = (A_{i,j},\alpha_{i,j}), (B,\beta)=(B_{i,j},\beta_{i,j})$ and + $f = f_{i,j}$. This means that there is a compatbile embedding of $(B,\beta)$ into + $(\Gamma_n, g_n)$, which means we can also embed it into $(\Gamma, g)$. + Hence, $(\Gamma,g)\cong(\Gamma,\sigma)$. 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 diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex index 0254280..993ca73 100644 --- a/sections/fraisse_classes.tex +++ b/sections/fraisse_classes.tex @@ -277,13 +277,13 @@ $A, B, C\in\cK$ such that $C = A\cap B$ the following diagram commutes: \begin{center} \begin{tikzcd} - & A\sqcup B & \\ + & A\sqcup_C B & \\ A \ar[ur, hook] & & B \ar[ul, hook'] \\ & C \ar[ur, hook] \ar[ul, hook'] & \end{tikzcd} \end{center} - $A\sqcup B$ here is an $L$-strcuture with domain $A\cup B$ such that + $A\sqcup_C B$ here is an $L$-strcuture with domain $A\cup B$ such that for every $n$-ary symbol $R$ from $L$, $n$-tuple $\bar{a}\subseteq A\cup B$, we have that $A\sqcup B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and $A\models R(\bar{a})$] or [$\bar{a}\subseteq B$ and $B\models R(\bar{a})$]. @@ -291,8 +291,7 @@ Actually we did already implicitly worked with free amalgamation in the Proposition \ref{proposition:finite-graphs-fraisse-class}, showing that - the class of finite strcuture is indeed a Fraïssé class. - + the class of finite graphs is indeed a Fraïssé class. \subsection{Canonical amalgamation} @@ -377,19 +376,9 @@ \end{center} Then, by the Fact \ref{fact:functor_iso}, $\otimes_C(\eta)$ is an automorphism - of the pushout diagram: + of the pushout diagram that looks exaclty like the diagram in the second + point of the Definition \ref{definition:canonical_amalgamation}. - \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)$ diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex index 05aa3ed..2bf254c 100644 --- a/sections/preliminaries.tex +++ b/sections/preliminaries.tex @@ -363,7 +363,7 @@ \end{fact} \begin{proof} - Suppose that $\eta_(A)$ is an isomorphism for every $A\in\cC$, where + Suppose that $\eta_{A}$ is an isomorphism for every $A\in\cC$, where $\eta_{A}\colon F(A)\to G(A)$ is the morphism of the natural transformation coresponding to $A$. Then $\eta^{-1}$ is simply given by the morphisms $\eta^{-1}_A$. diff --git a/uwagi_29_06_22.txt b/uwagi_29_06_22.txt index 805fb21..0f1ef2c 100644 --- a/uwagi_29_06_22.txt +++ b/uwagi_29_06_22.txt @@ -144,7 +144,7 @@ n and without the loss of generality we may assume that - [x] Po 4.4 powinien być wniosek, że kanoniczna amalgamacja+whp dają konkluzję 4.4, a potem z tego, że wolna amalgamacja daje 4.4 -- [ ] W sekcji 4.3 brakuje założeń. +- [x] W sekcji 4.3 brakuje założeń. - [x] Jak przekształcenie naturalne jest izomorfizmem, to ten składowe też są izomorfizmami (w dwie strony) @@ -156,7 +156,7 @@ n and without the loss of generality we may assume that - [x] Dodać uwagę, że jak piszę (\Pi, \sigma) to chodzi mi o co innego niż jak piszę \Pi -- [ ] "Odmętnić" początek dowódu 3.23 +- [x] "Odmętnić" początek dowódu 3.23 - [x] Poprawić wielkości liter przy theorem, facts itd -- cgit v1.2.3 From ae1c456f6467a50427fc485ec5ae163495ea0e52 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Wed, 13 Jul 2022 23:09:49 +0200 Subject: Ortografia --- lic_malinka.pdf | Bin 483862 -> 483781 bytes sections/conj_classes.tex | 12 ++++++------ sections/fraisse_classes.tex | 18 +++++++++--------- sections/preliminaries.tex | 2 +- 4 files changed, 16 insertions(+), 16 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 671b753..0529e44 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex index 9620220..c0120d3 100644 --- a/sections/conj_classes.tex +++ b/sections/conj_classes.tex @@ -32,7 +32,7 @@ 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\}$. + 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 consist @@ -96,7 +96,7 @@ $\langle \dom(g)\rangle$ and $\langle\rng(g)\rangle$, i.e. substructures generated by $\dom(g)$ and $\rng(g)$ respectively. Of course, in our case, $g$ is good - if and only if $[g]_{\Aut(\Gamma)} \neq\emptyset$ (becuase of ultrahomogeneity + if and only if $[g]_{\Aut(\Gamma)} \neq\emptyset$ (because of ultrahomogeneity of $\Gamma$. Also it is important to mention that an isomorphism between two finitely @@ -121,7 +121,7 @@ words, a basic open set is a set of all extensions of some finite partial automorphism $g_0$ of $\Gamma$. By $B_{g}\subseteq G$ we denote a basic open subset given by a finite partial isomorphism $g$. Again, Note that $B_g$ - is nonemty because of ultrahomogeneity of $\Gamma$. + is nonempty 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, @@ -165,7 +165,7 @@ $X_{-1} = \emptyset$. Suppose that player \textit{I} in the $n$-th move chooses a finite partial automorphism $f_n$. We will construct a finite partial automorphism - $g_n\supseteq f_n$ together with a finitely generated substrucutre + $g_n\supseteq f_n$ together with a finitely generated substructure $\Gamma_n \subseteq \Gamma$ and a set $X_n\subseteq\bN^2$ such that the following properties hold: @@ -263,7 +263,7 @@ and an embedding $f\colon(A,\alpha)\to(\Gamma,g)$, we may find $n\in\bN$ such that $(i,j) = \min\{\{0,1,\ldots n-1\}\times X_{n-1}\}$ and $(A,\alpha) = (A_{i,j},\alpha_{i,j}), (B,\beta)=(B_{i,j},\beta_{i,j})$ and - $f = f_{i,j}$. This means that there is a compatbile embedding of $(B,\beta)$ into + $f = f_{i,j}$. This means that there is a compatible embedding of $(B,\beta)$ into $(\Gamma_n, g_n)$, which means we can also embed it into $(\Gamma, g)$. Hence, $(\Gamma,g)\cong(\Gamma,\sigma)$. @@ -290,7 +290,7 @@ Let $\cC$ be a Fraïssé class of finitely generated $L$-structures with weak Hrushovski property and canonical amalgamation. Let $\cD$ be the Fraïssé class (by the Theorem \ref{theorem:key-theorem} - of the structures of $\cC$ with additional automorphism of the strucutre. + of the structures of $\cC$ with additional automorphism of the structure. Let $\Gamma = \Flim(\cC)$. \begin{proposition} diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex index 993ca73..87647c6 100644 --- a/sections/fraisse_classes.tex +++ b/sections/fraisse_classes.tex @@ -15,7 +15,7 @@ \end{definition} \begin{definition} - We say that a class $\cK$ of finitely generated strcutures + We say that a class $\cK$ of finitely generated structures is \emph{essentially countable} if it has countably many isomorphism types of finitely generated structures. \end{definition} @@ -40,7 +40,7 @@ \end{definition} In terms of category theory we may say that $\cK$ is a category of finitely - generated strcutures where morphims are embeddings of those strcutures. + generated structures where morphisms are embeddings of those structures. Then the above diagram is a \emph{span} diagram in category $\cK$. Fraïssé has shown fundamental theorems regarding age of a structure, one of @@ -272,7 +272,7 @@ \begin{definition} \label{definition:free_amalgamation} - Let $L$ be a relational language and $\cK$ a class of $L$-strucutres. + Let $L$ be a relational language and $\cK$ a class of $L$-structures. $\cK$ has \emph{free amalgamation} if for every $A, B, C\in\cK$ such that $C = A\cap B$ the following diagram commutes: \begin{center} @@ -283,7 +283,7 @@ \end{tikzcd} \end{center} - $A\sqcup_C B$ here is an $L$-strcuture with domain $A\cup B$ such that + $A\sqcup_C B$ here is an $L$-structure with domain $A\cup B$ such that for every $n$-ary symbol $R$ from $L$, $n$-tuple $\bar{a}\subseteq A\cup B$, we have that $A\sqcup B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and $A\models R(\bar{a})$] or [$\bar{a}\subseteq B$ and $B\models R(\bar{a})$]. @@ -346,11 +346,11 @@ \end{itemize} \end{definition} - From now on in the paper, when $A$ is an $L$-strcuture and $\alpha$ is + From now on in the paper, when $A$ is an $L$-structure and $\alpha$ is an automorphism of - $A$, then by $(A, \alpha)$ we mean the strucutre $A$ expanded by the - unary function corresping to $\alpha$, and $A$ constantly denotes the - $L$-strucutre. + $A$, then by $(A, \alpha)$ we mean the structure $A$ expanded by the + unary function corresponding to $\alpha$, and $A$ constantly denotes the + $L$-structure. \begin{theorem} \label{theorem:canonical_amalgamation_thm} @@ -376,7 +376,7 @@ \end{center} Then, by the Fact \ref{fact:functor_iso}, $\otimes_C(\eta)$ is an automorphism - of the pushout diagram that looks exaclty like the diagram in the second + of the pushout diagram that looks exactly like the diagram in the second point of the Definition \ref{definition:canonical_amalgamation}. This means that the morphism $\delta\colon A\otimes_C B\to A\otimes_C B$ diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex index 2bf254c..0a1b202 100644 --- a/sections/preliminaries.tex +++ b/sections/preliminaries.tex @@ -365,7 +365,7 @@ \begin{proof} Suppose that $\eta_{A}$ is an isomorphism for every $A\in\cC$, where $\eta_{A}\colon F(A)\to G(A)$ is the morphism of the natural transformation - coresponding to $A$. Then $\eta^{-1}$ is simply given by the morphisms + corresponding to $A$. Then $\eta^{-1}$ is simply given by the morphisms $\eta^{-1}_A$. Now assume that $\eta$ is an isomorphism, i.e. $\eta^{-1}\circ\eta = \id_F$. -- cgit v1.2.3 From 2b830cb2d9c2237fcb7809bab7c64966098ea6fb Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Sun, 17 Jul 2022 14:16:41 +0200 Subject: Oby ostatnie poprawki --- lic_malinka.pdf | Bin 483781 -> 480986 bytes licmalinka.bib | 10 ++---- sections/conj_classes.tex | 72 ++++++++++--------------------------------- sections/fraisse_classes.tex | 11 +++++-- sections/introduction-pl.tex | 4 +-- sections/introduction.tex | 6 ++-- sections/preliminaries.tex | 1 + 7 files changed, 32 insertions(+), 72 deletions(-) diff --git a/lic_malinka.pdf b/lic_malinka.pdf index 0529e44..6354005 100644 Binary files a/lic_malinka.pdf and b/lic_malinka.pdf differ diff --git a/licmalinka.bib b/licmalinka.bib index 6c1237c..26dd13f 100644 --- a/licmalinka.bib +++ b/licmalinka.bib @@ -53,26 +53,20 @@ year = {2007} }, @article{extending_iso_graphs, - title={http://math.univ-lyon1.fr/~milliet/grapheanglais.pdf}, + title={Extending partial isomorphisms of finite graphs}, url={http://math.univ-lyon1.fr/~milliet/grapheanglais.pdf}, author={Cédric Milliet}, year={2004} }, @article{hrushovski_extending_iso, author={Ehud Hrushovski}, + title={Extending partial isomorphisms of graphs}, year={1992}, journal={Combinatorica}, volume={12}, pages={411-416}, doi={https://doi.org/10.1007/BF01305233}, }, -@book{siniora2017automorphism, - title={Automorphism Groups of Homogeneous Structures}, - author={Siniora, D.N.}, - url={https://books.google.pl/books?id=-qiZtAEACAAJ}, - year={2017}, - publisher={University of Leeds (Department of Pure Mathematics)} -} @book{siniora2017automorphism, title={Automorphism Groups of Homogeneous Structures}, author={Daoud Nasri Siniora}, diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex index c0120d3..9ec4b0c 100644 --- a/sections/conj_classes.tex +++ b/sections/conj_classes.tex @@ -46,7 +46,7 @@ $\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 + one can easily construct a permutation that extends $\gamma$ and has at least $k$ many $n$-cycles. Now we see that $A = \bigcap_{n=1}^{\infty} A_n$ is a comeagre set consisting @@ -97,21 +97,21 @@ generated by $\dom(g)$ and $\rng(g)$ respectively. Of course, in our case, $g$ is good if and only if $[g]_{\Aut(\Gamma)} \neq\emptyset$ (because of ultrahomogeneity - of $\Gamma$. + of $\Gamma$). Also it is important to mention that an isomorphism between two finitely generated structures is uniquely given by a map from generators of one structure to the other. This allow us to treat a finite function as an isomorphism - of finitely generated structure. + of finitely generated structures. \begin{proof} Let $\Gamma = \Flim(\cC)$ and $(\Pi, \sigma) = \Flim(\cD)$. First, by the Theorem \ref{theorem:isomorphic_fr_lims}, we may assume without the loss of generality that $\Pi = \Gamma$. Let $G = \Aut(\Gamma)$, i.e. $G$ is the automorphism group of $\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 the $\sigma$'s conjugacy class. + We will construct a winning strategy for the second player in the Banach-Mazur game + (see \ref{definition:banach-mazur-game}) + on the topological space $G$ with $A$ being $\sigma$'s conjugacy class. By the Banach-Mazur theorem (see \ref{theorem:banach_mazur_thm}) this will prove that this class is comeagre. @@ -129,15 +129,6 @@ 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, 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 @@ -145,24 +136,14 @@ 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 - $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 ingredient of the proof will be a bookkeeping argument. For technical reasons, let $g_{-1} = \emptyset$ and - $X_{-1} = \emptyset$. + $X_{-1} = \emptyset$. Enumerate the elements of the Fraïssé limit + $\Gamma = \{v_0, v_1, \ldots\}$. Suppose that player \textit{I} in the $n$-th move chooses a finite partial automorphism $f_n$. We will construct a finite partial automorphism $g_n\supseteq f_n$ together with a finitely generated substructure @@ -204,26 +185,13 @@ \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 satisfy the item (iii). Namely, we will construct $\Gamma'_n, g'_n$ such that $g_{n-1}\subseteq g'_n$, $\Gamma_{n-1}\subseteq\Gamma'_n$, $g'_n$ gives an automorphism of $\Gamma'_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. + done by the fact, that $\cD$ has the amalgamation property. - \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} It is important to note that $g'_n$ should be a finite function and once again, as it is an automorphism of a finitely generated structure, we may @@ -231,14 +199,7 @@ others. By the weak ultrahomogeneity of $\Gamma$, we may assume that $\Gamma'_n\subseteq \Gamma$. - % \begin{center} - % \begin{tikzcd} - % B_{i,j}\cup\Gamma_{n-1} \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Gamma \\ - % \Gamma'_{n}\arrow[ur, dashed, "f"'] - % \end{tikzcd} - % \end{center} - - Now, by the WHP of $\cK$ we can extend $\langle\Gamma'_n\cup\{v_n\}\rangle$ together + Now, by the WHP of $\cC$ we can extend $\langle\Gamma'_n\cup\{v_n\}\rangle$ together with its partial isomorphism $g'_n$ to a finitely generated structure $\Gamma_n$ together with its automorphism $g_n\supseteq g'_n$ and (again by weak ultrahomogeneity) @@ -247,7 +208,7 @@ 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. + of $\Gamma$ such that $(\Gamma, g)$ has the age $\cD$ and is weakly ultrahomogeneous. It is of course an automorphism of $\Gamma$ as it is defined for every $v\in\Gamma$ and is an union of an increasing chain of automorphisms of finitely generated substructures. @@ -257,7 +218,8 @@ By the bookkeeping there was $n$ such that $(i, j) = \min\{\{0,1,\ldots n-1\}\times\bN\setminus X_{n-1}\}$. This means that $(B, \beta)$ embeds into $(\Gamma_n, g_n)$, hence it embeds - into $(\Gamma, g)$. Hence, the age of $(\Gamma, g)$ is $\cH$. + into $(\Gamma, g)$. Thus, $\cD$ is a subclass of the age of $(\Gamma, g)$. + The other inclusion is obvious. Hence, the age of $(\Gamma, g)$ is $\cH$. It is also weakly ultrahomogeneous. Having $(A,\alpha)\subseteq(B,\beta)$, and an embedding $f\colon(A,\alpha)\to(\Gamma,g)$, we may find $n\in\bN$ @@ -267,11 +229,9 @@ $(\Gamma_n, g_n)$, which means we can also embed it into $(\Gamma, g)$. Hence, $(\Gamma,g)\cong(\Gamma,\sigma)$. - 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$. + By this we know that $g$ and $\sigma$ are conjugate in $G$, thus player \textit{II} + have a winning strategy in the Banach-Mazur game with $A=\sigma^G$, + thus $\sigma^G$ is comeagre in $G$ and $\sigma$ is a generic automorphism. \end{proof} \begin{theorem} diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex index 87647c6..1126dee 100644 --- a/sections/fraisse_classes.tex +++ b/sections/fraisse_classes.tex @@ -283,13 +283,14 @@ \end{tikzcd} \end{center} + and $A\sqcup_C B\in\cC$. $A\sqcup_C B$ here is an $L$-structure with domain $A\cup B$ such that for every $n$-ary symbol $R$ from $L$, $n$-tuple $\bar{a}\subseteq A\cup B$, - we have that $A\sqcup B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and + we have that $A\sqcup_C B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and $A\models R(\bar{a})$] or [$\bar{a}\subseteq B$ and $B\models R(\bar{a})$]. \end{definition} - Actually we did already implicitly worked with free amalgamation in the + Actually we did already implicitly work with free amalgamation in the Proposition \ref{proposition:finite-graphs-fraisse-class}, showing that the class of finite graphs is indeed a Fraïssé class. @@ -298,7 +299,7 @@ Recall, $\Cospan(\cC)$, $\Pushout(\cC)$ are the categories of cospan and pushout diagrams of the category $\cC$. We have also denoted the notion of cospans and pushouts with a fixed base structure $C$ denoted - as $\Cospan_C(\cC)$ and $Pushout_C(\cC)$. + as $\Cospan_C(\cC)$ and $\Pushout_C(\cC)$. \begin{definition} \label{definition:canonical_amalgamation} @@ -346,6 +347,10 @@ \end{itemize} \end{definition} + \begin{remark} + Free amalgamation is canonical. + \end{remark} + From now on in the paper, when $A$ is an $L$-structure and $\alpha$ is an automorphism of $A$, then by $(A, \alpha)$ we mean the structure $A$ expanded by the diff --git a/sections/introduction-pl.tex b/sections/introduction-pl.tex index bd6e2f1..1b06733 100644 --- a/sections/introduction-pl.tex +++ b/sections/introduction-pl.tex @@ -38,6 +38,6 @@ 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}). + % 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/introduction.tex b/sections/introduction.tex index 655cba7..6cb432e 100644 --- a/sections/introduction.tex +++ b/sections/introduction.tex @@ -36,7 +36,7 @@ this by using the Banach-Mazur games, a well known method in the descriptive set theory, which proves useful in the study of comeagre sets. - Finally, we show how this construction of the generic automorphism can be - used to deduce some properties of generic automorphisms - (see \ref{proposition:fixed_points}, (COŚ JESZCE)). + % Finally, we show how this construction of the generic automorphism can be + % used to deduce some properties of generic automorphisms + % (see \ref{proposition:fixed_points}, (COŚ JESZCE)). \end{document} diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex index 0a1b202..b27cd69 100644 --- a/sections/preliminaries.tex +++ b/sections/preliminaries.tex @@ -76,6 +76,7 @@ \end{definition} \begin{definition} + \label{definition:banach-mazur-game} 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 -- cgit v1.2.3