diff options
Diffstat (limited to 'sections/fraisse_classes.tex')
| -rw-r--r-- | sections/fraisse_classes.tex | 119 |
1 files changed, 60 insertions, 59 deletions
diff --git a/sections/fraisse_classes.tex b/sections/fraisse_classes.tex index 1126dee..885eb81 100644 --- a/sections/fraisse_classes.tex +++ b/sections/fraisse_classes.tex @@ -9,27 +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 $\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}. + 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 $\cK$ of finitely generated structures + 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 $\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$. + 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 $\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$. + 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} @@ -39,18 +39,18 @@ \end{center} \end{definition} - In terms of category theory we may say that $\cK$ is a category of finitely + 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 $\cK$. + 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 $\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. + 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} @@ -59,13 +59,13 @@ \end{proof} Beside the HP and JEP Fraïssé has distinguished one more property of the - class $\cK$, namely the amalgamation property. + class $\cC$, namely the amalgamation property. \begin{definition} - 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 + 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} @@ -76,13 +76,13 @@ \end{center} \end{definition} - In terms of category theory, $\cK$ has the amalgamation property if every - cospan diagram can be extended to a pushout diagram in category $\cK$. + 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 $\cK$ of finitely generated structure is a \emph{Fraïssé class} + Class $\cC$ of finitely generated structures is a \emph{Fraïssé class} if it is essentially countable, has HP, JEP and AP. \end{definition} @@ -96,11 +96,11 @@ \begin{theorem}[Fraïssé theorem] \label{theorem:fraisse_thm} - 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 + 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 $\cK$ - and denote this by $M = \Flim(\cK)$. + 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} @@ -135,8 +135,8 @@ useful when recursively constructing the generic automorphism of a Fraïssé limit. - % \begin{fact} If $\cK$ is a uniformly locally finite Fraïssé class, then - % $\Flim(\cK)$ is $\aleph_0$-categorical and has quantifier elimination. + % \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} @@ -149,8 +149,8 @@ \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 omit the word - \textit{undirected} and consider only undirected graphs. + 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} @@ -158,11 +158,11 @@ \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 + (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\setminus A) \cap (C\setminus A) = \emptyset$. Then + $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$). @@ -183,10 +183,10 @@ The random graph $\FrGr$ has one particular property that is unique to the random graph. - \begin{fact}[random graph property] + \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$. + $\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 @@ -216,8 +216,8 @@ 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 + 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 @@ -234,11 +234,11 @@ 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 $\cK$ has the \emph{weak - Hrushovski property} (\emph{WHP}) if for every $A\in \cK$ and an isomorphism + \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 \cK$ such + 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: @@ -262,7 +262,7 @@ 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 + 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 @@ -272,9 +272,9 @@ \begin{definition} \label{definition:free_amalgamation} - Let $L$ be a relational language and $\cK$ a class of $L$-structures. - $\cK$ has \emph{free amalgamation} if for every - $A, B, C\in\cK$ such that $C = A\cap B$ the following diagram commutes: + 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 & \\ @@ -282,7 +282,6 @@ & 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$, @@ -294,6 +293,8 @@ 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 @@ -303,10 +304,10 @@ \begin{definition} \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: + 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.: @@ -359,16 +360,17 @@ \begin{theorem} \label{theorem:canonical_amalgamation_thm} - 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. + 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} - $\cH$ is obviously countable and has HP. It suffices to show that it + $\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 \cH$ such that $(C,\gamma)$ embeds + $(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) of a cospan: + an automorphism $\eta$ (as a natural transformation, see \ref{fact:natural-automorphism}) + of a cospan: \begin{center} \begin{tikzcd} A & & B \\ @@ -383,11 +385,10 @@ 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 $\cH$. + in $\cD$. \end{proof} The following theorem is one of the most important in construction of @@ -416,7 +417,7 @@ $(\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 homogeneous, take any structures $A, B\in\cC$ + 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$ @@ -462,8 +463,8 @@ 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 = \Flim(\cD)$. - Then $\Gamma \cong \Pi\mid_L$. + automorphism. Let $\Gamma = \Flim(\cC)$ and $(\Pi,\sigma) = \Flim(\cD)$. + Then $\Gamma \cong \Pi$. \end{corollary} \begin{proof} |