[FOM] Nik Weaver's conceptualism and the correctness of the Schu"tte-Feferman analysis

[William Tait]

On Apr 9, 2006, at 2:29 AM, Nik Weaver wrote:
> But before I do that, can someone *please* tell me what is wrong
> with my critique of Feferman-Schutte?
>
> THE CLAIM BEING CRITIQUED:
> Gamma_0 is the smallest predicatively non-provable ordinal.  That
> is, every ordinal less than Gamma_0 is isomorphic to an ordering
> of omega which can be predicatively proven to be a well-ordering;
> this is not true of Gamma_0 or any larger ordinal.
>
> THE ACCEPTED JUSTIFICATION FOR THE CLAIM:
> If a predicativist trusts some formal system for second order
> arithmetic, then he should accept not only the theorems of the
> system itself but also additional statements such as the assertion
> that the system is consistent.  He should indeed accept a "formalized
> omega-rule schema" applied to the original system.  Then the original
> system plus the schema constitutes a new system that he accepts, and
> the process can be iterated.  It can even be transfinitely iterated,
> yielding a family of formal systems S_a indexed by ordinal notations.

To say that the system RA(alpha) of ramified analysis up to order  
alpha is correct on the predicativist conception is not to say that  
predicativists 'trust' it. It rather means that the concepts and  
proofs formalized in it are predicatively valid.

It can happen that each deduction in a formal system is valid under a  
given conception, without the general statement of the validity of  
*all* deductions in the system being valid under that conception For  
example, I claimed that to be so for the system of primitive  
recursive functions  vis-a-vis the (or a) finitist conception of  
mathematics. Feferman and Schuette claimed it for the autonomous  
hierarchy of systems RA(alpha) of ramified analysis of order alpha,  
up to orders <  Gamma_0 vis-a-vis the predicative conception of  
second-order number theory.

Whether or not my analysis of finitism or the F-S analysis of  
predicativity is right, the possibility of some conception in this  
sense being precisely captured by a formal system (or hierarchy of  
them) should not be ruled out a priori.

So I think that what is described above under the heading "The  
accepted justification for the claim" is wrong. But I also don't  
recall it as a justification anyone gave for the claim that Gamma_0  
is the ordinal of predicative analysis.

> Kriesel proposed that a predicativist should accept the system S_a
> when and only when he has a prior proof that a is an ordinal notation.
> Feferman proved that if S_0 is a reasonable base system, then Gamma_0
> is the smallest ordinal with the property that there is no finite
> sequence of ordinal notations a_1, ..., a_n with a_1 a notation for
> 0, a_n a notation for Gamma_0, and such that S_{a_i} proves that
> a_{i+1} is an ordinal notation.  Thus, Gamma_0 is the smallest
> predicatively non-provable ordinal.

Let me put it this way: Let P be the least transitive set of ordinals  
containing omega, closed under successor and containing the limit  
beta when it contains alpha and induction up to beta I(beta, X) is  
deducible in RA(alpha) , where $X$ is a variable of order 0.  Then  
LUB P is Gamma_0. (Of course, given the deduction D of I(beta, X) in  
RA(alph    a), we can jack the order of X up to any gamma providing  
that gamma + delta < alpha whenever a formula of order delta appears  
in D.)

> FIRST OBJECTION:
> The plausibility of Kriesel's proposal hinges on our conflating two
> versions of the concept "ordinal notation" --- supports transfinite
> induction for arbitrary sets versus supports transfinite induction
> for arbitrary properties --- which are not predicatively equivalent.

I agree with the intent of this, but I would prefer to say that the  
notion of set in predicative analysis must carry with it a notion of  
order. One speaks of sets of order alpha---and these are the sets of  
numbers which can be expressed by formulas with one free numerical  
variable (i.e. properties) of order alpha. So the distinction is not  
between sets and properties, but between all sets and sets restricted  
to some order.

> When we prove a_i is an ordinal notation in Feferman's set-up, we
> are only showing transfinite induction up to a_i for statements of
> the form "b is in X".  That is, if we know that "everything less than
> b is in X implies b is in X", then we can infer that everything up
> to a_i is in X.  To infer soundness of S_{a_i} we need transfinite
> induction up to a_i for the statement "S_b is sound".  That is a
> genuinely stronger assertion since, for example, S_{a_i} proves the
> existence of arithmetical jump hierarchies up to a_i.  So we should
> not be able to infer soundness of S_{a_i} from the fact that a_i is
> an ordinal notation.

I don't altogether understand this. Let me relocate your point.  
Suppose that I(beta, X) is deducible in RA(alpha), where (whatever  
the grounds) we regard this system as predicative and beta is a  
limit. Here X is a free variable of some order bounded by alpha (of  
necessity, since RA(alpha) is restricted to such variables). We want  
now to justify as predicative introducing quantification over sets of  
order beta. I.e. we want to argue that the formulas of order beta+1  
are all predicatively meaningful.

NOTE: It is this, not showing that RA(beta) is sound, that should be  
required. The whole message of predicativism, as I understand it, is:  
The source of unsoundness lies in faulty (e.g. circular)definitions.  
Pay attention to definitions. If objects are suitably (i.e.  
predicatively) defined, soundness will look after itself.

How is one to predicatively justify introducing the formula of order  
beta+1?

Call phi and psi the components of phi & psi and of phi v psi. Call  
the phi(n) the components of forall x [hi(x) and of exists x phi(x).  
Call the phi(T) the components of forall X^{alpha}phi(X) and exists X^ 
{alpha}phi(X), where X^{alpha} ranges over sets of order <= alpha and  
T = lambda x psi(x) and psi is of order <= alpha.

One answer to the above question of how to justify introducing a  
formula phi of order beta+1is that we should show that every sequence  
phi = phi_0, phi_1, phi_2, ..., where phi_{n+1} is a component of  
phi_n, is finite (ending in an atomic or negated atomic formula). I  
would even argue that this is the right answer. [Notice that the  
requirement is stronger than simply that there should be no circles:  
there should be no infinite regresses in meaning.]

Now we can assign ordinals to the formulas of order <= alpha such  
that the ordinal of a component of a formula theta is less than the  
ordinal of theta. In particular, our formula phi will have ordinal  
omega x beta + n for some n. So (forgetting about the factor omega  
and the tern n), the component sequence above yields a descending  
sequence of ordinals < beta. Let M be the set of ordinals in the  
sequence. Now if M is a set of order 0, or even of some order delta  
such that the proof in RA(alpha) of I(beta, X) can be jacked up from  
X of order 0 to X of order delta, then we have a proof in RA(alpha)  
that the sequence in question is finite. Notice that this does not  
require the reflection principle that Nic cites. We need only   
recognize the deduction of I(beta, X) as predicatively correct, not  
the system RA(alpha).

  But RA(alpha), because of the limitation on what sets it can refer  
to, does not prove that there are NO infinite descending sequences of  
components, only those of some bounded order, and so it does not  
follow that phi is meaningful (as I am suggesting that we understand  
meaningfulness).

Note that this is fundamentally Nic's objection, but relocated where  
I think it belongs: If ramified analysis is locked into talking only  
about sets of given orders, then how can it prove meaningfulness of  
propositions of some order beta+1, where this seems to require well- 
foundedness with respect to all descending sequences from beta, and  
not just those of some specific order.  We may be predicativists (or  
rather, you may be); but god may not be and he (she?) may have  
devised a proposition of order beta whose truth-tree  requires paths  
which are not of order < Gamma_0.

What is the F-S response to it?  (I haven't looked for one from them.  
I do remember this point occurring to me a long time ago. But I  
wasn't sufficiently interested in predicativity to pursue it.)

Of course, as a non-predicativist, I am convince by the deduction of I 
(beta, X) in RA(alpha) that *all* descending sequences from beta are  
finite and so of the meaningfulness of all formulas of order beta+1/  
But that it because I can read the deduction while ignoring order  
restrictions and see it as a good deduction of transfinite induction  
up to beta for any set X.

> SECOND OBJECTION:
> Let us grant that the predicativist can somehow make the disputed
> inference.  Then for each a he has some way to make the deduction
>
> (*)   from  I(a)  and  Prov_{S_a}(A(n)),   infer   A(n)
>
> for any formula A, where I(a) formalizes the assertion that a is an
> ordinal notation (supporting transfinite induction for sets).
>
> Shouldn't he then accept the assertion
>
> (**)   (forall a)(forall n)[I(a) and Prov_{S_a}(A_n)  -->  A(n)]
>
> for any formula A?

As I stated above, I don't think that the predicativist  needs (*).  
He (along with gods, are there any women predicativists?) only needs  
from the proof of I(beta, X) in RA(alpha) that every component  
sequence from a formula of order beta+1 terminates. As I noted, I  
agree that, because of the restriction on the possible orders of X in  
the statement of induction, he doesn't really get this conclusion.

It is possible that Nic is referring to a different literature than  
what I remember. But, in any case, the above represents a question  
about the Feferman-Schuette analysis that has not really been  
answered (I think) and which follows from Nic's central point about  
the limitation of the meaning of I(beta, X) in RA(alpha).

Bill Tait