Databases Reference
In-Depth Information
cation, and for Fisher's quantifier
∼
α,Base
. The proof for the other listed
4ft-quantifiers is similar. The proof of classical undefinability of additional
4ft-quantifiers is given in [4].
First we prove that the 4ft-quantifiers
⇒
p,Base
of founded implication and
!
p,α,Base
of lower critical implication are not classically
definable. We will use the following lemmas.
the 4ft-quantifier
⇒
⇒
∗
be an implicational quantifier that satisfies the conditions
Lemma 1.
Let
⇒
∗
(
a,b
)=0
.
(a) There is A
≥
0
such that for each a
≥
A there is b satisfying
⇒
∗
(
a,b
)=0
there is a
≥
(b) For each a
≥
0
and b
≥
0
such that
a for which
⇒
∗
(
a
,b
)=1
.
Then the table Tb
⇒
∗
it is
⇒
∗
has infinitely many steps.
of maximal b of
⇒
∗
satisfies the condition (a) then it is Tb
⇒
∗
(
a
)
<
Proof. If the quantifier
∞
⇒
∗
(
a,Tb
⇒
∗
(
a
)) = 0
. If the quantifier
⇒
∗
satisfies the condition (b) then there is for each a>Aan a
>asuch
that it is
for each a
≥
0
. Remember that it is
⇒
∗
(
a,Tb
⇒
∗
(
a
)) = 0
and also it is
⇒
∗
(
a
,Tb
⇒
∗
(
a
)) = 1
. It means that between a and a
there must be a step s
of the table Tb
⇒
∗
.
We have proved that for each a>Athere is a step s
⇒
∗
(
a
,Tb
⇒
∗
(
a
)) = 1
. Thus it is
≥
a of the table Tb
⇒
∗
.
It but means that the table Tb
⇒
∗
has infinitely many steps. This finishes the
proof.
Lemma 2.
Let us suppose that
is an equivalency quantifier and c
0
and d
0
are natural numbers such that the following conditions are satisfied.
≈
(a) There is A
≥
0
such that for each a
≥
A there is b for which it is satisfied
(
a,b,c
0
,d
0
)=0
.
(b) For each a
≈
(
a,b,c
0
,d
0
)=0
there is a
≥
≥
0
and b
≥
0
such that
≈
a for
whichitis
≈
(
a
,b,c,d
)=1
.
Then the partial table Tbp
≈
(
a,c
0
,d
0
)
of maximal b of
≈
has infinitely many
steps.
Proof. The proof is similar to the proof of the Lemma 1.
Lemma 3.
Let us suppose that
0
<p<
1
and that i
≥
0
is a natural number.
Then it is
K
i
p
i
(1
p
)
K−i
=0
lim
K→∞
−
·
Proof. It is:
K
i
p
i
(1
− p
)
K−i
≤ K
i
p
i
(1
− p
)
K
(1
− p
)
−i
p
)
K
p
1
i
=
K
i
(1
−
.
−
p
