[FOM] Impredicativity of Kruskal's Theorem

[Harvey Friedman]

On 4/7/06 7:16 PM, "Todd Wilson" <twilson at csufresno.edu> wrote:

> I have been following, with some interest, the Friedman/Weaver debate on
> predicativity, although recently it seems to have stalled.  However, I
> think that Weaver, in the last two sentences of his latest post, has hit
> upon a possible way forward:
> 
>> Can you find any circularity in it?  That's the relevant question in
>> determining predicative legitimacy.
> 
> I would like to see anyone who claims that Weaver's analysis of
> predicativity goes too far produce an instance of circularity in it --
> or explain why the issue of circularity is inappropriate in analyzing
> predicativity.
> 
In his 

S. Feferman, Predicativity, In The Oxford Handbook of Philosophy of
Mathematics and Logic (S. Shapiro, ed.), Oxford University Press, Oxford
(2005) 590-624. 

Feferman seems to tie his notion of predicativity to that of: unfolding,
where the goal is to ferret out what principles of proof are *implicit* in a
full acceptance of the natural numbers.

Weaver seems to tie his notion to that of: non circularity.

When put this way, there does not seem to be any good reason to expect that
the notions should coincide.

What is needed in Weaver's case is a convincing, overriding, SIMPLE, CLEAR,
way of talking about what a circularity is (in a suitable kind of formal
system?), so that one can then do something convincing.

For example, we know what circularity is, in a directed graph. This has
great simplicity and clarity.

Here is a prototype of a treatment that could be exciting, but seems out of
reach.

Someone finds a very imaginative and simple basic notion of what we mean by
a noncircular comprehension axiom

{n: phi(n)} exists.

They then form the system of all noncircular comprehension axioms, and show
that this is equivalent to a standard axiomatization of some proper initial
segment of the hierarchy of hyperarithmetic sets of integers.

Harvey Friedman