From ef3fc25228cc13c9f39192813653b1b6dc339406 Mon Sep 17 00:00:00 2001
From: Franciszek Malinka <franciszek.malinka@gmail.com>
Date: Sun, 17 Jul 2022 23:22:37 +0200
Subject: Szkola orlow finish!

---
 sections/fraisse_classes.tex | 119 ++++++++++++++++++++++---------------------
 1 file changed, 60 insertions(+), 59 deletions(-)

(limited to 'sections/fraisse_classes.tex')

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}
-- 
cgit v1.2.3

