# Quantitative version of Godel's incompleteness theorem

Let $A$ be a list of axioms which we assume to be sound (for example, PA or ZFC). Godel's incompleteness theorems imply that if we add only finitely many (true) axioms to $A$, the new list $B$ will yield an incomplete theory.

One may relativize and quantify this idea as follows. Let $\Phi$ be any set of sentences. Say that a list $A$ settles $\phi$ if for any $\phi \in \Phi$ we have $A \vdash \phi$ or $A \vdash \lnot\phi$. Let $\Phi_n$ denote the set of all sentences with at most $n$ characters, and let $g(n)$ denote the size of the shortest list of true sentences (shortest in relation to the number of characters) we must add to $A$ to settle $\Phi_n$. Then $g$ is nondecreasing, and we have an upper bound of the form $g(n) \leq CK^n$.

By a pigeon-hole argument, $g$ is unbounded. If for example $A$ is the set of axioms of $ZFC$ and $n_1$ is the number of characters in a (suitable) formulation of the continuum hypothesis, we have $g(n_1)>0$. Are effective lower bounds known for $g$ ?

• I don't know the answer to your question, but concerning the 2nd sentence of your 1st paragraph, if you are not careful about which "axioms" you add to $A$, you may get an inconsistent (so, not incomplete) theory. – Gerry Myerson Oct 11 '11 at 5:01
• @Gerry : I am careful about that since I take care to say we can only add true sentences, that A is sound etc. – Ewan Delanoy Oct 11 '11 at 8:31
• You weren't careful about it originally - you only edited in the word "true" some hours after I posted my comment. In any event, "true" is only defined with respect to a model, while all you have is a list of axioms. – Gerry Myerson Oct 11 '11 at 11:34
• @ Gerry 1 : I was only half careful about it originally, putting "true" and soundness in the first paragraph only. – Ewan Delanoy Oct 11 '11 at 16:55
• @ Gerry 2 : I completely disagree with your statement that "truth is only defined with respect to a model". It is exactly the other way round. The very notions of set, model, interpretation etc cannot be even defined if you do not make an initial act of faith about a Platonic mathematical world in which there is a notion of truth. – Ewan Delanoy Oct 11 '11 at 17:06

## 1 Answer

For arbitrary A, there is no provable lower bound on g(n). For example, suppose A is the set of axioms of ZFC. If A is inconsistent, then g(n)=0. But inverting this we have that if g(n)≠0, then A is consistent. Then by Gödel's second incompleteness theorem, g(n)=0 is undecidable.

On the other hand, suppose $\Phi$ are statements in the language of Presburger arithmetic. In this case, g(n) has a constant upper bound since this theory is decidable. We still can't prove any lower bound on g(n) independent of A because the same language has undecidable theories.

• You misunderstood my question. I am assuming that A is sound of course, otherwise the question is uninteresting. I edited the end of the OP to explain it more plainly. – Ewan Delanoy Oct 11 '11 at 8:37
• Maybe I don't understand the idea of soundness in this context. I was thinking it is the same as the consistency of whatever formal system (ZFC?) we are using to establish the lower bound. – Dan Brumleve Oct 11 '11 at 8:43
• Regarding your edit: all we can say in ZFC is that Con(ZFC) implies Con(ZFC+CH). So it seems to me that we can't actually prove $g(n_1) > 0$. – Dan Brumleve Oct 11 '11 at 8:51
• If you prefer it this way, we can prove that (ZFC is sound)$\Rightarrow g(n_1)>0$, and I am asking from a lower bound of the form (ZFC is sound)$\Rightarrow g \geq h$. Note that (ZFC is sound) implies Con(ZFC), Con(ZFC+Con(ZFC)) etc and many others after them. – Ewan Delanoy Oct 11 '11 at 9:31
• How can (ZFC is sound) be expressed in ZFC? My understanding is that it can't. An enjoyable read with a bit of an anti-establishment bent: mathpages.com/home/kmath347/kmath347.htm (see the "joke" near the end). – Dan Brumleve Oct 11 '11 at 9:36