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$ ?

  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 11 '11 at 5:01
  • $\begingroup$ @Gerry : I am careful about that since I take care to say we can only add true sentences, that A is sound etc. $\endgroup$ – Ewan Delanoy Oct 11 '11 at 8:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Oct 11 '11 at 11:34
  • 1
    $\begingroup$ @ Gerry 1 : I was only half careful about it originally, putting "true" and soundness in the first paragraph only. $\endgroup$ – Ewan Delanoy Oct 11 '11 at 16:55
  • $\begingroup$ @ 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. $\endgroup$ – Ewan Delanoy Oct 11 '11 at 17:06

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Ewan Delanoy Oct 11 '11 at 8:37
  • $\begingroup$ 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. $\endgroup$ – Dan Brumleve Oct 11 '11 at 8:43
  • $\begingroup$ 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$. $\endgroup$ – Dan Brumleve Oct 11 '11 at 8:51
  • $\begingroup$ 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. $\endgroup$ – Ewan Delanoy Oct 11 '11 at 9:31
  • $\begingroup$ 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). $\endgroup$ – Dan Brumleve Oct 11 '11 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.