aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2022-06-28 21:36:53 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2022-06-28 21:36:53 +0200
commitcc29818ac950b734bba958c35ba1057cc6a73476 (patch)
tree6ee2530753adea32959cb1a8309d63339b94bc62
parent8c3772288630df347539eadde88dc22cc4ef2af0 (diff)
Teoria kategorii, kanoniczna amalgamacja
-rw-r--r--lic_malinka.pdfbin404331 -> 415528 bytes
-rw-r--r--lic_malinka.tex129
-rw-r--r--licmalinka.bib (renamed from lic_malinka.bib)2
3 files changed, 122 insertions, 9 deletions
diff --git a/lic_malinka.pdf b/lic_malinka.pdf
index a584720..0e26d72 100644
--- a/lic_malinka.pdf
+++ b/lic_malinka.pdf
Binary files differ
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
diff --git a/lic_malinka.bib b/licmalinka.bib
index 34451a7..e4c4143 100644
--- a/lic_malinka.bib
+++ b/licmalinka.bib
@@ -7,7 +7,7 @@
author={Hodges, Wilfrid},
year={1993},
collection={Encyclopedia of Mathematics and its Applications}
-}
+},
@book{maclane_1978,
title={Categories for the Working Mathematics},
DOI={10.1007/978-1-4757-4721-8},