[FOM] Meta-logic

[A.P. Hazen]

    In response to Paul Studtmann's question, about weak systems in 
which basic meta-logical results (e.g. soundness, completeness of 
First Order Logic) can  be proved, Roger Bishop Jones mentions  that 
Robinson's Q has been used for various  meta-mathematical 
investigations.  The best study I know of what can and can't be 
proven in (systems interpretable in) Q is Edward Nelson's 
"Predicative Arithmetic" (Princeton University Press, 1986).  An 
earlier result is in Bezboruah & Shepherdson, "JSL" vol 41 (1976 if 
I've done the arithmetic right), pp. 503-512.
    Panu Raatikainen mentions ACA-0, and says that the meta-logical 
results mentioned can be proven in it, but not in Q.
    Long-time FoM readers are familiar with the "Reverse Mathematics" 
program, and in particular with Steve Simpson's "Subsystems of Second 
Order Arithmetic" (first edition, Springer, 1999; second edition 
fairly recently).  The "heroes" of Simpson's book are the systems 
(listed in order of increasing strength) RCA-sub-0, WKL-sub-0, 
ACA-sub-0, ATR-sub-0. Pi-super-1-sub-1-CA-sub-0, and Z-sub-2.  One of 
the basic results (p. 36 in Simpson's book) is that Gödel's 
completeness theorem (in the form: consistent countable sets of First 
Order sentences  have countable models) is provable in WKL-sub-0 but 
not in RCA-sub-0 (and is in fact equivalent, over RCA-sub-0, to the 
characteristic axiom of WKL-sub-0).
    Robinson's Q is a proper subsystem of RCA-sub-0.  Nelson shows 
that, in a system interpretable in Q, the consistency of Q follows 
the Hilbert-Ackermann Consistency Theorem (a close cousin of 
Herbrand's Theorem).  In the light of Gödel's Second Incompleteness 
Theorem, those of us less formalist and nominalist in our philosophy 
than Nelson should HOPE that the Hilbert-Ackermann theorem is NOT 
provable in Q!
    Vladimir Sazonov says that he has shown that "in a  weak 
framework," the completeness theorem is provable iff NP=coNP.  Can 
you tell  us,  Vladimir, how your "weak framework" compares to the 
systems in Simpson's book?

Allen Hazen
Philosophy Department
University of Melbourne