[FOM] 454: Three Milestones in Incompleteness

Paul Budnik paul at mtnmath.com
Mon Feb 21 11:45:52 EST 2011

This is an observation on the post of  02/06/2011 03:33 AM by Harvey 
Friedman and related posts.

It is worth keeping in mind that any claim that a hyperarithmetic 
statement requires a large cardinal axiom to decide is relative to the 
existing development of mathematics. Such results are very interesting, 
but they can change.

Since Kleene's O is a \Pi_1^1 complete set, any hyperarithmetic 
statement can be decided in second order arithmetic augmented with a 
finite number of axioms that say  specific integers are or are not 
notations for recursive ordinals under Kleene's definition, because a TM 
with oracle that makes a decision, must do so after a finite number of 

Cardinal hierarchies seem to be powerful ways to implicitly define 
combinatorial iteration of a sort that is very difficult to tackle head 
on. Of course it may be too complex to develop such structures 
explicitly even with the aid of computers. However, because this 
iteration can be specified implicitly in relatively brief axiom systems, 
I suspect we can eventually uncover the explicit iteration schemes that 
are implicitly defined by using the computer to help manage the 
combinatorial complexity. Of course this is speculation. No one knows, 
but I think it is a possibility that deserves consideration.

Paul Budnik

More information about the FOM mailing list