Considering that $\Gamma$ is inconsistent if $ \Gamma \vdash ¬(\alpha \rightarrow \alpha) $ for some formula $\alpha$.

How to prove that if $ \Gamma $ is inconsistent, then $ \Gamma \vdash \beta $?

Do I need to assume that a proof of $ ¬(\alpha \rightarrow \alpha) $ exists and try to find $\beta$ using axioms? Is it possible?

List of axioms:


  • $\begingroup$ You can even prove that Bertrand Russell is actually the Pope. $\endgroup$ – Levent Jul 6 '16 at 20:09
  • 1
    $\begingroup$ @Levent: Only of the vocabulary of the theory you're working in allows you to state that claim. (Though indeed I have never seen Bertrand Russell and the Pope in the same room at the same time, which -- now that you mention it -- is kind of suspect ...) $\endgroup$ – Henning Makholm Jul 6 '16 at 20:17
  • $\begingroup$ We need to know more about the system at hand in order to answer all of your questions. What are the axiom(s) and the rule(s) of inference? $\endgroup$ – Doug Spoonwood Jul 6 '16 at 20:33
  • 1
    $\begingroup$ @DougSpoonwood, edited with the axioms. Thanks. I may use Deduction Theorem and Modus Ponens. $\endgroup$ – Bruno A Jul 6 '16 at 20:37

If you can prove $\Gamma \vdash ¬(\alpha \rightarrow \alpha)$, you can say $$\Gamma,\lnot \beta \vdash ¬(\alpha \rightarrow \alpha) \\ \Gamma \vdash (\lnot \beta \implies¬(\alpha \rightarrow \alpha)) \\ \Gamma \vdash \beta$$

  • $\begingroup$ How did you get from the second line to the last? Using axioms and Modus Ponens? $\endgroup$ – Bruno A Jul 6 '16 at 20:39
  • $\begingroup$ It is the usual proof by contradiction. From something implies contradiction, derive not something. $\endgroup$ – Ross Millikan Jul 6 '16 at 20:45

With Ax.1 and Ax.2 we can easily prove two useful results : the Deduction Theorem and:

$\vdash (\alpha \to \alpha)$.

From the last one, we have:

$\Gamma, \lnot \beta \vdash (\alpha \to \alpha)$.

From $\Gamma, \vdash \lnot (\alpha \to \alpha)$ we have:

$\Gamma, \lnot \beta \vdash \lnot (\alpha \to \alpha)$.

Now we may "cook" the two results together with the Ded Th and Ax.3:

$\vdash (\delta \to \gamma) \to ((\delta \to \lnot \gamma) \to \lnot \delta)$

to conclude with:

$\Gamma \vdash \lnot \lnot \beta$.

Using Ax.10 (Double Negation):

$\vdash \lnot \lnot \beta \to \beta$,

we conclude with:

$\Gamma \vdash \beta$.


Hint: Prove that, in Polish notation, $\vdash$CpCNpq.

More fully:

axiom 1 CpCqp
axiom 2 CCpCqrCCpqCpr
axiom 3 CCpqCCpNqNp
axiom 4 CNNpp
2 r/p 5 CCpCqpCCpqCpp
5, 1  6 CCpqCpp
6 q/Cqp 7 CCpCqpCpp
7, 1    8 Cpp
hypothesis  9 | p
hypothesis  10 || Np
1 q/Nq      11 || CpCNqp
1 q/Nq p/Np 12 || CNpCNqNp
11, 9       13 || CNqp
12, 10      14 || CNqNp
3 p/Nq, q/p 15 || CCNqpCCNqNpNNq
15, 14      16 || CCNqNpNNq
16, 14      17 || NNq
4 p/q       18 || CNNqq
18, 17      19 || q
10-19       20 | CNpq
9-20        21 CpCNpq
21 p/Cpp    22 CCppCNCppq
22, 8       23 CNCppq

Thus, given that $\Gamma$ $\vdash$ NCpp for some formula p, since 23 holds, it follows that $\Gamma$ $\vdash$ q.


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.