Skip to main content

Subsection 4.4.4 Counterexamples

We are about to present a collection of techniques for showing that a claim must be true in all interpretations. (Or, similarly, that it is false in all interpretations.) If there are infinitely many such interpretations, we need something other than “try them all”.

But suppose that we want to show that some claim is not valid. Or that it is not a contradiction. Then it suffices to find a single interpretation that makes a liar out of it. We’ll call such an interpretation a counterexample. Universally quantified statements are typically the easiest to refute in this way.

Video cover image

Also note that we can refute the claim that an expression is a contradiction by showing a single set of values that make the expression true.

Let the universe be the rational numbers. Now consider:

\(\forall \)x, y (\(\exists \)z (z = x/y))

We can show that this claim is not a tautology by finding a single (x, y) pair of values such that the required z does not exist.

That is easy. Let y = 0. (It doesn’t matter what x is.)

Exercises Exercises

Exercise Group.

1. Consider the following set of claims:

[1] ∀x (Cat(x) → Loves(x, Catnip))

[2] ∀x (Loves(x, Catnip) → Cat(x))

[3] ∀x (Loves(x, Chocolate) → Loves(x, IceCream))

[4] ∀x ((Cat(x) ∧ Calico(x)) → Loves(x, Chocolate))

[5] ∀x (Cat(x) → ¬Dog(x))

Let ModelOfCatsAndDogs be the conjunction of these five claims.

For each of the following statements, indicate whether or not it is a counterexample to ModelOfCatsAndDogs:

1.

(Part 1) Cat(Lucy) ∧ Calico(Lucy) ∧ ¬Loves(Lucy, Icecream)

Answer.
Correct answer is : Counterexample
Solution.
Explanation: All calico cats (including Lucy) love chocolate. So she must also love ice cream. But we are told that she does not love ice cream.
2.

(Part 2) Cat(Agnes) ∧ Loves(Agnes, Paper)

Answer.
Correct answer is : Not Counterexample
Solution.
Explanation: What we know about Agnes is consistent with the model. She loves paper, but she could also have the required love for catnip.
3.

(Part 3) Dog(Scarlet) ∧ ∀x (Loves(Scarlet, x))

Answer.
Correct answer is : Counterexample
Solution.
Explanation: Since Scarlet loves everything, she must love catnip. But then she must be a cat. But cats can’t be dogs, and Scarlet is a dog.
4.

(Part 4) Dog(Lloyd) ∧ Loves(Lloyd, Chocolate))

Answer.
Correct answer is : Not Counterexample
Solution.
Explanation: What we know about Pebbles is consistent with the model. He must also like ice cream, but that’s not ruled out by what we’ve been told.

Exercise Group.

2. Zamzows and Tenockritus For the purpose of this question, assume that the zamzow is a newly discovered species and tenockritus is an ailment that afflicts species like the zamzow. For each of the following claims, indicate an assertion that, if true, would falsify the claim:

1.

(Part 1) ∀x (Zamzow(x) → HasTenockritus(x)) All zamzows have tenockritus.

  1. Alfred and Reggie are zamzows that have tenockritus.

  2. There are no zamzows.

  3. Clora isn’t a zamzow but has tenockritus.

  4. Peapod is a zamzow and, by the way, no one has tenockritus.

  5. No one has tenockritus.

Answer.
Correct answer is D.
Solution.
Explanation: Peapod is a zamzow yet cannot have tenocritus because no one does. Note that the claim that there are no zamzows doesn’t falsify the claim, which is trivially true in that case.
2.

(Part 2) ∃x (Zamzow(x) ∧ HasTenockritus(x)) Some zamzows have tenockritus.

  1. Alfred and Reggie are zamzows that have tenockritus.

  2. Peapod is a zamzow who does not have tenockritus.

  3. Chlora isn’t a zamzow but has tenockritus.

  4. Tiddlywinks is the only zamzow and does not have tenockritus.

  5. Only bears have tenockritus.

Answer.
Correct answer is D.
Solution.
3.

(Part 3) ¬(∃x (Zamzow(x) ∧ HasTenockritus(x)) ) No zamzow has tenockritus.

  1. Alfred and Reggie are zamzows that have tenockritus.

  2. Peapod is a zamzow who does not have tenockritus.

  3. Chlora isn’t a zamzow but has tenockritus.

  4. Tiddlywinks is the only zamzow and does not have tenockritus.

  5. Only bears have tenockritus.

Answer.
Correct answer is A.
Solution.
Explanation: All we need is one counterexample (i.e., one zamzow with tenocritus). In fact, we’ve got two: Alfred and Reggie.