the difference between upward and downward entailment

Question

How does one show the difference of an upward entailment between that of a downward entailment? I have tried doing examples where the negative polarity item is moved from the verb phrase to the noun phrase but I still don't understand.

Answer 1

Upward entailment means that if a relation holds for some set X, then the relation will hold for a superset of X.
Downward entailment means that if a relation holds for some X, then the relation will hold for a subset of X.
X is a subset of Y and conversely Y is a superset of X iff all elements (members) of X are also elements of Y, i.e. Y "includes" X.

Entailment (P entails Q, written as P ⊨ Q) means that whenever P is true, Q will be true too, i.e. there will be no case (logically speaking: no assignment) under which P is true and Q is not true.

Monotonicity in general means that once we've established an entailment, adding more assumptions won't break the validity of the conclusion: If we can logically infer a conclusion Q from a set of premises P1, P2, ..., Pn (written: P1, ... Pn ⊨ Q), then this inference still holds if we add more assumptions to our existing premises (e.g. P1, ..., Pn, R ⊨ Q, where R is a new assumption). For example, if from the assumptions "If it rains, then the streets get wet" and "It rains" we can infer the conclusion that "The streets are wet", then adding the addional premise "Pigs are pink" will still keep up the inferene that the streets are wet, as long as the two other presmises are still there.
Monotonicity holds in classical logic, while it is problematic to assume for certain aspects of natural language use, but let's forget about that here. For our purpose, "monotonicity" means that I can always go higher and higher or lower and lower in my hierarchy of sub- and supersets and the pattern never breaks.

---

1) Generalized quantifiers

Before going into the various forms of entailment and monotonicity, I should breiefly establish some terminology:

Words like all, some, no, most, many, ... are so-called generalized quantifiers. Generalized quantifiers express relations between sets. For example, No X are Y means roughly that the sets X and Y have an empty intersection, i.e. no members in common.
Most generalized quantifiers you'll see talk about a relation between two sets, where the first/left one is called restriction and the second/right one is called the body or nuclear scope (I'll use the shorter term body throughout my answer): In the quantification Some pigs snore, the set pig is the restriction and the set snore (= the set of individuals which snore) is the body/nuclear scope of the quantifier some. In the quantification All happy children laugh, happy children is the restriction and laugh the body of the quantifier all. Linguistically speaking, the restriction is normally the subject NP (without the quantifier) and the body is the VP.

2) Upward and downard entailment/monotonicity

2.1) Basic idea

Let's look at some examples:

All women sang loudly |= All women sang
All women sang |= All women made some sound

You see that in each of the inferences above, the sets that constitute the body of the quantification in the premise of the entailment relation (sang loudly and sang, respectively) are a subset of the sets of the body in the conclusion sentence (sang and made some sound, respectively): The loudly singing individuals are a subset of the singing individuals, because everyone who sings loudly is also someone who sings; the singing individuals are a subset of the sound-making individuals, etc.
The entailment relation holds from the subset to the superset in the body/second/right-hand argument of the quantifier (the restriction/first/left-hand argument would be women in all cases), so the quantifier all is upward entailing in the body or (synonymously) right monotone increasing: We can always go from a smaller set in the body of the quantifier up to a larger set and the conclusion still holds. We can go from the smaller, more specific set of loud singers to the larger set of just singers, and again from the set of singers to the even larger set of sound-makers and can still infer that the all-quantification holds. This is upward entailment, or monotonicity. (The same works, by the way, for quantifiers like both or more than half of - try it out.)

We can express this behavior formally as follows:

right monotone increasing:
Q(A)(B) & B ⊆ B' ==> Q(A)(B')

meaning "If the quantifier Q (here: all) holds between a pair of sets A and B, and there is a set B' which is a superset of B, then the quantifier also holds between A and that larger set B'."
In our example, we chose A to be the set of women and the sets B and B' the set of loudly singing and singing individuals, respectively, but the point about monotonicity is that we could insert any such triples of pairs A, B, B' and would always get that inference pattern for this particular quantifier.

---

2.2) Other kinds of entailment

Now let's see what happens if we change our focus from the body to the restriction of the quantification (from the right/second to the let/first set), i.e. if we look at the NP women instead of the VP sing:
A superset of woman would be people (all those who are women are also people). So can we still make the inference? We immediately see that this does not work (I'll use |/= to indicate "does not entail"):

All women sang |/= All people sang

Just because all women sang doesn't mean we can infer that necessarily all people sang; it might well be that there were some men who didn't sing.
So the quantifier all is not upward entailing in the body, or not left monotone increasing.

But the other direction works:

All women sang |= All young women sang

The set of young women is a subset of the set of women/The set of women is a superset of the set of young women, because all young women are also women. So in the left argument of the quantification (the subject NP), we can go downwards: The quantifier all is downward entailing in the body, or left monotone decreasing. The inference stays valid when we go down in/decrease the set to the left of the quantification.

Formally:

left monotone decreasing:
Q(A)(B) & A' ⊆ A ==> Q(A')(B)

"If a quantifier holds betwee a pair of sets A, B and there is a set A' which is a subset of A (notice that the subset relation is the other way round than above!), then the quantifying relation also holds between that smaller set A' and B."

So now we have established that the quantifier all is upward-entailing in the body, and downward entailing in the restriction, i.e. right monotone increasing and left monotone decreasing.

What about the other possibilities?

The quantifier no is also downward entailing in the restriction, i.e. left monotone decreasing:

No women sang |= No young women sang

If no women sang at all, we know for sure that there wasn't any young woman who sang.

But in the body, i.e. on the right side of the quantification, we can not go up as with all:

No woman sang loudly |/= No woman sang

Just because no woman sang loudly, it doesn't mean that no woman sang at all - maybe some woman sang quietly, possibly even all of them. We can not infer from the subset sang loudly to the superset sang. So the quantifier no is not upward entailing/monotone increasing on the right.

Instead, we can go in the other direction:

No woman sang |= No woman sang loudly

If no woman sang at all, then it logically follows that there can be no woman who did so loudly. We can go from the superset sang down to the subset sang loudly in the body. So no is downward entailing in the body, or right monotone decreasing.

Formal notation:

right monotone decreasing:
Q(A)(B) & B' ⊆ B ==> Q(A)(B')

One final possibility is left:

The quantifier some, like all, is also upward entailing in the body, i.e. right monotone increasing:

Some women sang loudly |= Some women sang

But in the restriction, i.e. on the left, we can not go down, as with all:

Some women sang |/= Some young women sang

Just because we know some women sang doesn't mean we can tell that there was any young woman singing, might be that it was just old women. So some is not downward entailing/decreasing on the left. Instead, the other direction works again:

Some women sang |= Some people sang
Some young woman sang |= Some women sang

If the singing happend for some women, then there certainly where people involved, and the same holds for the subset/superset pair young women and women. We can go up in our sets on the left-hand side and the inference stays valid. So the quantifier some is upward entailing in the restriction or left monotone increasing.

Formally:

left monotone increasing:
Q(A)(B) & A ⊆ A' ==> Q(A')(B)

For the quantifier not every, you will find that it is upward entailing in the restriction (left monotone increasing) and downward entailing in the body (right monotone decreasing).

---

2.3) Summary

Again, here are the formal definitions of the notions:

upward entailing in the restriction/left monotone increasing:
Q(A)(B) & A ⊆ A' ==> Q(A')(B)

downward entailing in the restriction/left monotone decreasing:
Q(A)(B) & A' ⊆ A ==> Q(A')(B)

upward entailing in the body/right monotone increasing:
Q(A)(B) & B ⊆ B' ==> Q(A)(B')

downward entailing in the body/right monotone decreasing:
Q(A)(B) & B' ⊆ B ==> Q(A)(B')

We can summmarize our many observations as follows, and find a nice pattern betwen the quantifiers "all"/"some" and their negations (logically, "no" = "not some"):

--------------------------------------------------------
quantifier | restriction/left     | body/right
--------------------------------------------------------
all        | downwward/decreasing | upward/increasing
no         | downwward/decreasing | downwward/decreasing
some       | upward/increasing    | upward/increasing
not all    | upward/increasing    | downwward/decreasing

You can now test the behavior of other quantifiers like at least two, at most five, exactly two, both, most, many...

---

3) Negation of the VP

I'm not sure I understand completely what you mean by "where the negative polarity item is moved from the VP to the NP" (especially saying that the NPI (words like any or ever) is moved - are you sure you didn't mean the negation?) - probably something like this:

All women didn't sing ¹ --> Not all women sang
No woman didn't sing --> Not no woman sang]
etc.

In these examples, you see that for both right monotone increasing and decreasing quantifiers, the entailment relation perseveres when moving the negation from the VP to the NP (in every case where all women didn't sing it will be true that not all women sang, and in every case where no woman didn't sing (= all women sang) it will be true that not no woman sang (= at least one woman sang)).
But note that the propositions with the negated quantifiers as opposed to the negated VPs are weaker: We could imagine situations where the right-hand side is true, but the left-hand side not necssarily - e.g. when some women sang, then Not all women sang is true but All women didn't sing isn't, also Not no woman sang is true but No woman didn't sing isn't.

Interestingly, the entailment relations between the sentences with negated VPs turn around:

The entailment relations that held before can't be claimed to be true any more now - we no longer have right upward monotonicity for all and some:

All women didn't sing |/= All women didn't make a sound
Some women didn't sing loudly |/= Some women didn't sing
etc.

Conversely, right dowward monotonicity fails for no and not every when the VP (the body) is negated:

No woman didn't make any sound |/= No woman didn't sing
Not every woman didn't sing |/= Not every woman didn't sing loudly
etc.

On the other hand, the entailment relations that didn't hold before do hold now:

All women didn't sing |= All women didn't sing loudly
Some women didn't make any sound |= Some women didn't sing
etc.

The supersets sing/make some sound now entail the subsets sing loudly/sing, so the bodys of all and some are now a downard entailing environment.

No woman didn't sing |= No woman didn't make any sound
Not every woman didn't sing loudly |= Not every woman didn't sing
etc.

The subsets sing/sing loudly now entail the supersets make some sound/sing, so the bodys of no and not every are now an upward entailing environment.

You could summarize this observation as follows: Negation of the VP, i.e. negation in the body revers the direction of entailment: Upward entailment becomes downward entailment, and downward entailment becomes upward entailment.
Logically seen this should work analogously for negation in the restriction/subject NP, however I find it hard to imagine linguistic examples of negating subjects that don't sound completely made up and unnatural, so I'll leave it like this.

---

4) Negative polarity items #

Let's now briefly return to your mentioning of the negative polarity items (NPIs):

One can assert that NPIs are licensed in the context of downward entailing environments (remember that no is downward entailing in both the restriction and the body):

No woman sang --> No [woman] [sang anything]
No woman sang --> Not [any woman] [sang]

but they seem gramatically/pragmatically weird (that's what the # sign means) in an upward entailing environment (remember that all and a are upward entailing in the body:

All woman sang --> # All [women] [sang anything]
Some woman sang --> # Some [woman] [ever sang]

(BTW, can someone tell me why sang ever seems more marked than the reversed word order ever sang, but anything sang sound wrong? Or is my non-native speaker judgement wrong?)

That's pretty much it: Negative polarity items like any or ever work fine in downward entailing contexts, but are weird and hard to license in upward entailing environments.

---

Footnote

¹ Note that this setence is actually ambiguous, because English syntax basically allows for two interpretations (thanks to @jlawler for the hint):

All women didn't sing

a) linear interpretation of the negation (negation at the verb ≙ negation of the predicate):
For every woman it holds that she didn't sing
⇔ (∀x : Woman (x)) ¬Sing (x)

b) shifted interpretation of the negation (negation at the verb ≙ negation of the quantifier):
It does not hold for every woman that she sang
⇔ ¬(∀x : Woman (x)) Sing (x)

Those two interpretations obviously yield different truth conditions, but this discrepancy is a characteristics of English (and, with respect to similar issues, in general natural langauges') syntax and in speech usually resolved by contextual information and, most importantly, intonation.
One could even argue that due to the latter, the sentence is not actually ambiguous in the way that there would be two possible logical forms assigned to one phonetic form, since phonetic form does in fact distinguish between the two readings, namely in terms of intonation.
Anyway, this is only variation based on idiosyncratic behaviour of natural languages that should not affect the logic of upward and downward entailment in general; the patterns described will hold for any language that has semantic relations like hypernymy and hyponymy (and there is no way around having such relations in a language), regardless of whether there might be specific "semantax" side effects in one or the other context.