aboutsummaryrefslogtreecommitdiff
path: root/sections/fraisse_classes.tex
diff options
context:
space:
mode:
Diffstat (limited to 'sections/fraisse_classes.tex')
-rw-r--r--sections/fraisse_classes.tex135
1 files changed, 31 insertions, 104 deletions
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}