Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Due to Godel's incompleteness theorems we know that there are true statements in a system that cannot be proven with that system. My questions are 1) can we tell which statements in a system are the ones that cannot be proven, and 2) can we choose through the design of the system which statements will not be provable?

The motivation for my questions is simply the observation of how many results depend on the Riemann conjecture and how important to mathematics it is, along with the fact that it is almost universally believed to be true, yet it resists proof. Similar things can be said about the twin prime conjecture and many other unproven conjectures. Therefore, I ask the questions: is is possible that the Riemann conjecture (or twin prime conjecture) is one of those statements that is true but can never be proven? And can we know whether it is one of those questions?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

If first order Peano arithmetic is consistent, there is no algorithm that will determine, given input $\varphi$, whether or not $\varphi$ is neither provable nor refutable from first-order PA.

At our current state of knowledge, it is possible that the twin prime conjecture is true but not provable in first order PA.

share|improve this answer
    
So I understand your answer as: Yes, it is possible that any of these conjectures are true but unprovable, and No, we cannot know which questions are the unprovable ones. –  half-integer fan Nov 28 '13 at 16:35
    
We can discover that a particular sentence is neither provable nor refutable. The answer says that there is no algorithm for doing so. It could have been added that if we take a stronger recursively axiomatized theory such as ZFC, there are sentences neither provable nor refutable in PA, but such that this fact cannot be proved in ZFC. As to true but unprovable, yes, your interpretation is right. However, if the Goldbach conjecture is false, then that fact is provable. –  André Nicolas Nov 28 '13 at 16:43
    
Thanks for the clarification. –  half-integer fan Nov 28 '13 at 16:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.