FOM: Clarification on Pi^0_2 induction; call for examples
JOE SHIPMAN, BLOOMBERG/ SKILLMAN
JSHIPMAN at bloomberg.net
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