diff options
| -rw-r--r-- | lic_malinka.pdf | bin | 480503 -> 479056 bytes | |||
| -rw-r--r-- | lic_malinka.tex | 2 | ||||
| -rw-r--r-- | sections/conj_classes.tex | 47 | ||||
| -rw-r--r-- | sections/fraisse_classes.tex | 119 | ||||
| -rw-r--r-- | sections/preliminaries.tex | 1 |
5 files changed, 81 insertions, 88 deletions
diff --git a/lic_malinka.pdf b/lic_malinka.pdf Binary files differindex a61d98f..3725a5b 100644 --- a/lic_malinka.pdf +++ b/lic_malinka.pdf diff --git a/lic_malinka.tex b/lic_malinka.tex index 7e9fb07..6cfaac4 100644 --- a/lic_malinka.tex +++ b/lic_malinka.tex @@ -83,6 +83,7 @@ \newtheorem{axiom}[theorem]{Axiom}
\newtheorem{question}[theorem]{Question}
\newtheorem{corollary}[theorem]{Corollary}
+\newtheorem{remark}[theorem]{Remark}
\newtheorem*{theorem2}{Theorem}
\newtheorem*{claim2}{Claim}
\newtheorem*{corollary2}{Corollary}
@@ -97,7 +98,6 @@ \newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
-\newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark2}{Remark}
diff --git a/sections/conj_classes.tex b/sections/conj_classes.tex index 9ec4b0c..d37afd5 100644 --- a/sections/conj_classes.tex +++ b/sections/conj_classes.tex @@ -90,19 +90,11 @@ automorphism group of the $\Flim(\cC)$. \end{theorem} - Before we get to the proof, let us establish some notions. If - $g\colon\Gamma\to\Gamma$ is a finite injective function, then we say that - $g$ is \emph{good} if it gives (in a natural way) an isomorphism between - $\langle \dom(g)\rangle$ and $\langle\rng(g)\rangle$, i.e. substructures - generated by $\dom(g)$ and $\rng(g)$ respectively. Of course, in our - case, $g$ is good - if and only if $[g]_{\Aut(\Gamma)} \neq\emptyset$ (because of ultrahomogeneity - of $\Gamma$). - - Also it is important to mention that an isomorphism between two finitely + Before we get to the proof, it is important to mention that an isomorphism + between two finitely generated structures is uniquely given by a map from generators of one structure to the other. This allow us to treat a finite function as an isomorphism - of finitely generated structures. + of finitely generated structures (if it yields one) and \textit{vice versa}. \begin{proof} Let $\Gamma = \Flim(\cC)$ and $(\Pi, \sigma) = \Flim(\cD)$. First, by the Theorem @@ -115,16 +107,17 @@ By the Banach-Mazur theorem (see \ref{theorem:banach_mazur_thm}) this will prove that this class is comeagre. - Recall, $G$ has a basis consisting of open + Recall, $G$ has a basis consisting of sets $\{g\in G\mid g\upharpoonright_A = g_0\upharpoonright_A\}$ for some finite set $A\subseteq \Gamma$ and some automorphism $g_0\in G$. In other - words, a basic open set is a set of all extensions of some finite partial - automorphism $g_0$ of $\Gamma$. By $B_{g}\subseteq G$ we denote a basic - open subset given by a finite partial isomorphism $g$. Again, Note that $B_g$ + words, a basic open set is a set of all extensions of some partial + automorphism $g_0$ of finitely generated substructures of $\Gamma$. + By $B_{g}\subseteq G$ we denote a basic + open subset given by a partial isomorphism $g$. Again, Note that $B_g$ is nonempty because of ultrahomogeneity of $\Gamma$. With the use of Corollary \ref{corollary:banach-mazur-basis} we can consider - only games where both players choose finite partial isomorphisms. Namely, + only games where both players choose partial isomorphisms. Namely, player \textit{I} picks functions $f_0, f_1,\ldots$ and player \textit{II} chooses $g_0, g_1,\ldots$ such that $f_0\subseteq g_0\subseteq f_1\subseteq g_1\subseteq\ldots$, which identify @@ -144,20 +137,18 @@ For technical reasons, let $g_{-1} = \emptyset$ and $X_{-1} = \emptyset$. Enumerate the elements of the Fraïssé limit $\Gamma = \{v_0, v_1, \ldots\}$. - Suppose that player \textit{I} in the $n$-th move chooses a finite partial - automorphism $f_n$. We will construct a finite partial automorphism + Suppose that player \textit{I} in the $n$-th move chooses a partial + automorphism $f_n$. We will construct a partial automorphism $g_n\supseteq f_n$ together with a finitely generated substructure $\Gamma_n \subseteq \Gamma$ and a set $X_n\subseteq\bN^2$ such that the following properties hold: \begin{enumerate}[label=(\roman*)] - \item $g_n$ is good and - $\dom(g_n)\cup\rng(g_n)\subseteq\langle\dom(g_n)\rangle = \Gamma_n$, - i.e. $g_n$ gives an automorphism of a finitely generated - substructure $\Gamma_n$ - \item $g_n(v_n)$ and $g_n^{-1}(v_n)$ are defined, - + \item $g_n$ is is a partial automorphism of $\Gamma$ and an automorphism of + finitely generated substructure $\Gamma_n$, + \item $g_n(v_n)$ and $g_n^{-1}(v_n)$ are defined. \end{enumerate} + Before we give the third point, suppose recursively that $g_{n-1}$ already satisfy all those properties. Let us enumerate $\{\langle (A_{n,k}, \alpha_{n, k}), (B_{n,k}, \beta_{n,k}), f_{n, k}\rangle\}_{k\in\bN}$ @@ -166,14 +157,14 @@ $(A_{n,k}, \alpha_{n,k})\subseteq (B_{n,k}, \beta_{n,k})$, and $f_{n,k}$ is an embedding of $(A_{n,k}, \alpha_{n,k})$ in the $(\FrGr_{n-1}, g_{n-1})$. We allow $A_{n,k}$ to be empty. Although $g_{n-1}$ is a finite function, - we may treat it as an automorphism as we have said before. + we may treat it as a partial automorphism as we have said before. \begin{enumerate}[resume, label=(\roman*)] \item Let - $(i, j) = \min\{(\{0, 1, \ldots\} \times \bN) \setminus X_{n-1}\}$ (with the + $(i, j) = \min\{(\{0, 1, \ldots, n\} \times \bN) \setminus X_{n-1}\}$ (with the order induced by $\gamma$). Then $X_n = X_{n-1}\cup\{(i,j)\}$ and - $(B_{n,k}, \beta_{n,k})$ embeds in $(\FrGr_n, g_n)$ so that this diagram + $(B_{i,j}, \beta_{i,j})$ embeds in $(\FrGr_n, g_n)$ so that this diagram commutes: \begin{center} @@ -216,7 +207,7 @@ Take any $(B, \beta)\in\cD$. Then, there are $i, j$ such that $(B, \beta) = (B_{i, j}, \beta_{i,j})$ and $A_{i,j}=\emptyset$. By the bookkeeping there was $n$ such that - $(i, j) = \min\{\{0,1,\ldots n-1\}\times\bN\setminus X_{n-1}\}$. + $(i, j) = \min\{\{0,1,\ldots n\}\times\bN\setminus X_{n}\}$. This means that $(B, \beta)$ embeds into $(\Gamma_n, g_n)$, hence it embeds into $(\Gamma, g)$. Thus, $\cD$ is a subclass of the age of $(\Gamma, g)$. The other inclusion is obvious. Hence, the age of $(\Gamma, g)$ is $\cH$. 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} diff --git a/sections/preliminaries.tex b/sections/preliminaries.tex index d6d5376..b35b4d3 100644 --- a/sections/preliminaries.tex +++ b/sections/preliminaries.tex @@ -359,6 +359,7 @@ particularly interesting to us is the following fact. \begin{fact} + \label{fact:natural-automorphism} Let $\eta$ be a natural transformation of functors $F, G$ from category $\cC$ to $\cD$. Then $\eta$ is an isomorphism if and only if all of the component morphisms are isomorphisms. |