26
$\begingroup$

I am reading a Set Theory book by Kunen. He presents first-order logic and claims that if a set of sentences in inconsistent, then it proves every possible sentence. Since he does not explicitly specify the inference rules, I became curious as to how fundamental this property of inconsistent systems is.

So my question is what is the simplest proof, with the least use of assumptions, of the vague claim that "inconsistent systems can prove anything" - in particular I'm interested in the assumptions about the system needed to prove this - is it true only for first order logic? Only for first order logic with the "standard" rules of inference (Modus ponens and GEN)? Or is it such a basic truth that it can be proved for every "reasonable" proof system (and what is "reasonable")?

  • 0
    @CharlesStewart Absolutely right; in minimal logic by itself, the choice of $\bot$ is arbitrary, since it doesn't have the usual properties of $\bot$. But the interesting results about the relationship between classical, intuitionistic, and minimal logic (e.g., that classical and intuitionistic logic are interpretable with respect to derivability in minimal logic by a [double-negation translation](http://en.wikipedia.org/wiki/Double-negation_translation)) are more elegant to express if all the systems have a symbol $\bot$, and abbreviate $A \to \bot$ by $\lnot A$.2013-05-03

4 Answers 4

2

If you assume natural deduction, this is easy to explain. Let $\Sigma$ be an inconsistent set of axioms. This means you can prove both $\phi$ and $\lnot\phi$ for some statement $\phi$: in symbols $\Sigma\vdash\phi$ and $\Sigma\vdash\lnot\phi$. Now you suppose the negation of whatever statement $\psi$ you like to prove, but since, by monotonicity, $\Sigma\cup\{\lnot\psi\}\vdash\phi$ and $\Sigma\cup\{\lnot\psi\}\vdash\lnot\phi$, you can apply negation elimination obtaining $\Sigma\vdash\psi$.

  • 2
    Like Asaf's proof, this requires [double] negation elimination, which is not available in intuitionistic logic.2015-03-15
14

If $T$ is an inconsistent set of first order theorems (or axioms for the proof), then it is possible to prove from $T$ for some $\alpha$ both $\alpha$ and $\neg \alpha$. So without the loss of generality we can assume that $T$ includes $\alpha$ and $\neg\alpha$.

Now suppose that $\beta$ is whatever first order sentence that you want to prove.

  1. $\alpha$ (in $T$)
  2. $\beta \to \alpha$ (easily verified to be true since $\alpha$ is an axiom of $T$)
  3. $\neg \alpha \to \neg \beta$ (Contrapositive Law)
  4. $\neg \alpha$ (axiom of $T$)
  5. $\neg \beta$ (inferred from 3 & 4)
  6. $\neg \beta \to \alpha$ (holds for the same reason in 2, further more we have $\neg\beta$)
  7. $\neg \alpha \to \neg\neg\beta$
  8. $\neg \neg \beta$ (inferred from 4,7)
  9. $\neg \neg \beta \to \beta$ (tautology)
  10. $\beta$ (inferred from 8,9)

So you see, you can prove pretty much anything you want from $\\{\alpha ,\neg\alpha\\}$ for some first order sentence $\alpha$.

  • 1
    @GadiA I don't understand why you accepted Stewart's answer instead of this: Asaf answered exactly in the context you asked, Stewart's answer is a nice one, but it is more a curiosity than something that answers what you asked.2016-12-12
9

It doesn't have to: logics which don't are called paraconsistent.

The most important paraconsistent logic is relevance logic, which repudiates the K axiom: $\alpha \rightarrow (\beta \rightarrow \alpha)$ and replaces it by axioms that do not allow there to be unused assumptions. This is equivalent to saying weakening, the principle that if $\Gamma \vdash \alpha$ then $\Gamma'\vdash \alpha$ for $\Gamma\subset\Gamma'$. This blocks derivations such as Weltschmertz's, which appeals to the K axiom once, Asaf's which uses it twice; Francesco appeals to monotonicity in his proof, which is another name for weakening.

It's not difficult to see that this also blocks proofs of everything from a contradictory pair of propositions in a logic satisfying compactness, since one can prove inductively about such proof systems that if $\alpha\rightarrow\beta$, then all positive atoms in $\beta$ must occur either negatively in $\beta$ or positively in $\alpha$. So if our contradictory pair (over an assumption) takes the form $\alpha\rightarrow\beta$ and $\alpha\rightarrow\neg\beta$, we need to prove for any $\gamma$ that $\alpha\rightarrow\gamma$. But if we choose $\gamma$ to be any positive atom not occuring in $\alpha$, our inductive proof tells us this cannot be done. We need compactness here, to be ensure that the basis for all contradictory pairs can be expressed by a finitary formula.

  • 0
    How about adding the parentheses? The convention you're citing is obscure to many people who would be able to follow what you are saying immediately if you would add the parentheses.2018-08-01
7

From my recollection, it goes something like this: if $K$ is a first-order inconsistent theory, there exists, by definition, a formula $C$ such that $\vdash_{K} C$ and $\vdash_{K}\neg C$. If $D$ is an arbitrary formula in $K$ then we have the following chain (proof):

  1. $C$
  2. $\neg C$
  3. $\neg C \Rightarrow (C\Rightarrow D)$ (Tautology)
  4. $C \Rightarrow D$ (2,3, Modus Ponens)
  5. $D$ (1,4, Modus Ponens).

Now, if inconsistency is defined the same way for logics of any other order, I think this proof wouldn't change. I don't see anything explicit about first-orderness in it, but correct me if I'm wrong.

  • 0
    Now I see why your answer doesn't help me. For me inconsistent means that our syntactic derivation rules prove $\bot$. But $\bot$ does not mean $p \land \neg p$. In my case $\Sigma \vdash p \land \neg p \to \Sigma \vdash \bot$ bot the converse is not obvious (your proof doesn't work cuz I don't know $p$ and $\neg p$ are provable, thats what I want to show if $\bot$ is provable in $\Sigma$).2018-10-25