Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 6.1.3 Existentials in Implications

You might be tempted to think that we should have added an even weaker line to our scale on the previous slide:

Even weaker: [6] ∃x (Q(x))

It’s true that, almost all the time, asserting that there’s at least one thing of which Q is true is weaker (generally a lot weaker) than asserting that Q is true of everything. The exception is when the universe about which we are making our claim is, in fact, empty. In that case, the universal claim is trivially true, while the existential claim is stronger (and false).

Recall the example of my non-card-playing cat Lucy:

[1] Lucy has won every game of solitaire she’s ever played.

x (SolitaireGame(x)  Played(Lucy, x)  Won(Lucy, x))

[2] There is a solitaire game, played by Lucy, that she’s won.

x (SolitaireGame(x)  Played(Lucy, x)  Won(Lucy, x))

I’m pretty sure that Lucy has never played solitaire. So [1] is trivially true. Yet [2], the seemingly weaker existential claim, is false.

That exception aside, however, existential claims are generally weak.

Does it make sense to weaken them further, as we’ve done with universal ones, by adding guards? For example, rather than saying:

[1] ∃x (Q(x))

could we make the weaker (guarded claim):

[2] ∃x (P(x) → Q(x))

Of course we can say that. It’s a legal logical expression. But it’s hard to figure out what it means. Let’s rewrite it, using Conditional Disjunction, so we have:

[3] ∃x (¬P(x) ∨ Q(x))

Perhaps this is true and we might want to say it. This form makes our claim more clear than [2] does.

Using an implication inside an existential quantifier is even stranger when it’s negated. Suppose we write:

[4] ¬∃x (P(x) → Q(x))

This makes little sense: Let’s simplify:

[5] ¬∃x (¬P(x) ∨ Q(x)) Conditional Disjunction [4]

[6] ∀x ¬(¬P(x) ∨ Q(x)) Quantifier Exchange [5]

[7] ∀x (¬¬P(x) ∧ ¬Q(x)) De Morgan [6]

[8] ∀x (P(x) ∧ ¬Q(x)) Double Negation [7]

It’s hard to think of a case in which [8] isn’t the more natural thing to say.

Big Idea

Be very careful if you find yourself using an existentially quantified variable as a guard in an implication. It rarely does what you want it to do.

Recall our Bad Movie example. We want to claim that there’s a movie that everyone in our class hates. Define:

Movie(x): True if x is a movie.

InClass(x): True if x is in our class

Hates(x, y): True if x hates y.

A good way to represent this claim is:

[1] x (Movie(x)  y (InClass(y)  Hates(y, x)))

(Notice that we have Hates(y, x), with y coming before x, because, in this expression, x is a movie, and we’ve defined Hates so that the hater is the first argument and the hated thing is the second one.)

But consider an alternative that looks as though it might be correct:

[2] x (y ((Movie(x)  InClass(y))  Hates(y, x)))

Read [2] as, “There exists an x such that if x is a movie then everyone in the class hates it.” But notice that, if there exists even one non-movie, then this claim is trivially true. To see why, let k be the non-movie. Then Movie(k) is false (F). So, generalizing a bit, we have:

[3] (F  something)  conclusion

But that is trivially true, since F  something must be F (by the definition of and).

And F  conclusion is T (by the definition of implies). So [2] doesn’t actually tell us anything about the movie taste of our classmates.