diff options
Diffstat (limited to 'sections/fraisse_classes.tex')
| -rw-r--r-- | sections/fraisse_classes.tex | 451 |
1 files changed, 451 insertions, 0 deletions
diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex new file mode 100644 index 0000000..ca2247e --- /dev/null +++ b/sections/fraisse_classes.tex @@ -0,0 +1,451 @@ +\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 embeds 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} + 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 omited 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$ embedds into $\Pi$. + Also, if a structure $(B, \beta)\in\cD$ embedds 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 containg $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} |