# 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

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.
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