GENERALIZED QUANTIFIERS

"When Frege introduced quantification, he illuminated three topics: logic, language, and ontology" (Quine).

"Quantifiers are not necessarily logical symbols. Quantifiers denote families of sets" (Jon Barwise & Robin Cooper).

---

The Logical Quantifiers
Logical quantifiers are symbols used to indicate the number of elements in a set (or domain of discourse) that have a certain property. Traditional logical quantifiers are:

• The universal quantifier. All elements of the set satisfy the property P. The notation is: ∀xP(x) (for every element x, the property P is true). For example:
  
  (∀n∈N) n≥1 (every natural number has the property that it is greater than or equal to 1).
  
  
• The existential quantifier. At least one element of the set satisfies the property P. The notation is: ∃xP(x) (there exists an element x such that the property P is true). For example:
  
  (∃n∈N) n>5 (there exists a natural number that has the property to be greater than 5)

Remarks:

• The property P(x) is written in function format, where P is the function name, x is the argument and the result of the function is V (if the property is true) or F (if the property is false).
  
  
• The universal quantifier ∀xP(x) compactly indicates P(x₁)∧.... ∧P(x_n), siendo x₁, . .. , x_n the elements of the domain, n the number of elements of the domain and "∧" the logical connector "and" (conjunction).
  
  
• The existential quantifier ∃xP(x) compactly indicates P(x₁)∨.... ∨P(x_n), siendo x₁, . .. , where x_n are the elements of the domain, n the number of elements of the domain and "∨" the logical connector "or" (disjunction).
  
  
• ∀ and ∃ are dual quantifiers. There is a relation between the two quantifiers, which can be deduced from the above two equivalences and De Morgan's laws:
  
  
  ∃x P(x) ≡ ¬∀x ¬P(x)
  (there exists a x that has the property P means that not every x does not have the property P)
  
  ¬∃x P(x) ≡ ∀x ¬P(x)
  (there is no element x that has property P means that no x has property P)
  
  
• Variables in an expression can be bound (to a quantifier) or free (do not appear in any quantifier). For example:
  
  
  ∀x (∃y P(x, y)) ∨ Q(u, v)
  (x and y are bound, u and v are free)
  
  An expression is closed if all variables are bound, and open otherwise.
  
  
• The order of quantifiers is critical in establishing meaning. When more than one variable is quantified, they are applied from the inside out (the innermost always take precedence). For example,
  
  
  ∃y ∀x P(x, y) eq. ∃y [∀x P(x, y)]
  (for some y, P(x, y) for all x) is verified for all x)
  
  
• The property can be simple or compound. For example, (∃n∈N) (Prime(n) ∧ Even(n)) (there exists a natural number that is prime and even).
  
  
• Restricted quantifiers appear in compound logical expressions. For example:
  
  All the elements of the set A belong to the set B:
  ∀x (x∈A → x∈B).
  
  Some element of the set A belongs to the set B: ∃x (i>x∈A ∧ x∈B).
  
  
• The set of elements of a set C that satisfies a property P is called a "truth set". For example, in the domain of integers, if P(x) is (x² = 4), the truth set is {−2,−2}, and in the domain of natural numbers, the truth set is {2}.
  
  
• The scope of a quantifier is the part of a statement in which the variables are bound by the quantifier. For example,
  
  
  In ∃x(P(x) ∨ Q(x)), the scope of ∃ is (P(x) ∨ Q(x)).
  
  In ∀xP(x) ∨ Q(x), the scope of ∀ is P(x).
  
  
• The following distributive dual properties are satisfied:
  
  
  ∀x(P(x) ∧ Q(x)) ≡ ∀ x P(x) ∧ ∀x Q(x)
  (∀ is distributed over ∧)
  
  ∃x(P(x) ∨ Q(x)) ≡ ∃ x P(x) ∨ ∃x Q(x)
  (∃ is distributed over ∨)

Rules of inference

• Universal instantiation.
  From ∀xP(x) we infer P(a) (being a any element of the domain).
  
  
• Modus Ponens universal.
  From ∀x(P(x) → Q(x)) it is inferred P(a) → Q(a)
  
  
• Modus Tollens universal.
  From ∀x(P(x) → Q(x) we infer ¬Q(a) → ¬P(a)
  
  
• Universal syllogism.
  De ∀x(P(x) → Q(x)) y ∀x(Q(x) → R(x)) it is inferred ∀x(Q(x) → R(x))
  
  
• Universal generalization.
  If P(a) and a is an arbitrary element of the domain, we infer ∀xP(x).
  
  
• Existential generalization.
  From P(a) we infer ∃xP(x).
  
  
• Existential instantiation.
  From ∃xP(x) we infer P(a) for some element a of the domain.

Limitations of logical quantifiers

• Limited expressive power.
  Other quantifiers in natural linguistics cannot be defined. In natural linguistics there are many quantifiers, in the sense of fuzzy or qualitative quantities (besides "all" and "some") such as: many, some, a few, a few, quite a few, most, two-thirds, half, more than half, almost all, all except n, more than 30, between 5 and 10, etc.
  
  
• Absence of theoretical criteria.
  Just as logical connectors have a precise theory underpinning them, this is not the case with logical quantifiers, starting with the notation itself, which does not clearly and formally specify the scope of application of a quantifier. Neither are bound variables clearly differentiated from free variables, nor the scope of bound variables. All this requires an external interpretation.
  
  
• There is no canonical notation.
  For example, the universal and existential quantifiers can be written in several ways:
  
  
  ∀x∈D P(x)    (∀x∈D) P(x)    ∀(x∈D → P(x))
  
  ∃x∈D P(x)     (∃x∈D) P(x)    ∃x(x∈D ∧ P(x))

History of classical logical quantifiers

• Aristotle not only invented logic, but also introduced the subject of quantification in the "First Analytics" (the third book of the Organon). He was the first to consider logical quantifiers in his natural language syllogisms: all, some and none and not all. These quantifiers are not relations between elements, but between sets of elements. They are, therefore, second-order relations.
  
  The Aristotelian quantifiers expressed in modern notation are:
  
  

  Quantifier	Contrary
  All ∀	None ¬∃
  Not all ¬∀	Some ∃

  
  
• Gottlob Frege invented formal logic, modern logic with the predicate calculus. In his 1879 Conceptography he was the first to use symbols for quantifiers to link a variable with the domain of discourse, a variable that appeared in predicates. Frege's notation for the universal quantifier was the name of the variable over a dimple contained in a horizontal line of his diagrammatic formulas: |--∪--
  
  Frege did not create an explicit notation for existential quantification, but used its equivalent as ¬∀x ¬P(x). Frege defined various quantifiers: all, some, not all, exactly n, at least n, and so on. Frege considered quantifiers as second-order relations (he called them "second-level concepts"). Predicates he regarded as first-level concepts. According to Frege, existence is a second-level and unary (or monadic) concept or predicate because it requires only one argument.
  
  Frege's symbols had a fixed meaning, and the only domain he considered was totality. He did not consider the issue of possible interpretations or models.
  
  Frege's treatment of quantification went unnoticed until Bertrand Russell made it known in his Principles of Mathematics (1903).
  
  
• In 1855, Charles Sanders Peirce and his student Oscar Howard Mitchell invented the concepts of universal and existential quantifier. The notation they used was Πx and ∑x for what is now ∀x and ∃x, respectively. They also created the concepts of bound variable and free variable.
  
  
• In 1897, Giuseppe Peano invented another notation: (x) for universal quantification and ∃x for existential. Peano's notation spread rapidly and was adopted by Russell and Whitehead in their Principia Mathematica. It was also adopted by Alonzo Church and Quine.
  
  
• In 1935, Gerhard Gentzen introduced the symbol ∀ by analogy with Peano's ∃ symbol ("A" backwards and "E" backwards, respectively). From the 1960s onwards, the ∀ symbol became de facto standard, although even today Peano's symbolism (x) is still used.

The generalized quantifiers

• In 1957, Andrzej Mostowski introduced the concept of generalized quantifier in the journal Fundamenta Mathematicae with his article "On a generalization of quantifiers". His theory of generalized quantifiers is framed within set theory.
  
  Mostowski generalized the concept of logical quantifier by means of conditions concerning the cardinalities of the subsets of a set (or the universe of discourse) by means of a unary function. If A is the universe of discourse and B a subset of A, Q_A(B ) is a quantifier Q of B over A, which indicates the cardinality of B with respect to A.
  
  
  QA(B) ↔ |A∩B|Q
  
  The definition of generalized quantifier satisfies the invariance conditions: the quantifier Q_A(B) is invariant under all permutations of A and of B.
  
  Examples of generalized quantifiers are:
  
  
  (≥5)_A(B) ↔ |A∩B | ≥ 5 (subset B of A of cardinality ≥ 5).
  
  (=3)_A(B) ↔ |A∩B | = 3 (cardinality id. = 3)
  
  (even)_A(B) ↔ |A∩B | is even (id. of even cardinality)
  
  The universal and existential quantifiers are particular cases of the generalized quantifier concept:
  
  
  ∀_A(B) ↔ |A∩B| = |B|
  ∃_A(B) ↔ |A∩B| > 0
  
  
• In 1966, Per Lindström generalized Mostowski's criterion by not distinguishing isomorphic models: the truth or semantics of an expression does not depend on the particular individuals of which it consists. A quantifier Q_A(B) is invariant under all isomorphisms. He also extended Mostowski's generalized quantifiers to polyadic ones, and established a hierarchy of generalized quantifiers.
  
  
• In 1981, Jon Barwise and Robin Cooper published "Generalized Quantifiers and Natural Language" in the journal Linguistics and Philosophy. In this article, its authors propose:
  
  
  1. Distinguish between "strong" quantifiers (all, most, almost all, not all, etc.) and "weak" quantifiers (none, a few, some, etc.).
     
     
  2. Distinguish between quantifiers referring to nouns or noun phrases (a man, no woman, several people, etc.) and quantifiers referring to determiners (one, two, all, none, some, some, etc.).
     
     
  3. Extending Lindström's generalized quantifiers to infinite quantities.

MENTAL and Quantifiers
Intrinsic and extrinsic properties

We must distinguish between two types of properties of an entity:

• Intrinsic.
  They are those that are deduced from the entity itself and not from external information. Examples: abc (sequence of length 3), 23 (number greater than 0).
  
  These properties are expressed in the form xP. For example, (abc# = 3) and (23>0).
  
  
• Extrinsic.
  They are those that are determined by external information. They are attributes, qualities or predicates. For example, "Pepe is a man".
  
  These properties are expressed in the form x/P. For example, Pepe/man.

Traditional logical quantifiers

• Universal quantizer. Every element x of C satisfies the property P.
  
  ( {⟨( x ← (x∈C ∧ xP )⟩} = C ) (intrinsic property P)
  
  ( {⟨( x ← (x∈C ∧ x/P )⟩} = C ) (extrinsic property P)
  
  Examples:
  
  
  1. Notación clásica: (∀n∈N) n≥1
     MENTAL notation:
     ( {⟨( n ← (n∈N ∧ n≥≥1) )⟩} = N )
     
     
  2. Classical notation: (∀x∈C) x is white.
     MENTAL notation:
     ( {⟨( x ← (x∈C ∧ x/white) )⟩} = C )
  
  
• Existential quantifier. Some element x of C satisfies property P.
  
  ( {⟨( x ← (x∈C ∧ xP)) )⟩}# > 0 ) (intrinsic property P)
  
  ( {⟨( x ← (x∈C ∧ x/P)) )⟩}# > 0 ) (extrinsic property P)
  
  They can also be expressed like this:
  
  ( {⟨( x ← (x∈C ∧ xP)) )⟩}≠∅ ) (intrinsic property P)
  
  ( {⟨( x ← (x∈C ∧ x/P)) )⟩}≠∅ ) (extrinsic property P)
  
  Examples:
  
  
  1. Notación clásica: (∃n∈N) n>1
     ( {⟨( n ← (n∈N ∧ n>1) )⟩}# > 0 )
     
     
  2. Classical notation: (∃x∈C) x is white
     ( {⟨( x ← (x∈C ∧ x/white) )⟩}# > 0 )

Generalized quantifiers

The universal and existential quantifier expressions can be unified and generalized by the following auxiliary generic expression, which denotes the number of elements of a set C that satisfy the selection criterion S. A particular case of S is an intrinsic or extrinsic property.

⟨( Q(C S q) = {⟨( x ← x∈C ← S))⟩} = q )⟩

It follows then that the traditional logical quantifiers can be expressed as follows:

(∀x∈C) P(x) as (Q(C P C#)
(∃x∈C) P(x) as Q(C P >0)

This notation allows expressing many other quantifiers. For example,

1. n at most: Q(C P ≤n)
   
   
2. n as a minimum: Q(C P ≥n)
   
   
3. Greater than or equal to n1 and less than or equal to n2:
   Q(C P ∈{n1...n2})
   
   
4. All elements of the sets A1...An have property P.
   
   ( Q(A1∪...∪An P (A1∪...∪An)# )
   
   
5. At least one of the elements of the sets A1...An has property P.
   
   ( Q(A1∪...∪An P >0 )
   
   
6. Q(C P 12) (12 elements of C have property P
   
   
7. Q(R r>5 ∞) (the amount of real numbers greater than 5 is infinite)
   
   We do not distinguish between numerable infinity (the natural numbers) and non-numerable infinity (the real numbers) because infinity is a quality, not a quantity.

Reflections and conclusions

• Actually, despite their name, the traditional quantifiers (∀ and ∃) do not refer to concrete quantities, but to qualitative quantities (all and some).
  
  
• Traditional logical quantifiers mix two concepts that need to be separated: logic and quantification. Quantification refers to the number of elements of a set or domain that meet a certain condition and have a property or quality of cardinality. Logic intervenes only in the selection criterion.
  
  In MENTAL, quantifiers are of a general nature and can appear in all kinds of expressions, not only logical ones.
  
  
• The symbols for logical quantifiers (∀ and ∃) were invented because no formal mathematical language was available. The definitions of the logical quantifiers in MENTAL reveal their true structure, a structure that opens the way to their generalization.
  
  
• Parameterization of expressions is the natural path to generalization of quantifiers. MENTAL expressions with quantifiers are a type of parameterized generic expressions. The "Generalization" primitive is the most important primitive, since it allows to define everything from a higher level: functions, quantifiers, logical modalities, events, aspects, agents, etc., and making use of the rest of the language primitives.
  
  It is often claimed that quantification is a subject that connects or links logic, linguistics, mathematics, computer science, and philosophy. But the real unification lies in generic expressions, which are higher-order relations.
  
  
• Expressions are clearer because the scope of the universal quantifier is perfectly defined by generic expression delimiters, and bound variables appear in boldface.
  
  
• All expressions, including predicates and quantifiers, can be modified in a dynamic operating environment.

---

Addenda
The impact of generalized quantifiers

The theory of generalized quantifiers has led to a new view of the nature of quantification, and has had major impacts in several fields:

• In the development of mathematical logic, by providing expressive power superior to standard first-order quantification.
  
  
• It has led to the creation of a new field: model-theoretic logic.
  
  
• It has provided solutions to philosophical problems, such as the issue of ideal language.
  
  
• It has produced a rapprochement between mathematical logic and linguistics, between the semantics of formal logical language and the semantics of natural language.

In MENTAL, generalized quantification is a topic that affects all formal sciences: mathematics, computer science, logic, linguistics, etc.


The analogy between quantifiers and modal logical operators

There is an analogy between quantifiers (∀ and ∃) and the modal operators of necessity (□) and possibility (♢):

Modal operators	Quantifiers
It is necessary that x: □x	All x: ∀x
It is possible that x: ♢x	There is x: ∃x
□x ≡ ¬♢¬x	∀x P(x) ≡ ¬∃x ¬P(x)

Bibliography

• Andersson, A. On second-order generalized quantifiers and finite structures. Annals of Pure and Applied Logic, vol. 115, nro. 1, pp. 1-32, 2002.
  
  
• Badia, Antonio. Quantifiers in Action. Generalized Quantification in Query, Logical and Natural Languages. Springer, 2010.
  
  
• Barwise, Jan; Cooper, Robin. Generalized Quantifiers and Natural Language. Linguistics and Philosophy 4 (2): 159-219, 1981. Disponible online.
  
  
• Barwise, Jon. Infinitary logic and admisible sets. The Journal of Symbolic Logic., 34 (2), 226-252, 1969.
  
  
• Barwise, Jon. Abstract Logics and L∞ω. Annals of Mathematical Logic, 4: 309-340, 1973.
  
  
• Barwise, Jon. Axioms for abstract model theory. Annals of Mathematical Logic, 7, 221-265, 1974.
  
  
• Does, van derJaap; Eijck, Jan van (eds.). Quantifiers, Logic, and Language. CSLI (Center for the Study of Language and Information), 1996.
  
  
• Gärdenfors, Peter (ed.). Generalized Quantifiers. Linguistic and Logic Approaches. Springer, 1987.
  
  
• Glöckner, Ingo. Fuzzy Quantifiers. A Computational Theory. Springer, 2010.
  
  
• Leonetti, Jungl, Manuel. Los cuantificadores. Arco Libros, 2008.
  
  
• Lindström, Per. First Order Predicate Logic with Generalized Quantifiers. Theoria 32: 186-195, 1966.
  
  
• Lindström, P. On extension of elementary logic. Theoria 35, 1-11, 1969.
  
  
• López Palma, Helena. La interpretación de los cuantificadores. Aspectos sintácticos y semánticos. Visor Libros, 2000.
  
  
• Magáin, Hugo. Racionalidad, Lenguaje y Filosofía. UNAM (Universidad Nacional Autónoma de Mexico), Instituto de Investigaciones Filosóficas. Fonde de Cultura Económica, 1998.
  
  
• Mostowski, Andrzej. On a generalization of quantifiers. Fundamenta Mathematicae. 44: 12-36, 1957.
  
  
• Peters, Stanley; Westerståhl, Dag. Quantifiers in Language and Logic. Oxford University Press, 2008.
  
  
• Quine, Willard van Orman. Filosofía de la lógica. Alianza Editorial, 1998.
  
  
• San Ginés Ruiz, Aránzazu. Cuantificadores generalizados. De Mostowski a Barwise y Cooper. Editirial Académica Española, 2012.
  
  
• Väänänen, Jouko (editor). Generalized Quantifiers and Computation. Springer, 1999.
  
  
• Väänänen, Jouko. Generalized Quantifiers. Bulletin of the European Association for Theoretical Computer Science, 62, 115-136, 1997. Disponible en Internet. (Está incluido también en Generalized Quantifiers and Computation.)
  
  
• Van den Berg, Martin. Dynamic Generalized Quantifiers. Internet.