Finite versions of Godel' s incompleteness

Assume you have some notion of proof complexity: for instance, at the basic level, the length of a proof, or the number of symbols used, take your pick (there are more involved measures, but for sake of simplicity I will limit myself to the above).

Now, start from some ground arithmetical theory $T$, and say that $T\vdash_k \phi$ if there is a proof of $\phi$ from $T$ of complexity $\leq k$.

I call a sentence $\phi$ $k$-godelian iff it is $k$-undecidable (i.e. neither $T\vdash_k \phi$ nor $T\vdash_k \neg\phi$ , but provable in the standard sense in the theory $T$ (and so true in $N$, for those fortunate and seemingly numerous mortals who believe in such a creature).

$T$ is $k$-incomplete if there is such a $\phi$.

Now the two questions:

1. (first k-incompleteness) Which $T$s are k-incomplete for every $k$?

Are there theories that become eventually $k$-incomplete for a sufficiently large $k$ ?

2. (second k-incompleteness). Does any $k$-incomplete theory also satisfy the $k$-version of Godel 's second incompleteness? That is, is it true that $T$ is such that it $k$-proves its $k$-consistency only if it is $k$-inconsistent?

• Check Pavel Pudlak and Sam Buss's papers about finitistic Godel's theorem. – Kaveh Jun 29 '12 at 22:03
• @Kaveh : can you give me (us) the exact reference? Thank You – Mirco A. Mannucci Jun 29 '12 at 22:21
• here is one: math.cas.cz/~pudlak/fin-con.pdf there are a number of other papers IIRC. – Kaveh Jul 6 '12 at 22:50
• Harvey Friedman also has some results about finite consistency theorems. Pavel gave a few lectures on related topics last summer, I don't know if the the notes are online. Generally the question becomes more interesting when the complexity of the proof depends on the complexity of the statement (i.e. its length) so avoids the issue that David mentions in his answer. – Kaveh Jul 6 '12 at 23:04
• excellent refs, thanks Kaveh! I will have to rectify my question accordingly – Mirco A. Mannucci Jul 6 '12 at 23:05

Nice questions!

For the first question, I claim that every theory $T$ is $k$-incomplete in your sense for every finite $k$. This is because every statement appears explicitly as a part of any proof of it, and when $\phi$ is any very long theorem of $T$ in comparison with $k$, then any proof of $\phi$ has at least as many symbols in it as $\phi$ does, and so by your measures $\phi$ has no proof of size $k$ and hence is $k$-Goedelian by your definition. Thus, for any given $k$, the theory $T$ is $k$-incomplete. In particular, every theory becomes $k$-incomplete.

For the second question, it seems that any decent consistent theory will prove its own $k$-consistency for any particular $k$. For example, if $T$ is consistent and extends $PA$, and probably even extending $Q$ suffices, then since $T$ really does not have any proofs of contradictions, it has none of size $k$, and since there are only finitely many proofs of this size, which can be enumerated and known to be an exhaustive list within the theory $T$, it follows that $T$ will prove that there is no proof of a contradiction in $T$ of size at most $k$. That is, for each $k$ separately, $T$ proves its own $k$-consistency.

But since this is not a $k$-proof of its own consistency, it doesn't quite answer your second question. But it shows that you have to pay attention to the precise measure of $k$-provability. For example, it isn't even clear that a $k$-inconsistent theory will necessarily $k$-prove much, since perhaps the $k$-proof of a contradiction already uses up most of the $k$ symbols, leaving little room for further deductions from that contradiction.

In light of this, we can make a negative answer to your second question as follows. Let $T$ be the theory PA + $0=1$, which is $k$-inconsistent for a very small value of $k$, perhaps $25$ or so, since the extra axiom directly contradicts an axiom of PA. But this $k$ is much too small to even state the $k$-consistency of $T$, and so $T$ will not $k$-prove its own $k$-consistency. So it violates the second $k$-incompleteness theorem, because this is a theory that is $k$-inconsistent but does not $k$-prove its own $k$-consistency, contrary to the proposed equivalence in your question.

• Fast as usual Joel! Nice answer: for the time being I have given you my vote, let us see what others come up with. Meanwhile, I anticipate to you that my next question will be on the other side of the spectrum: a bit of heavy duty ultra-INfinitism never hurts! – Mirco A. Mannucci Jun 29 '12 at 0:14
• Oh yes, I also am waiting for the others to chime in with an answer to your second question. And meanwhile, I shall look forward to your infinitary question! Catch you tomorrow... – Joel David Hamkins Jun 29 '12 at 0:21
• I think it should be PA + 0 = 1 (rather than the unequal sign between 0 and 1). – abo Jun 29 '12 at 5:16
• Also, it's early in the morning, but in order to provide a negative answer to the second question, don't you need to provide a theory which k-proves its own k-consistency (and which is k-consistent)? – abo Jun 29 '12 at 5:30
• Thanks abo, I have edited to 0=1. The answer provides a negative solution to the second question, since it provides a theory that is $k$-inconsistent, but does not $k$-prove its own $k$-consistency, contrary to the equivalence stated in the question. It is true, however, that this is violating what might be regarded as the "easy" direction of the theorem, and it might be more interesting to violate the other implication. – Joel David Hamkins Jun 29 '12 at 10:10

The answer to the second question is negative. Consider a (first-order) theory of PA without the successor axiom like fpa. Then T is consistent and proves its own consistency. Let k be the complexity of this proof of consistency. Then trivially T is k-consistent and k-proves its k-consistency.

[the following is added in an edit] As my comment indicated, the previous remarks are not completely correct. Instead: Let T be a (first-order) theory of PA without the successor axiom like fpa. Then T is consistent and proves its own consistency. In fact, T proves:

(x)(there does not exist an x-proof of a contradiction in T). (*)

Let this proof have complexity z. Then T can prove - call this sentence S(y) -

"there does not exist a y-proof of a contradiction in T" for any y,

but its proof may have greater complexity than z; indeed, if the proof uses (*), then it will have greater complexity, by say f(y). That is, T proves S(y) with a proof of complexity no greater than z + f(y). Suppose there exists a k such that k <= z + f(k). Then T k-proves S(k), i.e. T k-proves the k-consistency of T. Since T is k-consistent, the answer to the question would therefore be negative.

Is there likely to exist k <= z + f(k)? The important step is to find k which can be referred to with complexity much less than k. If complexity is defined to be say the length of the proof, then this should be possible by defining an exponential operator and defining k to be a power of two reasonably large numbers.

• Actually on reflection this answer is not correct, as it stands. It seems to me to depend on the definition of complexity you are using and the number k. For instance, if your definition is such that the only way to refer to k is with a complexity of k or greater, then it will not be possible to prove the k-consistency of the theory, because it is not even possible to refer to k in any proof of complexity k. – abo Jun 29 '12 at 5:42

It is important to include the axioms as well, since there is a theorem of logic that an axiom system can be changed equivalently so that any given proof can be made arbitrarily sorter, or on the contrary, longer.