How do I show that a goal cannot be proven from premises?

Question

In the textbook, Introduction to Logic by Patrick Suppes, the reader is asked to derive a sentence from some premises on page 63. I have supplied the premises and the goal in the quote box.

So far as I can tell, it is not possible to derive the goal from the premises, since it is not satisfied by them, and neither is its negation (the premises do not assign either a truth value).

Premises:

• $\forall x \forall y \forall z(Q(x,y)\land Q(y,z)\rightarrow Q(x,z))$
• $\forall x \forall y (Q(x,y)\lor Q(y,x)$
• $\forall x \forall y (P(x,y)\iff \lnot Q(y,x)$

Using the above premises, the goal was to prove:

Goal:

• $\forall x \forall y \forall z(P(x,y)\land P(y,z)\rightarrow P(x,z))$

I want to know of a general way to show that the goal is not provable from the premises in situations like this one. Is there a way to show that a sentence and its negation are not assigned truth values from particular premises in FOL (first order logic)? If so, how would I go about showing this myself?

Answer 1

In general, to show that some argument is not valid, you have to consTruct a counterexample: a logically possible scenario where the premises are true, but the conclusion is false.

For a FOL argument, you do this by coming up with some domain and some interpretation for the predicate symbols. You could, for example, take as the domain the natural numbers or integers, and interpret $Q(x,y)$ as $x \leq y$. Note that that interpretation will nicely satisfy the first two premises, and by choosing $P(x,y)$ as $x > y$, you can also satisfy the third premise. However, this is not going to be a counterexample, because this interpretation will also make the conclsuion true.

So, if there is a counterexample to the argument, we'll need to [pick some other interpretation for the predicate symbols .. or a different domain altogether.

Now, you don;t actually have to think of some 'meaningful' domain like the integers. You could also just say: "OK, let the domain consist of some objects we'll call $a$, $b$, and $c$, and let relationship $Q$ hold between $a$ and $b$, but not vice versa ... etc."

In fact, let's see what it would take for the premises of this argument to be true but the conclusion to be false. Focusing on the conclusion first, this means that we need to have objects $a$, $b$, and $c$ such that we have $P(a,b)$ and $P(b,c)$, but not $P(a,c)$. By premise $3$, this also means we need to have $Q(c,a)$, but neither $Q(b,a)$ not $Q(c,b)$. By premise $2$, the latter means that we do need to have $Q(a,b)$ and $Q(b,c)$. But by premise $1$: once we have $Q(b,c)$ and $Q(c,a)$, we should also have $Q(b,a)$, which contradicts that we couldn't have $Q(b,a)$.

So, what this argument shows, is that there is no counterexample possible. In fact, the above argument can be made into a formal proof that does derive the conclusion from the premises.

Here is a proof in Fitch. The 'DS 2' is a lemma I use for Disjunctive Syllogism:

Answer 2

The usual way is to construct a model (a set and relations $Q$ and $P$ on it) that obey the premises, but not the conclusion. By the completeness of first order logic this is necessary and sufficient.

But I think here the goal nearly achievable:

assume $P(x,y) \land P(y,z)$. Then $\lnot Q(y,x)$ (by 3), hence $Q(x,y)$ by 2. Likewise $Q(y,z)$. Then apply 1. We get $Q(x,z)$, but indeed $P(x,z)$ is not yet clear. But if $\lnot P(x,z)$ we get $Q(z,x)$ by 3. But $Q(z,x)$ and $Q(x,z)$ could both hold (from the premises I see no direct problem). So this might give an idea for a "countermodel".

It seems that the premises 2 and 3 just prove $\forall x\forall y\left(P(x,y) \to Q(x,y)\right)$, at least when we have excluded middle, which I assume we do.