diff options
Diffstat (limited to 'sections/fraisse_classes.tex')
| -rw-r--r-- | sections/fraisse_classes.tex | 207 |
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 |