From cc29818ac950b734bba958c35ba1057cc6a73476 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 28 Jun 2022 21:36:53 +0200 Subject: Teoria kategorii, kanoniczna amalgamacja --- lic_malinka.tex | 129 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 121 insertions(+), 8 deletions(-) (limited to 'lic_malinka.tex') 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 -- cgit v1.2.3