Skip to main content

Subsection 8.4.9 Quantifier Exchange and Proof by Example/Counterexample

Recall our rules for quantifier exchange. When we “push” not through ∃, we get ∀. So what may appear to be an existentially quantified claim may actually be a universally quantified one (or vice versa). That then changes our job from finding a single example/counterexample to finding a general proof (or vice versa).

Consider:

[1] \(\neg\) \(\exists\)x (MuskOx(x) \(\wedge\) ColorOf(Purple, x))

That looks like an existence claim (i.e., that there exist no purple musk oxen). Can I prove it with one example?

Suppose that I exhibit one brown musk ox. Does that validate my claim? No.

Let’s do quantifier exchange. We get:

[2] \(\forall\)x ( \(\neg\)(MuskOx (x) \(\wedge\) ColorOf(Purple, x)))

Using De Morgan, we get:

[3] \(\forall\)x (\(\neg\)MuskOx (x) \(\vee\) \(\neg\)ColorOf(Purple, x)))

Now it’s clearer that I can’t support my claim with a single example. In fact, how many musk oxen would I have to find before I can be sure of my claim? Answer: all of them. I could refute it, however, with the existence of a single purple musk ox.

Our original statement looked like an existence claim that could perhaps have been verified by finding one existence proof. But now it’s clear that we have a universal claim.

Exercises Exercises

1.

Consider the claim, “No parents like rap music”. Which of the following statements is true:

  1. It could be proved by exhibiting one parent who likes rap music.

  2. It could be proved by exhibiting one parent who doesn’t like rap music.

  3. It could be disproved by exhibiting one parent who likes rap music.

  4. It could be disproved by exhibiting one parent who doesn’t like rap music.

  5. None of these.

Answer.
Correct answer is C
Solution.

Explanation: We can write this claim as:

[1] \(\neg\) \(\exists\)x (Parent(x) \(\wedge\) LikesRap(x))

Using Quantifier Exchange, we get:

[2] \(\forall\)x \(\neg\)(Parent(x) \(\wedge\) LikesRap(x))

Using De Morgan, we get:

[3] \(\forall\)x \(\neg\)(Parent(x) \(\vee\) \(\neg\)LikesRap(x))

Now it’s easy to see that we could disprove the claim by finding a single individual who is both a parent and a rap music fan. To prove this universal claim, we’d have to either reason from some sort of first principles or examine all parents and check their rap music sentiments.

2.

Suppose that I exhibit a 250 lb hot dog. Which (one or more) of the following claims have I proved:

I. ¬∀x (Hotdog(x) → (weight(x) < 50))

II. ∀x (Hotdog(x) → ¬(weight(x) < 50))

III. ∃x (Hotdog(x) ∧ ¬(weight(x) < 50))

  1. Just I.

  2. Just II.

  3. Just III.

  4. Just I and III.

  5. All of them.

Answer.
Correct answer is D.
Solution.
Explanation: A single example that fails to possess some property P (in this case that if you’re a hot dog then you weigh less than 50 pounds) can refute a universal claim that everything possesses property P. I clearly does that. We can derive III from I by applying Quantifier Exchange, then Conditional Disjunction, then De Morgan, then Double Negation. But to prove a universal claim, as in II, a single example doesn’t suffice.

3.

Assume that we have as a premise that peacocks are birds. Now suppose that I exhibit a white peacock. Which (one or more) of the following claims have I proved:

I. ∀x (Peacock(x) → HasMultiColoredFeathers(x))

II. ¬∀x (Bird(x) → HasMultiColoredFeathers(x))

III. ∃x (Peacock(x) ∧ ¬HasMultiColoredFeathers(x))

  1. Just I.

  2. Just II.

  3. Just III.

  4. I and III.

  5. II and III.

Answer.
Correct answer is E
Solution.
Explanation: I isn’t correct. In fact, this example disproves I, since clearly it’s not true that all peacocks have multicolored feathers. It’s easier to see that II is correct if you first do Quantifier Exchange to convert the universal quantifier into an existential one.