path: root/sections/conj_classes.tex

\documentclass[../lic_malinka.tex]{subfiles}

\begin{document}
  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\}$.  

  \subsection{Prototype: pure set} 

  In this section, $M=(M,=)$ is an infinite countable set (with no structure
  beyond equality).
  
  \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{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
	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 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\} \\
		  &= \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 union over basic open sets generated by finite
	permutations with $m$ in their domain. Denseness is also easy to see.

	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}

  \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 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 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 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
	and $\cD$ is a Fraïssé class, then there is a comeagre conjugacy class in the
	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)$. 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.
	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
	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
	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 
	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, 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 
	$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$. 
	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
	$\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 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,

	  \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
		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 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.

    \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
	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 an union of an increasing chain of automorphisms of finitely generated
	substructures.

	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 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$. 

	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
	comeagre and $\sigma$ is a generic automorphism, as it contains a comeagre
	set $A$.
  \end{proof}

  \begin{theorem}
	\label{theorem:key-theorem}
	Let $\cC$ be a Fraïssé class of finitely generated $L$-structures with WHP
	and canonical amalgamation. Then $\Flim(\cC)$ has a generic automorphism.
  \end{theorem}

  \begin{proof}
	It follows trivially from Corollary \ref{corollary:whp+canonical-iso}
	and the above Theorem \ref{theorem:generic_aut_general}.
  \end{proof}

  \subsection{Properties of the generic automorphism}

  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.
  Let $\Gamma = \Flim(\cC)$. 

  \begin{proposition}
	\label{proposition:fixed_points}
	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 $\cD$, thus we
	can embed 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 $\cD$.
  \end{proof}
\end{document}