diff options
| -rw-r--r-- | lic_malinka.pdf | bin | 490584 -> 493723 bytes | |||
| -rw-r--r-- | lic_malinka.tex | 17 | ||||
| -rw-r--r-- | licmalinka.bib | 7 | ||||
| -rw-r--r-- | sections/examples.tex | 74 |
4 files changed, 64 insertions, 34 deletions
diff --git a/lic_malinka.pdf b/lic_malinka.pdf Binary files differindex d5a991d..067df4a 100644 --- a/lic_malinka.pdf +++ b/lic_malinka.pdf diff --git a/lic_malinka.tex b/lic_malinka.tex index 47e1499..ed73de7 100644 --- a/lic_malinka.tex +++ b/lic_malinka.tex @@ -29,12 +29,18 @@ \usepackage{etoolbox}
\usepackage{xcolor}
-\definecolor{green}{RGB}{0,127,0}
-\definecolor{redd}{RGB}{191,0,0}
-
-\definecolor{red}{RGB}{105,89,205}
\usepackage[colorlinks=true]{hyperref}
-
+\hypersetup{
+ colorlinks,
+ linkcolor={red!50!black},
+ citecolor={blue!50!black},
+ urlcolor={blue!80!black}
+}
+% \definecolor{green}{RGB}{0,127,0}
+% \definecolor{redd}{RGB}{191,0,0}
+%
+% \definecolor{red}{RGB}{105,89,205}
+%
\usepackage[notref, notcite]{showkeys}
\usepackage[cmtip,arrow]{xy}
@@ -62,6 +68,7 @@ \newcommand{\bQ}{\mathbb Q}
\newcommand{\cK}{\mathcal K}
\newcommand{\cL}{\mathcal L}
+\newcommand{\cT}{\mathcal T}
\newcommand{\FrAut}{\Pi}
\newcommand{\FrGr}{\Gamma}
diff --git a/licmalinka.bib b/licmalinka.bib index 26dd13f..051ae83 100644 --- a/licmalinka.bib +++ b/licmalinka.bib @@ -73,5 +73,10 @@ url={https://core.ac.uk/download/pdf/83934818.pdf}, year={2017}, publisher={The University of Leeds (Department of Pure Mathematics)} +}, +@article{eppa_presentation, + title={Fraïssé Limits, Hrushovski Property and Generic Automorphisms}, + author={Shixiao Liu}, + url={https://logic.pku.edu.cn/ann_attachments/eppa-presentation.pdf}, + year={2017} } - diff --git a/sections/examples.tex b/sections/examples.tex index f65ebce..5f75953 100644 --- a/sections/examples.tex +++ b/sections/examples.tex @@ -10,11 +10,12 @@ \end{enumerate} \end{example} - $\cL$ of course has HP and is essentialy countable. JEP is also easy, - as having two finite linear orderings we can just embed the one with less + $\cL$ of course has HP and is essentially countable. JEP is also easy, + as having two finite linear orderings we can just embed the one with fewer elements into the bigger one. - We will show that $\cL$ has CAP. Let $C$ be a finite linear ordered set. + We will show that $\cL$ has canonical amalgamation (CAP). + Let $C$ be a finite linear ordered set. We will define $\otimes_C$. Let $A$, $B$ be finite linear orderings that $C$ embeds into. We may suppose that $C = A\cap B$. Then we define an ordering on $D = A\cup B$. For $d,e \in D$, let $d\le_D e$ if one of the @@ -48,7 +49,7 @@ \draw[->,thick] (-6, 2)--(0,2) node[right]{$A$}; \foreach \x in {0,...,7} - \node at ({-6 + 6/9 * (\x+1)},2)[rectangle,fill=magenta, inner sep=2pt]{}; + \node at ({-6 + 6/9 * (\x+1)},2)[rectangle,fill=red, inner sep=2pt]{}; \foreach \x in {2,5,6} \node at ({-6 + 6/9 * (\x+1)},2)[circle,fill=green, inner sep=2pt]{}; @@ -68,7 +69,7 @@ \foreach \x in {3,7,9} \node at ({-5+10/13*(\x+1)}, 4)[circle,fill=green,inner sep=2pt]{}; \foreach \x in {0,1,4,5,10} - \node at ({-5+10/13*(\x+1)}, 4)[rectangle,fill=magenta,inner sep=2pt]{}; + \node at ({-5+10/13*(\x+1)}, 4)[rectangle,fill=red,inner sep=2pt]{}; \foreach \x in {2,6,8,11} \node at ({-5+10/13*(\x+1)}, 4)[star,fill=blue,inner sep=2pt]{}; \end{tikzpicture} @@ -77,14 +78,14 @@ \vspace{0.5cm} On the other hand $\cL$ cannot have $WHP$. This follows from the fact that - that only automoprhism of a finite linear ordering is identity, so - we cannot extend a partial automoprhism sending exactly one element to - some distinct element. However, in this case, generic automoprhism exists + that only automorphism of a finite linear ordering is identity, so + we cannot extend a partial automorphism sending exactly one element to + some distinct element. However, in this case, generic automorphism exists which was shown by Truss \cite{truss_gen_aut}. \begin{definition} - Let $X$ be a set. A ternarny relation $\le^C \subseteq X^3$ is a - \emph{cyclic order}, where we denote $(a,b,c)\in\le^C$ as $a\le^{C}_{b}c$ + Let $X$ be a set. A ternary relation $\le^C \subseteq X^3$ is a + \emph{cyclic order}, where we denote $(a,b,c)\in{\le^C}$ as $a\le^{C}_{b}c$ (or simply $a\le_bc$ when there's only one relation in the context), when it satisfies the following properties: \begin{itemize} @@ -96,7 +97,7 @@ \end{itemize} \end{definition} - It is easy to visualise a cyclic ordering as a directed (\textit{nomen omen}) + It is easy to visualize a cyclic ordering as a directed (\textit{nomen omen}) cycle. For example, a 11-element cyclic order could be drawn like this: \begin{figure}[h] @@ -133,24 +134,37 @@ the linear orders. The Fraïssé limit of $\cC$ is a countable unit circle. $\cC$ hasn't WHP by the similar argument to this for linear - orderings. Imagine a cycling order of three elements and a partial automoprhism + orderings. Imagine a cycling order of three elements and a partial automorphism with one fixed point and moving second element to the third. This cannot be - extended to automoprhism of any finite cyclic order. + extended to automorphism of any finite cyclic order. Also, $\cC$ cannot have CAP. A reason to that is that it do not admit canonical amalgamation over the empty structure see this by taking - 1-element cyclic order and 3-element cyclic order with automoprhism other + 1-element cyclic order and 3-element cyclic order with automorphism other than identity). - % \begin{example} - % The class of all finitely generated vector spaces over a countable field - % $\cV$ is a Fraïssé class with WHP and CAP. - % \end{example} - % - % The prove of this is relatively easy knowing that there is essentially one - % vector space of finite dimension and that every linear independent subset - % of a vector space can be extended to a basis of this space. The Fraïssé limit - % of $\cV$ is the $\omega$-dimensional vector space. + In contrast to linear orderings the Fraïssé limit $\Sigma = \Flim{\cC}$ + has no generic automorphism. Consider the set $A$ of automorphisms of $\Sigma$ + with at least one finite orbit of size greater than $1$. It is open, not dense + and closed on conjugation. Openness follows from the fact that all + finite orbits of a given automorphism have the same size. Thus $A$ can be + represented as a union of basic set generated by finite cycles of + length greater than $1$. It is not dense, as it has empty intersection with + basic set generated by identity of a single element. It is also closed on + taking conjugation, as the order of elements does not change when conjugating. + Thus there cannot be a dense conjugacy class in $\Aut(\Sigma)$ and so there's + no generic automorphism. + + \begin{example} + The class of all finitely generated vector spaces over a countable field + $\cV$ is a Fraïssé class with WHP and CAP. + \end{example} + + The prove of this is relatively easy, knowing that there is essentially one + vector space of every finite dimension and that every linear independent subset + of a vector space can be extended to a basis of this space. The Fraïssé limit + of $\cV$ is the $\omega$-dimensional vector space. Thus, by our key Theorem + \ref{theorem:key-theorem} we know that it has a generic automorphism. \begin{example} The class of all finite graphs $\cG$ is a Fraïssé class with WHP and free @@ -158,12 +172,16 @@ \end{example} We have already shown this fact. Thus get that the random graph has a generic - automoprhism. + automorphism. \begin{example} - Graphs without triangles. - \end{example} - \begin{example} - Graphs without 3-paths. + A $K_n$-free graph is a graph with no $n$-clique as its subgraph. + Let $\cG_n$ be the class of finite \emph{$K_n$-free} graphs. $\cG_n$ + is a Fraïssé class with WHP and free amalgamation. \end{example} + + Showing that $\cG_n$ is indeed a Fraïssé class is almost the same as in + normal graphs, together with free amalgamation. WHP is trickier and the proof + can be seen in \cite{eppa_presentation} Theorem 3.6. Hence, $\Flim(\cG_n)$ + has a generic automorphism. \end{document} |