Buy eBook. Buy Softcover. FAQ Policy. Show all. Table of contents 21 chapters Table of contents 21 chapters Introduction Pages Bach, Emmon et al. Quantification in Correlatives Pages Dayal, Veneeta. Once our purpose has been explained, the next question is: why use Generalized Quantification as the tool to develop a research plan for this purpose? Generalized Quantification started as a narrow concept applied to a particular problem and then, like many good ideas, took off with a life of its own. The great logician Mostowski considered the limitations of expressive power of first order logic henceforth, F OL and focused on one that seemed somewhat troublesome to him: the inability of F OL to distinguish between finite and infinite sets [76].

The concept of infinity being so important for the foundations of mathematics, he considered that F OL had to be able to capture the notion there were contrary opinions: for other people, the notions of finite and infinite sets were not purely logical notions and hence did not belong in F OL. So he considered how to add to F OL the ability of expressing infinity. The challenge was doing so in a manner that was minimal, in the sense that minimal changes were introduced to both the syntax and the semantics of the language. The interpretation of this formula is, as usual, given in terms of whether an arbitrary model M would satisfy it2.

By studying the resulting language, one could learn what the concept exactly entails. For instance, if some property can also be expressed in the extended language that could not be expressed in plain F OL, that such property must be somehow related to infinity.

A trivial example is that of finiteness, which can be expressed in the language simply by using negation on the formula above. A few years later, as part of its meta-logic studies on exactly what constitutes a logic and on what makes F OL such an important language among many possible Lindstrom revisited the issue of Generalized Quantification and realized that it could be put in a more general setting [70].

But this all changed with time. Nowadays, the concept of Generalized Quantification is heavily used in at least two communities outside its original setting: theoretical Computer Science and Formal Linguistics. Since there can be many algorithms for a given problem, careful study of the problem is needed to establish such results -which should hold for all possible algorithms that compute solutions to the problem.

In [30], Fagin introduced the idea of using some logic language to describe the problem, and studying the properties of such logic in order to determine properties of the problem. This was a significant new viewpoint, since logics are declarative languages: they simply allows us to specify what the problem is, not how a solution looks like which is what algorithms do.

Thus, the study linked issues of computational complexity with issues of expressive power in logic, and a large number of results followed, starting a subfield that is usually called declara- 2 3 For readers not acquainted with logic, chapter 2 introduces all needed basic notions. The explosion of results was facilitated, in part, by the body of knowledge that logicians had developed over time. The idea had a direct impact on query languages.

It is well known that relational query languages are simply versions more or less disguised of F OL. The limitations in expressive power of F OL have became an important issue and, since Generalized Quantifiers offer a way to overcome some of those limitations, logics with Generalized Quantifiers have been studied in depth in this setting. There, the notion of quantifier is fixed: firstorder quantifiers are a closed class, capturing only the most basic concept.

Generalized Quantifiers consider the class open: you can add new quantifiers simply by defining them, subject to some very basic rules that make sure any quantifier behaves in a logical way what this means will be defined in Chapter 3. It turns out that this is a natural way to capture properties that are not expressible in F OL; this makes Generalized Quantifiers a great tool to investigate expressive power, and to add it in a controlled manner to query languages.

Formal linguists attempt to give a description of the meaning of natural language statements in a formalized language. F OL is one of the popular choices for a target language. The inadequacies of such a choice have been known for a long time. In a work that touched most later research, Richard Montague argued that natural language could be successfully modeled with tools that were better suited for the task [26]. However, he used heavy equipment: a logic derived from lambda calculus that contained many second-order constructs.

Surely there had to be something between F OL and the sophisticated tools of Montague that was adequate for the analysis of at least some simple fragments of natural language. In , in a seminal paper, Barwise and Cooper introduced the idea of using F OL extended with Generalized Quantifiers for the formal analysis of linguistic expressions [16]. Using a suitably simplified notion of Generalized Quantification, Barwise and Cooper established a basic framework that has lasted until today and has originated its own significant body of research see, for instance, [94].

We have, then, a theoretical concept that can have practical application, and that has spanned several areas of research. Going back to the old saying that there is nothing as practical as a good theory, Generalized Quantification fits the bill perfectly. At the same time, applying the idea may not be easy. Using the concepts introduced here in a practical scenario involves being able to implement them efficiently always a strong consideration in databases , and showing its usefulness for practical purposes.

Thus, unlike past research that dealt with theoretical issues of complexity and expressive power, the aim here is to work with a suitably limited version of the concept but to show that such version can still be useful and can be implemented efficiently. This endeavor is helped by the inter-disciplinary approach mentioned above, as 1 Introduction 5 the inspiration of what version of the concept to use in queries comes from research on linguistics. And this is the other main goal here: to show how concepts and techniques developed in one field help illuminate challenges in others.

The book starts with a formal view of queries and gradually widens the scope to incorporate more and more issues about questions. To develop this program, Chapter 2 gives some basic background in logic focused on the traditional notion of quantification. The idea is to make the rest of the book accessible to readers without a background in logic, making the book as selfcontained as possible. Readers with an adequate background may skip this chapter, which only introduces elementary concepts.

Chapter 3 introduces the notion of Generalized Quantifier in fact, two definitions are given and some basic properties. We have chosen to introduce further properties later, right when they are needed, so that their motivation is clear. Chapter 4 introduces the Query Language with Generalized Quantifiers QLGQ , which provides us with a general setting in which to study issues of quantification without being distracted by this or that particular syntax. The language is a simple variation of Datalog-like notations, and hopefully most readers will have no trouble becoming familiar with it.

Chapter 5 introduces what we consider the most common case of Generalized Quantification for practical use, and concentrates on giving an efficient implementation for this case. Chapter 6 studies the use and implementation of generalized quantifier prefixes. We will see that, even in the simplest of settings, some questions come up that may not be evident on first thought. Then chapter 7 introduces, following a more linguistic motivation, the use of Generalized Quantification to deal with pragmatic issues in querying, and chapter 8 finishes the change to a linguistic setting by showing the use of Generalized Quantifiers in Question Answering.

Finally, chapter 9 sketches how Generalized Quantifiers can be used in other settings, for instance distributed computing, so prominent nowadays with the raise of peer-to-peer systems and cloud computing. While the research in this chapter is just in its beginning stages, it will hopefully be enough to show the adaptability and promise of the approach.

We close the book with a short discussion in chapter This chapter is for readers with no background in logic, and it only includes some core concepts that facilitate further reading. Propositional also called zero-order logic is the basic building block of First-Order Logic recall that we abbreviate it as F OL. Because of the recursive nature of the definition, arbitrarily complex formulas can be formed. What truly distinguishes F OL from propositional logic is quantification. In F OL, statements are made about individuals, by stating relationships that may hold among them.

### ADVERTISEMENT

In propositional logic, such an statement would be considered atomic without parts , and denoted by a single symbol, like P. In F OL, statements are no longer atomic. Since they are about individuals, though, the next thing we need is some way to tell which individuals we are talking about. F OL uses terms to denote individuals. Terms are of two basic types: constants or names that denote a certain individual unequivocally, or variables, which stand for an individual without denoting a particular one. F OL languages then, will be made up of atomic formulas constituted by relations and terms.

Such formulas can then be combined with the Boolean A. It is customary to assume an infinite set of variable symbols, usually denotes x, y, z, x1 ,. For example, when talking about natural numbers, x, y denote arbitrary natural numbers, while the constant 5 denotes a particular natural number. A vocabulary also called signature in some logic books L is a non-empty set of symbols, which are classified as: relational symbols, function symbols and constant symbols.

Some signatures may have only functions they are called algebras ; some have only relations they are called relational. We restrict ourselves to the relational, finite case here1. This corresponds to how many elements R takes.

## Strategies of Quantification

Note: a relation of arity 1 will be called a property and is customarily identified with its underlying set instead of with a set of 1-tuples. Relations of arity 2 are called binary, and so on. An atomic formula is an expression of the form R t1 ,. Note that the infix notation the operator between the terms, instead of in front of them is more customary. Note that we stated that propositions were always true or false. Formulas, on the other hand, may not always have a truth value. Different values for x will yield different truth values for the formula. Interpretations sometimes called assignments are functions from the set of variables to the domain of a structure, and are used to indicate which value a given variable is intended to take.

With an assignment, then, a formula can be given a truth value; however, most of the interest is in cases where the assignment is really not relevant -as it is arbitrary this is formally explained later. Quantification is a way to handle variables systematically and assign truth values to certain formulas.

When there is a risk of ambiguity, parenthesis are used to make formulas non-ambiguous. In fact, one of the most important characteristics of formal languages compared to natural languages is that each formula in a formal language has a unique reading, i. In natural languages, ambiguity is a fact of life and is even necessary for some purposes e. A variable that is not free is bound. Bound variables, is easy to see, are the ones tied to a quantifier. A sentence is a formula with no free variables. In both sentences, there is a variable, x, but it is bound.

Also, the structure provides a meaning for function symbols and constants in L -each constant is related to some element in the domain. In order to define this formally, we need to deal with the variables, since a formula with free variables is neither true nor false until a value has been assigned to the variables. This function is what we called an interpretation. We allow this function to extend to constants by simply making it aware of the reference of constants in the structure.

We give a few examples, to show the generality and power of this seemingly simple definition. Thus, G is a graph. Note that this is a sentence.

### Subscriber Login

This is a sentence too. That is, there is a path of length at most two between x and y. Note that this is a formula. As another, more mundane, example, assume a universe of people and a binary relation L x, y , intended to mean x loves y. A happy world indeed. Several things are important enough about the crucial definition above to warrant closer attention. First, the interpretations are infinite, since the set of variables is infinite.

However, in evaluating a formula all it matters is what happens to the variables in the formula and the number of variables in a formula is finite : Lemma 2. The final point concerns the quantifiers, our main object of study. So the bound variables in a formula are not evaluated by giving them a value through the interpretation; rather, they have to take all values for universal or pick one certain value for existential.

That is why these variables are not considered free; it is also the reason for Lemma 2. That is, bound variables are just labels to relate quantifiers to certain positions in formulas. You can see that this is the case by reasoning from the rules above. This is typical of classes defined logically. Logics talk about the structure of a model, not about the particular components -although by using constants, they may mention them, but all they can do is talk about the properties of such and such element.

And if the structures are isomorphic, for each element in one there is an element in the other with identical properties. In fact, on deciding what can be called a logic, this is a fundamental condition on the definition, called the Isomorphism Condition, that isomorphic structures cannot be distinguished by formulas of the logic. The last case is the more interesting one.

There may be a lot of other stuff going on on those structures, but this is one thing that they all are guaranteed to have in common. As seen in some of our previous examples, a formula may contain several quantifiers. When quantifiers appear in a formula, they precede are to the left of the part of the formula where the variable they bound is used.

But the only requirement is that a quantifier binding a variable appears before to the left of the first mention of that variable. We saw that for some connectives, order does not matter. As an example, assume our past example of people and the binary relation L loves. We would say that, in real life, the first sentence is much more likely to be true than the second one. The scope of a quantifier is the part of the formula which it affects, and is all the formula to the immediate right of the quantifier.

The scope of a quantifier works left-to-right, the same order in which we read. Thus, the quantifier we read first takes precedence over a quantifier that we read later. However, order among universal quantifiers is irrelevant ie. Further, the variable can be changed without affecting the semantics of the program. Note that, while quantifiers can be moved in front of a formula without quantifiers, we cannot move a quantifier in front of another, since quantifiers order does matter. Thus, when putting a formula in PNF, we always move first the leftmost quantifier, and proceed in strict order.

There are two consequences of the facts just mentioned. First, every F OL sentence can be written in prenex normal form PNF : all quantifiers in front, forming a prefix, followed by a quantifier-free sentence.

- An Andrew Crozier Reader!
- Donate to arXiv.
- Heartstone.
- Course Info?
- Advances in Near-Infrared Measurements.

So the sentence has the form Q1 x1. The following definitions make this formal. Definition 2. A formula is in prenex normal form PNF if it is in the form Q1 x1. So, one or more existential respectively, universal quantifiers that follow each other form a existential respectively, universal block. The third block consists of only one quantifier. The observations that we made before can be rephrased as follows: it is ok to move quantifiers within the block they belong to, but not across blocks. In fact, old results from [] and KW2 state that any sentence obtained from a given one by moving quantifiers within a block is equivalent to the original one, while any sentence obtained by moving quantifiers across blocks is different.

In particular, [63] proved the Linear Prefix Theorem, stating that for each two different quantifier prefixes Q1 and Q2 of the same length there is a Q1 sentence i. Then we define the following sequence of formulas: 1. The function symbols introduced in this process are called Skolem functions. Skolemization produces a quantifier-free formula, where the complexity arity of the terms created by functionals shows the original quantifier prefix. The formula 2. Theorem 2. This whole Skolemization business depends on something called the Axiom of Choice. Since we just use Skolemization to illustrate quantifier interaction and later on, to introduce non-linear prefixes we will happily assume the axiom and not worry more about it4.

Note: it is well known that natural language is very ambiguous.

## Quantification - New World Encyclopedia

Then Sentence 1 must be understood with the existential quantifier in front of the universal we are talking about one single consultant for all the companies. Note that Sentence 1 could be followed by either sentence equally well. That is, if one represents the sentence as a tree, and counts the number of quantifiers in any path between the root and a leaf, quantifier depth is the maximum such number. Also, if the sentence if put in prenex normal form, quantifier depth is simply the number of quantifiers in the formula. The reason this notion is important is the following: a variable is really a name plus a quantifier.

This means that a name alone is not really enough to tell a variable from another. Variables can be reused, and a variable can have several occurrences. As a result, the number of quantifiers does not equal 3 4 Note that this is a second-order sentence, since it quantifies over functions. Further, one can develop Skolemization for F OL sentences without the Axiom of Choice, but we will not develop this here see [66] 16 2 Basic Concepts the number of different variable occurrences in a formula or a sentence! However, the number of quantifiers in a sentence equals the number of distinct variables.

In fact, it is the quantifier scope that defines the sentence: if the same variable appears quantified twice, we must consider that there are two variables that happen to have the same name in the sentence. Of course, in order to avoid confusion each variable occurrence can only be within the scope of a single quantifier. An example of variable reuse will make the situation clear: assume, as before, a model with just a binary relation G that is, a graph. Note that when the fourth quantifier occurs, the xs after that belong to it, and the previous variable x is shadowed by this new quantifier.

This is similar to a variable in a programming language with block scopes being declared twice. Finally, note that both this sentence and the previous one have 4 quantifiers. As we stated before, it is the quantifier scope that causes the variable to be a new one -even under an old name! This is easy to prove by induction on k. Variable reuse is important for logics where the number of distinct variables is limited. Such logics called bounded variable logics [81] are important in the study of computation, since logical variables can be seen in this context as the counterpart of programming variables, which are memory locations and hence resources.

Thus, the number of variable names tells us about the minimum amount of memory that it takes to compute something computation in this context means interpreting a formula or sentence in a given model. The games introduced later can be seen as a form of computation. This is why such logics are important in the study of descriptive complexity. Number of variables and quantifier rank will be related on section 2.

However, many times we want to restrict our attention to some part of the domain. This can be accomplished quite easily in F OL. In vocabularies with constants, it is also demanded that all constants in the vocabulary are present in the substructure. Lemma 2. Assume fixed a structure A. This idea is formalized in the next theorem. It is based on two-person games, due to Ehrenfeucht and Fraisse and sometimes called Ehrenfeucht-Fraisse games. The sentence is either true or false in a given structure A. We can see establishing its truth value as a game between two players, Spoiler Abelard and Duplicator Eloise , each one taking on side: Spoiler tries to prove the sentence false and Duplicator tries to prove the sentence true.

The moves on the game consist of picking values for the variables in the sentence from among the elements in the domain of A. Because of quantifier semantics, Spoiler picks values for universally quantified variables trying to find one that falsifies the sentence , while Duplicator picks values for existentially quantified variables trying to find the right one that makes the sentence true.

Such value is usually called a witness. Hence we can determine truth value easily. Note that the game reflects the quantifier scope and dependence, as follows: if an existential quantifier precedes a universal one, Duplicator chooses an individual without knowing what Spoiler will choose in turn. Thus, the individual must be good for all individuals, as Spoiler may choose any element of the domain.

It is this dependence that Skolem functions capture formally. Games are usually played in two structures, A and B, of a common vocabulary L. Let r be a positive integer. This is a move, and is repeated r times. On each move, Spoiler choses both the structure and the element, while Duplicator only choses the element. Let ai the element in A picked in the ith move, and bi the element in B picked in the ith move.

Duplicator wins the game of length r if it has a winning strategy. Games simulate back-and-forth equivalence of depth r. The main interest of the game is the following: if Duplicator has a winning strategy for games of length r, then one cannot distinguish between structures A and B by looking at r elements at a time. Basically, number of pebbles corresponds to number of variables, and number of moves corresponds to nesting depth of quantifiers.

This will be formalized in the next section. First, we introduce some basic relations among structures. Note that this implies that an isomorphism is a bijection between A and B. All the above definitions are related; here we give only the most basic and important relations. Corollary 2. Isomorphic structures are elementarily equivalent. Let A, B be two structures. To do so, we note that isomorphisms are functions relating whole structures, but we can give a more local definition, which is interesting on its own right.

Note: the empty map is a partial isomorphism. However, they do not preserve truth for formulas with quantifiers. The intuitive reason is that atomic sentences talk about particular elements, while sentences with quantifiers talk about arbitrary elements. For example, assume our language is a binary relation symbol R. Then the atomic formula R a, b , where a, b are constants, will be true in a structure A iff it is true in a structure of similar type B, whenever A and B are related by a partial isomorphism that sends a and b to some elements in the domain of B otherwise the function would not be a partial isomorphism.

A partial isomorphism can always be extended to a total isomorphism if the structures are isomorphic. A back-and-forth system is a set of partial isomorphism of size n for each n. That is, we can build partial isomorphisms of size n no matter which elements we choose. Note that this is similar to the definition of E-F games, and hence to equivalence up to formulas of quantifier rank m. With a finite number of symbols in the language, there are only finitely many formulas of quantifier rank m up to isomorphism , and therefore one can build appropriate m equivalences.

This sentence has a finite quantifier depth, r. Then pick two structures A and B such that A has the property, B does not, but you need to look at more than r elements to determine that. Then you can give a winning strategy for Duplicator for games of length r. Using the above, one can prove that many properties connectivity of a graph, evenness, 2-colorability of graphs, Eulerian graphs5 are not expressible in F OL. As an example, let the structure be a graph, and a, b two nodes. There is no sentence that will say that a has as many neighbors as b same number.

Because there are only n rounds, we can never show the difference. As another example, think of graph connectedness. For each n, take two graphs, one being a cycle of length 2n and another one made of two disjoint cycles of length 2n. This is always possible, due to the sizes of the graphs. Spoiler cannot show that there are two nodes with no path between them in the second structure, because all paths can have at most length n. A final example is transitive closure. When one studies models, it is very convenient to do so.

- Quantification in Natural Languages - Google Libros!
- Deconstructing the Hero: Literary Theory and Childrens Literature.
- Social Security: What Role for the Future? (Conference of the National Academy of Social Insurance).
- Karl Marxs Theory of Revolution: War and Revolution.
- Submission history!

However, in the context of databases it is also very interesting to think about the finite case. It turns out that finite and infinite models are very different, for reasons we cannot explain here. The study of finite models is a fascinating subject that has taken off in the last few years, but here we can only point out a few things that are of interest to us later. Let A be a finite model, that is, a model with a finite domain A note that this implies that all relations and functions in A are also finite. Let the cardinality of A be n. Some logic admit infinite conjunctions and disjunctions and formulas not surprisingly, they are called infinitary logics.

Note, though, that these sentences are equivalent to the original ones with quantifiers only in the given model A. For a different finite model B, we need a different sentence. We can see now that the power of quantification is that it let us say something about all or some of the elements in a model regardless of the model.

As an example of this power, one may wonder if there is a smarter way to get rid of quantifiers that works in all cases. The answer is no, there is no way to always get rid of the quantifiers -although there are procedures for quantifier elimination in some cases, and it is very interesting to know in which cases the elimination is possible and in which cases it is not.

The point we want to make here, though, is that quantifiers truly contribute to the expressive power, and that is why they cannot, in general, be eliminated. Finitely isomorphic finite models are isomorphic. Intuitively, if any arbitrary m elements in one model can be put in a isomorphic relation with m elements in the other models, then the relation can be extended to all the elements. In finite models, the converse is true, so we have this: Theorem 2. In the rest of the book, we will consider finite models, since these are the most appropriate models for considering computational issues, and our focus will be in efficient implementation of quantification, which means that we will try to give effective procedures for computing sentences with quantifiers.

Working with finite models will provide a definitive advantage here! Lindstrom generalized the original idea and set the definition used nowadays [70] 1. GQs remained mostly a concept of interest for logicians until years later. In a seminal paper, Barwise and Cooper showed their importance in natural language formalization [16]. Following in a tradition started by Montague, Barwise and Cooper show how GQs are a useful and powerful tool in the formal analysis of linguistic phenomena.

This insight established an interesting area of research, which we discuss briefly in chapter 8. Also, work on descriptive complexity has produced recently a large body of results tied to GQs see [47, 65, 93] as a small sample. Finally, some work has focused on practical applications of the concept in diverse areas of Computer Science, like query languages [52, 85] , Artificial Intelligence [90], [82] and graphical interfaces [17].

The research described in this book continues in this tradition, focusing on practical uses in query languages, and Information Systems in general. In this chapter we introduce the concept of GQ formally, provide several examples and describe some basic properties. Here we focus on fixing notation and providing some basic facts that will be used in the rest of the book. Additional properties will be introduced later as needed. We introduce first the former, as it may be a bit more intuitive, and provide some examples.

Then we develop the latter definition in order to introduce some notation that will be of use later. Of course, both definitions 1 GQs are also called Lindstrom quantifiers. We consider fixed an infinite universe U, the set of all values. Definition 3. A local GQ of type k1 ,. We will use Q as a variable over GQs, and boldface for names of particular quantifiers.

We will write QtM to indicate the quantifier of type t in domain M , although later on we may drop the subscript or the superscript as we will fix one or the other for some chapters. The expression QtM A1 ,. Next we introduce several examples of GQs, including some common ones that will be used later in queries and lemmas. To simplify notation, we consider a domain M as fixed and give the local definition of the quantifier, which allows us to drop the subscript. We keep the superscript as some quantifiers share the same name while having different types; these can be considered as versions of the same idea, and they are related in a way that will be explained later on.

Quantifiers of type 2 can be identified with graph properties, in the sense that they give properties of binary relations and we can identify binary relations with graphs3. Thus, QEu denotes Eulerian graphs using the well known property that a connected graph is Eulerian iff every vertex has an even degree. We could also define other graph properties, e.

QHam 2 which holds true only of Hamiltonian graphs. I is a simple example of a property that is not first order-definable, while the quantifier H is a more complex and powerful one4. Quantifier most 1 can 3 4 Note that most of the times a graph is assumed to be loop-free and non-directed, and hence the corresponding binary relation must be irreflexive and symmetric.

H be used in chapter 6 to capture non linear prefixes. The quantifiers of type Pm,n are sometimes called the proportional quantifiers. Note that the definition of aleastn , at mostn and the proportional quantifiers are definitions with parameters, and hence each one denotes a set of quantifiers when we instantiate n -and m if needed- to two natural numbers, we obtain a particular quantifier. QE is an interesting quantifier in that it is very simple, can be added to F OL in a straightforward way, and yet it transforms the logic radically, since it is known that F OL has a law on finite models, while the logic with QE added obviously does not have this law5.

The length of a type is called the binding of quantifiers of that type. The greatest element in the type is the arity of the quantifier. Thus, GQs of type 1,. In this text, unary monadic quantifiers type [1] are called simple, and binary monadic quantifiers type 1, 1 are called standard. They are all monadic except WR , which has type [1, 2], and H, which has type [4]. Note that not every relation between subsets of the domain is considered a GQ.

Intuitively, we would like a GQ to behave as a logical operator, in the sense that it should not distinguish between elements in the domain, and nothing should be dependent on the domain M chosen. Hence our requirement that GQs are closed under bijections.

In the context of database query languages, this constraint ensures that quantifiers are generic operations, while EXT ensures its domain independence. Both are important properties for query operators [6]. We will exploit them in chapter 4 to analyze issues of safety and domain independence.

## Quantification in natural language (II)

Some authors express express this requirement as a separate axiom, and give it a name [] : Definition 3. In the context of monadic quantifiers, ISOM implies that only the sizes of the sets, as opposed to the concrete individuals, matter. That is why it is called QUANT in [97], where only one domain is considered and therefore 5 A property has a law on finite models if, as the size n of the model grows, the probability that the property holds in all models of size n goes to 0 or to 1.

A logic has a law on finite models if all the properties definable in the logic have a law. This is a strong characterization of F OL, but it fails with QE since clearly the property of being even flip-flops between 0 and 1 as n grows, therefore not converging to either. There have been several other axioms considered. Barwise and Cooper [16] propose, for natural language quantifiers, the following one: Definition 3. They call this living on a set. Other authors call quantifiers that obey this axiom conservatives.

The axiom gives the first argument a privileged role. Natural language analysis has convinced researchers that this is indeed a very useful axiom, and it is assumed in other studies of generalized quantifiers in linguistics [96, 16, 61].

However, from a purely formal perspective it creates an imbalance which is not justified in logical grounds. For instance, quantifiers like I and more are not conservative. This partially implies that the behavior of a quantifier is independent of the context, as is the case for the usual logic constants. This seems, therefore, a desirable property. EXT expresses that quantifiers are completely independent of the domain, as the following proves: Proposition 3. The idea is that under EXT the domain is irrelevant, and therefore thinking of bijections between two domains or permutations inside one capture the same notion.

The model also shows that the sets of words in real languages result in more efficient communication than randomly selected sets of words with comparable meanings. Description Thesis M. Date issued Department Massachusetts Institute of Technology. Publisher Massachusetts Institute of Technology.

Keywords Electrical Engineering and Computer Science. Search DSpace. This Collection.