FOM: Relative Incompleteness of Q

[Jeffrey Ketland]

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

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

Jeff

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