Zmiana struktury, teraz osobne pliki na każdą sekcję

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}