1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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}
|
