A proof-theoretic analysis of collection
The author investigates relations -- implication, independence, conservativeness, etc. -- among collection principles \((\text{B}\Sigma_n)\), induction axioms \((\text{I}\Sigma_n)\), and reflection principles \((\text{RFN}_T(\Pi_n))\). Besides producing new results, he gives new proofs to known results and answers open problems. For instance, Paris's result that \(\text{B}\Sigma_{n+ 1}\) is conservative over \(\text{I}\Sigma_n\) with respect to \(\Pi_{n+2}\) sentences is proved here by proof-theoretic means (cut-elimination, Herbrand theorem). \(\text{B}\Sigma_{n+ 1}\) is shown to be not derivable from all the true \(\Pi_{n+ 2}\) sentences; that answers a problem raised by Gaifman and Dimitracopoulos. There are a number of results about the equivalence of systems. For example, for \(k>n\), \(\text{B}\Sigma_n+ \Sigma_k\)-IR and \((\text{I}\Sigma_{n- 1})^{k+ 1}_\omega\) are equivalent. [`IR' stands for `induction rule', and for a theory \(T\), \((T)^n_{m+ 1}\) is \((T)^n_m+ \text{RFN}_{(T)^n_m}(\Pi_n)\).] The author provides a diagram that indicates relations about conservativeness and equivalence.
scientific article; zbMATH DE number 1210618