3
$\begingroup$

I am aware of threads here and here which asks something similar. However, I had something very specific to ask under the same context.

I have a very elementary question about the connection between Godel's second incompleteness thorem and the method of proof by contradiction. From my limited knowledge that I have managed to gather from books and the internet, Godel's second theorem states that "No consistent, recursively axiomatized theory that includes Peano Arithmetic can prove its own consistency."

Consistency means that an axiomatic system cannot result in some statement, and its negation to be both simultaneously provable from the axioms or in other words, the axiomatic system is free of contradictions.

Proof by contradiction, I suppose, is based on the above fact. Since the axiomatic system is consistent, we should not be able to prove that a statement is both true and false at the same time. In other words, we are basically assuming that the system is free from contradictions based on which, we have proofs by contradiction. Proof by contradiction is routinely used in many mathematical disciplines like real analysis which I presume includes the Peano Arithmetic for the construction of real numbers.

However, Godel's second theorem states that we can never prove formally, within that system, its own consistency.

My question: Are we then just "assuming" consistency of the axiomatic system and then construct proofs based on contradiction? Consistency has to be assumed because Godel's second theorem makes it clear that we can never prove that the axiomatic system is consistent. Please clarify if consistency is assumed or if it is not so, please clarify the error in this thought process.

$\endgroup$
15
  • $\begingroup$ You posted an identical question here: math.stackexchange.com/questions/3701956/… Please delete the duplicate. $\endgroup$
    – heropup
    Jun 2, 2020 at 6:40
  • 2
    $\begingroup$ I am sorry about that. They are all deleted now. $\endgroup$
    – TryingHardToBecomeAGoodPrSlvr
    Jun 2, 2020 at 6:48
  • 3
    $\begingroup$ If the system is inconsistent, then everything can be proved, so if you prove something by contradiction, then you have proved it, whether the system is consistent or not. $\endgroup$
    – Gerry Myerson
    Jun 2, 2020 at 6:50
  • $\begingroup$ "Proof by contradiction" is a logical tool and we formalize it through proof systems (Natural Deduction, Hilbert-style) that are consistent. This means that the rule does not produce inconsistencies: this is exactly how the rule works. We assume $P$ and if we derive $\bot$, due to the fact that the rules are sound, we have to conclude that $P$ is not true. $\endgroup$
    – Mauro ALLEGRANZA
    Jun 2, 2020 at 7:58
  • $\begingroup$ But we use logical rules to derive theorems from axioms; if the axioms are already inconsistent, then... $\endgroup$
    – Mauro ALLEGRANZA
    Jun 2, 2020 at 8:00

1 Answer 1

Reset to default
5
$\begingroup$

We do not make that assumption, per se, when we prove things in a given system. Proof by contradiction is a valid rule of inference in (classical) logic... we can use it to prove things in a consistent system and we can use it to prove things in an inconsistent system. There is no assumption here... the rules are the rules.

Of course, if you are using an inconsistent set of axioms, you will be able to, in principle, to prove every statement. That's not a very good state of affairs from a philosophical standpoint.

So we want to know our axioms are consistent, not so that we can use proof by contradiction (again, that's cart-before-horse), but so that we know we're doing something meaningful. And Godel tells us (with a few caveats) that we'll never have a proof of a strong system from a weak (i.e. "safer") system, so tells us we will basically be assuming consistency rather than proving it in a philosophically satisfying way.

(Note also that even without knowledge of Godel's theorem, we would know that we need to take some consistency on faith since we need to assume the consistency of whatever simple "system" we make our most basic arguments about how proofs fit together. The hope that Godel destroys is that within this simple system, we might prove the consistency of a strong system like ZFC, where real heavy-duty mathematics is done)

$\endgroup$
13
  • 2
    $\begingroup$ This is pretty much what I had expected. Your comment that "we will basically be assuming consistency rather than proving it in a philosophically satisfying way." confirmed my doubts. The reason why I posted this question is because when we have a proof by contradiction, strictly speaking, what we are saying is that "the hypothesis is wrong OR the system is inconsistent." Proofs by contradiction just assumes that the hypothesis is wrong. There is always the possibility that the system is inconsistent, which is never mentioned in any proof involving proof by contradiction. $\endgroup$
    – TryingHardToBecomeAGoodPrSlvr
    Jun 2, 2020 at 8:54
  • $\begingroup$ @TryingHardToBecomeAGoodPrSlvr Classical logic has been remarkably successful in modelling many aspects of reality. You can be paralyzed with doubt, fretting about the remote possibilities, or you can get on with the task of making the world a better place. Perhaps you might be comforted by the fact that the only time that an inconsistency was found in a set theory, it was detected by Russell even before it was published. It took only a few years to tweak the axioms sufficiently. Einstein's relativity theory came out at the height of this supposed "crisis". Math and science went on as before. $\endgroup$
    – Dan Christensen
    Jun 2, 2020 at 14:51
  • 2
    $\begingroup$ @DanChristensen It's not really about being paralyzed with doubt or about fretting about remote possibilities. It is about rigor. If we were to be completely rigorous about our proofs, then any proof by contradiction should have concluded with "Hence, either our hypothesis is wrong, or the axiomatic system is inconsistent." The second part of the conclusion never appears in any proof, nor in the footnotes. It would suffice if this is made clear in the introductory part of the book saying $\endgroup$
    – TryingHardToBecomeAGoodPrSlvr
    Jun 2, 2020 at 14:53
  • $\begingroup$ "All proofs by contradiction, technically speaking, can possibly be a result of an inconsistent axiomatic system. With the assumption that this is always a possibility, we will typically conclude such proofs by contradiction by saying that the hypothesis is false." $\endgroup$
    – TryingHardToBecomeAGoodPrSlvr
    Jun 2, 2020 at 14:53
  • $\begingroup$ @TryingHardToBecomeAGoodPrSlvr Proof by contradiction has worked for thousands of years. "Tested and found effective" as they say in TV commercials. I'm guessing you don't have much experience writing formal proofs. (Like most people, even mathematicians.) If I may suggest, you should download some software that will teach you basic method of proofs including proof by contradiction. They should become second nature to you with only a few hours of practice. $\endgroup$
    – Dan Christensen
    Jun 2, 2020 at 15:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .