sgo.to

Relational Theory of Determiners

Sam Goto

This is an open study on the semantics of quantified noun phrases and reasoning over them.

More specifically, we are interested in understanding the semantic contributions that generalized quantifiers make in the representation of discourse and what kinds of reasoning tasks can be performed over them.

Generalized quantifiers extend the universal (every) and existential (some) quantifiers of first order logic to bind variables using different operators.

In natural language, they appear as determiners attached to noun phrases to describe quantities. For example:

  • Every man is mortal.
  • Some men are rich.
  • No animal is a plant.
  • At least 3 men are alive.
  • At most 4 players are injured.
  • Between 3 and 10 countries are members of the United Nations.
  • Most birds fly.
  • Few players are injured.
  • Many politicians lie.
  • Only citizens can vote.
  • All birds but penguins can fly.
  • No student but John can pass.
  • Both John and Mary own the restaurant.
  • Enough students have passed.

So far, we've been using first order logic to cover our classifical quantifiers (all and exists).

Unforunately, it is provable that many determiners that appear in natural language (Most As are Bs, At least 3 As are Bs, etc) can't be represented in first order logic (reference).

So, if first order logic isn't a meaningful representation for natural language quantifiers, what is?

Set Theory

The Relational Theory of Determiner Denotations is based on the observation that the cognitive interpretations of many quantifier expressions (determiners) in natural languages seem to follow similar relationships to those in set theory.

For example:

Every men is mortal.

Some men are mortal.

No men is mortal.

Only citizens are voters.

Most players are fine.

Few (the-minority-of) players are fine.

Exactly 2 players are injured.

At least 2 players are injured.

At most 2 players are injured.

All birds but penguins can fly.

To sum up, here are a few common quantifiers that appear in natural language and their relationship with the sets they operate on:

Quantifer Relation Example
all(X, Y) X ⊆ Y All men are mortal.
some(X, Y) X ∩ Y != ∅ Some men are rich.
no(X, Y) X ∩ Y = ∅ No mammals are plants.
not-all(X, Y) X - Y != ∅ Not all birds are fliers. (note: same as "some-not")
at-least(N, X, Y) ` X ∩ Y
at-most(N, X, Y) ` X ∩ Y
more-than(N, X, Y) ` X ∩ Y
fewer-than(N, X, Y) ` X ∩ Y
many(X, Y) ` X ∩ Y
exactly(N, X, Y) ` X ∩ Y
the-majority-of(X, Y) ` X ∩ Y
the-minority-of(X, Y) ` X ∩ Y
only(X, Y) Y ⊆ X Only citizens are voters.
all-but(X, Z, Y) Z ⊆ X and (X - Z) ⊆ Y All birds but penguins are fliers.

Reasoning

Now that we established that quantifiers can be represented as relationships between sets, lets explore what kinds of reasoning tasks we would like to apply to them.

Take the following tasks as examples:

  • Set Relationship: Are Ps Qs? Most Ps are Qs.
  • Quantification: How many Ps are Qs? There are at most / at least / exactly N Ps that are Qs.

For example:

  • All birds but penguins can fly.
  • Penguins are birds.
  • Seagulls are birds.
  • Can penguins fly?
  • I don't know (makes an open world assumption).
  • Can seagulls fly?
  • Seagulls can fly [because seagulls are birds and all birds but penguins can fly].
  • How many birds can fly?
  • All birds but penguins can fly.

Aristotelian Syllogisms

Before we look at all of the generalized quantifers, lets look at the syllogisms of:

  • ALL(A, B)
  • NO(A, B)
  • SOME(A, B)
  • SOME-NOT(A, B)

A categorial syllogism consists of three parts:

  • Major premise
  • Minor premise
  • Conclusion

For example:

All men are mortal. All greeks are men. All greeks are mortal.

No reptiles are mammals. All snakes are reptiles. No snakes are mammals.

It is visually easy to verify when some inference is invalid. Take as an example the following:

Some men are rich. All greeks are men. Some greeks are rich.

As well as the following:

Some men are rich. All greeks are men. No greeks are rich.

For any predicate A, B and C and quantifier Q of every, some-are, none and some-arent, can be generalized as:

  • Q1 As are Bs.
  • Q2 Cs are As.
  • Q3 Cs are Bs.

There are 256 combinations of Q1, Q2, Q3, A, B, C of which only 24 are valid inferences. Here are a few examples:

  1. all M are P, all S are M, thus all S are P.
  2. all M are P, all S are M, and there is some S, thus some S are P
  3. all M are P, all M are S, and there is some M, thus some S are P
  4. all P are M, all M are S, and there is some P, thus some S are P
  5. all P are M, and no S is M, thus no S is P
  6. all P are M, and no M is S, thus no S is P
  7. ...

If we added the rest of the generalized quantifiers to this analysis, how many - and which - inferences would be valid?

In order to answer that question, lets look at ways to categorize all generalized quantifiers. The three ways we'll categorize them are:

Monotonicity

Monotonicity is one way to categorize quantifiers.

Take, for example, the ALL(A, B) quantifier (whose relation is inclusion A ⊆ B):

All humans are mortal. All greeks are humans. Therefore, all greeks are mortal.

A function F is called monotone increasing relative to an ordering ≤1 of the arguments and an ordering ≤2 of the values iff x ≤1 y ⇒ F(x) ≤2 F(y). In terms of generalized quantifiers, ”≤1“ is inclusion ⊆ and ”≤2“ implication →.

A quantifier Q is right-side monotone increasing if and only if B ⊆ B' ⇒ Q(A, B) → Q(A, B').

ALL(A, B) is right-side monotone increasing (write ALL(A, B)↑), for any set A, B and B'.

All Bs are B's. All As are Bs. Therefore, all As are B's.

NOTE: sanity check if I got this right for ONLY.

Take ONLY(A, B) (meaning B ⊆ A) for example.

All Bs are B's. Only As are Bs (B ⊆ A). It is clearly not the case from the example bellow that only As are B's (B' ⊆ A) isn't true for every B and B's (counter example). So, ONLY(A, B) is not right-side monotone increasing.

A quantifier Q is right-side monotone decreasing if and only if B' ⊆ B ⇒ Q(A, B) → Q(A, B').

NOTE: sanity check if I got this right for ONLY.

Going back to the case of ONLY(A, B) (meaning B ⊆ A).

All B's are Bs. Only As are Bs (B ⊆ A). It has to be the case that only As are B's (B' ⊆ A) for every B and B's. So, ONLY(A, B) is right-side monotone decreasing.

For example, take the NO(A, B) quantifier (Plans ∩ Animals = 0).

All Mammals are Animals. No Plants are Animals. Therefore, no Plants are Mammals.

All B's are Bs. No As are Bs. Therefore, no As are B's.

Because that's the case for any set A, B and B' for the quantifier NO(A, B), NO(A, B) is said to be right-side monotone decreasing (written as NO(A, B)↓)

A quantifier Q is left-side monotone increasing if and only if A ⊆ A' ⇒ Q(A, B) → Q(A', B).

Take, for example, the SOME(A, B) quantifier (whose relation is X ∩ Y != 0):

All humans are mortal. Some humans are rich. Therefore, some mortals are rich.

All As are A's. Some As are Bs. Therefore, some A's are Bs.

Because that's the case for any set A, B and B' for the quantifier SOME(A, B), SOME(A, B) is said to be left-side monotone decreasing (written as SOME(A, B)↑)

Going back to ONLY(A, B) (meaning B ⊆ A). Is it the case that A ⊆ A' ⇒ ONLY(A, B) → ONLY(A', B)?.

All As are A's. Only As are Bs (B ⊆ A). It has to be the case that only A's are Bs (B ⊆ A') for every A and A's. So, ONLY(A, B) is left-side monotone increasing.

A quantifier Q is left-side monotone decreasing if and only if A' ⊆ A ⇒ Q(A, B) → Q(A', B).

As an example, take the AT-MOST-3(A, B) quantifiers (|A ∩ B| <= N).

All greeks are humans. At most 3 humans are alive. Therefore, at most 3 greeks are alive.

All A's are As. At most 3 As are Bs. Therefore, at most 3 A's are Bs.

Because that's the case for any set A, B and B' for the quantifier AT-MOST-3(A, B), AT-MOST-3(A, B) is said to be left-side monotone decreasing (written as AT-MOST-3(A, B)↓)

Monotonicity Profiles

Quantifiers can be increasing in one of the arguments while being decreasing in the other. Some quantifiers like MOST even are right upward monotone, while being neither left upward nor left downward monotone.

As a shorthand for the monotonicity properties of a quantifier Q, we will talk about its monotonicity profile. As an example, instead of stating that a quantifiers is leftside downward monotone and right-side upward monotone, we will say that its monotonicity profile is ↓↑. To make the monotonicity profile of a quantifier explicit, we will often also write ↓ Q ↑. If a quantifier does not have any monotonicity properties on a side, we will write a dot instead.

Here are the monotonicity profiles of the quantifiers we looked at so far:

Quantifer Relation Left Right
all(X, Y) X ⊆ Y ↓ ↑
some(X, Y) X ∩ Y != ∅ ↑ ↑
none(X, Y) X ∩ Y = ∅ ↓ ↓
not-all(X, Y) X - Y != ∅ ↑ ↓
at-least(N, X, Y) ` X ∩ Y >= N`
at-most(N, X, Y) ` X ∩ Y <= N`
more-than(N, X, Y) ` X ∩ Y > N`
fewer-than(N, X, Y) ` X ∩ Y < N`
many(X, Y) ` X ∩ Y >= 2`
exactly(N, X, Y) ` X ∩ Y == N`
the-majority-of(X, Y) ` X ∩ Y >
the-minority-of(X, Y) ` X ∩ Y <
only(X, Y) Y ⊆ X ↑ ↓
all-but(X, Z, Y) Z ⊆ X and (X - Z) ⊆ Y ~ ↑

Symmetry

Another property of generalized quantifiers that allows for inferences is symmetry. Take NO(X, Y) as an example:

No animal is a plant.

It is clear that it can also be said that No plant is an animal.

When that conversion Q(A, B) ⇒ Q(B, A) is possible, the quantifier is called symmetric.

Another example of a symmetric quantifier is SOME(X, Y). For example:

Some men are rich. Therefore, some rich are men.

A concrete example of a non-symmetric quantifier is ALL(X, Y). For example: every men is mortal, but it is not the case that every mortal is a men.

Which quantifiers are symmetric and which are not?

Quantifer Relation Symmetric
all(X, Y) X ⊆ Y false
some(X, Y) X ∩ Y != ∅ true
none(X, Y) X ∩ Y = ∅ true
not-all(X, Y) X - Y != ∅ false
at-least(N, X, Y) ` X ∩ Y
at-most(N, X, Y) ` X ∩ Y
more-than(N, X, Y) ` X ∩ Y
fewer-than(N, X, Y) ` X ∩ Y
many(X, Y) ` X ∩ Y
exactly(N, X, Y) ` X ∩ Y
the-majority-of(X, Y) ` X ∩ Y
the-minority-of(X, Y) ` X ∩ Y
only(X, Y) Y ⊆ X false
all-but(X, Z, Y) Z ⊆ X and (X - Z) ⊆ Y false

From this:

Typical symmetric quantifiers are some, no, at least five, exactly three, an even number of, infinitely many, whereas all, most, at most one-third of the are non-symmetric. Another

From this

According to the definitions just given, some quantifiers are symmetric while others are not. For example, “some”, “no”, and “three” are symmetric; “all” and “most” are not.

Non-symmetric quantifiers are universal (English “all”, “every”, and “each”) or proportional, like “most” and “half of the”. The distinction between symmetric and non-symmetric quantifiers has been shown to manifest itself in several ways, the best-known of which is that in many languages, including English, existential there-sentences only admit symmetric quantifiers, so that "There are (some/no/three) laywers on the beach works" whereas "There are (all, most) lawyers on the beach" doesn't.

Inference Rules

Inference Rule Premise Entailment
Right-side Upward Monotone Q↑(A, B), ALL(B, C) Q↑(A, C)
Right-side Downward Monotone Q↓(A, B), ALL(C, B) Q↓(A, C)
Left-side Upward Monotone ↑Q(A, B), ALL(A, C) ↑Q(C, B)
Left-side Downward Monotone ↓Q(A, B), ALL(C, A) ↓Q(C, B)
Symmetry Conversion Qs(A, B) Qs(B, A)
Pseudo Conversion NO(A, B) ALL-NOT(A, B)
Existential Import ALL(A, B) SOME(A, B)

The above inference rules allow for proving all syllogisms that are valid in predicate calculus and/or aristotelian logic plus the other generalized quantifiers:

Take, for example, ALL(M, P), ALL(S, M) |- ALL(S, P).

ALL(A, B)'s profile is ↓ALL↑ and it is not symmetric.

  1. ALL(M, P), premise
  2. ALL(S, M), premise
  3. Therefore ALL(S, P), 1,2 and left-side downward monotone (S = C, A = M, B = P)

Lets try another example with ↓AT-MOST-THREE↓:

  1. ALL(Engineers, Employees), premise
  2. AT-MOST-THREE(Employees, Promoted), premise
  3. Therefore AT-MOST-THREE(Engineers, Promoted), 1,2 and left-side downward monotone (C=Engineers, A=Employees, B=Promoted)

All engineers are employees. At most 3 employees are promoted. Therefore, at most 3 engineers are promoted.

Lets try another example with ~MOST↑:

  1. ALL(Engineers, Smart), premise
  2. MOST(Employees, Engineers), premise
  3. Therefore MOST(Employees, Smart), 1,2 and right-side upwards monotone (B=Engineers, C=Smart, A= Employees)

All engineers are smart. Most employees are engineers. Therefore, most employees are smart.

Lets try another example with ↓NO↓:

  1. ALL(Seaguls, Fly), premise
  2. NO(Penguins, Fly), premise
  3. Therefore NO(Penguins, Seaguls), 1,2 and right-side downward monotone (B=Seaguls, C=Fly, A= Penguins)

All seaguls fly. No penguins fly. Therefore, no penguins are seaguls.

Existential Imports

How do existential imports expand beyond ALL -> SOME? It certainly seems the case that it would be applicable to a lot more rules. Say, maybe:

  • ALL(X, Y) -> MOST(X, Y) -> AT-LEAST(1, X, Y) -> EXACTLY(1, X, Y) -> SOME(X, Y)
  • AT-LEAST(N, X, Y) -> AT-LEAST(N < M < 0, X, Y)
  • AT-MOST(N, X, Y) -> AT-MOST(N < M < 0, X, Y)?
  • MORE-THAN(N, X, Y) -> AT-LEAST(N + 1, X, Y)
  • FEWER-THAN(N, X, Y) -> AT-MOST(N - 1, X, Y)
  • ONLY(X, Y) -> ALL(Y, X)
  • NO(X, Y) -> AT-MOST(N, X, Y)?

Are these reciprocal?

Connectives

How do connectives work with generalized quantifiers? For example, what do the following mean?

Finally, we wish to remark that the ”natural“ approach is expanding: Seuren (2010) offers an overview over natural set theory approaches that, similarly to Braine’s propositional natural logic (above) tries to give a more plausible meaning to set-theoretical operations such as ”∪“ and ”∩“.

TODO(goto): maybe that's what we need to read?

  • Universal Conjunction Elimination: forall(x) P(x) && Q(x) => forall(x) P(x) && forall(x) Q(x).
  • Universal Modus Ponens: forall(x) P(x) => Q(x). P(a). => Q(a).
  • Universal Introduction: forall(x) => P(x). => P(a).
  • Universal Conjunction Introduction: forall(x) P(x) && forall(x) Q(x) => forall(x) => P(x) && Q(x).
  • Universal Disjunction Syllogism: forall(x) P(x) || Q(x). ~Q(a). => P(a).
  • Existential Introduction: P(a). => exists(x) P(x).

How do these first order inference rules apply to ALL(A, B) and SOME(A, B)?

  • Universal Conjunction Elimination: ALL(A, B && C) => ALL(A, B) and ALL(A, C)?
  • Universal Modus Ponens: ALL(A, B). a ∈ A. => a ∈ B.
  • Universal Introduction: ALL(U, A). a ∈ A. (Everything is pretty.).
  • Universal Conjunction Introduction: ALL(A, B) and ALL(A, C) => ALL(A, B && C)?

Is that the case too for NO(A, B) and SOME-NOT(A, B)?

  • Most employees are either software engineers or product managers.
  • Most employees are smart and honest.
  • Some employees are evil or not smart.

And how do the inference rules apply to them?

For example, in first order logic, you have something like:

  • All employees are smart and honest => *All employees are smart.

Can the same be said for MOST?

  • Most employees are smart and honest => *Most employees are smart?

Does it matter if we change the connector?

  • Most employees are smart or honest => *Most employees are smart?

Conservativity

It was observed early on that quantifiers denoted by determiners in natural languages have the following property:

Q(A,B) ⟺ Q(A,A ∩ B).

For example:

  • Most students smoke ⟺ Most students are students who smoke.
  • At least five professors were absent ⟺ At least five professors were absent professors.
  • More than one third of the graduate students are foreigners ⟺ More than one third of the graduate students are foreign graduate students.

Conserv says that only the part of B which is common to A matters for the truth of QM(A,B). That is, the part B−A in Figure 1 doesn’t matter. This appears to hold for all determiner denotations, but it fails for perfectly natural logical quantifiers, such as MO and I from the list (11) above. The reason is that it is characteristic of determiner denotations that the restriction argument restricts the domain of quantification to that argument.

NOTE(goto): didn't quite follow this.

Duals

Keenan (2003 and 2004) studies inferential properties of quantifiers that are related through complement and postcomplement relations. In that vein, the quantifier NO STUDENT is the postcomplement of EVERY STUDENT because we can infer ”every student passed“ from ”no student did not pass“ and vice versa. Keenan thus states that the semantic properties of quantifiers allow for inferences on their duals: if a quantifier Q1 can be characterized as the dual of another (e.g. Q1 = ¬(Q2¬)), this allows for some inferences between them. Highlighting the inferential relationships between quantifiers of all kind operating on natural language representations makes for a natural logic – Keenan however offers no additional insights, e.g. alignment with empirical data or testable predictions.

Iterated Quantifiers

MOST A played against AT LEAST THREE B

Q1, Q2φ(A, B)

Combinatorial Monotonicity Profiles (CMP) Similar as single quantifiers, most iterated quantifiers put their arguments in positions that allow for monotonicity inferences. Iterated quantifiers then have a monotonicity profile similar to those of single
quantifiers. So, for example,
↓ Q1, Q2 ↑
means that the iteration of Q1 and Q2 puts the first argument in a downward entailing
position and the second argument in an upward entailing position.

Geurts & van der Silk (2005) did an experiment on reasoning with iterated quantifiers investigating how their combined monotonicity properties interact with the cognitive difficulty of inferences. For lack of a better name, we will henceforth call the natural language fragment involved in their experiment on reasoning the quantifier iteration (QI) fragment. W

The work of Geurts and van der Silk (2005, 108) suggests that the combined (rightside) monotonicity profile of two iterated quantifiers depends only on their respective right-side monotonicity properties, but this is not the case. ... The iteration scheme that Geurts and van der Silk (2005) suggest for all quantifiers is thus only working for the combinations of quantifiers in their fragment. While this does not interfere with our plan of creating a complexity measure for inference rules, it does interfere with our plan of creating general inference rules.

We can however state that left-side monotonicity properties are unproblematic: those are directly inherited from the first quantifier.

Bindings

  • Existential Introduction: P(a) => some(x) P(X)
  • Universal Elimination: all(x) P(x) => P(a)

References

Other theories suggest that drawing conclusions from two syllogistic premises involves deliberate reasoning using sets. Using Venn diagrams, the three sets involved in syllogistic reasoning, A, B, and C, can be represented as three circles, a perspicuous representation that allows for the making of inferences (e.g. Shin 1992). This yields a feasible method that is at the same time sufficiently flexible – Peirce’s diagrams for example can account for all of predicate calculus but, according to their creator, lose all psychological plausibility (Peirce 1958). Furthermore, number of researchers have considered natural set theory, a hypothesis stating that humans have a natural way to deal with a plurality of objects (e.g. Seuren 2010). While this hypothesis has, to the best of our knowledge, not been tested yet, this could yield an alternative to create formal models of syllogistic reasoning focusing on sets. Figural effects, atmosphere theory and Venn diagrams have in common that they suggest solutions to syllogisms but not their difficulty – we will now look at three paradigmatic theories that have something to say about that.

An immediate observation is, unsurprisingly, that some good inferences are easier than others.

Natural Logic An early account that aimed to investigate the psychology of reasoning with a logical model was given by Rips (1983 and 1994). Reasoning was thereby understood as proof in a natural deduction system while the cognitive difficulty of a sequence of inferences was conceptualized as the length of proof of a conclusion from assumptions. Rips introduced further inference rules to account for the fact that some inferences, e.g. the syllogism AA1A, are of low cognitive difficulty while its proof in natural deduction systems takes seven steps. While Rips’ work is certainly to be understood as the ancestor of much work into natural logics that followed, it became increasingly clear that it faces a variety of problems connected to its first order logic representations ... We will thus focus on a later model brought forward by Geurts (2003), which we will also extend later on.

Despite these introductory remarks, it is still not easy to pin down what natural logic actually is – a natural logic is a set of inference rules that act on the surface of natural language.

Braine (1978) introduces a natural propositional logic that tries to capture the inferential properties of the natural language words that correspond to the connectives of propositional logic – the logic, for example, gives up on the truth-functionality of entailment: the conditional is understood as directional, meaning that, for example, p → q does not imply ¬q → ¬p.

While the expressions mostly associated with generalized quantifiers are of the kind MOST, MORE THAN HALF and MANY, those are determiners, not quantifiers. It takes the combination of a determiner with a set expression to obtain a generalized quantifier.

A natural logic is not only interested in inferences but in inferences that relate strongly to natural language. We thus have two distinct justifications for our pick of natural logic: other systems of inference are not expressive enough and we wish to have inferences operating on natural language representations (as we will see in more detail later, SOME(A, B) is just a much more plausible representation than ∃x(A(x) ∧ B(x)) – Barwise and Cooper call this the ”norotious mismatch“ between the representational capacities of predicate calculus and natural language). Natural logic is thus not only about reasoning, but also about language and how the two interact: some parts of natural language allow fo