Is this sequent rule unacceptable?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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