Teoria kategorii, kanoniczna amalgamacja

1 files changed, 121 insertions, 8 deletions

diff --git a/lic_malinka.tex b/lic_malinka.tex
index bc4d53b..6672e83 100644
--- a/lic_malinka.tex
+++ b/lic_malinka.tex
@@ -3,7 +3,7 @@
 

 \usepackage[utf8]{inputenc}

 \usepackage[backend=biber]{biblatex}

-\addbibresource{lic_malinka.bib}

+\addbibresource{licmalinka.bib}

 

 \usepackage[T1]{fontenc} 

 \usepackage{mathtools}

@@ -67,6 +67,8 @@
 \DeclareMathOperator{\lin}{{Lin}}

 \DeclareMathOperator{\Th}{{Th}}

 \DeclareMathOperator{\Obj}{{Obj}}

+\DeclareMathOperator{\Cospan}{{Cospan}}

+\DeclareMathOperator{\Pushout}{{Pushout}}

 \DeclareMathOperator{\Mor}{{Mor}}

 

 \newtheorem{theorem}{Theorem} 

@@ -374,13 +376,18 @@
   \emph{identity morphism} $\id_A$ such that for any morphism $f\in \Mor(A, B)$

   it follows that $f\circ id_A = \id_B \circ f$.

 

-  A \emph{functor} is a ``homeomorphism`` of categories. $F\colon\cC\to\cD$ is a functor

+  A \emph{functor} is a ``homeomorphism`` of categories. We say that 

+  $F\colon\cC\to\cD$ is a functor

   from category $\cC$ to category $\cD$ if it associates each object $A\in\cC$

   with an object $F(A)\in\cD$, associates each morphism $f\colon A\to B$ in

   $\cC$ with a morphism $F(f)\colon F(A)\to F(B)$. We also require that 

   $F(\id_A) = \id_{F(A)}$ and that for any (compatible) morphisms $f, g$ in $\cC$

   $F(f\circ g) = F(f) \circ F(g)$.

 

+  In category theory we distinguish \emph{covariant} and \emph{contravariant}

+  functors. Here, we only consider \emph{covariant functors}, so we will simply

+  say \emph{functor}.

+

   Notion that will be very important for us is a ``morphism of functors``

   which is called \emph{natural transformation}.

   \begin{definition}

@@ -397,7 +404,53 @@
       \end{tikzcd}

     \end{center}

   \end{definition}

-  

+

+  \begin{definition}

+	In category theory, a \emph{diagram} of type $\mathcal{J}$ in category $\cC$

+	is a functor $D\colon \mathcal{J}\to\cC$. $\mathcal{J}$ is called the

+	\emph{index category} of $D$. In other words, $D$ is of \emph{shape} $\mathcal{J}$.

+

+	For example, $\mathcal{J} = \{-1\leftarrow 0 \rightarrow 1\}$, then a diagram

+	$D\colon\mathcal{J}\to \cC$ is called a \emph{cospan}. For example,

+	if $A, B, C$ are objects of $\cC$ and $f\in\Mor(C, A), g\in\Mor(C, B)$, then

+	the following diagram is a cospan:

+

+    \begin{center}

+      \begin{tikzcd}

+		A &  & B \\

+		& C \arrow[ur, "g"'] \arrow[ul, "f"] &

+      \end{tikzcd}

+    \end{center}

+  \end{definition}

+

+  From now we omit explicit definition of the index category, as it is easily

+  referable from a picture.

+

+  \begin{definition}

+	Let $A, B, C, D$ be objects in the category $\cC$ with morphisms

+	$e\colon C\to A, f\colon C\to B, g\colon A\to D, h\colon B\to D$ such

+	that $g\circ e = h\circ f$.

+	Then the following diagram:

+    \begin{center}

+      \begin{tikzcd}

+		& D & \\

+		A \arrow[ur, "g"] &  & B \arrow[ul, "h"'] \\

+		& C \arrow[ur, "e"'] \arrow[ul, "f"] &

+      \end{tikzcd}

+    \end{center}

+	

+	is called a \emph{pushout} diagram 

+  \end{definition}

+

+  \begin{definition}

+	The \emph{cospan category} of category $\cC$, refered to as $\Cospan(\cC)$,

+	is the category of cospan diagrams of $\cC$, where morphisms between

+	two cospans are normal transformations of the underlying functors.

+

+	We define \emph{pushout category} analogously and call it $\Pushout(\cC)$.

+  \end{definition}

+

+  TODO: dodać tu przykład?

 

   \section{Fraïssé classes}

 

@@ -429,6 +482,15 @@
     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 

@@ -447,18 +509,21 @@
   \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 $f\colon A\to B, g\colon A\to C$ there exists $D\in\bK$ together

-    with embeddings $h\colon B\to D$ and $j\colon C\to D$ such that 

-    $h\circ f = j\circ g$.

+    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 & \\

-        B \arrow[ur, dashed, "h"] &   & C \arrow[ul, dashed, "j"'] \\

-                                  & A \arrow[ur, "g"'] \arrow[ul, "f"]

+        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

@@ -623,6 +688,53 @@
     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}

+	\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}

+

   \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

@@ -694,6 +806,7 @@
     $\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