From ad63d0a98d8595d3267fd81196cf8c96361bd911 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Mon, 11 Jul 2022 20:13:42 +0200 Subject: Updates updates --- sections/fraisse_classes.tex | 135 ++++++++++--------------------------------- 1 file changed, 31 insertions(+), 104 deletions(-) (limited to 'sections/fraisse_classes.tex') diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex index 74a8d61..0254280 100644 --- a/sections/fraisse_classes.tex +++ b/sections/fraisse_classes.tex @@ -236,7 +236,8 @@ \begin{definition} We say that a Fraïssé class $\cK$ has the \emph{weak Hrushovski property} (\emph{WHP}) if for every $A\in \cK$ and an isomorphism - of its substructures $p\colon A\to A$ (also called a partial automorphism of $A$), + of its finitely generated substructures + $p\colon A\to A$ (also called a partial automorphism of $A$), there is some $B\in \cK$ such that $p$ can be extended to an automorphism of $B$, i.e.\ there is an embedding $i\colon A\to B$ and a $\bar p\in \Aut(B)$ such that the following @@ -346,6 +347,12 @@ \end{itemize} \end{definition} + From now on in the paper, when $A$ is an $L$-strcuture 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. + \begin{theorem} \label{theorem:canonical_amalgamation_thm} Let $\cK$ be a Fraïssé class of $L$-structures with canonical amalgamation. @@ -389,79 +396,11 @@ in $\cH$. \end{proof} - \subsection{Graphs with automorphism} - The language and theory of undirected graphs is fairly simple. We extend the - language by one unary symbol $\sigma$ and interpret it as an arbitrary - automorphism on the graph structure. It turns out that the class of such - structures is a Fraïssé class. - - \begin{proposition} - Let $\cH$ be the class of all finite graphs with an automorphism, i.e. - structures in the language $(E, \sigma)$ such that $E$ is a symmetric - relation and $\sigma$ is an automorphism on the structure. $\cH$ is - a Fraïssé class. - \end{proposition} - \begin{proof} - Countability and HP are obvious, JEP follows by the same argument as in - plain graphs. We need to show that the class has the amalgamation property. - - Take any $(A, \alpha), (B, \beta), (C,\gamma)\in\cH$ such that $A$ embeds - into $B$ and $C$. Without the loss of generality we may assume that - $B\cap C = A$ and $\alpha\subseteq\beta,\gamma$. - Let $D$ be the amalgamation of $B$ and $C$ over $A$ as in - the proof for the plain graphs. We will define the automorphism - $\delta\in\Aut(D)$ so it extends $\beta$ and $\gamma$. - We let $\delta\upharpoonright_B = \beta, \delta\upharpoonright_C = \gamma$. - - Let us check that the definition is correct. We have to show that - $(uE_Dv\leftrightarrow \delta(u)E_D\delta(v))$ holds for any $u, v\in - D$. We have two cases: - \begin{itemize} - \item $u, v\in X$, where $X$ is either $B$ or $C$. This case is trivial. - \item $u\in B\setminus A, v\in C\setminus A$. Then - $\delta(u)=\beta(u)\in B\setminus A$, similarly $\delta(v)=\gamma(v)\in - C\setminus A$. This follows from the fact that $\beta\upharpoonright_A - = \alpha$, so for any $w\in A$ it holds that - $\beta^{-1}(w)=\alpha^{-1}(w)\in A$, - similarly for $\gamma$. Thus, from the construction of $D$, $\neg uE_Dv$ - and $\neg \delta(u)E_D\delta(v)$. - \end{itemize} - \end{proof} - - The proposition says that there is a Fraïssé limit for the class $\cH$ of finite - graphs with automorphisms. We shall call it $(\FrAut, \sigma)$. Not - surprisingly, $\FrAut$ is in fact a random graph. - - \begin{proposition} - \label{proposition:graph-aut-is-normal} - The Fraïssé limit of $\cH$ interpreted as a plain graph (i.e. as a reduct - to the language of graphs) is isomorphic to the random graph $\FrGr$. - \end{proposition} - - \begin{proof} - It is enough to show that $\FrAut = \Flim(\cH)$ has the random graph - property. Take any finite disjoint $X, Y\subseteq \FrAut$. Without the loss - of generality assume that $X\cup Y$ is $\sigma$-invariant, i.e. - $\sigma(v)\in X\cup Y$ for $v\in X\cup Y$. This assumption can be made - because there are no infinite orbits in $\sigma$, which in turn is due to - the fact that $\cH$ is the age of $\FrAut$. - - Let $G_{XY}$ be the graph induced by $X\cup Y$. Take $H=G_{XY}\sqcup {v}$ - as a supergraph of $G_{XY}$ with one new vertex $v$ connected to all - vertices of $X$ and to none of $Y$. By the proposition - \ref{proposition:finite-graphs-whp} we can extend $H$ together with its - partial isomorphism $\sigma\upharpoonright_{X\cup Y}$ to a graph $R$ with - automorphism $\tau$. Once again, without the loss of generality we can - assume that $R\subseteq\FrAut$, because $\cH$ is the age of $\FrAut$. But - $R\upharpoonright_{G_{XY}}$ together with $\tau\upharpoonright_{G_{XY}}$ - are isomorphic to the $G_{XY}$ with $\sigma\upharpoonright_{G_{XY}}$. - - Thus, by ultrahomogeneity of $\FrAut$ this isomorphism extends to an - automorphism $\theta$ of $(\FrAut, \sigma)$. Then $\theta(v)$ is the vertex - that is connected to all vertices of $X$ and none of $Y$, because - $\theta[R\upharpoonright_X] = X, \theta[R\upharpoonright_Y] = Y$. - \end{proof} - + The following theorem is one of the most important in construction of + the generic automorphism given in the next section. Together with canonical + amalgamation it gives a general fact about Fraïssé classes, namely it says + that expanding a Fraïssé class with an automorphism of the structures + does not change the limit. \begin{theorem} \label{theorem:isomorphic_fr_lims} @@ -483,11 +422,11 @@ $(\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$. We will - find an embedding of $B$ into $\Pi$ to show that $\Pi$ is indeed weakly - homogeneous. + Now, to show that $\Pi$ is weakly homogeneous, take any structures $A, B\in\cC$ + such that $A\subseteq B$ with a fixed embedding of $A$ into $\Pi$. Without the - loss of generality assume that $A = B\cap \Pi$. Let $\bar{A}\subseteq\Pi$ + loss of generality assume that $A = B\cap \Pi$ (i.e. $A$ embeds into $\Pi$ + by inclusion). Let $\bar{A}\subseteq\Pi$ be the smallest substructure closed under the automorphism $\sigma$ and containing $A$. It is finitely generated as an $L$-structure, @@ -520,33 +459,21 @@ \end{tikzcd} \end{center} - % - % By the weak Hrushovski property - % of $\cC$ let $(\bar{B}, \beta)$ be a structure extending - % $(B, \sigma\upharpoonright_{A})$. Again, we may assume - % that $B\cup \bar{A}\subseteq \bar{B}$. Then, by the fact that $\Pi$ is a - % Fraïssé limit of $\cD$ there is an embedding - % $f\colon(\bar{B}, \beta)\to(\Pi, \sigma)$ - % such that the following diagram commutes: - % - % - % \begin{center} - % \begin{tikzcd} - % (A, \emptyset) \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & (\bar{A}, \sigma\upharpoonright_A) \arrow[d, "\subseteq"] \arrow[r, "\subseteq"] & (\Pi, \sigma) \\ - % (B, \sigma\upharpoonright_B) \arrow[r, dashed, "\subseteq"'] & (\bar{B}, \beta) \arrow[ur, dashed, "f"] - % \end{tikzcd} - % \end{center} - - % Then we simply get the following diagram: - % - % \begin{center} - % \begin{tikzcd} - % A \arrow[d, "\subseteq"'] \arrow[r, "\subseteq"] & \Pi \\ - % B \arrow[ur, dashed, "f\upharpoonright_B"'] - % \end{tikzcd} - % \end{center} - % which proves that $\Pi$ is indeed a weakly ultrahomogeneous structure. Hence, it is isomorphic to $\Gamma$. \end{proof} + + \begin{corollary} + \label{corollary:whp+canonical-iso} + Let $\cC$ be a Fraïssé class of finitely generated $L$-structures + with WHP and canonical amalgamation. Let + $\cD$ be the class consisting of structures from $\cC$ with an additional + automorphism. Let $\Gamma = \Flim(\cC)$ and $\Pi = \Flim(\cD)$. + Then $\Gamma \cong \Pi\mid_L$. + \end{corollary} + + \begin{proof} + It follows from Theorems \ref{theorem:canonical_amalgamation_thm} and + \ref{theorem:isomorphic_fr_lims}. + \end{proof} \end{document} -- cgit v1.2.3