FOM: Relative Incompleteness of Q
ketland at ketland.fsnet.co.uk
Sun Oct 29 18:28:20 EST 2000
Professor Friedman has defined a notion of relative completeness (turning on
a certain measure complexity of axiom systems) and has conjectured that all
of the main systems used in foundational studies are relatively complete.
Matt Frank has just today posted a nice message questioning this conjecture.
Friedman wrote (FOM 94: Relative Completeness, Sept 19, 2000):
DEFINITION. Let T be a finitely axiomatized theory. We say that
T is relatively complete if and only if for all formulas A of complexity at
most #(T), either A is a logical consequence of T or the negation of the
universal closure of A is a logical consequence of T.
CONJECTURE. All of the main systems of f.o.m. that are finitely
axiomatizable, and are intended to fully formalize a kind or level of
mathematical reasoning, are relatively complete.
Matt's message made me think about Q - Robinson arithmetic. Of course,
nobody supposes that Q "fully formalizes a kind of mathematical reasoning",
but it is worth pointing out that Robinson arithmetic Q isn't relatively
complete in Friedman's sense.
Q is true but incomplete. Gödel's 1st Incompleteness Theorem applies to Q.
(i) Q doesn't prove the formula "(0 + n = n)"
(ii) Q doesn't prove the formula "not-forall n (0 + n = n)"
So, consider the formula (0 + n = n), which is TRUE, when interpreted over
the natural numbers. Call this formula A. This is a very simple formula.
The unprovability of A in Q shows that Q is not relatively complete.
Friedman defined a measure of the complexity of formulas and axiom systems.
This assigns an integer #(phi) to any formula phi, by simply counting
occurrences of primitive symbols in phi (excluding parentheses and commas).
Clearly, #(A) is 5.
For a theory T, #(T) is defined to be:
"the least integer n such that T has an axiomatization consisting entirely
of formulas of complexity at most n."
I.e., when T is finitely axiomatizable, then #(T) is a measure of the
complexity of the longest axiom of T (in the least complex axiom system for
Here are the axioms of Q
~~(s(n) = 0) complexity = 5
s(n) = s(m) -> n = m complexity = 9
~~(n = 0) -> there is m (n = s(m)) complexity = 10
n + 0 = n complexity = 5
n + s(m) = s(n + m) complexity = 9
n x 0 = 0 complexity = 5
n x s(m) = n x m + n complexity = 10
So, unless there is a simpler axiomatization, we have
#(Q) = 10 and #(A) = 5. So Q isn't relatively complete.
Of course, this may be irrelevant (because unlike PA or Z_2) the formal
system Q in no sense "fully formalizes" arithmetic reasoning (even though Q
represents all recursive functions).
~~~~~~~~~~~ Jeffrey Ketland ~~~~~~~~~
Dept of Philosophy, University of Nottingham
Nottingham NG7 2RD United Kingdom
Tel: 0115 951 5843
Home: 0115 922 3978
E-mail: jeffrey.ketland at nottingham.ac.uk
Home: ketland at ketland.fsnet.co.uk
More information about the FOM