Information Technology Reference
In-Depth Information
15. Gradel, E., Vaananen, J.: Dependence and independence. Studia Logica 101(2),
399-410 (2013)
16. Hrushovski, E.: Extending partial isomorphisms of graphs. Combinatorica 12(4),
411-416 (1992)
17. Fraısse, R.: Sur une nouvelle classification des systmes de relations. Comptes Ren-
dus 230, 1022-1024 (1950)
18. Ehrenfeucht, A.: An application of games to the completeness problem for formal-
ized theories. Fundamenta Mathematicae 49, 129-141 (1961)
19. Imhof, H.: Computational aspects of arity hierarchies. In: van Dalen, D., Bezem,
M. (eds.) CSL 1996. LNCS, vol. 1258, pp. 211-225. Springer, Heidelberg (1997)
Appendix
The proof of Lemma 1 is presented in the following.
Proof (Lemma 1).
We may start from Step 3 of the outline of the proof presented
after Lemma 1. Hence we have
(
A
,
b
,
c
)
|
=
X
ʸ,
(6)
[
F
1
/x
1
]
...
[
F
m
/x
m
], and the first step is to construct a team
X
∗
for
X
:=
{∅}
such that
(
A
,
b
,ʵ
(
c
))
|
=
X
∗
ʸ.
(7)
For this, we first define the operation auto. By item 4 of Theorem 8, for all
a
list-
ing
a
1
,...,a
k−
1
∈
A
there exists an automorphism
f
a
which maps
a
pointwise to
ʵ
(
), but leaves all elements in rows of distance
>
1fromrow(
a
1
)
,...,
row(
a
k−
1
)
fixed. Let
a
) be the group generated by the automorphisms
f
a
where
f
a
is obtained from item 4 of Theorem 8 and
a
is a sequence listing
a
1
,...,a
k−
1
∈ A
such that 2
<
row(
a
i
)
<n−
1, for 1
≤ i ≤ k−
1. For a team
Y
of
A
,wethenlet
F
=(
F,
ⓦ
auto(
Y
):=
{
f
ⓦ
s
|
f
∈F
,s
∈
Y
}
.
Next we will define the operation swap. For this, we will first define mappings
mid and
h
.Weletmidmap
m
-sequences of
{
1
,...,n
}
into
{
1
,...,n
}
so that,
m
,
for any
p
:= (
p
1
,...,p
m
)and
q
:= (
q
1
,...,q
m
)in
{
1
,...,n
}
1. 1
<
mid(
p
)
<n
,
2.
∀
i
≤
m
: mid(
p
)
=
p
i
,
3.
∀
l
≤
m
:if
p
{
1
,...,l
}
=
q
{
1
,...,l
}
,then
∀
i
≤
l
:
p
i
<
mid(
p
)iff
q
i
<
mid(
q
).
