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

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