<p>Note that G&ouml;del's Incompleteness Theorems are the following statements:</p>

<ol>
<li><p>Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither provable nor disprovable) or inconsistent.</p></li>
<li><p>Any formal system which can be used to prove a statement equivalent to  its own consistency, is in fact inconsistent.</p></li>
</ol>

<p>But assuming, for instance, that ZF set theory (or an essentially equivalent  foundation for mathematical subjects such as computer science) is consistent, we don't need G&ouml;del's Theorems anymore to tell us that there are statements which are neither provable nor disprovable from our foundations: interesting specific examples, such as the Axiom of Choice have already been demonstrated. So even without G&ouml;del's Theorem, it is certainly <em>concievable</em> that a statement such as "<strong>P</strong> = <strong>NP</strong>" is indepdendent of set theory.</p>

<p>For this question, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.6548">Scott Aaronson has written a very accessible article</a> on the subject, which also goes over the basics of formal logic, what it could mean to have a model of set theory which included an axiom which is equivalent to asserting its own inconsistency, and the subject of logical independence results in general.</p>

CC BY-SA 3.0
2012-10-18T16:49:53.180Z
The article of Scott Aaronson was, what I was searching for thanks.
SpaceTrucker
CC BY-SA 3.0
2012-10-18T22:30:34.010Z
The Axiom of Choice is not arithmetical, like P vs NP. I don't think there are any natural arithmetical questions which are known undecidable in ZFC (or any equivalent set theory).
David Harris
CC BY-SA 3.0
2012-10-19T18:06:11.083Z
@DavidHarris: I'm curious. What would you say are the properties on an "arithmetical" statement? There certainly is a difference in character between $\mathsf{P} \ne \mathsf{NP}$ and the Axiom of Choice, but "arithmetical" isn't an adjective I would readily apply to either of them.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T16:42:31.227Z
2012-10-18T16:42:31.227Z
Niel de Beaudrap
<blockquote>
  <p><strong>Possible Duplicate:</strong><br>
  <a href="https://cstheory.stackexchange.com/questions/10044/implications-of-unprovability-of-p-neq-np">Implications of unprovability of $P\neq NP$</a>  </p>
</blockquote>



<p>I shortly came across Gödels incompleteness theorem again and I wondered, since so much time has been spent on trying to answer whether $P = NP$, do we know that such a proof exists? Maybe $P = NP$ is a theorem that can't be answered with the kind of math we are currently working with. Do you know evidence or even a proof that Gödels incompleteness theorem does not apply to whether $P = NP$?</p>

CC BY-SA 3.0
2012-10-18T16:09:34.813Z
This post should be migrated to the (non-research-level) CS stackexchange.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T16:33:50.167Z
@NieldeBeaudrap i think there is a research level question in here: is P vs NP provable in ZF/other logical theory. I have a feeling I have seen this question before though.
Sasho Nikolov
CC BY-SA 3.0
2012-10-18T16:36:14.867Z
@SashoNikolov: It is indeed a research question. It's a very good research question. Unfortunately, it is a research question of essentially the same magnitude as **P** versus **NP** itself, and our tendancy for such problems which was why I suggested the transfer. My impression is that we prefer here questions which are not only research-caliber, but also with a reasonable probability of being answerable. The reason why I suggested transferring to CS.SE instead is because an easier answer providing just an outline of the idea would be suitable there. But I suppose it can be posted here.
Niel de Beaudrap
CC BY-SA 3.0
2012-10-18T16:39:28.913Z
A migration would be fine, since I'm merely expecting references to published work. But I also appreciate some interesting thoughts on this topic.
SpaceTrucker
CC BY-SA 3.0
2012-10-18T16:41:56.163Z
actually, SpaceTrucker (space trucker?!) here is the question I recalled seeing http://cstheory.stackexchange.com/questions/10044/implications-of-unprovability-of-p-neq-np. Look at the Aaronson survey linked in the question and the wonderful answers by Timothy Chow and Kaveh. I think that should address your question..if it does I'd vote to close as a close duplicate.
Sasho Nikolov
CC BY-SA 3.0
2012-10-18T16:44:21.950Z
@SashoNikolov SpaceTrucker is fine. I will have a look at the question.
SpaceTrucker
CC BY-SA 3.0
2012-10-18T16:51:16.750Z
@SashoNikolov I have flagged my question as a duplicate.
SpaceTrucker
<reference-request><open-problem><p-vs-np>
Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?
SpaceTrucker
# Do we know that the P vs. NP question isn't affected by Gödels incompleteness theorem?

(Asked by: username_0 on 2012-10-18)

> **Possible Duplicate:**  
> [Implications of unprovability of $P\neq NP$](https://cstheory.stackexchange.com/questions/10044/implications-of-unprovability-of-p-neq-np)

I shortly came across Gödels incompleteness theorem again and I wondered, since so much time has been spent on trying to answer whether $P = NP$, do we know that such a proof exists? Maybe $P = NP$ is a theorem that can't be answered with the kind of math we are currently working with. Do you know evidence or even a proof that Gödels incompleteness theorem does not apply to whether $P = NP$?

**Tags:** reference-request, open-problem, p-vs-np

> **Comments:**
> **username_1**: This post should be migrated to the (non-research-level) CS stackexchange.  
> **username_2**: @NieldeBeaudrap i think there is a research level question in here: is P vs NP provable in ZF/other logical theory. I have a feeling I have seen this question before though.  
> **username_1**: @SashoNikolov: It is indeed a research question. It's a very good research question. Unfortunately, it is a research question of essentially the same magnitude as **P** versus **NP** itself, and our tendancy for such problems which was why I suggested the transfer. My impression is that we prefer here questions which are not only research-caliber, but also with a reasonable probability of being answerable. The reason why I suggested transferring to CS.SE instead is because an easier answer providing just an outline of the idea would be suitable there. But I suppose it can be posted here.  
> **username_0**: A migration would be fine, since I'm merely expecting references to published work. But I also appreciate some interesting thoughts on this topic.  
> **username_2**: actually, username_0 (space trucker?!) here is the question I recalled seeing http://cstheory.stackexchange.com/questions/10044/implications-of-unprovability-of-p-neq-np. Look at the Aaronson survey linked in the question and the wonderful answers by Timothy Chow and Kaveh. I think that should address your question..if it does I'd vote to close as a close duplicate.  
> **username_0**: @SashoNikolov username_0 is fine. I will have a look at the question.  
> **username_0**: @SashoNikolov I have flagged my question as a duplicate.  

---

## 1 answers

### Answer by username_1 on 2012-10-18. Score: 9 | Accepted answer

Note that Gödel's Incompleteness Theorems are the following statements:

1. Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither provable nor disprovable) or inconsistent.
2. Any formal system which can be used to prove a statement equivalent to its own consistency, is in fact inconsistent.

But assuming, for instance, that ZF set theory (or an essentially equivalent foundation for mathematical subjects such as computer science) is consistent, we don't need Gödel's Theorems anymore to tell us that there are statements which are neither provable nor disprovable from our foundations: interesting specific examples, such as the Axiom of Choice have already been demonstrated. So even without Gödel's Theorem, it is certainly *concievable* that a statement such as "**P** = **NP**" is indepdendent of set theory.

For this question, [Scott Aaronson has written a very accessible article](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.6548) on the subject, which also goes over the basics of formal logic, what it could mean to have a model of set theory which included an axiom which is equivalent to asserting its own inconsistency, and the subject of logical independence results in general.

> **Comments:**
> **username_0**: The article of Scott Aaronson was, what I was searching for thanks.  
> **username_3**: The Axiom of Choice is not arithmetical, like P vs NP. I don't think there are any natural arithmetical questions which are known undecidable in ZFC (or any equivalent set theory).  
> **username_1**: @DavidHarris: I'm curious. What would you say are the properties on an "arithmetical" statement? There certainly is a difference in character between $\mathsf{P} \ne \mathsf{NP}$ and the Axiom of Choice, but "arithmetical" isn't an adjective I would readily apply to either of them.  

---

