In [Mathematical Logic] by Chiswell and Hodges, within the context of natural deduction and the language of propositions LP (basically like here) it is asked to show, by counter-example that a certain 'sequent rule' is 'unacceptable'.

I suppose the proof should follow an example a few pages earlier that shows that the sequent rule $$(p_0 \to p_1 \vdash p_1)$$ is unacceptable due to the following counter-example: let both $p_0$ and $p_1$ mean $(2=3)$. The book argues that indeed if $(2=3)$ then $(2=3)$, so the left side is true, but the right side: $(2=3)$ is false. The conclusion is that we found a counter-examples and the sequent rule is unacceptable.

It is now asked to prove that this sequent rule is unacceptable:

If $$(\Gamma \vdash (\phi \lor \psi))$$ is correct (i.e has a derivation), then at least one of $$(\Gamma \vdash (\phi))$$ and $$(\Gamma \vdash (\psi))$$ is also correct.

The book hints that one should first try to give a counter-example 'for both sequents $(\vdash p_0)$ and $(\vdash \lnot p_0)$'. What could such a $p_0$ be? Does the book mean using as $p_0$ something like 'red is square'? Or some liar kind of sentence 'this sentence is false'? Or some known undecidable statement (which I doubt due to the level of this book)? Or am I totally off and misunderstand something?

  • $\begingroup$ Adding on @Noah comment, you have to consider two counterexamples; we know that e.g. $\vdash \forall x Px \lor \lnot \forall x Px$ because it is a tautology. Now, to show that no one of the two disjuncts is a tautology, consider as interpretation of $Px$ : "$x$ is $\text{ even}$" : clearly, $\mathbb N$ falsify $\forall x Px$ and thus we have that $\nvdash \forall x Px$. 1/2 $\endgroup$ – Mauro ALLEGRANZA Apr 13 '17 at 8:52
  • $\begingroup$ Now consider a different interpretation for $P$ : $(x \ge 0)$ and we have again that $\mathbb N$ falsify $\lnot \forall x (x \ge 0)$ (i.e. $\exists x (x < 0)$ and thus : $\nvdash \lnot \forall x Px$. 2/2 $\endgroup$ – Mauro ALLEGRANZA Apr 13 '17 at 8:55

There is in fact a small taste of undecidability lurking here, but it's in a very weak form: we're looking at sentences which are undecidable from the empty theory.

The point is that no matter what $p$ is, we can prove - from no axioms at all! - the sentence "$p\vee\neg p$". That is, the sequent $$\vdash p\vee\neg p$$ is derivable (at least, in any decent sequent calculus).

But think about what "$\vdash p$" means - it means that $p$ is a tautology. Similarly, $\vdash \neg p$ means that $\neg p$ is a tautology. So it's enough to find a single sentence which is neither a tautology nor a contradiction.

In natural language, a good example is something like "Blue is my favorite color." Maybe it is! Maybe it isn't! Certainly we can't prove what my favorite color is just using the axioms of logic - we would need some assumptions about me - but we can prove "Either blue is my favorite color or it isn't."

In propositional logic, we could just take $p$ to be some propositional atom. Then $p\mapsto\top$ makes $\neg p$ false, while $p\mapsto\bot$ makes $p$ false; so neither $p$ nor $\neg p$ is true under every evaluation. That is, neither $\vdash p$ nor $\vdash \neg p$ is acceptable.

In predicate (=first-order) logic, we could take $p$ to be something like "$U(c)$", where $U$ is a predicate symbol and $c$ is a constant symbol. This sentence is true in some structures, and false in others. So again neither $\vdash p$ nor $\vdash \neg p$ is acceptable.

  • $\begingroup$ I see, to make it more concrete like the books example, setting $p:=\text{'every natural is even'}$ would do the job? $\endgroup$ – jadn Apr 12 '17 at 23:57
  • $\begingroup$ @weakmoons Well, that might be a bad example - although we can't disprove it without using any axioms, it is false in the intended interpretation. I feel like the intuition is better communicated by using a sentence which is just ambiguous - for which we have no intuition for whether it's true or false. Another example could be "$c$ is even," where $c$ is some constant symbol - without declaring something about $c$, even the axioms of arithmetic won't let you prove or disprove this sentence! $\endgroup$ – Noah Schweber Apr 13 '17 at 0:04

My approach would be a bit different: if $\Gamma = \{ p \vee q \}$ where $p$ and $q$ are atomic formulae, then $\Gamma \vdash p \vee q$ so the rule would imply that either $\{ p \vee q \} \vdash p$ or $\{ p \vee q \} \vdash q$. But in the first case, assigning $p := (2 = 3)$ and $q := (3 = 3)$ would disprove that; and in the second case, assigning $p := (3 = 3)$ and $q := (2 = 3)$ would disprove that.

(It is interesting to observe, however, that if $\Gamma = \emptyset$ and you're restricted to intuitionistic logic, then the statement is actually true: if $\phi \vee \psi$ is an intuitionistic tautology then either $\phi$ is an intuitionistic tautology or $\psi$ is an intuitionistic tautology. Again, that's obviously false if you extend to classical logic.)

  • $\begingroup$ That is a nice approach indeed. But your note leads me to another possible misunderstanding I might have. You say that in classical logic, and if $\Gamma = \emptyset$, then 'that is obviously false', what is obviously false? If I write a truth table with $[(p),(q),(p \lor q)]$ as columns, whenever $(p \lor q)$ is $1$, either one of $(p)$ or $(q)$ is also one ... what am I missing here? $\endgroup$ – jadn Apr 12 '17 at 23:53
  • $\begingroup$ That goes back to Noah Schweber's answer: classically, $p \vee \lnot p$ is a tautology for an atomic formula $p$, but neither $p$ nor $\lnot p$ is a tautology by itself. $\endgroup$ – Daniel Schepler Apr 12 '17 at 23:55
  • $\begingroup$ So then my idiotic mistake is not thinking of the right sides of $\vdash p$ and $\vdash q$ as tautologies ... :S $\endgroup$ – jadn Apr 13 '17 at 0:11
  • $\begingroup$ @NoahSchweber My argument was: apply the rule in the case where the atoms are precisely $\{ p, q \}$ then it derives one or the other of $p \vee q \vdash p$ or $p \vee q \vdash q$, and by appropriate assignments of truth values to $p$ and $q$ you can show both are invalid. No need for an implicit assumption that the rule must be "functorial" in which case it would indeed reduce to one of the silly rules (since this example is essentially a "universal example"). $\endgroup$ – Daniel Schepler Apr 13 '17 at 0:14
  • 1
    $\begingroup$ @weakmoons As a response to your first comment - I'm not sure how far afield this is getting, but there also happen to be Boolean algebras where it's possible $x \vee y = \top$ but $x \ne \top$ and $y \ne \top$. $\endgroup$ – Daniel Schepler Apr 13 '17 at 0:17

$p_0$ could be: 'it is raining'. Then, while we can claim without any assumptions that '(it is raining) or (it is not raining)' is correct, it is clear that we cannot from that claim derive a claim, using no assumptions, that '(it is raining)' is correct, similarly for '(it is not raining)'.


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.