[FOM] Iterating under Con(T)

Alasdair Urquhart urquhart at cs.toronto.edu
Fri Mar 10 16:56:56 EST 2006

If I understand what Joe Shipman said correctly,
the worry is that the original definition supposed
that Con(T_i) is defined for all countable ordinals.
But since there are uncountably many of these,
it must be impossible to define consistency in such
a progression, in general.  We have to make some
assumptions about ordinal notations -- it is
impossible to proceed in a naive fashion here.

I've been looking in the new anthology (recommended!)
"The Essential Turing" edited by Jack Copeland.
It contains some of the basic information in this
area.  Turing in his thesis proved that there is
a complete ordinal logic for Pi^0_1 statements.
He conjectured that it was complete for Pi^0_2
statements, but this was refuted by Feferman:

"Transfinite Recursive Progressions of Axiomatic
Theories", JSL, 27 (1962), 259-316.

Shoenfield showed the existence of a recursive progression
that is complete for true arithmetic:

"On a restricted omega rule", Bulletin of the Polish Academy
of Sciences, 7 (1962), 405-407.

Another very useful and very clearly written reference:

"Turing in the Land of O(z)" by Solomon Feferman,
in "The Universal Turing Machine" ed. by Rolf Herken.

Alasdair Urquhart

More information about the FOM mailing list