[FOM] PA and recursive saturation

[A.S.Virdi@lse.ac.uk]

Many thanks for the responses to this. In fact, as Henryk Kotlarski has pointed out
to me by email, the cut elimination argument Harvey Friedman alludes to below, 
has already been articulated in Volker Halbach's "Conservative Theories of Classical Truth" (Studia
Logica, 1999, volume 62, pp. 353-370). 

On a (slightly) related issue, I have been re-reading the fascinating FOM exchanges on
'Deflationism and the Godel Phenomena' (see the archives, February 2005:
http://www.cs.nyu.edu/pipermail/fom/2005-February/008769.html).
This issue interests me greatly. In those exchanges, it was made clear that the conservativity 
of a truth theory over a suitable base theory ( typically Peano Arithmetic) is a desirable property if one is
deflationarily inclined, i.e. if one's metaphysical picture is such that truth plays no
theoretical explanatory part (so one cannot make epistemic advances
into the non-semantic domain with the help of truth) and that truth's raison d'etre is 
exhausted by its serving the purpose of finitarily expressing a potentially infinte 
conjunction/disjunction. In fact, this "gauntlet" of identifying the deflationist's implicit commitment to 
conservativity was thrown into the ring by Jeffrey Ketland in 1999 ("Deflationism and
Tarski's Paradise, Mind journal) and independently by Stewart Shapiro in 1998
("Proof and Truth, Through Thick and Thin", Journal of Philosophy); they think conservativity
is inadequate to proving what the deflationist wants: namely these potentially infinite conjunctions/disjunctions
dressed up in the form of soundness/reflection principles. Both received various
responses by Jody Azzouni, Hartry Field, Neil Tennant, Volker Halbach (amongst others).

Here is a quick summary of the facts:

(1) Add to Peano Arithmetic (PA) the (restricted) set of T-sentences. Call this theory PA(T).
     Then PA(T) is a conservative extension of PA.
     This result holds even if semantic reasoning features in the induction axioms, i.e. the 
     expanded theory is permitted to perform induction on sentences with the truth predicate.
     However, the restricted set of T-sentences is too weak as a theory of truth. It fails to prove, 
     for example, that all sentences of the form 'if p then p' is true. Moreover:

(2) PA(T) does not imply 'All theorems of PA are true'. 
     {It is not enough that the truth predicate should express generalizations, it should also be able 
     to PROVE them:- this point is accentated by Halbach & Horsten in their "Deflationist axioms of 
     truth" in the anthology "Deflationism and Paradox" (editors: Beall & Armour-Garb, 2006)}.

Halbach (see his Synthese 2001 paper on "How Innocent is Deflationism?") argues that 
a natural strengthening of the T-sentences is to introduce the Tarskian inductive definition 
of truth. These are: 

     If p has the form t = u, then p is true iff val(t) = val(u)
     not-p is true iff p is not true
     p and q is true iff both p and q are true
     p or q is true iff either p is true or q is true
     There is an x such that p is true iff, for each number n, p(ñ) is true
     For all x such that p is true iff, for some number n, p(ñ) is true

Call the theory PA + arithmetical induction axioms only + the above axioms governing the truth predicate T(PA). 
Then:

(3) T(PA) is a conservative extension of PA. In particular, T(PA) does NOT prove the soundness statement 
      for PA.

By allowing truth to appear in the induction scheme (and calling the resultant theory Tr(PA)) we 
have the following

(4) Tr(PA) is NOT a conservative extension of PA. In particular, Tr(PA) DOES prove the soundness statement 
      for PA.

To get what the deflationist wants (namely the ability of truth to prove soundness/reflection principles), we need a 
theory of truth that does not conservatively extend the base theory. So, something has to give. Given the mathematical 
incompatibility of conservation and reflection, the deflationist can either: (a) reject the conservation condition, or (b) forego
the claim that truth is reflective in a manner that does not compromise her philosophical position. 

This is an incredibly nice reductio and one that lends great support to the idea that truth is in fact a 
substantial/informative notion. My puzzle however is this: why does Ketland (see his defence of 
this argument in his Mind 2005 response to Tennant's Mind 2002 paper 'Deflationism and the Godel 
Phenomena, as well as the FOM archives) need to go as far as pointing out facts (3) and (4) above?
As soon as the deflationist makes an appeal to the Tarskian axioms, isn't she already moving away from her deflationary 
position? In other words, Tarski's semantic conception of truth precisifies the so-called correspondence
theory of truth (according to which a statement is true just in case it corresponds to the facts) without
allowing it to fall foul of the Fregean objection that such a construal presupposes that which is to be 
defined (typically, for example, facts a taken to be whatever it is that makes a statement true, and
the correspondence relation is that relation with which a statement stands to the world when it is true).
The right hand side of the bi-conditional of the first Tarskian axiom above does not mention truth!!!

Tarski himself claimed he was attempting to do justice to the correspondence theory of truth in his work.
If the deflationist wants conservativity (i.e. to get to fact (3) above) then she will be forced to walk 
hand-in-hand with a substantialist about truth. Surely this should be enough to give all the "substantialist"
about truth needs to win her case against the deflationist? 

Any thoughts?

All the best,
Arhat Virdi

-----Original Message-----
From: Harvey Friedman [mailto:friedman at math.ohio-state.edu]
Sent: 19 March 2006 03:44
To: fom
Subject: Re: [FOM] PA and recursive saturation


On 3/9/06 5:55 AM, "A.S.Virdi at lse.ac.uk" <A.S.Virdi at lse.ac.uk> wrote:

Your posting is not very readable in the Archives because of margin
problems. So I reproduce your entire post here.

Your post has already received a response by Avigad at
http://www.cs.nyu.edu/pipermail/fom/2006-March/010172.html
 
> In Chapter 15 ('Recursive Saturation') of Richard Kaye's 1991 "Models of Peano
> Arithmetic", Kaye demonstrates the following: (roughly) take the system known
> as PA(S) - an extension of the language of Peano Arithmetic by adding a
> satisfaction predicate governed by the Tarskian axioms - and disallow the
> extended langauge to feature in the inductive reasoning of this theory. Call
> this theory PA(S)_0. Kaye shows in this chapter that any countable model of
> Peano Arithmetic can be extended to a recursively saturated model of PA(S)_0.
> From this it follows that PA(S)_0 is a conservative extension of PA. In fact,
> this result was first established by Kotlarski, Krajewski & Lachlan in 1981.
> 
> Does anyone on the list know of a proof-theoretic correlate to this
> conservativeness result?
> 

Let T be any reasonable theory, finitely axiomatized like ISigma1, or
schematically like PA. We can form T(sat) as you indicate.

One can give a proof of the conservativity of T(sat) over T for all formulas
in L(T), by a cut elimination argument. This argument will establish that
any proof in T(sat) of a formula in L(T) can be converted to a proof in T of
that same formula, whose number of symbols is bounded by a stack of 2's
whose height is linear in the number of symbols of the original proof in
T(sat). 

It also appears that for reasonable T, there is a superexponential blowup
here. Is this known?

Harvey Friedman


_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom