Information Technology Reference
In-Depth Information
-
Assume first that
ˈ
is of the form
x
i
=
b
j
or
x
i
=
c
j
, and let
s
∈
Y
∗
be
arbitrary. For (8), it suces to show by Theorem 1 that
(
A
,
b
,ʵ
(
c
))
|
=
s
ˈ.
(9)
First note that
s
=
h
(
f
ⓦ
t
) for some automorphism
f
∈F
and assign-
ment
t ∈ Y
for which, by the assumption and Theorem 1, (
A
,
b
,
c
)
|
=
t
ˈ
.
Hence for (9), we only need to show that
s
(
x
i
)=
t
(
x
i
)incase
t
(
x
i
) is listed
in
b
,and
s
(
x
i
)=
ʵ ⓦ t
(
x
i
)incase
t
(
x
i
) is listed in
c
.Forthis,firstrecall
that
is the group generated by automorphisms
f
a
where
f
a
is obtained
from item 4 of Theorem 8 and
F
a
is a sequence listing
a
1
,...,a
k−
1
∈
A
such that 2
<
row(
a
i
)
<n
1. Therefore
f
leaves all ele-
ments in the first and the last row fixed when
f
(
−
1, for 1
≤
i
≤
k
−
b
)=
b
and
f
(
c
)=
c
.Onthe
other hand, by the definition of mid, 1
<
mid(row(
f
ⓦ
t
(
x
))))
<n
, and hence
h
(
f
ⓦ
t
)(
x
i
)=
f
ⓦ
t
(
x
i
)if
f
ⓦ
t
(
x
i
) is in the first row, and
h
(
f
ⓦ
t
)(
x
i
)=
ʵ
ⓦ
f
ⓦ
t
(
x
i
)
if
f
are in the first and the last
row, respectively, we conclude that the claim holds. The case where
ˈ
is of
the form
x
i
=
x
j
or
ⓦ
t
(
x
i
) is in the last row. Since tuples
b
and
c
x
i
=
x
j
is straightforward.
-
Assume that
ˈ
is of the form
E
(
x
i
,x
j
)or
¬
Y
∗
¬
E
(
x
i
,x
j
). Again, let
s
∈
when
s
=
h
(
f
ⓦ
t
)forsome
f
∈F
and
t
∈
Y
. For (9), consider first the cases
where
row(
t
(
x
i
))
,
row(
t
(
x
j
))
<
mid(row(
t
(
x
))), or
(10)
row(
t
(
x
i
))
,
row(
t
(
x
j
))
>
mid(row(
t
(
x
)))
.
(11)
Since
f
is a row-preserving automorphism, we conclude by the definition of
h
that
s
maps both
x
i
and
x
j
either according to
f
t
.
Since
ʵ
is also an automorphism, we obtain (9) in both cases. Assume then
that (10) and (11) both fail. Then by symmetry suppose we have
ⓦ
t
or according to
ʵ
ⓦ
f
ⓦ
row(
t
(
x
i
))
<
mid(row(
t
(
x
))))
<
row(
t
(
x
j
))
.
Since (
A
,
b
,
c
)
|
=
t
ˈ
,wehavebyitem1ofTheorem8that
ˈ
is
¬E
(
x
i
,x
j
).
Since
f
and
ʵ
preserve the rows, we have
row(
s
(
x
i
))
<
mid(row(
s
(
x
))))
<
row(
s
(
x
j
))
.
Therefore we obtain (
A
,
b
,
c
)
|
=
s
¬
E
(
x
i
,x
j
) which concludes this case.
-
Assume that
ˆ
is
y
ↆ
z
,forsome
y
=
y
1
...y
l
and
z
=
z
1
...z
l
where
Y
∗
be arbitrary. For (8), we show that there exists a
l
≤
k
−
1. Let
s
∈
s
∈
Y
∗
such that
s
(
)=
s
(
y
z
). Now
s
=
h
(
f
ⓦ
t
)forsome
f
∈F
and
t
∈
Y
,
=
Y
ˈ
by the assumption. Hence there exists a
t
∈
and (
A
,
b
,
c
)
|
Y
such that
)=
t
(
l
for which (i) or (ii) hold:
6
t
(
y
z
). Let now
I
list the indices 1
≤
i
≤
6
An example where
y
:=
y
1
y
2
y
3
and
z
:=
z
1
z
2
z
3
is illustrated in Fig. 2. Note that
in the example,
I
=
{
2
}
since the index number 2 satisfies (ii). Then letting
s
0
:=
h
(
f ⓦ t
), we obtain
s
(
y
1
y
3
)=
s
0
(
z
1
z
3
) but only
s
(
y
2
)=
ʵ ⓦ s
0
(
z
2
). Fig. 3 shows that
choosing
s
:=
h
(
f
a
ⓦ f ⓦ t
), for
a
:=
f ⓦ t
(
z
2
), we obtain
s
(
y
)=
s
(
z
).
