# Prove that if $\Gamma$ is inconsistent, then $\Gamma \vdash \beta$ for every formula $\beta$

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:

Axioms

• You can even prove that Bertrand Russell is actually the Pope. – Levent Jul 6 '16 at 20:09
• @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 ...) – Henning Makholm Jul 6 '16 at 20:17
• 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? – Doug Spoonwood Jul 6 '16 at 20:33
• @DougSpoonwood, edited with the axioms. Thanks. I may use Deduction Theorem and Modus Ponens. – 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$$

• How did you get from the second line to the last? Using axioms and Modus Ponens? – Bruno A Jul 6 '16 at 20:39
• It is the usual proof by contradiction. From something implies contradiction, derive not something. – 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.