diff options
Diffstat (limited to 'sections/conj_classes.tex')
| -rw-r--r-- | sections/conj_classes.tex | 251 |
1 files changed, 251 insertions, 0 deletions
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} |