aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorFranciszek Malinka <franciszek.malinka@gmail.com>2022-07-17 23:22:37 +0200
committerFranciszek Malinka <franciszek.malinka@gmail.com>2022-07-17 23:22:37 +0200
commitef3fc25228cc13c9f39192813653b1b6dc339406 (patch)
tree69168435e9c11b1a4b217eaae81b2b350e482939
parent3379b5851e1dd3096e832215b5685ec9f058ebb0 (diff)
Szkola orlow finish!
-rw-r--r--lic_malinka.pdfbin480503 -> 479056 bytes
-rw-r--r--lic_malinka.tex2
-rw-r--r--sections/conj_classes.tex47
-rw-r--r--sections/fraisse_classes.tex119
-rw-r--r--sections/preliminaries.tex1
5 files changed, 81 insertions, 88 deletions
diff --git a/lic_malinka.pdf b/lic_malinka.pdf
index a61d98f..3725a5b 100644
--- a/lic_malinka.pdf
+++ b/lic_malinka.pdf
Binary files differ
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.