diff options
Diffstat (limited to 'sections/examples.tex')
| -rw-r--r-- | sections/examples.tex | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/sections/examples.tex b/sections/examples.tex new file mode 100644 index 0000000..0b45b32 --- /dev/null +++ b/sections/examples.tex @@ -0,0 +1,120 @@ +\documentclass[../lic_malinka.tex]{subfiles} + +\begin{document} + \begin{example} + Let $\cL$ be the class of all finite linear orderings. Then: + \begin{enumerate} + \item $\cL$ is a Fraïssé class. + \item $\cL$ has canonical amalgamation. + \item $\cL$ does not have WHP. + \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 + elements into the bigger one. + + We will show that $\cL$ has 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 + following hold: + \begin{itemize} + \item $d,e\in A$ and $d\le_A e$, + \item $d,e\in B$ and $d\le_B e$, + \item $d\in A, e\in B$ and there is $c\in C$ such that $d\le_A c$ and + $c\le_B e$, + \item $d\in B, e\in A$ and there is $c\in C$ such that $d\le_B c$ and + $c\le_A e$, + \item $d\in A, e\in B$ and for all $c\in C$ $d\le_A c\Leftrightarrow e\le_B c$ + \end{itemize} + + One can imagine that $D$ can be constructed by laying elements of $C$ + in a row and putting elements of $A$ and $B$ appropriately between elements + of $C$ with all elements of $A$ to the left and all elements of $B$ to + the right between two adjacent elements of $C$. This clearly is + a canonical amalgamation. + + \vspace{0.5cm} + \begin{figure}[h] + \centering + \begin{tikzpicture} + \draw[->,thick] (-1.5,0)--(1.5,0) node[right]{$C$}; + \foreach \x in {0,...,2} + \node at ({-1.5+3/4*(1+\x)},0)[circle,fill=green,inner sep=2pt]{}; + + \draw[->] (-1,0.5) -- (-3,1.5); + \draw[->] (1,0.5) -- (3,1.5); + + \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]{}; + \foreach \x in {2,5,6} + \node at ({-6 + 6/9 * (\x+1)},2)[circle,fill=green, inner sep=2pt]{}; + + \draw[->] (-3,2.5) -- (-2,3.5); + + \draw[->,thick] (1, 2)--(6,2) node[right]{$B$}; + \foreach \x in {0,2,4,6} + \node at ({1+5/8*(\x+1)},2)[star,fill=blue, inner sep=2pt]{}; + \foreach \x in {1, 3, 5} + \node at ({1+5/8*(\x+1)},2)[circle,fill=green, inner sep=2pt]{}; + + \draw[->] (3,2.5) -- (2,3.5); + + \draw[->,thick] (-5, 4)--(5,4) node[right]{$D$}; + % \foreach \x in {0,...,11} + % \node at ({-5+10/13*(\x+1)}, 4)[circle,fill=black,inner sep=2pt]{}; + \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]{}; + \foreach \x in {2,6,8,11} + \node at ({-5+10/13*(\x+1)}, 4)[star,fill=blue,inner sep=2pt]{}; + \end{tikzpicture} + \caption{Visual representation of the construction.} + \end{figure} + \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. + + \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$ + (or simply $a\le_bc$ when there's only one relation in the context), + when it satisfies the following properties: + \begin{itemize} + \item If $a\le_bc$, then $b\le_ca$. + \item If $a\le_bc$, then not $c\le_ba$. + \item If $a\le_bc$ and $a\le_cd$, then $a\le_bd$. + \item If $a,b,c$ are pairwise distinct, then either $a\le_bc$ or + $c\le_ba$. + \end{itemize} + \end{definition} + + \begin{example} + Let $\cC$ be the class of all finite cyclic orderings. Then: + \begin{enumerate} + \item $\cC$ is a Fraïssé class. + \item $\cC$ does not have WHP. + \item $\cC$ does not have CAP. + \end{enumerate} + \end{example} + + \begin{example} + The class of all finitely generated vector spaces $\cV$ is a Fraïssé class + with WHP and CAP. + \end{example} + \begin{example} + The class of all finite graphs $\cG$ is a + \end{example} + \begin{example} + Graphs without triangles. + \end{example} + \begin{example} + Graphs without 3-paths. + \end{example} +\end{document} |