Skip to main content
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