1
$\begingroup$

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
    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.2011-10-11
  • 0
    @Gerry : I am careful about that since I take care to say we can only add true sentences, that A is sound etc.2011-10-11
  • 1
    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.2011-10-11
  • 1
    @ Gerry 1 : I was only half careful about it originally, putting "true" and soundness in the first paragraph only.2011-10-11
  • 0
    @ 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.2011-10-11

1 Answers 1

1

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.

  • 0
    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.2011-10-11
  • 0
    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.2011-10-11
  • 0
    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$.2011-10-11
  • 0
    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.2011-10-11
  • 0
    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: http://www.mathpages.com/home/kmath347/kmath347.htm (see the "joke" near the end).2011-10-11
  • 0
    Of course it can't, so my question is rather meta-mathematical than mathematical. If you insist on definability, you may weaken the original question to Con(ZFC) "\Rightarrow g \geq h". This already a non-trivial and interesting (in my opinion) question.2011-10-11
  • 0
    Also, we may extend the original alphabet of ZFC by adding a "truth" predicate Tr on formulas, and then add axioms stating the properties of truth and the axiom scheme $(ZFC \vdash \phi) \Rightarrow Tr(\phi)$.2011-10-11