updates updates

1 files changed, 136 insertions, 71 deletions

diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex
index dc6392d..32804f2 100644
--- a/sections/fraisse_classes.tex
+++ b/sections/fraisse_classes.tex
@@ -9,26 +9,27 @@
   \subsection{Definitions} 
   \begin{definition}
     Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is
-    the class $\bK$ of all finitely generated structures that embed into $M$.
+    the class $\cK$ of all finitely generated structures that embed into $M$.
     The age of $M$ is also associated with class of all structures embeddable in
     $M$ \emph{up to isomorphism}.
   \end{definition}
 
   \begin{definition}
-    We say that $M$ has \emph{countable age} when its age has countably many 
-    isomorphism types of finitely generated structures. 
+	We say that a class $\cK$ of finitely generated strcutures 
+	is \emph{essentially countable} if it has countably many isomorphism types
+	of finitely generated structures.
   \end{definition}
 
   \begin{definition}
-    Let $\bK$ be a class of finitely generated structures. $\bK$ has 
-    \emph{hereditary property (HP)} if for any $A\in\bK$, any finitely generated
-    substructure $B$ of $A$ it holds that $B\in\bK$. 
+    Let $\cK$ be a class of finitely generated structures. $\cK$ has the
+    \emph{hereditary property (HP)} if for any $A\in\cK$ and any finitely 
+	generated substructure $B$ of $A$ it holds that $B\in\cK$. 
   \end{definition}
 
   \begin{definition}
-    Let $\bK$ be a class of finitely generated structures. We say that $\bK$ has
-    \emph{joint embedding property (JEP)} if for any $A, B\in\bK$ there is a
-    structure $C\in\bK$ such that both $A$ and $B$ embed in $C$.
+    Let $\cK$ be a class of finitely generated structures. We say that $\cK$ has
+	the \emph{joint embedding property (JEP)} if for any $A, B\in\cK$ there is 
+	a structure $C\in\cK$ such that both $A$ and $B$ embed in $C$.
 
     \begin{center}
       \begin{tikzcd}
@@ -36,27 +37,34 @@
         A \arrow[ur, dashed, "f"] &   & B \arrow[ul, dashed, "g"'] 
 	  \end{tikzcd}
     \end{center}
-
-	In terms of category theory, this is a \emph{span} in category $\bK$.
   \end{definition}
 
-  Fraïssé has shown fundamental theories regarding age of a structure, one of 
+  In terms of category theory we may say that $\cK$ is a category of finitely
+  generated strcutures where morphims are embeddings of those strcutures.
+  Then the above diagram is a \emph{span} diagram in category $\cK$. 
+
+  Fraïssé has shown fundamental theorems regarding age of a structure, one of 
   them being the following one:
   
   \begin{fact}
     \label{fact:age_is_hpjep}
-    Suppose $L$ is a signature and $\bK$ is a nonempty finite or countable set 
-    of finitely generated $L$-structures. Then $\bK$ has the HP and JEP if
-    and only if $\bK$ is the age of some finite or countable structure. 
+    Suppose $L$ is a signature and $\cK$ is a nonempty essentially countable set 
+    of finitely generated $L$-structures. Then $\cK$ has the HP and JEP if
+    and only if $\cK$ is the age of some finite or countable structure. 
   \end{fact}
 
+  \begin{proof}
+	One can read a proof of this fact in Wilfrid
+	Hodges' classical book \textit{Model Theory}~\cite[Theorem~7.1.1]{hodges_1993}. 
+  \end{proof}
+
   Beside the HP and JEP Fraïssé has distinguished one more property of the 
-  class $\bK$, namely amalgamation property.
+  class $\cK$, namely the amalgamation property.
 
   \begin{definition}
-    Let $\bK$ be a class of finitely generated $L$-structures. We say that $\bK$
-    has the \emph{amalgamation property (AP)} if for any $A, B, C\in\bK$ and
-    embeddings $e\colon C\to A, f\colon C\to B$ there exists $D\in\bK$ together
+    Let $\cK$ be a class of finitely generated $L$-structures. We say that $\cK$
+    has the \emph{amalgamation property (AP)} if for any $A, B, C\in\cK$ and
+    embeddings $e\colon C\to A, f\colon C\to B$ there exists $D\in\cK$ together
     with embeddings $g\colon A\to D$ and $h\colon A\to D$ such that 
     $g\circ e = h\circ f$.
     \begin{center}
@@ -68,8 +76,15 @@
     \end{center}
   \end{definition}
 
-  In terms of category theory, amalgamation over some structure $C$ is a
-  pushout diagram.
+  In terms of category theory, $\cK$ has the amalgamation property if every
+  cospan diagram can be extended to a pushout diagram in category $\cK$.
+  We will get into more details later, in the definition of canonical 
+  amalgamation \ref{definition:canonical_amalgamation}.
+
+  \begin{definition}
+	Class $\cK$ of finitely generated structure is a \emph{Fraïssé class}
+	if it is essentially countable, has HP, JEP and AP.
+  \end{definition}
 
   \begin{definition}
     Let $M$ be an $L$-structure. $M$ is \emph{ultrahomogeneous} if every
@@ -81,20 +96,20 @@
 
   \begin{theorem}[Fraïssé theorem]
     \label{theorem:fraisse_thm}
-    Let L be a countable language and let $\bK$ be a nonempty countable set of
-    finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ is 
+    Let L be a countable language and let $\cK$ be a nonempty countable set of
+    finitely generated $L$-structures which has HP, JEP and AP. Then $\cK$ is 
     the age of a countable, ultrahomogeneous $L$-structure $M$. Moreover, $M$ is
-    unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\bK$
-    and denote this by $M = \Flim(\bK)$.
+    unique up to isomorphism. We say that $M$ is a \emph{Fraïssé limit} of $\cK$
+    and denote this by $M = \Flim(\cK)$.
   \end{theorem}
 
-  This is a well known theorem. One can read a proof of this theorem in Wilfrid
-  Hodges' classical book \textit{Model Theory}~\cite{hodges_1993}. In the proof
-  of this theorem appears another, equally important \ref{lemma:weak_ultrahom}.
+  \begin{proof}
+	Check the proof in \cite[theorem~7.1.2]{hodges_1993}.
+  \end{proof}
 
   \begin{definition}
     We say that an $L$-structure $M$ is \emph{weakly ultrahomogeneous} if for any
-    $A, B$ finitely generated substructures of $M$ such that $A\subseteq B$ and
+    $A, B$, finitely generated substructures of $M$, such that $A\subseteq B$ and
     an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which
     extends $f$.
     \begin{center}
@@ -111,29 +126,34 @@
     ultrahomogeneous.
   \end{lemma}
 
+  \begin{proof}
+	Proof can be again found in \cite[lemma~7.1.4(b)]{hodges_1993}.
+  \end{proof}
+
   This lemma will play a major role in the later parts of the paper. Weak
   ultrahomogeneity is an easier and more intuitive property and it will prove
   useful when recursively constructing the generic automorphism of a Fraïssé 
   limit.
 
-  % \begin{fact} If $\bK$ is a uniformly locally finite Fraïssé class, then
-  % $\Flim(\bK)$ is $\aleph_0$-categorical and has quantifier elimination.
+  % \begin{fact} If $\cK$ is a uniformly locally finite Fraïssé class, then
+  % $\Flim(\cK)$ is $\aleph_0$-categorical and has quantifier elimination.
   % \end{fact}
 
   \subsection{Random graph} 
   
-  In this section we'll take a closer look on a class of finite unordered graphs, 
+  In this section we'll take a closer look on a class of finite undirected graphs, 
   which is a Fraïssé class. 
 
-  The language of unordered graphs $L$ consists of a single binary
+  The language of undirected graphs $L$ consists of a single binary
   relational symbol $E$. If $G$ is an $L$-structure then we call it a
   \emph{graph}, and its elements $\emph{vertices}$. If for some vertices 
   $u, v\in G$ we have $G\models uEv$ then we say that there is an $\emph{edge}$ 
   connecting $u$ and $v$. If $G\models \forall x\forall y (xEy\leftrightarrow yEx)$
-  then we say that $G$ is an \emph{unordered graph}. From now on we omit the word
-  \textit{unordered} and  graphs as unordered.
+  then we say that $G$ is an \emph{undirected graph}. From now on we omit the word
+  \textit{undirected} and consider only undirected graphs.
 
   \begin{proposition}
+	\label{proposition:finite-graphs-fraisse-class}
     Let $\cG$ be the class of all finite graphs. $\cG$ is a Fraïssé class.
   \end{proposition}
   \begin{proof}
@@ -141,9 +161,9 @@
     (graph substructure is also a graph). It has JEP: having two finite graphs 
     $G_1,G_2$ take their disjoint union $G_1\sqcup G_2$ as the extension of them
     both. $\cG$ has the AP. Having graphs $A, B, C$, where $B$ and $C$ are
-    supergraphs of $A$, we can assume without loss of generality, that 
+    supergraphs of $A$, we can assume without loss of generality that 
     $(B\setminus A) \cap (C\setminus A) = \emptyset$. Then 
-    $A\sqcup (B\setminus A)\sqcup (C\setminus A)$ is the graph we're looking
+    $A\sqcup (B\setminus A)\sqcup (C\setminus A)$ is the graph we are looking
     for (with edges as in B and C and without any edges between $B\setminus A$
 	and $C\setminus A$).
   \end{proof}
@@ -165,17 +185,19 @@
 
   \begin{fact}[random graph property]
 	For each finite disjoint $X, Y\subseteq \FrGr$ there exists $v\in\FrGr\setminus (X\cup Y)$
-    such that $\forall u\in X (vEu)$ and $\forall u\in Y (\neg vEu)$.
+    such that $\forall u\in X$ we have that $\FrGr\models vEu$ and 
+	$\forall u\in Y$ We have that $\FrGr\models \neg vEu$.
   \end{fact}
   \begin{proof}
     Take any finite disjoint $X, Y\subseteq\FrGr$. Let $G_{XY}$ be the
     subgraph of $\FrGr$ induced by the $X\cup Y$. Let $H = G_{XY}\cup \{w\}$,
     where $w$ is a new vertex that does not appear in $G_{XY}$. Also, $w$ is connected to 
     all vertices of $G_{XY}$ that come from $X$ and to none of those that come
-    from $Y$. This graph is of course finite, so it is embeddable in $\FrGr$.
-    Without loss of generality assume that this embedding is simply inclusion. 
-    Let $f$ be the partial isomorphism from $X\sqcup Y$ to $H$, with $X$ and
-    $Y$ projected to the part of $H$ that come from $X$ and $Y$ respectively. 
+    from $Y$. This graph is of course finite, so it is embeddable in $\FrGr$
+	by some $h\colon H\to \FrGr$.
+	Let $f$ be the partial isomorphism from $X\sqcup Y$ to $h[H]\subseteq\FrGr$, 
+	with $X$ and
+	$Y$ projected to the part of $h[H]$ that come from $X$ and $Y$ respectively. 
     By the ultrahomogeneity of $\FrGr$ this isomorphism extends to an automorphism
     $\sigma\in\Aut(\FrGr)$. Then $v = \sigma^{-1}(w)$ is the vertex we sought. 
   \end{proof}
@@ -189,7 +211,7 @@
     = \{b_1, b_2\ldots\}$.
     We will construct a chain of partial isomorphisms $f_n\colon \FrGr\to G$
     such that $\emptyset = f_0\subseteq f_1\subseteq f_2\subseteq\ldots$ and $a_n \in
-    \dom(f_n)$ and $b_n\in\rng(f_n)$.
+    \dom(f_n)$ and $b_n\in\rng(f_n)$ for each $n\in\bN$.
 
 	Suppose we have $f_n$. We seek $b\in G$ such that $f_n\cup \{\langle
     a_{n+1}, b\rangle\}$ is a partial isomorphism. 
@@ -212,10 +234,10 @@
   Using this fact one can show that the graph constructed in the probabilistic
   manner is in fact isomorphic to the random graph $\FrGr$.
 
-  \begin{definition} We say that a Fraïssé class $\bK$ has \emph{weak
-    Hrushovski property} (\emph{WHP}) if for every $A\in \bK$ and an isomorphism
+  \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$),
-	there is some $B\in \bK$ such 
+	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
     diagram commutes: 
@@ -232,20 +254,61 @@
     The class of finite graphs $\cG$ has the weak Hrushovski property. 
   \end{proposition}
 
-  \begin{proof}
-    It may be there some day, but it may not!
-  \end{proof}
+  The proof of this proposition can be done directly, in a combinatorial manner,
+  as shown in \cite{extending_iso_graphs}. Hrushovski has also shown 
+  in \cite{hrushovski_extending_iso} that
+  finite graphs have stronger property, where each graph can be extended 
+  to a supergraph so that every partial automorphism of the graph extend
+  to an automorphism of the supergraph.
+
+  Moreover, there is a theorem saying that every Fraïssé class $\cK$, in a
+  relational language $L$, with \emph{free amalgamation} (see the definition
+  \ref{definition:free_amalgamation} below) has WHP. The statement and
+  proof of this theorem can be found in 
+  \cite[theorem 3.2.8]{siniora2017automorphism}. We provide the definition
+  of free amalgamation that is coherent with the notions established 
+  in our paper.
+
+  \begin{definition}
+	\label{definition:free_amalgamation} 
+	Let $L$ be a relational language and $\cK$ a class of $L$-strucutres.
+	$\cK$ has \emph{free amalgamation} if for every
+	$A, B, C\in\cK$ such that $C = A\cap B$ the following diagram commutes:
+	\begin{center}
+	  \begin{tikzcd}
+		& A\sqcup B & \\
+		A \ar[ur, hook] & & B \ar[ul, hook'] \\
+		& C \ar[ur, hook] \ar[ul, hook'] & 
+	  \end{tikzcd}
+	\end{center}
+
+	$A\sqcup B$ here is an $L$-strcuture with domain $A\cup B$ such that
+	for every $n$-ary symbol $R$ from $L$, $n$-tuple $\bar{a}\subseteq A\cup B$,
+	we have that $A\sqcup B\models R(\bar{a})$ if and only if [$\bar{a}\subseteq A$ and
+	$A\models R(\bar{a})$] or [$\bar{a}\subseteq B$ and $B\models R(\bar{a})$].
+  \end{definition}
+
+  Actually we did already implicitly worked with free amalgamation in the 
+  proposition \ref{proposition:finite-graphs-fraisse-class}, showing that
+  the class of finite strcuture is indeed a Fraïssé class.
+
 
   \subsection{Canonical amalgamation}
 
+  Recall, $\Cospan(\cC)$, $\Pushout(\cC)$ are the categories of cospan
+  and pushout diagrams of the category $\cC$. We have also denoted the notion
+  of cospans and pushouts with a fixed base structure $C$ denoted
+  as $\Cospan_C(\cC)$ and $Pushout_C(\cC)$.
+
   \begin{definition}
-	Let $\bK$ be a class finitely generated $L$-structures. We say that
-	$\bK$ has \emph{canonical amalgamation} if for every $C\in\bK$ there
-	is a functor $\otimes_C\colon\Cospan(\bK)\to\Pushout(\bK)$ such that
+	\label{definition:canonical_amalgamation}
+	Let $\cK$ be a class finitely generated $L$-structures. We say that
+	$\cK$ has \emph{canonical amalgamation} if for every $C\in\cK$ there
+	is a functor $\otimes_C\colon\Cospan_C(\cK)\to\Pushout_C(\cK)$ such that
 	it has the following properties:
 	\begin{itemize}
 	  \item Let $A\leftarrow C\rightarrow B$ be a cospan. Then $\otimes_C$ sends
-		it to a pushout that preserves ``the bottom`` structures and embeddings, i.e.:
+		it to a pushout that preserves ``the bottom'' structures and embeddings, i.e.:
 		\begin{center}
 		  \begin{tikzcd}
 			& & 	 							& 		 & A\otimes_C B & \\
@@ -258,10 +321,9 @@
 	  the functor has to take them into account, but this abuse of notation
 	  is convenient and should not lead into confusion.
 	  \item Let $A\leftarrow C\rightarrow B$, $A'\leftarrow C\rightarrow B'$ be cospans
-		with a natural transformation given by $\alpha\colon A\to A', \beta\colon B\to B',
-		\gamma\colon C\to C$. Then $\otimes_C$ preserves the morphisms of
-		when sending the natural transformation of those cospans to natural
-		transformation of pushouts by adding the 
+		with a natural transformation $\eta$ given by $\alpha\colon A\to A', \beta\colon B\to B',
+		\gamma\colon C\to C$. Then $\otimes_C$ preserves the morphisms of $\eta$
+		when sending it to the natural transformation of pushouts by adding the 
 		$\delta\colon A\otimes_C B\to A'\otimes_C B'$ morphism:
 
 		\begin{center}
@@ -286,7 +348,7 @@
 
   \begin{theorem}
 	\label{theorem:canonical_amalgamation_thm}
-	Let $\bK$ be a Fraïssé class of $L$-structures with canonical amalgamation. 
+	Let $\cK$ be a Fraïssé class of $L$-structures with canonical amalgamation. 
 	Then the class $\cH$ of $L$-structures with automorphism is a Fraïssé class.
   \end{theorem}
 
@@ -328,7 +390,7 @@
   \end{proof}
 
   \subsection{Graphs with automorphism}
-  The language and theory of unordered graphs is fairly simple. We extend the
+  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.
@@ -350,21 +412,23 @@
     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's check the definition is correct. We have to show that 
+
+	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\quad\beta^{-1}(w)=\alpha^{-1}(w)\in A$,
+        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é for the class $\cH$ of finite
+  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.
 
@@ -401,9 +465,8 @@
 
   \begin{theorem}
 	\label{theorem:isomorphic_fr_lims}
-	Let $\cC$ be a Fraïssé class of finite structures in a relational language
-	$L$ of some theory $T$. Let $\cD$ be a class of finite structures of the
-	theory $T$ in a relational language $L$ with additional unary function 
+	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 the Fraïssé
 	limit of $\cC$ is isomorphic to the Fraïssé limit of $\cD$ reduced
@@ -413,15 +476,17 @@
   \begin{proof}
 	Let $\Gamma=\Flim(\cC)$ and $(\Pi, \sigma) =\Flim(\cD)$. By the Fraïssé 
 	theorem \ref{theorem:fraisse_thm} it suffices to show that the age of $\Pi$
-	is $\cC$ and that it has the weak ultrahomogeneity in the class $\cC$. The
+	is $\cC$ and that it is weakly ultrahomogeneous. The
 	former comes easily, as for every structure $A\in \cC$ we have the structure
 	$(A, \id_A)\in \cD$, which means that the structure $A$ embeds into $\Pi$.
-	Also, if a structure $(B, \beta)\in\cD$ embeds into $\cD$, then $B\in\cC$.
+	On the other hand, if a structure $(B, \beta)\in\cD$ embeds into 
+	$(\Pi, \sigma)$, then obviously $B\in\cC$ by the definition of $\cD$.
 	Hence, $\cC$ is indeed the age of $\Pi$.
 
-	Now, take any structure $A, B\in\cC$ such that $A\subseteq B$. Without the
-	loss of generality assume that $A = B\cap \Pi$. Let $\bar{A}$ be the
-	smallest structure closed on the automorphism $\sigma$ and containing $A$.
+	Now, take any structures $A, B\in\cC$ such that $A\subseteq B$. Without the
+	loss of generality assume that $A = B\cap \Pi$. Let $\bar{A}\subseteq\Pi$ 
+	be the
+	smallest structure closed under the automorphism $\sigma$ and containing $A$.
 	It is finite, as $\cC$ is the age of $\Pi$. By the weak Hrushovski property,
 	of $\cC$ let $(\bar{B}, \beta)$ be a structure extending 
 	$(B\cup \bar{A}, \sigma\upharpoonright_{\bar{A}})$. Again, we may assume