path: root/sections/fraisse_classes.tex

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

\begin{document}
  In this section we will take a closer look at classes of finitely
  generated structures with some characteristic properties. More
  specifically, we will describe a concept developed by a French
  mathematician Roland Fraïssé called Fraïssé limit.

  \subsection{Definitions} 
  \begin{definition}
    Let $L$ be a signature and $M$ be an $L$-structure. The \emph{age} of $M$ is
    the class $\cC$ of all finitely generated structures that embed into $M$.
    The age of $M$ is also associated with class of all finitely generated
	structures embeddable in $M$ \emph{up to isomorphism}.
  \end{definition}

  \begin{definition}
	We say that a class $\cC$ of finitely generated structures 
	is \emph{essentially countable} if it has countably many isomorphism types
	of finitely generated structures.
  \end{definition}

  \begin{definition}
    Let $\cC$ be a class of finitely generated structures. $\cC$ has the
    \emph{hereditary property (HP)} if for any $A\in\cC$ and any finitely 
	generated substructure $B$ of $A$ it holds that $B\in\cC$. 
  \end{definition}

  \begin{definition}
    Let $\cC$ be a class of finitely generated structures. We say that $\cC$ has
	the \emph{joint embedding property (JEP)} if for any $A, B\in\cC$ there is 
	a structure $C\in\cC$ such that both $A$ and $B$ embed in $C$.

    \begin{center}
      \begin{tikzcd}
                                  & C & \\
        A \arrow[ur, dashed, "f"] &   & B \arrow[ul, dashed, "g"'] 
	  \end{tikzcd}
    \end{center}
  \end{definition}

  In terms of category theory we may say that $\cC$ is a category of finitely
  generated structures where morphisms are embeddings of those structures.
  Then the above diagram is a \emph{span} diagram in category $\cC$. 

  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 $\cC$ is a nonempty essentially countable set 
    of finitely generated $L$-structures. Then $\cC$ has the HP and JEP if
    and only if $\cC$ 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 $\cC$, namely the amalgamation property.

  \begin{definition}
    Let $\cC$ be a class of finitely generated $L$-structures. We say that $\cC$
    has the \emph{amalgamation property (AP)} if for any $A, B, C\in\cC$ and
    embeddings $e\colon C\to A, f\colon C\to B$ there exists $D\in\cC$ together
    with embeddings $g\colon A\to D$ and $h\colon B\to D$ such that 
    $g\circ e = h\circ f$.
    \begin{center}
      \begin{tikzcd}
                                  & D & \\
        A \arrow[ur, dashed, "g"] &   & B \arrow[ul, dashed, "h"'] \\
								  & C \arrow[ur, "f"'] \arrow[ul, "e"] & 
      \end{tikzcd}
    \end{center}
  \end{definition}

  In terms of category theory, $\cC$ has the amalgamation property if every
  cospan diagram can be extended to a pushout diagram in category $\cC$.
  We will get into more details later, in the definition of canonical 
  amalgamation \ref{definition:canonical_amalgamation}.

  \begin{definition}
	Class $\cC$ of finitely generated structures 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
    isomorphism between finitely generated substructures of $M$ extends to an
    automorphism of $M$.
  \end{definition}

  Having those definitions we can provide the main Fraïssé theorem.

  \begin{theorem}[Fraïssé theorem]
    \label{theorem:fraisse_thm}
    Let L be a countable language and let $\cC$ be a nonempty countable set of
    finitely generated $L$-structures which has HP, JEP and AP. Then $\cC$ 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 $\cC$
    and denote this by $M = \Flim(\cC)$.
  \end{theorem}

  \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
    an embedding $f\colon A\to M$ there is an embedding $g\colon B\to M$ which
    extends $f$.
    \begin{center}
      \begin{tikzcd}
        A \arrow[d, "\subseteq"'] \arrow[r, "f"] & D \\
        B \arrow[ur, dashed, "g"']
      \end{tikzcd}
    \end{center}
  \end{definition}

  \begin{lemma}
    \label{lemma:weak_ultrahom}
    A countable structure is ultrahomogeneous if and only if it is weakly
    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 $\cC$ is a uniformly locally finite Fraïssé class, then
  % $\Flim(\cC)$ 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 undirected graphs, 
  which is a Fraïssé class. 

  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{undirected graph}. From now on we 
  consider only undirected graphs and omit the word \textit{undirected}.

  \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}
    $\cG$ is of course countable (up to isomorphism) and has the HP 
    (substructure of a graph 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 
    $B\cap C = A$. Then 
    $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}

  \begin{definition}
	\label{definition:random_graph}
    The \emph{random graph} is the Fraïssé limit of the class of finite graphs
    $\cG$ denoted by $\FrGr = \Flim(\cG)$.
  \end{definition}

  The concept of the random graph emerges independently in many fields of
  mathematics. For example, one can construct the graph by choosing at random
  for each pair of vertices if they should be connected or not. It turns out
  that the graph constructed this way is isomorphic to the random graph with
  probability 1.

  The random graph $\FrGr$ has one particular property that is unique to the
  random graph.

  \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$ 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$
	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}

  \begin{fact}
    If a countable graph $G$ has the random graph property, then it is
    isomorphic to the random graph $\FrGr$.
  \end{fact}
  \begin{proof}
    Enumerate vertices of both graphs: $\FrGr = \{a_1, a_2\ldots\}$ and $G
    = \{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)$ 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. 
    If $a_{n+1}\in\dom{f_n}$, then simply $b = f_n(a_{n+1})$. Otherwise,
	let $X = \{a\in\dom{f_n}\mid
    aE_{\FrGr} a_{n+1}\}, Y = \dom{f_n}\setminus X$, i.e. $X$ are
    vertices of $\dom{f_n}$ that are connected with $a_{n+1}$ in $\FrGr$ and
    $Y$ are those vertices that are not connected with $a_{n+1}$. Let $b$ be
    a vertex of $G$ that is connected to all vertices of $f_n[X]$ and to none
    $f_n[Y]$ (it exists by the random graph property). Then $f_n\cup \{\langle
    a_{n+1}, b\rangle\}$ is a partial isomorphism. We find $a$ for the
    $b_{n+1}$ in the similar manner, so that $f_{n+1} = f_n\cup \{\langle
    a_{n+1}, b\rangle, \langle a, b_{n+1}\rangle\}$ is a partial isomorphism.

    Finally, $f = \bigcup^{\infty}_{n=0}f_n$ is an isomorphism between $\FrGr$
    and $G$. Take any $a, b\in \FrGr$. Then for some big enough $n$ we have
    that $aE_{\FrGr}b\Leftrightarrow f_n(a)E_{G}f_n(b) \Leftrightarrow f(a)E_{G}f(b)$.
  \end{proof}

  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 $\cC$ has the \emph{weak
    Hrushovski property} (\emph{WHP}) if for every $A\in \cC$ and an isomorphism
	of its finitely generated substructures 
	$p\colon A\to A$ (also called a partial automorphism of $A$),
	there is some $B\in \cC$ 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: 
    \begin{center} 
      \begin{tikzcd} 
        B\ar[r,dashed,"\bar p"]&B\\
        A\ar[u,dashed,"i"]\ar[r,"p"]&A\ar[u,dashed,"i"] 
      \end{tikzcd} 
    \end{center}
  \end{definition}

  \begin{proposition}
    \label{proposition:finite-graphs-whp}
    The class of finite graphs $\cG$ has the weak Hrushovski property. 
  \end{proposition}

  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 $\cC$, 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 $\cC$ a class of $L$-structures.
	$\cC$ has \emph{free amalgamation} if for every
	$A, B, C\in\cC$ such that $C = A\cap B$ the following diagram commutes:
	\begin{center}
	  \begin{tikzcd}
		& A\sqcup_C B & \\
		A \ar[ur, hook] & & B \ar[ul, hook'] \\
		& C \ar[ur, hook] \ar[ul, hook'] & 
	  \end{tikzcd}
	\end{center}
	and $A\sqcup_C B\in\cC$.
	$A\sqcup_C B$ here is an $L$-structure 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_C 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 work with free amalgamation in the 
  Proposition \ref{proposition:finite-graphs-fraisse-class}, showing that
  the class of finite graphs is indeed a Fraïssé class.

  \vspace{3cm}

  \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}
	\label{definition:canonical_amalgamation}
	Let $\cC$ be a class of finitely generated $L$-structures. We say that
	$\cC$ has \emph{canonical amalgamation} if for every $C\in\cC$ there
	is a functor $\otimes_C\colon\Cospan_C(\cC)\to\Pushout_C(\cC)$ with
	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.:
		\begin{center}
		  \begin{tikzcd}
			& & 	 							& 		 & A\otimes_C B & \\
			A & & B  \arrow[r, dashed, "A\otimes_C B"] & A \arrow[ur, dashed] & & B \arrow[ul, dashed] \\
			& C \arrow[ul] \arrow[ur]  & & & C \arrow[ul] \arrow[ur] &
		  \end{tikzcd}
		\end{center}

	  We have deliberately omitted names for embeddings of $C$. Of course, 
	  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 $\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}
		  \begin{tikzcd}
			& A'\otimes_C B' & \\
			A' \arrow[ur] & & B' \arrow[ul] \\
			& A\otimes_C B  \ar[uu, dashed, "\delta"] & \\
			& C \arrow[uul, bend left] \arrow[uur, bend right] & \\
			A \arrow[uuu, dashed, "\alpha"] \arrow[uur, bend left, crossing over] & & B \arrow[uuu, dashed, "\beta"'] \arrow[uul, bend right, crossing over] \\
			& C \arrow[ur] \arrow[ul] \arrow[uu, dashed, "\gamma"] & \\ 
		  \end{tikzcd}
		\end{center}
		% \begin{center}
		%   \begin{tikzcd}
			% & A \ar[rrr, dashed, "\alpha"] \ar[drr, bend left=20, crossing over] & & & A' \ar[dr] & \\
			% C \ar[rr, dashed, "\gamma"] \ar[ur] \ar[dr] & & C \ar[rrd, bend right=20] \ar[rru, bend left=20] & A\otimes_C B \ar[rr, dashed, "\delta"] & & A' \otimes_C B' \\
			% & B \ar[rrr, dashed, "\beta"] \ar[urr, bend right=20, crossing over] & & & B' \ar[ur] & \\
		%   \end{tikzcd}
		% \end{center}
	\end{itemize}
  \end{definition}

  \begin{remark}
	Free amalgamation is canonical.
  \end{remark}

  From now on in the paper, when $A$ is an $L$-structure and $\alpha$ is 
  an automorphism of
  $A$, then by $(A, \alpha)$ we mean the structure $A$ expanded by the
  unary function corresponding to $\alpha$, and $A$ constantly denotes the
  $L$-structure.

  \begin{theorem}
	\label{theorem:canonical_amalgamation_thm}
	Let $\cC$ be a Fraïssé class of $L$-structures with canonical amalgamation. 
	Then the class $\cD$ of $L$-structures with automorphism is a Fraïssé class.
  \end{theorem}

  \begin{proof}
	$\cD$ is obviously countable and has HP. It suffices to show that it
	has AP (JEP follows by taking $C$ to be the empty structure). Take any
	$(A,\alpha), (B,\beta), (C,\gamma)\in \cD$ such that $(C,\gamma)$ embeds
	into $(A,\alpha)$ and $(B,\beta)$. Then $\alpha, \beta, \gamma$ yield
	an automorphism $\eta$ (as a natural transformation, see \ref{fact:natural-automorphism}) 
	of a cospan:
	\begin{center}
	  \begin{tikzcd}
		A & & B \\
		% & C \ar[ur] \ar[ul] & \\
		A \ar[u, dashed, "\alpha"] & C \ar[ur] \ar[ul] & B \ar[u, dashed, "\beta"'] \\
		& C \ar[ur] \ar[ul] \ar[u, dashed, "\gamma"] &
		% (A, \alpha) & & (B, \beta) \\
		% & (C, \gamma) \ar[ur] \ar[ul] &
	  \end{tikzcd}
	\end{center}
	
	Then, by the Fact \ref{fact:functor_iso}, $\otimes_C(\eta)$ is an automorphism
	of the pushout diagram that looks exactly like the diagram in the second
	point of the Definition \ref{definition:canonical_amalgamation}.
	This means that the morphism $\delta\colon A\otimes_C B\to A\otimes_C B$
	has to be automorphism. Thus, by the fact that the diagram commutes, 
	we have the amalgamation of $(A, \alpha)$ and $(B, \beta)$ over $(C,\gamma)$ 
	in $\cD$.
  \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}
	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
	to the language $L$.
  \end{theorem}

  \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 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$.
	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, to show that $\Pi$ is weakly ultrahomogeneous, 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$ (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, 
	as $\cC$ is the age	of $\Pi$. 
	Let $C$ be a finitely generated structure such that 
	$\bar{A}\rightarrow C \leftarrow B$. Such structure exists by the JEP
	of $\cC$. Again, we may assume without the loss of generality that
	$\bar{A}\subseteq C$. Then $\sigma\upharpoonright_{\bar{A}}$ is a
	partial automorphism of $C$, hence by the WHP it can be extended to
	a structure $(\bar{C}, \gamma)\in\cD$ such that 
	$\gamma\upharpoonright_{\bar{A}} = \sigma\upharpoonright_{\bar{A}}$.

	Then, by the weak ultrahomogeneity of $(\Pi, \sigma)$ we can find an
	embedding $g$ of $(\bar{C},\gamma)$ such that the following diagram commutes:

	\begin{center}
	  \begin{tikzcd}
		(\bar{A}, \sigma\upharpoonright_{\bar{A}}) \ar[d, "\subseteq"] \ar[r, "\subseteq"] & (\Pi, \sigma) \\
		(\bar{C}, \gamma) \ar[ur, "g"'] &
	  \end{tikzcd}
	\end{center}


	Thus, we have that the following diagram commutes:

	\begin{center}
	  \begin{tikzcd}
		A \ar[r, "\subseteq"] \ar[d, "\subseteq"] & \bar{A} \ar[r, "\subseteq"] \ar[d, "\subseteq"] & \Pi \\
		B \ar[r, "f"] & C \ar[r, "\subseteq"] & \bar{C} \ar[u, "g"] \\
	  \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,\sigma) = \Flim(\cD)$.
	Then $\Gamma \cong \Pi$.
  \end{corollary}

  \begin{proof}
	It follows from Theorems \ref{theorem:canonical_amalgamation_thm} and
	\ref{theorem:isomorphic_fr_lims}.
  \end{proof}
\end{document}