Section Progress:

26.1 Counterexamples in FOL

You already know how to use counterexamples in propositional logic (BOOL and PROP).

For example, consider this argument:

1. (P&Q)→R

Thus,

2. P→R

In PROP and BOOL, a counterexample is just a row of a truth table.

More specifically, a counterexample is an assignment of truth values to the atomics, so that the premises are true and the conclusion false.

So this counterexample is: P is true and Q and R are false.

In FOL, truth tables cannot provide a semantics of the quantifiers and identity, because those new symbols are not truth functional.

But we still need to do something analogous: we give meaning to the basic parts of the system so that the premises are true and the conclusion false.

Only now, the basic parts aren’t atomic sentences. They are the names and predicates, plus the domain of quantification.

For example, consider this argument:

1. (G(p)&G(q))→G(r)

Thus,

2. G(p)→G(r)

This is just like the propositional argument above, but not it’s in FOL. We still want G(p) to be true and G(q) and G(r) to be false.

But we have to create that pattern of truth values by interpreting the names and predicates. Here’s how we do it.

3 Parts in a FO Counterexample:
1. Meanings
2. Facts
3. Domain

First, we give meanings to the predicate G() and the names p, q and r. For example,

G(x) == x is guilty

p == Pia

q == Quinn

r == Raquel

But that doesn’t yet tell us whether those atomics are true or false. We have to know not just that G(p) means “Pia is guilty”, we have to know the facts: who is guilty and who isn’t.

So here’s the second part of our counterexample: Pis is guilty, and Quinn and Raquel are not.

This argument has no quantifiers, so technically we are done, because the premise is true and the conclusion is false.

But if we had quantifiers, we would also have to specify the domain.

Usually the domain is easy to specify. For example, we could just have it include the objects that our names refer to. So D = {Pia, Quinn, Raquel}.

Next, consider a new argument:

1. ∃xC(x)&∃xD(x)

Thus,

2. ∃x(C(x)&D(x))

The problem above could only be solved one way, by assigning “x is a cat” to C(x). But that is misleading.

It would actually work to assign “x is a cat” to D(x), etc. The premise would still be true and the conclusion false.

Logic doesn’t care whether C(x) means x is a cat. When we translate into FOL, we try to choose predicates that make it easy for us to read, whether long form or short form.

But remember what we said about intended interpretations in Chapter 22. FOL doesn’t require that Cat() or C() mean “cat”.

For all logic cares, we could interpret C() to mean “dog”.

Here’s how we’ll handle this situation: whenever possible, build counterexamples in obvious ways, following an intended interpretation.

But you’ll also encounter situations where the predicates have no intended interpretation, and you just have to figure out what interpretation makes the premises true and conclusion false.

27.1 Counterexamples in FOL