1

It seems to me that mathematicians or computer science theorists are still trying to come up a proof for conjecture they made in first or second order logic. By Godel's incompleteness theorems there are statements that could be true but unprovable.

My question is how do they know they are not wasting their time working on something unprovable? In general, are there any "work around" after Godel's incompleteness theorems?

Improve this question
6
  • They are true but unprovable in a specified formal system; nevertheless, they are provable "outside" that specific formal system. Thus, no "work around" is needed. – Mauro ALLEGRANZA Jun 6 '15 at 18:16
  • Do you mean people would use something stronger that first or second order logic? Are there any example? If they use something "outside" a specific formal system, do we need some more effort to show that this "new system" is sound? – hIkIGaya Jun 6 '15 at 18:33
  • The proof of G's First Th "produce" a sentence of arithmetic that is not derivable in the f-o formal system for Peano's arithmetic; but it is a mathematical proof of a mathematical sentence... – Mauro ALLEGRANZA Jun 6 '15 at 18:38
  • 2
    Why is this on the Philosophy stack, and not on Mathematics or Computer Science? – user2953 Jun 6 '15 at 20:42
  • What you can or cannot proove depends on the system you work in. As Keelan said you'll have a more precise and complete answer on mathematics SE. – Quentin Ruyant Jun 7 '15 at 21:08
2

Godel's result tells us that any sufficiently rich formal theory will permit propositions whose truth is not decidable within that theory.

In some cases it is possible to prove that a proposition is not decidable. A well known example of this is the continuum hypothesis of standard set theory.

In other cases it may not be possible to prove that a proposition is decidable because such a proof does not exist. In other words, decidability is not necessarily decidable.

So yes, it is entirely possible that people are completely wasting their time working on such problems as the Riemann Hypothesis, the Goldbach Conjecture, or any of the other well known conjectures.

EDIT

Considering the idea of a "work around". Firstly, it must be said that a mathematical theorem is a mathematical truth, so the idea of working around it seems opposed to the idea of mathematical truth. Having said that, if we are willing to bend the truth, then consider this :

Take the case of the continuum hypothesis of set theory. We can prove that this proposition is not decidable. We can also prove that both the continuum hypothesis and its negation are consistent with standard set theory in the sense that if we were to add either the hypothesis or its negation to our axioms, then the resulting theory would be consistent if set theory is consistent.

In this sense, we can work around the road block and explore a set theory where the continuum hypothesis is true ( or false ).

The axioms of any formal theory are generally taken to be self-evident truths. This is because we accept that some statements are true for no reason at all. Similarly, the continuum hypothesis, or any other conjecture which is not decidable, may be true for no reason whatsoever. However, in the case of the continuum hypothesis, its truth is clearly not self-evident.

Improve this answer
14
  • So are there any work around for this Godel's incompleteness doom from the logic perspective, e.g. does using some "stronger" proof system helps? Do people working on these conjecture relies solely on their own skill and luck? – hIkIGaya Jun 6 '15 at 19:00
  • @hIkIGaya Hi. Give me a few minutes and I shall edit my answer to include some ideas on a "work around". – Nick Jun 6 '15 at 19:03
  • @hIkIGaya I've just had a lovely lunch and an answer accepted on the stack exchange. A good start to my day. Thanks. – Nick Jun 6 '15 at 19:30
  • I guess I could have a good sleep now with your answer. Thanks. – hIkIGaya Jun 6 '15 at 19:31
  • Note that the trick of adding a statement S to the set of axioms only works if we actually have proof that S is undecidable. If we just found S hard to decide, and give up trying to prove or disprove it, and add either S or ~S to the set of axioms, but S is actually decidable, then we have either added an "axiom" that can be derived from the original axioms (not good), or we have created an inconsistent set of axioms (very, very bad), – gnasher729 Jun 6 '15 at 20:29
0

This is more of a question of psychology than philosophy.

As you point out, a mathematical conjecture can be true, false or undecidable.

However, you're assuming that a mathematician will prefer one or other of the outcomes. This is by no means the case. In other words, if one was to show that, say, the Riemann Hypothesis was undecidable that would be as important a result as proving it true or false.

Improve this answer
3
  • The point you make is a good point, but it is not entirely true. Mathematicians should not show preference for the truth status of an undecidable proposition, but in practice there are occasions in which they do. For example, ZF set theory is too weak for set theorists tastes. So they assume the truth of an undecidable proposition of ZF called the Axiom of Choice to extend ZF to formulate ZFC. It is ZFC which set theorists refer to as standard set theory and spend their time exploring. The truth of Axiom of Choice is not self-evident as are the other axioms. – Nick Jun 8 '15 at 16:59
  • @Nick R Fair point. Maybe I shouldn't have used the word prefer. There are indeed cases where one or other result leads down more interesting paths and so there would be a preference for the interesting alternative. That doesn't imply that the original result is in any sense wasted though, it's just less interesting. – Alex Jun 9 '15 at 10:47
  • To say that a mathematical conjecture can be "true, false, or undecideable" is accurate in (and only in) the same sense that it is accurate to say that an ice cream cone can be "chocolate, vanilla or melted". – WillO Jul 6 '15 at 13:08

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.