How understand in which logic a sequent is provable and in which one is not?

59 Views Asked by At

Determine if the following sequent is provable in the classic logic, intuitionistic logic or minimal logic. $$ ( \exists x \psi(x) \rightarrow \forall x \theta(x) ) \vdash \forall x ( \psi(x) \rightarrow \theta(x) ) $$ Where $ \psi, \theta$ are two formula such that the only free variable is $x$. I can't use $\forall R$ to go up because $ \psi(x) \rightarrow \theta(x) $ possesses a free variable. I have no idea how to do it. Anyway how do understand in which logic is provable and in which one is not?

1

There are 1 best solutions below

3
On

I try to answer my own question since I think i get how to prove it (at least in classic logic)

$$ \vdash \exists x \psi(x), \forall x( \psi(x) \rightarrow \theta(x) ; \forall x \theta(x) \vdash \forall x( \psi(x) \rightarrow \theta(x) $$ $$ \text{--------------------------------------------------- } \rightarrow L $$ $$ (\exists x \psi(x) \rightarrow \forall x \theta(x)) \vdash \forall x( \psi(x) \rightarrow \theta(x) $$

then for

$$ \text{--------------------------------------------------- axiom } $$ $$ \psi \vdash \psi $$ $$ \text{--------------------------------------------------- } P $$ $$ \psi \vdash \psi, \theta $$ $$ \text{--------------------------------------------------- } \rightarrow R $$ $$ \vdash \psi, \psi \rightarrow \theta $$ $$ \text{--------------------------------------------------- } L \exists , L \forall $$ $$ \vdash \exists x \psi(x), \forall x( \psi(x) \rightarrow \theta(x)$$ and for $$ \text{--------------------------------------------------- axiom } $$ $$ \theta \vdash \theta $$ $$ \text{--------------------------------------------------- } P $$ $$ \theta, \psi \vdash \theta $$ $$ \text{--------------------------------------------------- } R \rightarrow $$ $$ \theta \vdash \psi \rightarrow \theta $$ $$ \text{--------------------------------------------------- } R \forall $$ $$ \theta(t) \vdash \forall x( \psi(x) \rightarrow \theta(x) $$ $$ \text{--------------------------------------------------- } R \forall $$ $$ \forall x \theta(x) \vdash \forall x( \psi(x) \rightarrow \theta(x) $$

Hence it is prouvable in the classic logic. And since I don't think there exist a prove in sequent calculus with less than 1 right rule used then it is not provable in the intuitionistic logic, a fortiori in the minimal.