FOM: Clarification on Pi^0_2 induction; call for examples

Fri Apr 24 18:19:23 EDT 1998

Harvey's theorem "AkEn every element S of k^n has i<j such that s(i),...,s(2i)
is a subsequence of s(j),...,s(2j)" does not imply (over weak theories) Pi^0_2
induction; rather it implies (in fact is equivalent to over EFA or RCA_0) the
*1-consistency* of Pi^0_2 induction. Of course this still implies non-primitive-
recursive growth of n with respect to k.

Can anyone else add some important open questions with their logically simplest
known equivalents to my list?  In areas like abstract algebra I'd like to know
if the open question is still open when restricted to "small" structures
(cardinality less than Beth_omega) because the Pi^n_m, Sigma^n_m classification
doesn't apply above this.

-- Joe Shipman

More information about the FOM mailing list