1

In Chiswell's Mathematical Logic, one of the exercises is to show that the following statement admits counterexamples:

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.

The hint for this exercise suggests finding examples where both $\vdash p$ and $\vdash(\neg p)$ are not correct sequents. But even this last part perplexes me, for, given the context, one is expected to give a counterexample from basic mathematics.

My question is: what's a simple example wherein both $\vdash p$ and $\vdash(\neg p)$ are not correct sequents?

Doubt
  • 1,719
  • If the language has $P$ as an atom and no axioms, then I would think neither $\vdash P$ nor $\vdash \lnot P$ would be a correct sequent (since in each case there will be an assignment of truth values to atoms making the statement false). – Daniel Schepler Jul 03 '18 at 21:38
  • @DanielSchepler you're right -- fixed! I must confess I don't quite understand your first comment. – Doubt Jul 03 '18 at 21:44
  • In terms of Model Theory: If $\Gamma$ is not a complete theory then some sentence $p$ is neither provable nor disprovable from $\Gamma.$ Then neither $\Gamma \vdash p$ nor $\Gamma \vdash \neg p$ is true. But the law of the Excluded Middle requires $\Gamma\vdash (p\lor \neg p).$ – DanielWainfleet Jul 03 '18 at 22:08
  • @DanielWainfleet But what would be a simple example of this? The textbook uses examples like having $p$ stand for $2=3$, and other simple sentences. That's what has me stuck. – Doubt Jul 04 '18 at 18:26
  • 1
    Let $\Gamma$ be the axioms for a group. Let $p$ be $\forall x,y;(xy=yx).$ – DanielWainfleet Jul 06 '18 at 01:41

2 Answers2

2

See : Chiswell and Hodges, page 7 :

We read the sequent $(Γ \vdash ψ)$ as "$Γ$ entails $ψ$". The sequent means

There is a proof whose conclusion is $ψ$ and whose undischarged assumptions are all in the set $Γ$.

When it is true, we say that the sequent is correct. The set $Γ$ can be empty, in which case we write $(\vdash ψ)$; this sequent is correct if and only if there is a proof of $ψ$ with no undischarged assumptions.

Both $p$ and $\lnot p$ are not derivable without assumptions in a sound calculus, because $p$ is a propositional letter: it stands for a sentence whatever and thus we can always interpret it with a FALSE statement.

And the same for $\lnot p$.

Thus :

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

But the problem asks for : $\Gamma \vdash (\phi \lor \psi)$.

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

We have obviously :

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

but :

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

"Real world" example : for sure, it is TRUE that "either it is raining or it is not raining".

But from the obvious fact that : it is the case that (it is raining or it is not raining) we cannot infer that it is raining, nor that it is not raining.

Community
  • 1
Mauro ALLEGRANZA
  • 94,169
1

Strangely enough I read an answer that I put up here a few years ago to a similar question, which also applies here. I'm not sure where the answer lies though.

$\Gamma$ could be any set of formulas, correct? So, suppose that $\Gamma$ is the set of all tautologies. Now, can you fine some $\phi$ and some $\psi$ where Γ⊢(ϕ∨ψ) holds, but neither Γ⊢ϕ nor Γ⊢ψ?

Doug Spoonwood
  • 11,211
  • Thanks Doug. I suppose $\Gamma\vdash(\phi\lor\phi)$ would be an example of this. But my real question has to do with Chiswell's hint: what's a simple sentence $p$ wherein $\vdash p$ and $\vdash(\neg p)$ are both incorrect sequents? – Doubt Jul 04 '18 at 18:30
  • Γ⊢(ϕ∨ϕ) doesn't work when Γ is the set of all tautologies. With respect to Chsiwell's hint, suppose that $\psi$ is $\lnot$p, and $\phi$ is p. – Doug Spoonwood Jul 05 '18 at 13:44