Definability of Polyadic Lifts of Generalized Quantifiers.
We study generalized quantifiers on finite structures. With every function f : we associate a quantifier Q_f by letting Q_fx &phis; say there are at least f(n) elementsx satisfying &phis;, where n is the size of the universe. This is the general form of what is known as a monotone quantifier of type  1 . We study so called polyadic lifts of such quantifiers. The particular lifts we consider are Ramseyfication, branching and resumption. In each case we get exact criteria for definability of the lift in terms of simpler quantifiers.
to a given logic? Such questions can be quite hard. On finite models,
Partially supported by a grant from the University of Helsinki. This research was initiated
while the first author was a Junior Researcher at the Academy of Finland.
answering some of these questions would mean solving notoriously difficult open
problems about computational complexity.
The results on (un)definability in the literature usually concern particular quan-
tifiers; few general definability results for interesting classes of quantifiers are known.
For monadic quantifiers, however, the definability question above has recently been
given a complete answer in algebraic terms (cf. [18]), an answer which also permits
complete classifications with respect to expressive power of various classes of
monadic quantifiers.
Nothing similar is in sight for polyadic quantifiers, not even for the simplest kind
whose signature consists of one binary relation. A rough way of measuring complexity
of a quantifier is by its arity, i.e., the largest arity of the relations occurring in the
corresponding signature. So monadic quantifiers are unary, and an early result by
Lindstr-om [14] is that the binary well-ordering quantifier is not definable by means
of any monadic quantifiers added to first-order logic. This leads to the question
of the existence of arity hierarchies of quantifiers: sequences hQ n i n2! where Q n is
n-ary and not definable in terms of Q k for k ! n, or even in terms of any quantifiers
of lower arity. Several such hierarchies are known; a systematic treatment is given
in [6].
These hierarchy results make essential use of infinite models. Recently, some
hierarchy results have also been obtained for finite models. One result by Luosto
[15] is that the binary quantifier " R contains at least half of the ordered pairs of
elements of the universe" is not definable from any monadic quantifiers over finite
models. The proof uses advanced finite combinatorics. Another recent result, the
Hierarchy Theorem of [8], states that, with respect to a more fine-grained complexity
ordering than the arity ordering, there exists at every step quantifiers not definable
in terms of quantifiers of lower complexity, over finite models. However, the existence
of these quantifiers is proved by probabilistic methods, not by explicit construction.
In this paper we shall give definability characterizations over finite models for
certain classes of polyadic quantifiers, more precisely for polyadic quantifiers that
are obtained from monadic ones by means of certain operations. We call these
operations polyadic lifts. Three such lifts are studied: branching, Ramseyfication
and resumption.
Let Q be a simple unary quantifier (one whose signature contains just one unary
predicate symbol), which is also monotone. Then there is a function f from natural
numbers to natural numbers such that on a universe with n elements
"at least f(n) ". The branching of Q (with itself) says of a binary relation R that
there are subsets X;Y of the universe with at least f(n) elements such that the
Y is contained in R . Similarly we can branch two distinct monotone
simple unary quantifiers (requiring then that jXj - f(n) and jY j - g(n)), or k such
quantifiers. The k-ary Ramseyfication of Q says that there is a set X of cardinality
at least f(n) which is homogeneous for R , i.e., any k distinct elements of X stand
in the relation R to each other. A resumption of a monadic quantifier, finally, says
the same thing about tuples of individuals that the monadic quantifier says about
individuals. So the k-ary resumption of Q says, on a universe with n elements, of
a k-place relation that it contains at least f(n k ) k -tuples.
These polyadic lifts turn up in various contexts. The Ramseyfication operation
is familiar from model theory. The ability to quantify over k-tuples is sometimes
assumed in finite model theory in order to be able to describe certain behavior of Turing
machines. And all three lifts have been proposed in natural language semantics.
Actually, this is the context where the idea of polyadic lifts and their definability
arose, even though the definability issues themselves are standard mathematical-
logical questions.
The most immediate question to ask about a polyadic lift is whether it really
gives anything new, i.e.: Is definable in terms of Q
is the question we deal with in this paper. We prove that for the three lifts under
consideration, the lifted quantifiers are usually not definable in first-order logic
augmented with the argument quantifiers. More precisely, we show that a certain
condition of unboundedness of the functions associated with monotone simple unary
quantifiers is sufficient for undefinability of branching and Ramseyfication. Actually,
our results are stronger. We show that, if Q is unbounded, the 1)-ary branching
of Q is not definable from any monadic quantifiers added to first-order logic
1). And for Ramseyfication we obtain undefinability even if any quantifiers of
arity at most k are allowed, and even if first-order logic is replaced by the stronger
logic
1! (a logic which extends fixed point logic). Moreover, we also show that
unboundedness is a necessary condition for undefinability. That is, if Q is bounded,
branching and Ramseyfication of Q is definable in terms of Q. We have a similar
characterization for the definability of the branching of k
For resumption, our results are similar but a little weaker. We show that a
slight strengthening of unboundedness is necessary and sufficient for the 1)-ary
resumption of Q to be undefinable from any monotone simple unary quantifiers
added to first-order logic. We also identify another necessary condition for the
+1)-ary resumption of Q to be undefinable from Q, roughly that the behavior of
Q on universes of size n does not determine its behavior of universes of size n k+1 .
In natural language semantics, the basic quantifiers are not the simple unary
ones but instead those of type h1; 1i, whose signature has two unary predicate
symbols. English determiners like all, some, no, at least five, most, all but three,
more than two thirds of, etc., denote such quantifiers. The lift operations arise
from the way noun phrases containing determiners are combined with each other
in sentences. The standard lifts here give polyadic quantifiers which are definable
from the determiner denotations, but some sentences appear to use the three lifts
studied in this paper. We show that our results about branching and Ramseyfication
generalize to type h1; 1i quantifiers, provided these satisfy two conditions. These
conditions are believed to hold (almost) universally for determiner denotations.
We restrict attention to finite models, a constraint which is common in natural
language semantics and model theory for computer science. The undefinability
results of course hold for arbitrary models - it's just that the counter-examples we
give to definability are finite. But our results that certain quantifiers are definable
in a certain logics require the assumption of finiteness.
In the remainder of this section we first recall the relevant notions pertaining
to logics with generalized quantifiers, and then introduce the three lift operations
in the context of natural language semantics. The brief linguistic excursion there
is included for background and motivation, but not used in the rest of the paper.
In Section 2 we state some facts about monotone quantifiers and establish that
boundedness implies definability (of branching and Ramseyfication). Sections 3,4,
and 5 deal with branching, Ramseyfication and resumption, respectively. In each
case, undefinability is established by means of a suitable Ehrenfeucht-Fra-iss'e game,
although the three proofs are quite different. Section 6 ends the paper with some
questions and open problems.
1.1 Generalized quantifiers and definability
We begin by recalling the concept of a generalized (Lindstr-om) quantifier, and of
logics with such quantifiers (cf. [13]).
A (generalized) quantifier is a class Q of structures of a finite relational signature
which is closed under isomorphism. The type of Q can be identified with a finite
sequence positive natural numbers (n ? 0). Equivalently, Q can
be defined as a functional assigning to each non-empty set A a quantifier QA of
a subset of
relation over A). Instead of
simply . The arity of Q is maxfk g. Q is monadic if it is unary
polyadic. We let Q k be the class of all quantifiers of
A quantifier Q of type hki is called simple. It is monotone if for all A and
all R; S ' A k , QAR and R ' S implies QAS . The notion of a type hk
quantifier being monotone in the i:th argument is defined similarly.
With many familiar logics L one can uniquely associate a logic L(Q) obtained
by adding the quantifier Q: a new formation rule yields formulas
are formulas, x i is a string of k i distinct variables, and the semantics
is given by the clause
A
Here A is the universe of A, a is a finite sequence of elements in A, and ' A
b)g. Similarly one defines the logic L(Q) when Q is a class
of quantifiers.
In this paper L will be either first-order logic L !! , or L k
1! (which is like L1!
except that it only has k variables), or L !
1! . As usual,
means that the same L(Q)-sentences are true in A and in B. When ' is an
its quantifier rank qr(') is the maximal number of nestings of
quantifier symbols (including 8 and in ', and
means that the same L !! (Q)-sentences of quantifier rank at most q are true in A
and in B.
The relativization of a type hk
quantifier Q rel defined by
A (X; R
This can be extended to formulas of L(Q): if P is a (new) unary predicate symbol
and ' such a formula one defines inductively a formula ' (P ) of L(Q rel ) which says
the same thing about (A; X) as ' says about the substructure of A generated by
X .
The quantifier Q is definable in L(Q) if the sentence
is logically equivalent to some L(Q)-sentence in those predicate symbols. A logic
extends another logic if every sentence in the latter is equivalent to some sentence
in the former. In particular, L(Q 0 ) extends L(Q) iff each Q 2 Q is definable in
1.2 Polyadic lifts and natural language quantification
Before defining the polyadic lifts we briefly explain how they turn up in natural
language semantics. More details can be found in [10].
Monadic generalized quantifiers provide the most straightforward way to give
the semantics of noun phrases (NPs) in natural languages. Consider a sentence like
It consists of a noun phrase no students, in turn constituted by the determiner no
and the noun students, and a verb phrase smoke, in this case a simple intransitive
verb. In a model A the noun and the verb phrase denote subsets of A. Thus, the
determiner is naturally taken to denote a binary relation between subsets of A, i.e.,
with varying A, a type h1; 1i generalized quantifier.
In (1) the quantifier used is noAXY , (using the same symbol for the
determiner as for its denotation). Changing the determiner in (1) we obtain other
quantifiers such as all, some, at least five, most, all but three,
more than two thirds of, etc., where, for example,
and all but three AXY ,
The first argument in these quantifiers is called the noun argument, and the
second the verb argument. Some determiners take more than one noun argument,
as in
(2) More students than teachers smoke
where more. than denotes the type h1;
Zj. The role of type h1i quantifiers in this context is as NP denota-
tions. For example, the denotation of most students is obtained by fixing the noun
argument of most to the denotation of students. Other NPs do not involve deter-
miners, like something and everything which denote 9 (9AX , X 6= ;) and 8
respectively, and phrases like John or Mary, which denotes the
set of X ' A such that note that whereas the determiner
denotations above are all closed under isomorphism, most NP denotations are not,
and thus do not qualify as quantifiers in the present sense.
Determiners usually denote type h1; 1i quantifiers, but not all such quantifiers
are determiner denotations. Indeed, the following two constraints have been found
to hold (almost) universally:
CONS QAXY () QAX X "Y
CONS predicts, for example, that the H-artig quantifier
I AXY ()
is not the denotation of any English determiner. And EXT implies that no determiner
can mean, say, some on universes with less than 10 elements and all on other
universes. Nevertheless, the determiner denotations form a rich class of quantifiers:
as further examples we may take the proportional quantifiers
and more than (at least) m n:ths
of the, and Boolean combinations of these, such as less than half of the, between ten
and twenty percent of the, not more than ten or at least twenty percent of the, etc.
Together, CONS and EXT express a characteristic asymmetry between the two
arguments of determiner denotations: the role of the noun argument is to restrict
the domain of quantification. A precise statement is the following
1.1 Fact. A type h1; 1i quantifier is CONS and EXT iff it is the relativization of
some simple unary quantifier.
Clearly, Q rel is always CONS and EXT and, conversely, if Q 0 is CONS and EXT
defined by QAY , Q
A AY , Q This simple fact often enables
one to generalize results about simple unary quantifiers to determiner denotations.
Notice also that a simple unary Q is monotone iff Q rel is right monotone (mono-
tone in the verb argument). For example, the proportional quantifiers above are
right monotone.
Thus, NP semantics involves monadic quantifiers. But sentences can combine
several NPs, together with transitive or ditransitive verbs denoting not sets but
binary or ternary relations. Their truth conditions can then be given by means of
polyadic quantifiers. Indeed, common sentential structures correspond to ways of
lifting monadic quantifiers to polyadic ones. The most ubiquitous lift is iteration,
as in
(3) Most students criticized three teachers
with a quantified subject and object (Q 1 X and Q transitive verb (R ).
The truth conditions (of one of the two readings of (3)) are
or, equivalently, the result of applying the lifted quantifier It(Q to the arguments
X;Y and R : define (suppressing
(R seemingly similar sentences sometimes correspond to
other lifts than iteration. For example,
researchers wrote thirty-two papers for the Handbook
presumably means neither that each of the forty researchers wrote thirty-two papers,
nor that each of the thirty-two papers was written by forty (co)authors. Instead, this
is an instance of so-called cumulative quantification: each of the forty researchers
authored at least one paper for the Handbook, and each of the thirty-two papers
was authored by at least one researcher. Thus, we have the lift
We now come to the lifts studied in this paper. The first was introduced by
Barwise in [1] with examples such as
Most boys in your class and most girls in my class have all dated each other
Here the lift in question, on at least one plausible reading, is branching.
1.2 Definition. For right monotone type h1; 1i quantifiers
(again suppressing the universe)
We write Br k (Q) for arguments). The branching of k monotone
type h1i quantifiers is defined similarly (suppress
So (8) means that there is a set X containing more than half the boys in your
class and a set Y containing more than half the girls in my class such that any pair
in X \Theta Y is a 'dating' pair.
A similar lift occurs in certain reciprocal sentences like
At least two thirds of the boys in your class all like each other
which can be taken as saying that there is a set containing at least two thirds of
the boys in your class such that any two distinct boys in this set are in the 'like'
relation:
1.3 Definition. Let Q be a right monotone type h1; 1i quantifier.
(where I(Y )g). Similarly for a
monotone simple unary Q.
We call the values of this lift Ramsey quantifiers, extending slightly the common
usage of this term (where Q is the quantifier 'there exists a least @ ff ').
Our final example of a polyadic lift, resumption, amounts to using a monadic
quantifier to quantify over k-tuples of individuals. This lift has found uses in computer
science (cf. [4] and [16]) but can be given a linguistic motivation as well; cf.
cases like
Most neighbours like each other
Most twins never separate
1.4 Definition. Let Q be of type h1; 1i. Define
(Res k (Q))ARS () Q A k RS
Similarly for simple unary quantifiers.
The route to the lifts here went via linguistics, but they are natural in other
contexts too. For example, to say that a graph contains so and so many vertices of
degree 3 one iterates monadic quantifiers. But to say that a graph contains a clique
of such and such size, one needs a Ramsey quantifier. Of course, one could also use
second-order logic. But the Ramsey quantifier gives a better estimate of just how
much expressive power one needs to add to first-order logic in this case.
To know how powerful the lifts are one needs first of all to answer the basic
logical definability question:
When is
(The question is also significant in a linguistic context. For example, non-definability
may imply that a certain kind of grammar for the corresponding expressions does
not exist.) Trivially, iterations and Boolean combinations thereof are so definable.
We shall prove below that the other polyadic lifts - branching, Ramseyfication and
resumption - are usually not definable in this way.
Monotone quantifiers
?From now on, unless otherwise noted, we restrict attention to finite models. Then,
a monotone simple unary quantifier can be identified with a function
quantifier corresponding to f says of a set X that it has at least f(n) elements,
where n is the cardinality of the universe (if f(n) ? n this is trivially false). More
precisely, given f , define
for A. Conversely, if Q is monotone, and
least k s. t. 9A9X ' if such a k exists
then
Rather perspicuous definability criteria can be given for monotone simple unary
quantifiers. A full characterization can be found in [18]; here we quote for illustration
the following special cases:
2.1 Theorem.
1. ([11], [20]) The quantifier Q f is first order definable iff either f(n) or n \Gamma f(n)
is eventually constant.
2. ([18]) Suppose that lim n!1 that either
lim is definable
in L !! (Q f ) iff at least one of
eventually constant.
In the second of these statements Q f is assumed to satisfy a strong unboundedness
condition. For most of this paper, the following weaker notion is sufficient.
2.2 Definition. We say that the function f (or quantifier Q f ) is unbounded if
Canonical examples of unbounded functions are
n ], and [log(n)] (where
[a] is the integer part of a). Typical bounded functions are (corresponding
to 9),
2.3 Theorem. If f is bounded, then for any k - 2, Br k (Q f ) and Ram k (Q f ) are
definable in L !! (Q f ).
Proof. By hypothesis, there is a number m such that for every n, either
0, or n. We can use Q f to
uniquely characterize each of these possibilities for f(n). To see this, note first that
are the
sentences respectively. Second, for p ? 0 we have
Third, let / q be the conjunction of
y
y
and :- . Then
Moreover, for each one of these finitely many possibilities, the branching conditio

is expressible in first-order logic. Indeed, if condition is
equivalent to the sentence
states that all components of x are
distinct, and H is the set of all functions h pg. In the case
the branching condition is equivalent to the sentence
simply
finally, if 1), then the
branching condition is trivially true (false).
Putting all this together we conclude that Br k (Q f )x
equivalent to the sentence
1-p!m
q!m
The case of Ram k (Q f ) is similar. 2
The relativization Q rel
f of Q f is the right monotone type h1; 1i quantifier
(Q rel
We say that
f is bounded if f is bounded. Notice that Q f is definable in
f ), that Br(Q f 1
is definable in L !! (Br(Q rel
)), and that
Ram k (Q f ) is definable in L !! (Ram k (Q rel
f )). ?From Fact 1.1 we see that right monotone
determiner denotations usually are of the form Q rel
f . For example, the quantifier
most is Q rel
f for 1. And in most of these cases, relativization increases
expressive power. In fact, the following result tells us precisely when this happens.
2.4 Theorem. ([11], [20]) The quantifier Q rel
f is definable in L !! (Q f ) (or in
eventually constant (i.e., iff Q f is first-order
definable).
Note that Q rel is definable in L(Q) iff L(Q) has the relativization property,
i.e., for any L(Q)-sentence ', ' (P ) is equivalent to an L(Q)-sentence. We end
this section by stating a relativized version of Theorem 2.3 (these theorems will be
generalized to the branching of several quantifiers in section 3).
2.5 Theorem. If f is bounded, then Br k (Q rel
f ) and Ram k (Q rel
f are definable in
Proof. Similar to the proof of Theorem 2.3. To formulate the branching condition
Br k (Q rel
over a universe A, we need to express statements of the
(p ? 0, q - 0), and this can be done with the quantifier Q rel
f . 2
3 Definability of branching
In this section we first recall definitions and basic properties of some Ehrenfeucht-
Fra-iss'e type games, and then apply these games to the definability of branching.
The bijective Ehrenfeucht-Fra-iss'e game of length q , BEF q (A; B), has two play-
ers, which we call Duplicator and Spoiler , respectively. In each round 1
of the game Duplicator chooses first a bijection f
by choosing an element a i 2 A. These q pairs of moves of the players determine
a relation Duplicator wins the game
if p is a partial isomorphism A ! B, i.e., if p is an injective function such that
for each relation R of A and the corresponding relation R 0 of B, and for all tuples
(b
(b
Spoiler wins if this is not the case, or if Duplicator cannot make his moves, i.e., if
there are no bijections
As usual, what happens in some particular play of BEF q (A; B) is not important.
It is rather the question "which one of the players has a winning strategy" that is
relevant for us. Here we say that Duplicator (Spoiler) has a winning strategy if he
has a systematic way of choosing the bijections f i (the elements a i ) such that using
it he always wins the game, no matter how the other player moves.
The following result is a direct consequence of Theorem 2.5 of [6]. For the sake
of completeness we will explain here the basic idea behind its proof.
3.1 Proposition. If Duplicator has a winning strategy in the game BEF q (A; B),
then A j q
B.
Proof. (idea) Consider a formula
of L !! (Q 1 ) and a partial function a 7! b. If f is a bijection
such that for every a 2 A and each 1 - j - m, A
then the function f is an isomorphism between the defined structures
(b; \Delta)) . Hence, A
only if B no matter what the interpretation of the quantifier Q is. Using
this observation it is easy to prove by induction on r that if f are bijections
which Duplicator has chosen according to his winning strategy, and
are the elements chosen by Spoiler, then
A
for every formula ' of L !! (Q 1 ) with qr(') - r . In particular, the equivalence
A holds for every sentence ' of quantifier rank - q . 2
If the structures A and B are finite, then the converse of Proposition 3.1 is
also true: A j q
only if Duplicator has a winnning strategy in
BEF q (A; B). Furthermore, this equivalence holds for infinite structures, too, if the
logic L !! (Q 1 ) is replaced with the infinitary logic L1! (Q 1 ) (cf. [6]). However, the
implication stated in Proposition 3.1 is all that is needed for proving undefinability
results.
3.2 Corollary. Let K be a class of structures. If for every natural number q there
exist structures A and B such that A 2 K , B 62 K and Duplicator has a winning
strategy in BEF q (A; B), then K is not definable in L !! (Q 1 ).
Below we will give a non-trivial application of BEF q (A; B) to finite models. But
to get a feeling for the game, it may be helpful to to first see the use of Corollary
3.2 with a much simpler example, which involves infinite models.
3.3 Example. For each natural number m, let Em be an equivalence relation
on equivalence classes, all of cardinality ! . Similarly, let
an equivalence relation with ! equivalence classes of cardinality ! . We claim that
To see this, consider an arbitrary
partial isomorphism such that . For each i, let
A i be the set of all elements of ! which are Em -equivalent with a i , and let B i
be the set of those elements which are E n -equivalent with b i . Clearly all these sets
are of cardinality ! . Furthermore, since r ! q - m;n,
the sets are also of cardinality
. Hence, there exists a bijection extending p which maps A i onto B i
is a partial isomorphism
In particular, Duplicator can keep choosing
bijections in the game BEF q ((!; Em in such a way that
the mapping f (a is always a partial isomorphism.
Let K be the class of all structures (A; E) such that E is an equivalence relation
on A with finitely many equivalence classes. Since (!; Em
but it follows from Corollary 3.2 that K is not definable in L !! (Q 1 ).
In a similar fashion we see that the class K 0 consisting of those equivalence relations
E) that have an even number of equivalence classes is not definable in L !! (Q 1 ).
Historical remark. The example is a variant of Keisler's counterexample to interpolation
in L !! (Q 1 ). It was realized by Caicedo [3] and V-a-an-anen (cf. [12]) that
this kind of example (though with infinitely many equivalence classes) works for all
monadic quantifiers; a proof using the BEF game was given in [6].
3.1 Branching of one quantifier
In Section 2 we saw that branching a bounded quantifier does not have any effect
on its expressive power. However, the following result shows that branching usually
increases the expressive power even beyond the reach of any monadic quantifiers.
3.4 Theorem. Let Q be a monotone simple monadic quantifier. If Q is un-
bounded, then Br 2 (Q) is not definable in L !! (Q 1 ).
Putting together Theorems 2.3 and 3.4 we obtain a complete characterization of
the definability of Br 2 (Q) in terms of Q for any monotone simple monadic quantifier
Q. Using Theorem 2.5 (and the fact that Br 2 (Q f ) is definable in L !! (Br 2 (Q rel
we get the same characterization for relativizations of such quantifiers. Moreover, 2
can be replaced by any k ? 1, since we have
3.5 Lemma. If Q is a monotone simple unary quantifier, or the relativization of
such a quantifier, then Br k (Q) is definable in L !! (Br k+1 (Q)).
Proof. When simply
which is seen by considering separately the three cases (1)
1. The relativized case is similar. 2
Applying also Fact 1.1, we obtain the following characterization.
3.6 Corollary. Suppose that Q is either a monotone type h1i quantifier, or a
right monotone type h1; 1i quantifier satisfying CONS and EXT. Then the following
conditions are equivalent, for any k ? 1:
(1) Br k (Q) is definable in L !! (Q).
(2) Br k (Q) is definable in L !! (Q 1 ).
(3) Q is bounded.
In [9], Hella and Sandu proved, modifying a model construction by Fagin [5],
that connectivity of (finite) graphs is not definable in terms of monadic quantifiers.
Their proof implies a special case of Corollary 3.6: Br 2 (most) is not definable in
Here we will use a simple trick to modify this proof so that it
works for any unbounded quantifier Q f .
3.7 Definition. Let n be a natural number and E) a graph. We say
that A is n-separable if there exist subsets C; D ' A such that
(C \Theta D) " by K f the
class of all graphs A which are f(jAj)-separable.
Here all graphs are assumed to be undirected, but not necessarily irreflexive.
Thus, a structure (A; E) is a graph if E is a symmetric binary relation on A,
possibly containing self-loops (a; a).
Observe now that a graph (A; E) is in the class K f if and only if its complement
graph E) is in the quantifier Br 2 (Q f ). Hence, we have
3.8 Lemma. For any function f the class K f is definable in the logic
We shall now define two families of graphs that are the heart of the proof of
Theorem 3.4.
3.9 Definition. Let q , r and s be natural numbers, and let P , P 0 , R and
S be mutually disjoint sets of cardinalities respectively.
Assume further that
1. We define two graphs A q;r;s = (A; E) and B
g.
In the case simply by A q and B q .
Thus, one can visualize the graphs A q;r;s and B q;r;s as follows. A q;r;s consists
of a cycle (with self-loops) of length two 'boxes' R and S containing
r and s elements, respectively. Each element in S is connected by an edge to all
elements of A (including itself), whereas the elements in R are not adjacent to any
other elements than those in S . The graph B q;r;s is similar, except that instead of
the big cycle it contains two cycles of length 2
3.10 Lemma. For all natural numbers q , r and s, Duplicator has a winning
strategy in the game BEF q
Proof. We start by observing that the subsets R and S of the universe of A q;r;s
and B q;r;s can be omitted in this proof without loss of generality: Duplicator has a
winning strategy in BEF q only if he has one in BEF q
Indeed, the mapping f 7! f [ id R [ id S for each bijection
any winning strategy of Duplicator in BEF q to a winning strategy
in BEF q On the other hand, if Duplicator wins the game between
the larger structures A q;r;s and B q;r;s , then he wins the game between A q and B q
simply by choosing the restrictions of his bijections to the set P . Hence, it suffices
to show that Duplicator can always win the game BEF q This was already
done in [9] (for cycles without self-loops), but for the sake of completeness we give
here a new proof.
For each k ! be the bijection defined by
ae
(Here we are stipulating that if t - similarly for e i .)
Thus, g k arises by splitting the big cycle in A q into two halves and mapping each
of these halves, in a uniform way, onto one of the small cycles in B q . We will show
below that Duplicator wins the game BEF q choosing bijections of the
form g k for suitable k .
Before describing this winning strategy we need to introduce some auxiliary
concepts. Let C be a subset of P and k and l integers ! 2t. We say that k and
l are C -equivalent if g l (a) = g k (a) for every a 2 C . The splitting points of g k are
. The distance of C from the splitting corresponding to g k
is
splitting pointg;
denotes the usual distance between elements in a graph. Furthermore,
for each a 2 P , we denote by h k (a) the splitting point which is closest to a. Note
that if d k (C) ? 0, then the restriction of the bijection g k to the set C [ fag is a
partial isomorphism A q ! B q for any a 2 P .
We claim now that Duplicator can choose his bijections f in the
game BEF q in such a way that, for each 1 - i - q ,
(1) there is k ! 2t such that f
g-equivalent to f
where a are the elements chosen by Spoiler. This constitutes the
promised winning strategy for Duplicator, since condition (2) implies that the mapping
is the restriction of f q to the set fa
and this restriction is a partial isomorphism by condition (1) for . The claim
is proved by induction on i:
(i) We let f note that conditions (1) and (2) are trivially satisfied
(ii) If a is the unique natural number ! 2t
such that k+2 q\Gamma2
assume as induction hypothesis that conditions (1) and
(2) hold for the bijection f . There are two possibilities: If h k (a i
g, we choose f l for . Then we have
d l (fa
and since there are no elements of fa l or between
c t+k and c t+l , g l is g-equivalent to g k . In the case h k (a i
we let f l for conditions (1) and (2) are seen
to hold by a similar argument.Proof of Theorem 3.4. Note first that in the graph B q;r;s there are no edges
between the sets
whence B q;r;s is (t+r)-separable. On the other hand, A q;r;s is not (t+r)-separable,
since if C; D ' A are sets of cardinality t +r , then either there is an element a of S
in C or D , or there are elements 1g.
In the former case, there is an edge between a and every element of C and D , and
in the latter case, there is an edge between c i and c j (here is where the self-loops
are used).
Now given Q f with f unbounded we can choose n such that t - f(n) - t.
equals the size of the graphs A q;r;s
and B q;r;s , and . By the observation above, B q;r;s is f(n)-separable,
but A q;r;s is not. From Corollary 3.2 and Lemma 3.10 it follows that the class K f is
not definable in L !! (Q 1 ). Since, by Lemma 3.8, K f is definable in L !! (Br 2 (Q f )),
it follows that Br 2 (Q f ) is not definable in L !! (Q 1
3.2 Branching of several quantifiers
We shall now extend the characterization in Corollary 3.6 to the branching of more
than one quantifier. The first thing to observe is that if both f and g are unbounded,
it does not necessarily follow that Br(Q f ; Q g ) is undefinable in L !! (Q f ; Q g ). For
example, let f(n) be n=2 if n is even and n+1 otherwise, and let g(n) be (n+1)=2
if n is odd and n+1 otherwise. Then Br(Q trivially false of every relation,
hence definable in L !! , although Br 2 (Q f ) and Br 2 (Q g ) are both undefinable in
What we need for ) is that f and g are 'jointly unbounded' in the sense
that the proof of Theorem 3.4 can be modified
to show that Br(Q f ; Q g ) is not definable in L !! (Q 1 ). And in fact the converse also
holds: if f; g are not jointly unbounded it can be shown that Br(Q f ; Q g ) is definable
in L !! (Both of these claims will follow from from Theorem 3.12 below.)
But these observations on the branching of two quantifiers do not generalize
immediately to the branching of k quantifiers. First, the condition on f; g; h of
not being jointly unbounded in the above sense turns out to be too weak to permit
the conclusion that Br(Q f ; Q
Lemma 3.5 does not generalize directly to the branching of several quantifiers. This
is because on a model A where
false, whereas if
If we know that h(n) is never 0 or n definable in terms of
as in the proof of Lemma 3.5, but not necessarily otherwise.
It turns out, however, that with a more careful generalization of the notion of
(un)boundedness to sequences of functions, we can obtain a necessary and sufficient
condition for the definability of the branching of k quantifiers.
3.11 bounded if there exists a number t
such that for all n, either
holds for at most one i. Otherwise hf
We also say that
are (un)bounded under these
circumstances.
The relation to the previous concept of boundedness for one function is the
(observe that if P holds of f i for at most one i, k ? 1, and all the f i are equal,
then P does not hold of any f i ). Also, note that if each of f
or even if all but one of them are bounded, then hf
The following theorem generalizes Corollary 3.6.
3.12 Theorem. Let hQ be either a sequence of monotone type h1i quan-
tifiers, or a sequence of right monotone type h1; 1i quantifiers satisfying CONS and
1). Then the following conditions are equivalent:
definable in L !! (Q 1 ).
Proof. (outline) Let hQ
i.
Claim: There are such that for every t there is n
such that
(i) for all l , f l (n) 6= 0 and f l (n)
For, by the unboundedness of hf holds that for every t there is n and
a pair such that (i) and (ii) hold. But there are only finitely many
pairs so for at least one of them, (ii) holds for infinitely many t. From this the
readily follows.
Let, be as in the Claim. Note that now we are essentially back
to the case mentioned above with two 'jointly unbounded' functions. The proof of
Theorem 3.4 is modified as follows. In the two models A q;r;s and B q;r;s , split the
into two subsets R 1 and R 2 with r 1 and r 2 elements, respectively. R 1 and
need not be disjoint but their union is R . Expand the models to A q;r 1 ;r 2 ;s and
by adjoining two unary predicate symbols P 1 and P 2 , which in A q;r 1 ;r 2 ;s
are interpreted as P respectively, and in B q;r 1 ;r 2 ;s as
and elements in R 1 and R 2 are only connected to elements in
S , Duplicator still has a winning strategy in the game BEF q
Consider the sentence
Take any quantifier depth q and choose n such that (i) and (ii) of the Claim hold.
Say
So we take R R of size r 2 , and R 1 as a subset of R of size r 1 . Then n is the
size of the models A q;r 1 ;r 2 ;s and B q;r 1 ;r 2 ;s and f i . It is
then easy to see, using the fact that none of f 1 that the
sentence above is true in B q;r 1 ;r 2 ;s but false in A q;r 1 ;r 2 ;s .
Assume that hf is bounded and let t be the bound. For
i be L !! (Q f i )-sentences such that (cf.
the proof of Theorem 2.3) in a model with universe A,
Let Finally, let \Phi s be a list of all
conjunctions built up from the sentences ' i , - i , ' r
which specify the value
of f i (jAj) for all but one i, and also state that f i (jAj) is not jAj + 1 or 0 for any i.
It follows from the assumption that in any model, either \Theta or \Xi or one of
In models of \Theta the branching sentence
is false, and in models of :\Theta - \Xi it is true. Moreover, we make the following
Claim: For each \Phi j there is a sentence \Psi j in L !! (Q f 1
such that in models
of \Phi j ,
?From this it follows that the branching sentence is logically equivalent to the
sentence
(:\Theta - \Xi) -
s
Proof of the Claim: An example will suffice to give the idea. Suppose that
and that \Phi j says that f 2 that none of f 1 (jAj),
(written semi-formally) is
9 distinct y
(We have and the
conjunct " x 3 62 fz above.) For this sentence says that there are sets Y
and Z g) such that jY
Using the monotonicity of Q f 1
one sees that this is the same as saying that there
are sets X;Y;Z such that jY
which, by the monotonicity of Q f 2
and
, is precisely what the branching sentence
holds.
This proves the Claim, and thereby the Theorem in the unrelativized case. The
case with relativized quantifiers is similar (cf. the proof of Theorem 2.5). 2
4 Definability of Ramseyfication
In this section we show that the Ramsey lift Ram k+1 (Q) of an unbounded quantifier
Q is not definable in L !! (Q). So the situation is analogous to the case of the
branching lift: the lift of Q is definable in L !! (Q) if and only if Q is bounded.
However, in two important respects our results about the Ramsey lift are stronger.
Namely, we prove that for unbounded Q the lift Ram k+1 (Q) is not definable even
in
Recall that L !
1! is the fragment of the infinitary language L1! in
which every formula contains finitely many different variables only, and Q k is the
family of all k-ary generalized quantifiers. Thus we can prove the undefinability
of Ram k+1 (Q) even with respect to infinite disjunctions and conjunctions and even
with arbitrary k-ary generalized quantifiers.
The main interest of L !
is in the fact that it contains various fixpoint
extensions of L !! (Q k ) (see [7, 11]). Intuitively speaking, L !
by allowing recursive definitions.
In Section 3 we introduced the game BEF q (A; B). The point of this was that
if Duplicator has a winning strategy in BEF q (A; B), then A j q
B. We shall
now recall a modification BP l
k (A; B) of BEF q (A; B) from [7] in order to get a
criterion for A j L l 1! (Q k ) B.
The k -bijective l -pebble Ehrenfeucht-Fra-iss'e game, BP l
k (A; B) is defined as fol-
lows: In each round q of the game Duplicator chooses first a bijection f
and Spoiler responds by choosing sets C q ' A and D q ' A so that jD q
and jC q [ D q j - l . Intuitively speaking, Duplicator claims that f q is an isomorphism
and Spoiler tries to dispute this by pointing to the part C q [ D q of A where
he thinks f q does not preserve structure. To check this out the referee defines
(letting rule dictates that Spoiler has to
play in such a way that C q ' dom(p wins the game if for all q the
relation p q is a partial isomorphism A ! B. Spoiler wins if this is not the case, or
if Duplicator cannot make his moves, i.e., if there are no bijections
The difference between BP l
is the following: In the
latter game all moves of Spoiler remain in the game and Duplicator has to create
bigger and bigger partial isomorphisms, whereas in the former game Spoiler can
only up to l previously played elements so the task of Duplicator is easier
but, on the other hand, Duplicator does not know how many moves the game has.
The game BP l
introduces the new feature that Spoiler can let the set D q of
"new" elements contain up to k elements.
4.1 Proposition. A j L l 1! Duplicator has a winning strategy in the
game BP l
Proof. See the proof of Proposition 3.1 and the proof of Corollary 5.9 in [7]. 2
4.2 Corollary. Let Q be a quantifier. If for some sentence ' of L !! (Q) and for
all natural numbers l there exist structures A and B such that A
and Duplicator has a winning strategy in BP l
then Q is not definable in
We shall consider the lift Ram 2 (Q) first, because the construction behind our
result on the general case of Ram k (Q) is different.
4.3 Theorem. If f is unbounded, then Ram 2 (Q f ) is not definable in L !
Proof. Let l - 1 be arbitrary. We show that Ram 2 (Q) is not definable in
The proof is based on a modification of the proof of the main result
of [2]. As in [2], let X be the colored graph which has the following
vertices:
ffl a
for each subset S of ng of even cardinality.
ffl The vertices a i and b i have the same color i and are called mates of each
other,
ffl The vertices m S are colored magenta,
ffl If i 6= j , then a i and a j have different color,
and the following edges:
ffl a i and m S are joined by an edge if i 2 S ,
are joined by an edge if i 62 S .
The relevant properties of these graphs are ([2]):
ffl For any even number of pairs there is an automorphism of X n which
swaps a i and b i for these i and leaves other a j and b j fixed.
Every automorphism of X n is obtained in this way.
2. Let T be a copy of K n , i.e. the complete graph with n vertices.
We define a new graph G as follows: For each vertex v of T, we replace v by a copy
X(v) of X n\Gamma1 . These copies are called gadgets. We endow X(v) with an additional
color which is different for different v . For each w 6= v in T we select one pair
from X(v) and one pair fa i(w;v) ; b i(w;v) g from X(w), in such a way
that all selected pairs in each gadget are distinct. Then we connect with an edge
a i(v;w) to a i(w;v) and b i(v;w) to b i(w;v) . This ends the description of G. The graph H
is defined similarly, except that for one edge (v T, we create a "twist" by
connecting a i(v 0 ;w 0 ) to b i(w 0 ;v 0 ) and b i(v 0 ;w 0 ) to a i(w 0 ;v 0 ) .
Note that because of the coloring, an automorphism of G or H induces an
automorphism of each gadget, and vice versa. The crucial properties of G and H
are:
ffl For any even number of edges of T there is an automorphism
of G (H) which twists f(v leaves other edges
fixed. Every automorphism of G and H is obtained in this way.
ffl For any edge (v; w) of T there is an isomorphism G   ! H, where G   is
obtained from G by twisting (v; w) and leaving other edges fixed.
ffl G and H are not isomorphic.
Since f is unbounded, there is a natural number m so that d -
be the disjoint union of G and two complete
graphs K u and K v , where
Likewise, let H 0 be the disjoint union of H, K u and K v . In both graphs the clique
K u is colored beige and K v violet. Note that the number of vertices of both G 0
and H 0 is exactly m.
The automorphisms of G 0 consist of an automorphism of G plus permutations
of K u and K v . The same holds for H 0 . Thus all the automorphisms of G 0 and H 0
are known. The same is true of isomorphisms G 0   ! H 0 , where G 0   is obtained
from G 0 by twisting an edge (v; w) of T and leaving other edges fixed.
We shall now show that G 0 j L l 1! by describing a winning strategy of
Duplicator in BP l
The task of Duplicator is to choose bijections G
Suppose Duplicator has played f q\Gamma1 , Spoiler has played C q\Gamma1 and D q\Gamma1 and the
referee has defined which is indeed a partial
We assume that Duplicator found f
by choosing a vertex v q\Gamma1 from T, twisting an edge adjacent to it and letting f
be the arising isomorphim onto H 0 . Naturally, v q\Gamma1 had to be chosen carefully.
Now, Duplicator chooses v q 6= v q\Gamma1 so that X(v q ) does not meet C This
is possible because n ? l + 1. Then he twists the edge (v q ; v q\Gamma1 ) and lets f q be
the arising isomorphism onto H 0 such that p q\Gamma1 ' f q . Next Spoiler plays C q and
D q and the referee defines p This is a partial isomorphism
is a singleton and no edge with one end in dom(p
twisted when f q was defined. This ends the description of the winning strategy of
Duplicator in BP k
ending the proof of G
We shall next describe the sentence of L !! (Ram 2 (Q)) that separates these two
graphs. The sentence stipulates the existence of a set which contains all beige
elements and exactly one element from the magenta part of each gadget X
Once we have this one fixed element x in the magenta part of a gadget, we can
divide each pair (a into the element with an edge to x - call it "lower" - and
the element without an edge to x - call it "upper" . The sentence we need says:
There is a set X such that jXj - f(m) and any two distinct elements x and y from
1. x is magenta or beige,
2. If x and y are not beige, then they are in different gadgets,
3. If there is a connection from the gadget of x to the gadget of y , it connects
"upper" elements to "upper" elements.
To see that this sentence really separates G 0 and H 0 we first note that the sentence
is true in G 0 , since we can let X consist of all beige elements plus the element m ;
from all gadgets. Then On the other hand, suppose such a
set X existed in H 0 . Since elements of X are either beige or in different gadgets,
actually consists of exactly the
beige elements and exactly one vertex from the magenta part of each gadget. This
element has the form m S for some set S of even cardinality, so the a i for i 2 S are
"lower". Now, in each gadget, flip the even number of pairs (a leave
the others. This results in an automorphism h of H 0 such that, in each gadget,
But with respect to m ; , all the a i are "upper". Since part 3 of the
sentence is true (for h(x) and h(y)), it follows that H 0 must be isomorphic to G 0 ,
which is a contradiction. Thus the sentence is false in H 0 , and the proof is finished.4.4 Theorem. If f is unbounded, then Ram k+1 (Q f ) is not definable in L !
Proof. The case Theorem 4.3, so we assume k ? 1. Fix l - 1. We
use the models constructed in [7]. By general results
in [7] we have A j L l 1! (Q k ) B. By [7, Corollary 8.8] A and B can be separated by
We shall make a little modification to the proof of
[7, Corollary 8.8] in order to cover an arbitrary unbounded f .
Let x be the size of the graph G. Note that A has a homogeneous subset of
cardinality does not. With this in mind, and since f is unbounded,
we choose an n with
extend the model A with two disjoint sets U and V , where jU
and f(n). The elements of U are colored beige and the elements
of V violet. The same extension is applied to B. We get two new models A 0 and
. We can separate these models with
the sentence Ram k+1 (Q)x is the
disjunction of /(x Corollary 8.8] and the formula " x 1 is beige".Combining Theorems 2.3 and 4.4 we obtain a complete characterization of the
definability of Ramseyfication for all monotone simple monadic quantifiers. And
as in the case of branching, the same characterization holds also for relativizations
of such quantifiers (this follows from Theorem 2.5 and the fact that Ram k (Q f ) is
definable in L !! (Ram k (Q rel
f ))).
4.5 Corollary. Suppose that Q is either a monotone type h1i quantifier, or a
right monotone type h1; 1i quantifier satisfying CONS and EXT. Then the following
conditions are equivalent, for any k - 1:
(1) Ram k+1 (Q) is definable in L !! (Q).
(2) Ram k+1 (Q) is definable in L !! (Q k ).
(3) Q is bounded.
5 Definability of resumption
We do not have as strong results for Res k (Q) as for Br k (Q) and Ram k+1 (Q) above.
In fact, it is proved in [11] that for type h1i Q, Res k (Q) is always definable in
extends to resumptions of any monadic quantifiers). But we prove
that if f is unbounded in a sense which is appropriate from the resumption point of
view, then Res k (Q f ) is not definable in L !
and hence not in L !! (M), where M is the collection of all monotone type h1i
quantifiers. For this result we need again a new version of an Ehrenfeucht-Fra-iss'e
type game from [11].
Ig be a family of type h1i quantifiers, A and B two
structures, and l a positive integer. The game MEF l (Q; A;B) has the following
rules: There are l pairs of pebbles. During the game Spoiler may take a pebble
and put it on an element of one of the models, and then Duplicator has to take the
corresponding pebble and put it on an element of the other model. If all pebbles
have been used already, Spoiler can remove one of his pebbles from one of the models
and reposition it on another element of one of the model. In such a case Duplicator
has to reposition the corresponding pebble on some element of the other model.
These pebble moves are called elementary moves.
There is another type of move that Spoiler can choose to make. This is called
a quantifier move. In this move Spoiler takes a pebble, one of the structures A
and B, say A, a quantifier Q j from the family Q, and a subset X of the universe
A of A such that the structure (A; X) is in the quantifier Q j , and the set X is
invariant under all automorphisms of A that fix all pebbled elements. Duplicator
must respond by choosing a subset Y of the universe of the other structure (in this
case Y must be a subset of the universe B of B) such that the structure (B; Y )
is in the quantifier Q j . Then Spoiler places the pebble on an element b 1 2 Y and
Duplicator must respond by placing a pebble on an element a 1 2 X .
In each round of the game Spoiler first makes an elementary move or a quantifier
move and then Duplicator responds as described above. This is repeated indefinitely.
After each round the referee checks if Spoiler has won already. For this, let a i and
, be the elements of A and B respectively pebbled by the two
players using the up to k pebbles available. If the mapping a
to be a partial isomorphism between A and B, then Spoiler wins. Otherwise, the
game goes on. If the game lasts for infinitely many moves without Spoiler winning,
then Duplicator is declared the winner.
5.1 Proposition. ([11]) Let Ig be a family of monotone type
quantifiers, A and B two finite structures, and l a positive integer. Then the
following statements are equivalent:
(3) Duplicator has a winning strategy for the game MEF l (Q; A;B).
5.2 Corollary. ([11]) Let Q be a quantifier and Q a family of monotone type h1i
quantifiers. If for some sentence ' of L !! (Q) and for all natural numbers l there
exist structures A and B such that A and Duplicator has a winning
strategy in MEF l (Q; A;B), then Q is not definable in L !
1! (Q).
We shall now give some examples concerning the definability of Res k (Q f ) in
The examples display characteristic features of resumption in this respect.
5.3 Proposition. Both boundedness of f and unboundedness of f are consistent
with Res k (Q f ) being definable in L !! (Q f ), but neither condition is sufficient or
necessary for this to hold.
Proof. Suppose is a k 'th power and
Then f is bounded and Q f is not first order (cf. Theorem 2.1), but Res k (Q f )
is. Hence Res k (Q f ) is trivially definable from Q f . Thus boundedness is consistent
with Res k (Q f ) being definable in L !! even when Q f is not.
To see that boundedness is not sufficient for Res k (Q f ) to be definable from Q f ,
suppose is the k'th power of a prime and
Then f is bounded and Q f is not first order. Moreover, Res k (Q f ) is not definable
from Q f , as the following argument shows: We can use Res k (Q f ) to define the
property "the size of the universe is a prime". But we can use Corollary 5.2 to
show that this property is not definable from l is a natural number.
l be a prime such that wins the game
Unboundedness of f is consistent with Res k (Q f ) being definable in L !! even
when Q f is not. To see this, suppose is a k 'th power and
otherwise. Then f is unbounded and Q f is not first order, but Res k (Q f ) is.
Finally, suppose is the k'th power of a prime and
otherwise. Then f is unbounded, Q f is not first order, and Res k (Q f ) is not definable
from Q f , because "the size of the universe is a prime" is definable from Res k (Q f ),
but not from Q f . 2
5.4 Definition. Let f be a function. The function f 0 is said to be
determined by f if for all m;n
5.5 Proposition. Suppose f is bounded and f(n k ) is determined by f . Then
Res k (Q f ) is definable in L !! (Q f ).
Proof. Let m, - , ' p , / q (p ? 0; q - 0) be as in the proof of Theorem 2.3,
and let '
sentence in L !! saying of a k-ary predicate R that the
number of k-tuples it contains is at least i (jAj k \Gamma i). By assumption there are
functions g and h such that f(n k
Res k (Q f )x equivalent to the L !! (Q f )-sentence
i!m
i!m
)The condition of Theorem 5.5 holds, for example, for the following
divides n
Thus Res k (Q fp ) is definable from Q fp . By a result of M. Mostowski ([17]), resump-
tions of the stronger divisibility quantifiers
divides the number of elements x satisfying OE(x):
are likewise definable from the quantifiers themselves.
is unbounded on X , if
is bounded on X .
The following theorem is the main result of this section:
5.7 Theorem. Suppose f is unbounded on fn k 2. Then
Res k (Q f ) is not definable in L !
Proof. For every m there is an n so that m - f(n k m. This f(n k ) is
either - [n k =2] or ? [n k =2]. One of these possibilities occurs infinitely often, and
hence we have
or
We start by assuming (1) and indicate at the end of the proof how to handle the
case that (2) holds.
Suppose are functions and l is a natural number. We are going to
prove that Res k (Q f ) is not definable in L l
consist of intervals of the following form:
We call a real a 2 [0; n] n-good, if a is not on any of the intervals in I n . A set
if each of its elements is. A direct calculation reveals that if
I is a subinterval of [0; n] of length -
there is an n-good subinterval J of I of length x. Let C
. By (1) there is an n such that
-=n .
s
s
In either case we have proved the claim.
2. There are an n-good x and a non-integer n-good y ? x on [0; n] so
that x
By Claim 1, there is an n-good subinterval I of [-] of length ? C 1 . On
the interval [-] the function F derivative
so the interval F 00 I has length ? C 1 . Hence there is a non-integer
n-good I . Now also x is n-good and x
proved.
Let a be the integer part of x, and b the integer part of y . We define now two
structures
ng
ag
bg.
3. Duplicator wins the game MEF l (fQ
The elementary moves are easy for Duplicator. Suppose then Spoiler chooses
a pebble, the model A, the quantifier Q and an invariant subset X of A with
furthermore that the pebbled elements in A are a
that Duplicator has not lost the game yet. Let the correspondingly
pebbled elements of B be b . For any set Z and d 2 f0; 1g let Z
is invariant under automorphisms of A that fix the elements
there are d 1 ; d 2 ; d 3 2 f0; 1g so that
where
Let
and
even then jjX
Therefore we can make the following inference, making use of the n-goodness of
x t. Hence jX
contrary to assumption. This inference shows that jY j - g j (n). So
Duplicator can play the set Y . Next Spoiler puts the pebble on some element y of
Y . It is now easy for Duplicator to put his pebble on an element x of X so that
the following condition are satisfied:
only if
To end the proof we have to exhibit a sentence of L !! (Res k (Q f )) which distinguishes
A and B. Consider the sentence
of L !! (Res k (Q f )). This sentence is true in A but false in B
because
a
We made the assumption that (1) holds. Suppose now (2) holds. We proceed
as above until the definition of n and -. This time we use (2) to find an n so that
we can continue as above. When we come to the sentence ', we replace it with
:Res k (Q f )x
The theorem is proved. 2
A special case of the above theorem - that Res 2 (Q f ) is not definable in L !! (Q f )
for proved in [19].
5.8 Theorem. The following conditions are equivalent for any monotone simple
monadic quantifier Q and any k - 2:
Res k (Q) is definable in L !! (M).
(2) Q is bounded on fn k !g.
Proof. Theorem 5.7 gives (1) ) (2). Assume then (2). So there is a number
m such that for all n, either
or
sentence in L !! (Q g ) (L !! (Q h )) saying that
i), and let \Phi i and \Psi i ) be as in the proof of Proposition 5.5. Then the sentence
Res k (Q f )x equivalent to the L !! (Q )-sentence
i!m
i!m
The field of definability of generalized quantifiers on finite structures is full of open
problems. Especially the polyadic quantifiers as well as the non-monotone ones
give rise to problems that no one knows how to approach. In this paper we have
considered certain polyadic lifts of monotone quantifiers, obtaining the following
results
I.
definable in L !! (Q f 1
is definable in L !!
II. Ram k (Q f ) is definable in L !! (Q f )
iff f is bounded.
III. Res k (Q f ) is definable in L !! (M) iff f is bounded on fn k !g.
I and II were also proved for relativizations of monotone simple unary quantifiers.
The following questions seem to be the most natural direction to continue the work
of this paper:
1. Find necessary and sufficient conditions for Br(Q f 1
to be definable
in
2. Find necessary and sufficient conditions for Res k (Q) to be definable in L !! (Q).
This question makes sense for non-monadic and non-monotone quantifiers, too.
3. Find necessary and sufficient conditions for Res 2 (Q f ) to be definable in L !! (Q 1 ).
(As we mentioned in the Introduction, K. Luosto [15] has proved that Res 2 (Q f )
is not definable in L !!
4. Find a suitable extension of III to relativizations of monotone simple unary
quantifiers.



--R

On branching quantifiers in English

Maximality and Interpolation in Abstract Logic
Journal of Logic and Computation

Definability hierarchies of generalized quantifiers
Logical hierarchies in PTIME

Partially ordered connectives and finite graphs

Kolaitis and J.

First order predicate logic with generalized quantifiers
On extensions of elementary logic
The hierarchy of monadic quantifiers
Computable quantifiers and logics over finite struc- tures
The logic of divisibility

Quantifiers in formal and natural languages
Relativization of quantifiers in finite models
Quantifiers in natural language - a survey of some recent work
--TR

--CTR
Jouko Vnnen, Unary Quantifiers on Finite Models, Journal of Logic, Language and Information, v.6 n.3, p.275-304, July 1997
resumption;ramsey quantifier;branching;finite model theory;generalized quantifier