Disproving: If $(\Gamma\vdash(\phi\,\lor\psi))$, either $(\Gamma\vdash\phi)$ or $(\Gamma\vdash\psi)$ is true

Question

In Chiswell's Mathematical Logic, there is the following problem is posed using the language of propositions (LP):

In some systems of logic (mostly constructive systems where 'true' is taken to mean 'provable') there is a rule

if $(\Gamma\vdash(\phi\,\lor\psi))$ is a correct sequent then at least one of $(\Gamma\vdash\phi)$ and $(\Gamma\vdash\psi)$ is also correct.

By giving a counterexample to a particular instance, show that this is unacceptable as a rule for LP. [Start by giving counterexamples for both the sequents $(\vdash p_0)$ and $(\vdash(\neg p_0))$.]

In my first post on this question, it was answered that one can let $\Gamma = \{p_0\,\lor\,(\neg p_0)\}$. From there, one can deduce neither $(\Gamma\vdash p_0)$ nor $(\Gamma\vdash (\neg p_0))$.

But this does not proceed by the counterexample route that the author suggests. Namely, he seems to imply that we should (1) take an interpretation of propositional variables $p_0,\,p_1,\,\ldots$ (setting each one equal to T or F), and (2) write $\phi$ and $\psi$ as functions of these propositional variables, and (3) pick sentences for $\Gamma$ which are all T, all with the conditions that (A) $(\phi\,\lor\psi)$ is evaluated as T, yet (B) both $\phi$ and $\psi$ are evaluated as F.

This, of course, seems impossible. What, then, am I missing? It seems that taking a concrete interpretation of the propositional symbols makes the constructivist's rule irrefutable. (Note: this is supposed to be a very simple problem set, and I am an elementary logician).

Answer 1

Your confusion seems to stem from limiting yourself to considering only one interpretation at a time. Remember that "$A\vdash p$" means "Every interpretation in which $A$ is true, makes $p$ true." So to show $A\not\vdash p$, you just need to cook up a single interpretation in which $A$ is true and $p$ is false.

In particular, here you need to prove three things:

• $(1)\quad$ $\{p\vee\neg p\}\vdash p\vee\neg p$.

• $(2)\quad$ $\{p\vee\neg p\}\not\vdash p$.

• $(3)\quad$ $\{p\vee\neg p\}\not\vdash\neg p$.

The first point is easy. For the second and third points, you need to cook up counterexample interpretations, but you don't need to use the same interpretation for each point! That is:

• If you can find a single $\nu_1$ satisfying $p\vee\neg p$ but not satisfying $p$, you've done the second bulletpoint above.

• If you can find a single $\nu_2$ satisfying $p\vee\neg p$ but not satisfying $\neg p$, you've done the third bulletpoint above.

Nowhere is there a requirement that both bulletpoints be proved via the same counterexample. Indeed, the fact that points $(2)$ and $(3)$ above can't be proved by the same counterexample is exactly what point $(1)$ says!

Answer 2

See Chiswell & Hodges, page 59 :

Definition 3.4.7 Let ($Γ \vdash ψ$) be a sequent, and let $I$ be an interpretation that makes each propositional symbol appearing in formulas in the sequent into a meaningful sentence that is either true or false. Using this interpretation, each formula in the sequent is either true or false. We say that $I$ is a counterexample to the sequent if $I$ makes all the formulas of $Γ$ into true sentences and $ψ$ into a false sentence.

Consider the case : $\Gamma = \{ p \lor \lnot p \}$.

We have obviously that :

$p \lor \lnot p \vdash p \lor \lnot p$

is correct, because there is no way to find an interpretation $I$ such that $I(p \lor \lnot p)$ is both TRUE (in order to satisfy the premise) and FALSE (in order to falsify the conclusion).

At the same time we have :

$p \lor \lnot p \nvdash p \text { and } p \lor \lnot p \nvdash \lnot p$.

The counterexample for the first one is $I_1$ such that $I_1(p)= \text {FALSE}$, while for the second one is an interpretation $I_2$ such that $I_2(p)= \text {TRUE}$.

We need a counterexample to show that a sequent is not correct. But there is no need that it is the same one for both sequents.