How can I provide a counterexample for this predicate logic problem?

Question

I'm honesty still unsure of what a counterexample even is, and what I've found on isn't helping me much in the way of understanding. I'm hoping to get pointed in a correct direction.

Predicates L(x) (lion), A(x) (animal), M(x) (mortal). Give a counterexample to show that the following is not a valid logical implication.

“All lions are animals. All lions are mortal. Therefore all animals are mortal.”

I think I've formalized this correctly as...

∀x(lion(x) → animal(x))

∀x(lion(x) → mortal(x))

Therefore...

∀x(animal(x) → mortal(x))

But I'm unsure as to how to begin with providing a counterexample.

Answer 1

It's difficult to answer this without doing the problem; presumably you have some other problems like this, where you can use the basic idea.

You use a counterexample when the statement is FALSE. In this case, you need to show that the first two parts are true, but the last part doesn't have to be.

To make the last part false, you need an $x$ which is an animal but not mortal.

Can that animal be a lion? No, because then it would be mortal by assumption. It could be any other type of animal, though, such as a unicorn.

An immortal unicorn doesn't contradict the assumptions you're given -- False implies anything is True -- but it does contradict the conclusion.

Answer 2

Imagine there is an imortal porpoise. This doesn't violate any of the two hypotheses. It's an animal, but is not a lion so it doesn't need to be mortal.

(Don't cross the state lion with gulls for immortal porpoises.)

Answer 3

The (proposizional) logic implication $(A \wedge B) \to C$ is obviously not "valid": it is not true for every interpretation, for example it is false when $C$ is false and both $A$ and $B$ are true.

You have something simlar with predicate logic, where $A=\forall x( l(x) \to a(x))$, $B=\forall x (l(x) \to m(x))$ and $C=\forall x (a(x) \to m(x))$, it's still not valid because it is false for $C$ false and both $A$ and $B$ true, but you need to find a "predicate logic"-interpretation, that is not just truth value assignment but a "universe" set and three actual property for elements of the set.

For example we can take:

• the set $\mathbb N$ of natural numbers
• $l(x)$ is $x$ is divisible by $6$
• $a(x)$ is $x$ is divisible by $2$
• $m(x)$ is $x$ is divisible by $3$

now you have:

• $\forall x( l(x) \to a(x))$ true
• $\forall x( l(x) \to m(x))$ true

but

• $\forall x( a(x) \to m(x))$ false

So this model offers a counterexample proving that the implication is not valid.

Answer 4

Let your domain be $\{1,~2\}$. Define $\text{animal}(x)$ as $x = 1$. Define $\text{mortal}(x)$ as $x = 2$. Define $\text{lion}(x)$ as $x \ne 1 \land x \ne 2$.

Then

$$\begin{array} {c} \forall x ~:~ \text{lion}(x) \implies \text{animal(x)},~ \forall x ~:~ \text{lion}(x) \implies \text{mortal(x)} \\ \not \models \\ \forall x ~:~ \text{animal}(x) \implies \text{mortal(x)} \end{array}$$

And since the statement doesn't hold in all models, it is not valid.