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).


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!

  • $\begingroup$ Thanks Noah. Is it fair to say that, "in any given interpretation, if (1) is true, then either (2) and (3) is true"? Furthermore, can I say that, "for all interpretations, (1) being true neither implies that (2) is true nor (3) is true -- rather, which one of (2) or (3) being true will depend on the given interpretation". $\endgroup$ – Doubt Sep 8 '18 at 1:57
  • 2
    $\begingroup$ @Doubt You're on the right track, but you're conflating various statements. Let me first rephrase your comment so that it's correct: "in any given interpretation, if $p\vee q$ is true, then either $p$ [or] $q$ is true." This is right. Similarly, "for all interpretations, $p\vee q$ being true neither implies that $p$ is true nor $q$ is true -- rather, which one of $p$ or $q$ [is] true will depend on the given interpretation" is correct in general. (cont'd) $\endgroup$ – Noah Schweber Sep 8 '18 at 16:43
  • 1
    $\begingroup$ However, note that my statements (1),(2),(3) are statements about provability; they're not statements which are true/false about a single interpretation, they're statements about the class of all interpretations. It doesn't make sense to ask whether "$\{p\vee q\}\vdash p$" (or similar) is true in an interpretation $\nu$. Does this make sense? $\endgroup$ – Noah Schweber Sep 8 '18 at 16:44
  • $\begingroup$ Yes, you're last statement is very helpful! The distinction between provability and truth is a evidently a very delicate one! If you know of any (introductory-level) reading on this subject, let me know. $\endgroup$ – Doubt Sep 10 '18 at 16:36

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.

  • $\begingroup$ Thanks Mauro -- but this uses two different interpretations $v_1$ and $v_2$. Aren't interpretations only meaningful if we stick to one of them? $\endgroup$ – Doubt Sep 6 '18 at 15:20
  • 1
    $\begingroup$ @Doubt - we need a counterexample to show that the sequent is not correct; but it is not necessary that it is the same one for boty. $\endgroup$ – Mauro ALLEGRANZA Sep 6 '18 at 15:29
  • $\begingroup$ @Doubt Think about it this way: if I make two false claims, you don't have to refute them each in the same way. (To clarify, the false claims in this case are "$\{p\vee\neg p\}\vdash p$" and "$\{p\vee\neg p\}\vdash\neg p$" - not "$p$" and "$\neg p$.") $\endgroup$ – Noah Schweber Sep 6 '18 at 16:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.