Timeline for complexity of proof of p(n) grows greater with n if for all x P(x) is unprovable?
Current License: CC BY-SA 3.0
9 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Sep 29, 2014 at 19:27 | comment | added | Robert Israel | Presumably you're using a model of "complexity" where the complexity of any natural number is bounded, otherwise you don't need the "if" clause: assuming $P(n)$ contains $n$, simply to state $P(n)$ requires an unbounded number of bits as $n$ gets large. | |
Sep 29, 2014 at 13:18 | answer | added | Joel David Hamkins | timeline score: 2 | |
Sep 29, 2014 at 13:18 | answer | added | Emil Jeřábek | timeline score: 9 | |
Sep 29, 2014 at 13:13 | comment | added | Stefan Geschke | I think Anders means that the "complexity" (to be clarified) of proofs of P(n) is unbounded if $\forall xP(x)$ is unprovable in PA and every instance P(n) is provable in PA. | |
Sep 29, 2014 at 13:08 | comment | added | Joel David Hamkins | Could you tell what measure of proof complexity you are using? Also, couldn't it easily be that $P(n)$ is trivial when $n$ is even, but not when $n$ is odd, in which case you have very easy proofs for very large even $n$, in which case it wouldn't be true that all larger $n$ have only more complex proofs. | |
Sep 29, 2014 at 13:07 | comment | added | Anders Göransson | Yes to both questions. | |
Sep 29, 2014 at 13:05 | comment | added | Stefan Geschke | I assume that by pA you mean Peano arithmetic. Also, you probably assume that every instance P(n) is provable in PA. Can you elaborate what you mean by the complexity of a proof? | |
Sep 29, 2014 at 13:03 | review | First posts | |||
Sep 29, 2014 at 13:10 | |||||
Sep 29, 2014 at 12:57 | history | asked | Anders Göransson | CC BY-SA 3.0 |