[FOM] Two questions about proof theoretic reductions
Aatu Koskensilta
aatu.koskensilta at xortec.fi
Fri May 7 13:24:29 EDT 2004
A theory T_1 can be conservative over some theory T_2 with respect to
some class of formulas F, meaning that if T_1 |- f and f \in F, then T_2
|- f.
If this is to be epistemologically interesting, a stronger condition is
needed, namely that of proof theoretic reducibility. The basic idea is
that if we are to be entitled (based on principles formalised in T_2) to
use T_1 when deriving F-theorems, the conservativity should be provable
in T_2. Feferman gives the following definition:
T_1 is proof theoretically reducible to T_2 for a class of formulas F,
T_1 < T_2 [F], if there is a recursive function f, s.t.
1) if p is a proof of f \in F in T_1, then f(p) is a proof of f in T_2
2) the above is provable in T_2
We know that for example WKL_0 < PRA [Pi_2] (if I recall correctly) and
that ATR_0 < IR [Pi1_1] (ATR_0 is a subsystem of second order arithmetic
embodying definition by arithmetic transfinite recursion and IR is
Feferman's system of predicative analysis).
First question
-----------------
My first question is whether there are any interesting and natural
theories T_1 and T_2, such that T_1 is conservative over T_2 for some
class of formulas F, but T_1 < T_2 [F] does not hold.
It's not difficult to come up with a contrived example. For example, let
H(x) = a formula defining the epsilon-zeroth function E in the
Gregrorzyck hierarchy, and add to PA the set of sentences {Cons(PA<H(n))
| n \in N }, i.e. for every n the assertion that axioms of PA of
complexity less than E(n) form a consistent theory. PA proves all of
these sentences, so the resulting theory T is obviously conservative
over PA. It can't be proof theoretically reducible to PA, however,
because proof of Cons(PA<E(n)) has (n + some constant) symbols in T, but
must have over E(n) symbols in PA. Hence the function sending proofs in
T to proofs in PA grows faster than any function that can be proved
total in PA. Of course, the only reason anyone would consider T is in
context of my question, so it's not quite natural...
Second question
-------------------
Originally, it Hilbert's idea was to prove (abstract mathematics) <
(finitistic mathematics) [Pi_1]. We now know this is impossible, but on
the other hand we know that for some very interesting and natural
theories T < PRA[Pi_2].
At first sight this seems to suggests that a finitist can safely use T
to prove Pi_2 theorems. Presumably he would wish to do this because
proofs are much shorter and more intelligible in T than in PRA. However,
if PRA really captures
all finitisticly valid mathematical principles, it seems that the above
result is not relevant to the finitist at all! This is because if we
have a proof of T < PRA[Pi_1] in PRA we obviously can't prove (in PRA)
the reflection principle
T |- \phi --> \phi. Why should the finitist then care about T, if he
can't actually use it to shorten proofs? Am I correct in assuming that
proof theoretic reductions T_1 < T_2[F] are (epistemologically) of
interest only to those who do accept
F-soundness of T_2?
--
Aatu Koskensilta (aatu.koskensilta at xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
More information about the FOM
mailing list