[FOM] Nik Weaver's conceptualism and the correctness of the Schu"tte-Feferman analysis
William Tait
wwtx at earthlink.net
Thu Apr 13 16:06:38 EDT 2006
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
More information about the FOM
mailing list