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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
\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. However, in this case, generic automoprhism 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$
(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}
It is easy to visualise 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]
\centering
\begin{tikzpicture}
\def \n {11}
\def \radius {3cm}
\def \margin {10}
\foreach \s in {1,...,\n}
{
\node[draw, circle] at ({360/\n * (\s - 1)}:\radius) {};
\draw[->, >=latex] ({360/\n * (\s - 1)+\margin}:\radius)
arc ({360/\n * (\s - 1)+\margin}:{360/\n * (\s)-\margin}:\radius);
}
\node[draw, circle, fill=green] at ({360/\n * (1 - 1)}:\radius) {};
\node[draw, circle, fill=blue] at ({360/\n * (5 - 1)}:\radius) {};
\node[draw, circle, fill=red] at ({360/\n * (9 - 1)}:\radius) {};
\end{tikzpicture}
\end{figure}
For three elements $a, b, c$ we say that $a\le_bc$ if after ''cutting'' the
cycle at $b$ we have a path from $a$ to $c$.
In this particular example we can say that the green element is
red-element-smaller than the blue one.
\begin{example}
The class $\cC$ of all finite cyclic orders is a Fraïssé class, but does
not have WHP or CAP.
\end{example}
It is not hard to show that $\cC$ is indeed the Fraïssé class. As usual,
the hardest part is showing AP, which in this case is done analogously to
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
with one fixed point and moving second element to the third. This cannot be
extended to automoprhism 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
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.
\begin{example}
The class of all finite graphs $\cG$ is a Fraïssé class with WHP and free
amalgamation.
\end{example}
We have already shown this fact. Thus get that the random graph has a generic
automoprhism.
\begin{example}
Graphs without triangles.
\end{example}
\begin{example}
Graphs without 3-paths.
\end{example}
\end{document}
|
