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 $\bK$ 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. 
  \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$. 
  \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$.

    \begin{center}
      \begin{tikzcd}
                                  & C & \\
        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 
  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. 
  \end{fact}

  Beside the HP and JEP Fraïssé has distinguished one more property of the 
  class $\bK$, namely 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
    with embeddings $g\colon A\to D$ and $h\colon A\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, amalgamation over some structure $C$ is a
  pushout diagram.

  \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 $\bK$ be a nonempty countable set of
    finitely generated $L$-structures which has HP, JEP and AP. Then $\bK$ 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)$.
  \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{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}

  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.
  % \end{fact}

  \subsection{Random graph} 
  
  In this section we'll take a closer look on a class of finite unordered graphs, 
  which is a Fraïssé class. 

  The language of unordered 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.

  \begin{proposition}
    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 
    (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 
    $(B\setminus A) \cap (C\setminus A) = \emptyset$. Then 
    $A\sqcup (B\setminus A)\sqcup (C\setminus A)$ is the graph we're 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 (vEu)$ and $\forall u\in Y (\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. 
    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)$.

	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\FrGr\mid
    aE_{\FrGr} a_{n+1}\}\cap \dom{f_n}, Y = X^{c}\cap \dom{f_n}$, 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 $\bK$ has \emph{weak
    Hrushovski property} (\emph{WHP}) if for every $A\in \bK$ 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 
    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}

  \begin{proof}
    It may be there some day, but it may not!
  \end{proof}

  \subsection{Canonical amalgamation}

  \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
	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.:
		\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 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 
		$\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{theorem}
	\label{theorem:canonical_amalgamation_thm}
	Let $\bK$ 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}

  \begin{proof}
	$\cH$ 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 \cH$ such that $(C,\gamma)$ embeds
	into $(A,\alpha)$ and $(B,\beta)$. Then $\alpha, \beta, \gamma$ yield
	an automorphism $\eta$ (as a natural transformation) 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:
	
	\begin{center}
	  \begin{tikzcd}
		& A\otimes_C B \ar[loop above, "\delta"] & \\
		A \ar[ur] \ar[loop left, "\alpha"]& & B \ar[ul] \ar[loop right, "\beta"]\\
		& C \ar[ur] \ar[ul] \ar[loop below, "\gamma"] & 
	  \end{tikzcd}
	\end{center}
	
	TODO: ten diagram nie jest do końca taki jak trzeba, trzeba w zasadzie skopiować
	ten z definicji kanonicznej amalgamcji. Czy to nie będzie wyglądać źle?

	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 $\cH$.
  \end{proof}

  \subsection{Graphs with automorphism}
  The language and theory of unordered 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's check 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$,
        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
  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}


  \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 
	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 has the weak ultrahomogeneity in the class $\cC$. 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$.
	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$.
	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 
	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 in $\cC$.
	Hence, it is isomorphic to $\Gamma$.
  \end{proof}
\end{document}