FOM: truth predicates, predicativity and reflection

[Volker Halbach]

In an earlier posting from Tue, 29 Dec 1998 11:39:56 I argued that
usually justififications of the proof-theoretic reflection principles
rely on a notion of truth. The argument runs as follows: If we accept
the theory T, then we must accept that T is sound (true); otherwise we
shouldn't accept T.  Thus we must also assume the consistency
statement for T, local and uniform reflection for T (unfortunately
they are not uniquely determined, since provability may be expressed
in different ways).

In this posting I want to relate this with the posting by Stephen G
Simpson Tue, 22 Dec 1998 17:52:09 on the Feferfest and with Feferman's
"Reflecting on Incompleteness" JSL 1990.

Historically people have preferred to extend theories by the
proof-theoretic reflection principles. Obviously adding to, say, PA
the uniform reflection principle yields again a system we accept, so
we can once again add the uniform reflection principle for this system
and so on (Turing and Feferman's "Transfinite Recursive
Progressions...").

Now Feferman has offered in "Reflecting on Incompleteness" a somewhat
different approach. Instead of adding reflection principles, truth
theories are added. Unfortunately, ramified truth predicates have to
be added. As with the progressions of reflection principles autonomy
indicates natural halting points. Feferman has also proposed a truth
theoretic system which embraces all levels in the hierarchy in one
truth predicate. He calls his systems Ref(PA) and Ref*(PA) the
Ordinary and the Strong Reflective Closure of Theories.

Now truth is deeply related to certain second-order theories. For sake
of simplicity let's consider simple uniterated truth:

(PA + Tarskian Truth (the "inductive" clauses + full induction) = ACA

(PA + uniform Tarski Biconditionals) = ACA with comprehension
restricted to formulas *without* second-order parameters

The = means (at least) relative interpretability conservative over the
arithmetical language.

Thus the Tarskian Theory of Truth is related to predicative set
formation.  Both can be iterated up to epsilon_0 and then autonomously
to Gamma_0. In the case of comprehension the resulting system is known
as predicative analysis (ramified analysis up to Gamma_0). Thus
iterating predicative set formation (elementary comprehension) and
Tarskin Truth yields equivalent theories, also Ref*(PA) is equivalent.

I make the following (tentative) claim: the limits of predicativity
conincide with the limits of compositional semantics. Tarskian truth
is clearly compositional, iterating it should be considered still as
compositional. Thus the reflective closure of PA, that is, the result
of making everything (?) explicit, which is in our acceptance of PA
coincides with the strongest predicative systems. Thus somehow
compositionality and predicativity coincide.

Also this seems to offer the opportunity to justify predicative
analysis and predicative systems via truth systems considered as
reflection principles (or rather what is behind them).

There are more results that support this conjecture: for instance,
there are theories of truth stronger than predicative analysis
(Friedman & Sheard, APAL 1987 (?), Cantini JSL 1991); but they violate
compositionality, because they employ "global" reflection principles
like Ax(Bew_{PA}(x)->Tx), which are clearly not compositional.

So much about the relation of compositionality and predicativity. But
I am worried whether ACA and its iterations are clearly
predicative. Consider the following concept of predicativity: A set is
predicatively defined if it is defined elementarily from sets we
already have. But ACA is in this sense not predicative, becuase it
allows second-order parameters in the comprehension formula. What
people (e.g. Kreisel) have saif in favour of these parameters does not
convince me. Disallowing them makes the system uninteresting: almost
no non-trivial construction that can be done in ACA or ACA_0 can be
done without the parameter-version and yields a system conservative
over PA.  So it is mathematically not very interesting, but some
motivations of predicativity motivate this weak system rather than
ACA.

On the truth theoretic side we get a similar picture: The Tarskian
equivalences interpret elementary comprehension without second-order
parameters, but of course the theory is quite weak.

Volker Halbach
***************************
Volker Halbach
Universitaet Konstanz
Fachgruppe Philosophie
Postfach 5560
78434 Konstanz Germany
Office phone: 07531 88 3524
Fax: 07531 88 4121
Home phone: 07732 970863
***************************